2022年3月の記事一覧

フィボナッチ数列の演習

(定義)語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つのコインが連続して表を向くことがない確率を求めなさい.

0

フィボナッチ数と葉序

 

写真は,今を盛りに咲いている花桃です.葉となる芽の位置を,枝の元から先に向かって調べると,5つごとに重なる位置になることがわかります.左回りの螺旋配置で,5つ目で重なるまでに2回転しますので,葉序比2/5といいます.2も5もフィボナッチ数です. 

一般に,植物や樹木の枝につく葉は螺旋配置をしています.1つの枝に沿って枝先に向かって,ある葉から出発しその葉に重なる上の葉までの葉の数を数えて見ましょう.その数は,だいたいフィボナッチ数になることが知られています.螺旋配置になるのは,木の枝が成長しながら,葉が重ならないよう葉が育つと考えると理解できます.同じ位置の上の葉と重なるまで(1周期)の葉の数がフィボナッチ数と言うことです.植物(精密な工業製品ではない)ですので,それほど厳密な話ではなく,だいたいの配置を言っているに過ぎません.重ならないようにするなら,周期が出来ない(∞周期)方が,良いのではないかとも思いますが,周期というのはだいたいのもので,結晶のように完全に周期的というわけではありませんから,目くじらを立てないでください.

シナノキとニレではこの数は2(左右交互);ブナとハシバミでは3;アンズ,桜,カシでは5;梨とポプラでは8;アーモンドと柳では13と言われています.[Hoggatt,1979]

出発点の葉から終着点の葉までの時計回りあるいは反時計回りの回転数は,やはり通常はフィボナッチ数で,例えば,シナノキとニレでは1回転;ブナとハシバミではやはり1回転;アンズ,桜,カシでは2回転;梨とポプラでは3回転;アーモンドと柳では5回転だそうです.

樹木の枝の葉の配置は葉序と呼ばれます.葉が重なるまでの葉の数と,回転数の比は葉序比と呼ばれ,シナノキとニレの葉序比は1/2;ブナとハシバミでは1/3;アンズ,桜,カシでは2/5;梨とポプラでは3/8;アーモンドと柳では5/13です.[Fibonacci and Lucas numbers with applications, Thomas Koshy]

ここまでに観察される数値は,1,1,2,3,5,8,13までのフィボナッチ数です.さらに大きなフィボナッチ数が観測されるかどうかや,漸化式が葉の発芽の機構から必然的に導くことができるのかには言及しません.

 

0