フィボナッチ数列 －階段昇り問題－

こんにちは。東久留米市の学習塾塾長です。

天気予報によると梅雨前線が北上し奄美大島辺りに停滞するようです。暫くするとさらに北上してくるので梅雨の中休みも終わりです。

昨日の数列の話のなかで挙げたフィボナッチ数列について紹介します。フィボナッチは中世イタリアの数学者の名前で、彼は次のような「兎の問題」を提示しました。

「１つがいの兎は、生まれて２ヶ月後から毎月１つがいの兎を産むものとして、１つがいの兎は１年後に何つがいになるか」
という問題です。

最初の１つがいの兎が生まれた月を１月とすると、１月のつがい数は１、２月も１、３月は２、・・・と増えていきます。翌年の１月までのつがい数を示すと以下のようになります。

　１月　　　１
　２月　　　１
　３月　　　２
　４月　　　３
　５月　　　５
　６月　　　８
　７月　　１３
　８月　　２１
　９月　　３４
１０月　　５５
１１月　　８９
１２月　１４４
　１月　２３３

ここで、つがい数を良く見てみると、ある月のつがい数は前月のつがい数と前々月のつがい数との和になっていることが分かります。これを数式で表すと、ある月のつがい数をＦ(n+2)、前月のつがい数をＦ(n+1)、前々月のつがい数をＦ(n)、とすると、
Ｆ(n+2)＝Ｆ(n+1)＋Ｆ(n)　　　（１）
となります。

この（１）の漸化式で表される数列をフィボナッチ数列といいます。

このフィボナッチ数列に関連した問題は、「階段昇り問題」などで中学入試でも定番となっています。

次の問題は、２０１０年　本郷中学の入試問題です。
「階段を１段ずつと２段ずつ混ぜて昇るのぼり方を調べます。例えば３段の階段の場合、のぼり方は、（１段＋１段＋１段）、（１段＋２段）、（２段＋１段）の３通りになります。階段が８段のとき、のぼり方は何通りですか」

問題では、８段の階段を昇るのぼり方を問うていますが、ｎ段の階段を昇るのぼり方を考えると漸化式を利用することができます。そこで、ｎ段の階段ののぼり方をＦ(n)とすると、Ｆ(1)＝１、Ｆ(2)＝２　となります。

次に、ｎ≧３のとき、
〈１〉初めの一歩が１段昇りなら、残りの（ｎ－１）段ののぼり方は、Ｆ(n-1)通り
〈２〉初めの一歩が２段昇りなら、残りの（ｎ－２）段ののぼり方は、Ｆ(n-2)通り
になるので、
Ｆ(n)＝Ｆ(n-1)＋Ｆ(n-2) 　　（２）

（２）の漸化式を使って順次計算していくと、
Ｆ(3)＝３
Ｆ(4)＝５
Ｆ(5)＝８
Ｆ(6)＝１３
Ｆ(7)＝２１
Ｆ(8)＝３４
となり、答えは３４通りということになります。

類題として、２００７年の慶応中の問題を示します。
「階段を昇るのに、１度に１段、２段、３段を昇る３種類の昇り方が可能であるとします。例えば、３段の階段を昇るには、次の〈１〉～〈４〉の４通りの昇り方があります。
〈１〉１度に３段昇る
〈２〉初めに１段、次に２段昇る
〈３〉初めに２段、次に１段昇る
〈４〉１段ずつ３度で昇る

問（１）略
問（２）１０段の階段の昇り方は何通りか」

先ほどの問題との違いは、のぼり方が３種類あることですが解き方は同じです。

まず、ｎ段の階段ののぼり方をＦ(n)とすると、Ｆ(1)＝１、Ｆ(2)＝２、Ｆ(3)＝４　となります。

次に、ｎ≧４のとき、
〈１〉初めの一歩が１段昇りなら、残りの（ｎ－１）段ののぼり方は、Ｆ(n-1)通り
〈２〉初めの一歩が２段昇りなら、残りの（ｎ－２）段ののぼり方は、Ｆ(n-2)通り
〈３〉初めの一歩が３段昇りなら、残りの（ｎ－３）段ののぼり方は、Ｆ(n-3)通り
になるので、
Ｆ(n)＝Ｆ(n-1)＋Ｆ(n-2)＋Ｆ(n-3)　　　（３）

（３）の漸化式を使って順次計算していくと、
Ｆ(4)＝７
Ｆ(5)＝１３
Ｆ(6)＝２４
Ｆ(7)＝４４
Ｆ(8)＝８１
Ｆ(9)＝１４９
Ｆ(10)＝２７４
となり、答えは２７４通りになります。のぼり方が３種類に増えたので（３）の漸化式の右辺の項が３つになりました。このような漸化式で表される数列を、トリボナッチ数列とも言います。

これらの「階段昇り問題」は中学入試ばかりでなく大学入試にも出題されます。次の問題は、２００７年　京都大のものです。

「１歩で１段または２段のいづれかで階段を昇るとき、１歩で２段昇ることは連続しないものとする。１５段の階段を昇る昇り方は何通りあるか」

漸化式を作って解くという基本戦略は同じですが、今までの問題と異なる条件、つまり、一歩で２段昇るのを続けてはいけないということをどのように漸化式に取り込むかがポイントになります。

少し長くなってしまったので、解答は後日。