可能なパスの数

Question

なぜ次のグラフでSからTまでの2^kの可能なパスがあるのですか？ 誰でも説明できますか？ 注：図のすべての方向は左から右です。あなただけの時間でそれらのを選択することができます並列パスのすべてのペアについては

Answer 1

。
したがって、kのようなパラレルパスのペアがあります。
従って、組み合わせの総数は、次のとおり2 * 2 * 2 ... k回カウントする構成では= 2^K

Answer 2

は、エンコードへの道を見つけるために時々有益です可能なコードを数えます。これは、コード化されたオブジェクトとコードとの間に1-1の対応がある限り、機能します。

この場合、各段階で上部ブランチまたは下部ブランチを使用します。与えられたビット位置で0を使用することにより、パスをkビットの2進数としてコード化します。対応するパスがそのステージで最上位の分岐をとる場合は1、それ以外は1です。これは明らかに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 

（あなたがそれで遊んする:)

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)