ブログ倉庫

■直線上にｎ個の点が並んでいるとします．点が連続しないように選んで点の集合を作ります．そのような集合の選び方A_nは何通りありますか？　ただし，点を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個の点が並んでいる場合はどうでしょうか．今度はｎ番目の点と，1番目の点が連続してはダメです．この場合の集合の選び方をB_n個とします．

・n=1のとき：　Φ，{1}　　　　　→　$$B_1=2$$　
・n=2のとき：　Φ，{1}，{2}　　　→　$$B_2=3$$
・n=3のとき：　Φ，{1}，{2}，{3} 　→　$$B_3=４$$　
（注）｛1,3｝は繋がるので条件にあいません．
・n=nのとき：
n点を除いた場合は$$ A_{n-1}$$通り，n点がある場合には，自分n点と両隣り（n-1と１）の計３点は除くので$$A_{n-3}$$通りがあります．

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

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