2020年8月の記事一覧

フィボナッチ数列とルーカス数列

 

 

 

 

 

 

 

 

■直線上にn個の点が並んでいるとします.点が連続しないように選んで点の集合を作ります.そのような集合の選び方A_nは何通りありますか? ただし,点を1つも含まない集合は空集合Φと言いますが,集合の選び方の1つに空集合もあります.

・n=1のとき: Φ,{1}     → $$A_1=2$$
・n=2のとき: Φ,{1},{2}   → $$A_2=3$$ 
(注){1,2}の集合は点が連続するので条件を満たしません.

・n=3のとき: Φ,{1},{2},{3},{1,3} → $$A_3=5$$

・n=nのときは: n点目を選ばない $$A_{n-1}$$個の方法と,n点目は選ぶがn-1点目は選ばない $$A_{n-2}$$個の方法があります.
従って,$$A_n=A_{n-1}+A_{n-2}$$ ,これは,フィボナッチ数列$$F_n$$の定義ですが,初項が2なので,$$A_n=F_{n+2}$$になります.

■円周上にn個の点が並んでいる場合はどうでしょうか.今度はn番目の点と,1番目の点が連続してはダメです.この場合の集合の選び方をB_n個とします.

・n=1のとき: Φ,{1}     → $$B_1=2$$ 
・n=2のとき: Φ,{1},{2}   → $$B_2=3$$
・n=3のとき: Φ,{1},{2},{3}  → $$B_3=4$$ 
(注){1,3}は繋がるので条件にあいません.
・n=nのとき:
n点を除いた場合は$$ A_{n-1}$$通り,n点がある場合には,自分n点と両隣り(n-1と1)の計3点は除くので$$A_{n-3}$$通りがあります.

この両者の合計が一般式です:$$B_n=A_{n-1}+A_{n-3}=F_{n+1}+F_{n-1}=L_n$$

このような数列 $$B_n$$ はルーカス数列$$L_n$$と呼ばれます.

0