ブログ

フィボナッチ数列の出現★

0と1だけが並んでいる語を考えます.そのようなn桁の語をn-bit語と呼びます.
連続して1を含まないn-bit語はいくつあるでしょうか.
(1)n=1のとき,そのような語は,0, 1,ですから,計2個あります.
これをa(1)=2と書きます.
(2)n=2のとき,そのような語は,00, 01, 10で,a(2)=3個です.
11は1が連続するので条件に合いません.
(3)n=3のとき,そのような語は,
n=2のときの語の末尾に0を付加した,000, 010, 100,のa(2)個,
および,n=2のときの末尾に1を付加したものと言いたいところですが,
1の連続を避けるために,n=1のときの語に01を付加し,001, 101のa(1)個で,
互いに背反するこの両ケースを合わせて,a(3)=a(2)+a(1)=5です.

連続した1のない語の数の数列a(n)は,このような手順(一般のnで成立)で作れ,
2,3,5,・・・・・と続き,a(n)=a(n-1)+a(n-2)が得られます.
これはフィボナッチ数列の再帰的な定義そのものです.
フィボナッチ数列F(n)は,1,1,2,3,5,・・・・・ですから,
a(n)は3項目から始まるフィボナッチ数列です.a(n)=F(n+2)

それでは,連続した111を含まないn-bit語の数はいくつでしょうか.
これも同様な議論で,a(n)=a(n-1)+a(n-2)+a(n-3) となることが証明できます.

(問題)n個のコインを順番に投げて,連続して表がでない確率を求めよ.
(解)連続して表の出ないに相当する語の数はa(n)=F(n+2)でした.
n個のコインを順番に投げて実現する状態数は2nですから,求める確率はF(n+2)/2nとなります.