組み合わせ: 状態遷移の経路数を求めたい

Question

0 から d-1 までの d 個の状態のいずれかを持つことのできる N 個の数値 n_i からなる状態ベクトルを仮定します。任意の要素 n_i を加算してゆき最終的にすべての数値が n_i=d-1 となるような有向グラフを考えています。

例として、以下の図は d=2, N=3 としたときに (0,0,0) から (1,1,1) に至る状態遷移を有向グラフで表しています。

状態ベクトルの表現は d 進数 N 桁の整数表記と同じですので、状態の個数は d^N 個存在することがわかります (上の例では 2^3=8 個の箱があります)。では状態の遷移数 (なんと言えば良いのか?; 上記の例では矢印の数の 12 を求めたい) が何個になるかはどうすれば求められるでしょうか? あるいは組み合わせ理論でそれに相当する公式などはあるでしょうか?

(元々は並行システムでの処理の進行パターンを考えていて、d 個のステップを持つ N 個のプロセスを実行したとき、個別の状態の遷移数をいくつ検証すればよいかを組み合わせ理論ぽく抽象化してみた質問です。形式手法の文脈になります。)

Answer 1

n_iが+1されるような遷移を考えると、ほかの要素の状態によらずn_iが0以上d-1未満であるような状態からそれぞれ一つずつ存在します。

n_iの状態がd-1通り
ほかの要素の状態がd^(N-1)通り
iとしてありうるものがN通り

なので、全体で(d-1) * d^(N-1) * Nです。

Comments

[退会済みユーザー]

ありがとうございます! 説明を読んで見直したらすっきり腑に落ちました。