可能路徑數

Question

爲什麼在下圖中有從S到T的2^k個可能路徑。 任何人都可以解釋。 注意：圖中所有方向都是從左到右。

Answer 1

每對並行的路徑，你只能在一個時間選擇其中一個。
所以有這樣的平行路徑對。
因此，組合的總數是：2 * 2 * 2 ...... k倍= 2^ķ

Answer 2

在計數配置，有時有助於找到一種方法來編碼的配置，然後計算可能的代碼。只要在編碼的對象和代碼之間存在1-1對應關係，這就起作用。

在這種情況下，您可以在每個階段採用頂部分支或底部分支。如果相應路徑在該階段採用頂部分支，否則爲1，那麼通過在給定位位置處使用0來將路徑編碼爲k位二進制數。這顯然是1-1對應關係，因此這種路徑的數量是k比特數的數量是2^k（計算k比特數的數量本質上是相同的問題，所以這不完全是一個證明，但是如果你已經熟悉k比特數是如何工作的，這可以闡明路徑問題）。

例如（具有k = 4）：

path code num 
vvvv 0000 0 
vvv^ 0001 1 
vv^v 0010 2 
vv^^ 0011 3 
v^vv 0100 4 
v^v^ 0101 5 
v^^v 0110 6 
v^^^ 0111 7 
^vvv 1000 8 
^vv^ 1001 9 
^v^v 1010 10 
^v^^ 1011 11 
^^vv 1100 12 
^^v^ 1101 13 
^^^v 1110 14 
^^^^ 1111 15 

（由下面的Python 3腳本生成的，如果你要玩它:)

def pathCodes(k): 
    print('path code num') 
    for n in range(2**k): 
     b = bin(n)[2:] 
     b = ('0'*(k-len(b))) + b 
     s = b.replace('0','v') 
     s = s.replace('1','^') 
     print(s,b,n)