可能路径数

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)