ブログ倉庫

（定義）語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個のコインを投げて，隣り合う２つのコインが連続して表を向くことがない確率を求めなさい．