フィボナッチ数列的な場合の数

よく見かける問題で、階段の上り方が何通りあるか、というものがあります。
「階段を上るのに１度に1段または2段しか上ることができないとします。
たとえば，2段の階段は，1段ずつ2回上る方法と，2段を1回で上る方法の2通りの上り方があります。」
この上り方で、順に階段を上ると、何通りの上り方ができるかを考えるというものです。



上の図の4段目までの上り方を見てみると、2＋3＝5で5通りと求めているのが分かります。4段目に来るためにはその1段前の3段目まできてあと1段上るか、2段前の2段目まで来てそこから一足で4段目に来るかの2つしか考えられません。2段目までの上り方が2通り、3段目までの上り方が3通りなので、2＋3＝5(通り)となるのです。
こう考えると、5段目までは3＋5＝8(通り)，6段目までは5＋8＝13(通り)，…となって、出てくる数を順に書くと(0段目は1通りと考えて)、1，1，2，3，5，8，13，21，…とフィボナッチ数列が出てきます。

この「階段の問題」以外にも、フィボナッチ数列的な考え方を場合の数に持ち込んだものとして、次のような問題がありました。



1kmから順に見ると、
1km　…　(1)の1通り　…　☆1
2km　…　(1，1)か(2)の2通り　…　☆2
3km　…　(1，1，1)，(1，2)，(2，1)，(3)の4通り　…　☆3
4kmは、 最後にA(1km)走る　←　その前に3km走るので4通り(☆3)
　　　　 最後にB(2km)走る　←　その前に2km走るので2通り(☆2)
　　　　 最後にC(3km)走る　←　その前に1km走るので1通り(☆1)
合計4＋2＋1＝7(通り)
5kmは、同様に考えて、7＋4＋2＝13(通り)
6km　…　13＋7＋4＝24(通り)
7km　…　24＋13＋7＝44(通り)
8km　…　44＋24＋13＝81(通り)

前3項の和(トリボナッチ数列)が並ぶことになりますね。

フィボナッチ数列やその仲間の数列が場合の数の問題に時々登場します。
問題全体を見て、答えの登場の仕方などをよく考えながら、上手に応用できるように
練習を積んでいってくださいね！（算数科　道幸）