フィボナッチ数列の演習

(定義)語wordとは,順序つけられた記号の配列である.

(例)例えば,abcはアルファベット文字を用いた長さ3の語である.001101は,バイナリー語(各ビットには,0あるいは1が入る)で,長さ6ビットである.

(注)ビットbitとは,binaryとdigitを縮めて作った造語である.

(例題)$${a_{n } }$$ を連続して1が続くことのないようなb-ビット語の数とする.$${a_{n } }$$を求めなさい.

(実験)

n=0のとき: 空集合が1つ: $${a_{0}=1}$$

n=1のとき: 0,1 :$${a_{1}=2}$$

n=2のとき: 00,01,10 :$${a_{2}=3}$$

n=3のとき: 000,010,100,001,101 :$${a_{3}=5}$$

n=4のとき: 0000,0100,1000,0010,1010,0001,0101,1001 :$${a_{4}=8}$$

$${a_{n } }$$はフィボナッチ数列,1,2,3,5,8,....…になることが予想される.

(証明)

1.任意のn-ビット語wを考える.語wが0で終わるとすると,末尾の1つ前(n-1)番ビットは,0でも1でも良いので,この場合の1~(n-1)番ビットでできる(n-1)-ビット語の数は,$${a_{n-1 } }$$個である.従って,0で終わり,連続する1を含まないn-ビット語は$${a_{n-1 } }$$個である.

2.語wが1で終わるとすると,(n-1)番ビットは0でなければならない.(n-2)番ビットは何の制約もなく,0でも1でもかまわない.従って,1で終わり,連続して1を含まないn-ビット語は$${a_{n-2 } }$$個ある.

1.,2.の2つのケースは互いに排他的であるので,加算原理により;$${a_{n}=a_{n-1}+a_{n-2 } }$$これは,フィボナッチ数列の定義に他ならない.

(練習問題)n個のコインを投げて,隣り合う2つのコインが連続して表を向くことがない確率を求めなさい.