【場合の数】フィボナッチ数列で階段の上り方が何通りかがわかるの？

場合の数には、階段の上り方が何通りあるかを考えなければならない問題があります。

もちろん、1歩で1段ずつ階段を上るだけなら、階段が何段あろうとも1通りしか上り方はありません。しかし、1段飛ばし（1歩で2段）で上る場合も考えると、階段の段数が多いほど場合の数は増えていきます。

本記事では、代表的な階段上りの問題を解説します。

5段の階段を上る上り方は何通りあるか？
1. (1)の解答
2. (2)の解答
  1. (2)の別解（フィボナッチ数列を利用する）

5段の階段を上る上り方は何通りあるか？

【例題】太郎君は5段の階段を上ります。「1歩で1段上る」と「1歩で2段上る（1段飛ばし）」を組み合わせて5段の階段を上るとき、次の問いに答えなさい。

(1) もっとも少ない歩数で上る上り方は何通りありますか。

(2) (1)もふくめて、上り方は全部で何通りありますか。

(1)の解答

「もっとも少ない歩数で上る」とあるので、「1歩で2段上ることがもっとも多い」と考えます。そこで、歩数と1歩の段数だけに注目すると、次のようになります。

（2段、2段、1段）…3歩

【例題】のように、場合分けが必要な問題では、順列（並び順を考える）を考える前に組合せ（並び順を考えない）を考えることが大切です。初めから「1歩目で1段上って、2歩目で2段上って……」のように考えてはいけません。

【場合の数】順列と組合せ、和の法則と積の法則を正しく使い分けよう

場合の数の基本となる「順列」と「組合せ」の区別、「和の法則」と「積の法則」の区別について解説します。「何が違うのかな？」と考えてみましょう。

組合せがわかったら、次に何歩目に何段上ったかを考えます。

（2段、2段、1段）の場合、1段が1歩目から3歩目のどこかに来ればいいので3通りが答えです。

すぐに答が分からなければ、地道にすべての場合を書き上げましょう。

（1歩目、2歩目、3歩目）とすると、（2段、2段、1段）（2段、1段、2段）（1段、2段、2段）の3通りなので、書き上げても大した手間ではありません。

(2)の解答

(2)でも、まずは歩数と1歩の段数の組合せをすべて書きます。これが場合分けになります。

(1)で「もっとも少ない歩数で上る」場合が出ているので、つるかめ算と同じく「交換」していくといいでしょう。

【つるかめ算】方程式も公式も要らない！表・面積図・消去算で考える

つるかめ算は、「公式」に頼るのではなく、表や面積図などを使って考えましょう。情報を整理したり、図を描いたりすることに慣れることが大切です。

(1)で求めた組合せの「2段」を「1段、1段」に交換していきます。

ア　（2段、2段、1段）…3歩

イ　（2段、1段、1段、1段）…4歩

ウ　（1段、1段、1段、1段、1段）…5歩

ポイントは、規則的に交換していくことです。今回は、右から順に「2段→1段、1段」に交換していきました。

次に、アからウのそれぞれが何通りかを考えます。

アは(1)から3通りです。
イは、(1)と同じように考えて、2段が1歩目から4歩目のどこかに来ればいいので4通りです。
ウは見るからに1通りしかありません。

したがって、アからウまでを足して3＋4＋1＝8（通り）が答えです。

(2)の別解（フィボナッチ数列を利用する）

(2)のように、「1歩で1段上る」と「1歩で2段上る」を組み合わせた上り方を全部求める問題ではフィボナッチ数列が使えます。

フィボナッチ数列とは、どの数も前の2つの数の和になっている数列です。例としては、次の数列があります。

0、1、1、2、3、5、8、13、21、34、55、89、144、…

3番目は1＝0＋1、4番目は2＝1＋1、5番目は3＝1＋2、…となっていて、確かにどの数も前の2つの数の和です。

(2)のような問題では、例として挙げたフィボナッチ数列の3番目の1から使います。

1段の階段を上るときは、（1段）だけなので1通りです。
2段の階段を上るときは、（2段）（1段、1段）の2通りです。
3段の階段を上るときは、（2段、1段）（1段、2段）（1段、1段、1段）の3通りです。
4段の階段を上るときは、（2段、2段）（2段、1段、1段）（1段、2段、1段）（1段、1段、2段）（1段、1段、1段、1段）の5通りです。
5段の階段を上るときは、上で求めた通り8通りです。

エノキさん

確かに、5段の階段を上るときまでは、1、2、3、5、8というフィボナッチ数列になっています。でも、6段、7段、…と段数が増えていっても、本当にフィボナッチ数列になっているんですか？

エリンギ先生

それを今から考えていこう！

階段の上り方がフィボナッチ数列になっている理由を、3段の階段を上るときで考えましょう。

3段の階段を上るとき、1歩目が2段か1段かで場合分けできます。

1歩目が2段の場合、残りの段数は1段なので、1段の階段の上り方は1通りです。
1歩目が1段の場合、残りの段数は2段なので、2段の階段の上り方は2通りです。

したがって、1＋2＝3（通り）となり、前の2つの数の和になっています。

階段の段数が4段、5段、…と増えていっても、1歩目が2段か1段かで場合分けできるので、3段のときと同じように考えれば、ずっとフィボナッチ数列が続くことがわかるでしょう。

階段の上り方とフィボナッチ数列の関係を知っていれば、【例題】の(2)が8通りであるとすぐに答えられます。

シイタケくん

入試本番でも、フィボナッチ数列を使って、階段の上り方の問題を解いてもいいんですか？

エリンギ先生

答えしか書かない形式ならば、フィボナッチ数列を使っても、他のどんな解き方でも問題ない。でも、途中の考え方を書かなければならないときは、ここまでで説明したようなことは書かないといけない。解答欄に「1、2、3、5、8」だけ書いても、採点者には何をしたのか伝わらないからね。