ブログ倉庫

（定義）語wordとは，順序つけられた記号の配列である．

（例）例えば，abcはアルファベット文字を用いた長さ３の語である．001101は，バイナリー語（各ビットには，0あるいは1が入る）で，長さ6ビットである．

（注）ビットbitとは，binaryとdigitを縮めて作った造語である．

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

(実験)

n=0のとき：　空集合が１つ：　$${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,....…になることが予想される．

（証明）

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

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

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

（練習問題）n個のコインを投げて，隣り合う２つのコインが連続して表を向くことがない確率を求めなさい．