- 【不細工おまんこ女学院】フェリス女学院高校・大学 【所詮神奈川 衰退女子校】
408 ：エリート街道さん[sage]：2019/09/08(日) 14:28:01.81 ID:Vcc0gZO+ - 今日は，フィボナッチ数列の出現する例を見てみましょう．
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を付加したものと言いたいところですが，
１の連続を避けるために，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個のコインを順番に投げて実現する状態数は2^nですから，求める確率はF(n+2)/2^nとなります．
|