Log of ROYGB

はてなダイアリーが廃止されるので、引っ越しました。

フィボナッチ数とべき乗(1)

はじめに

63.2%の憂鬱(1)(5)自然の中のe(1)(3)の続きですが、内容としては単独で読んでも大丈夫です。

階段にて

「2、4、6、8、10、…」
階段を登るときに数を数えながらというのは何故か習慣になっている。ワトソンがホームズに階段の段数を質問された話を読んだのがきっかけだったような気がする。
そういえば、階段の登り方の問題があった。階段を1段づつ、もしくは一度に2段で登る場合の組み合わせは何通りあるかという問題。場合分けをして数えればできるだろうというのまではすぐに思いついたのだけど、面倒なので実際の計算はやっていなかった。
それを階段を登っている最中に思い出したのだ。休み中なので学校にはほとんど誰もいないし、部活の集合時間まではまだ余裕があったので暇つぶしもかねて実際に階段を使って考えることにした。


1段の場合は1通りで考えるまでも無い。
2段の場合も、1段づつで登るか2段で一気に登るかの2通り。
3段の場合は、1段づつが1通りは変わらず、2段で登るのがある場合は2通りだから合計3通り。
4段になると少し複雑で、1段づつが1通り、1回だけ2段で登る場合が3通り、2回2段で登る場合が1通りで計5通り。
つまり、全部1段で登る場合、1回だけ2段で登る場合、2回2段で登る場合と場合分けして考えるわけだ。
段数が増えるとだんだん面倒になるが、原理は同じはず。段数が増えた場合でも全部1段の場合が1通りなのと、1回だけ2段で登る場合が(段数−1)になるのは簡単にわかる。12345と続く数の連続した2つを選ぶのに、(12)345、1(23)45、12(34)5、123(45)となるのと同じだ。


5段の場合は、
全部1段が1通り
1回2段が4通り、
2回2段で登る場合は、さらに場合分けをして
 最初の2段が一番最初の場合が2通り
 最初の2段が1段登った所からの場合が1通り
あわせて3通り
すべて合計して8通りになる。


6段の場合は、
全部1段が1通り
1回2段が5通り
2回2段が最初の2段が
 1段目の場合が3通り
 2段目の場合が2通り
 3段目の場合が1通り
合わせて6通り
3回2段の場合が1通り
すべて合計すると13通りになる。


もっと大きな段数でも場合分けを間違えなければ解けることは間違いない。


「何してるの。」


動きを止めて振り向くと、階段の下で不思議そうに首をかしげている顔が見えた。


「いや、なにっていうか…。」


人が来るとは思っていたので驚いたが、前にも似たような数学の問題を話したことのある彼女だったので、階段の問題を考えていたことと、場合分けで答えが求まることを説明した。


「ふうん、階段の登り方か。」


彼女はそう言ってから少し下をむいて黙る。
と、すぐに顔を上げて、


「こんなのはどうかしら。まず最初の一歩が1段の場合。」


そう言って、実際に階段を1段登る。


「1段登ると、段数がマイナス1される。」


階段を降りて、こんどは1段飛ばしで登った。


「2段登ると、段数がマイナス2される。」


その場で止まって、階段の上にいる僕の方を見る。何が言いたいのかよくわからない。


「この間教えてもらったプレゼント交換の場合と同じように考えられるんじゃないかしら。」


プレゼント交換の場合って…。あっ!


「そうか、最初に1段登った場合はn−1段の場合、2段登った場合はn−2段の場合から求められるのか。」


これには気がつかなかった。プレゼント交換のときよりも簡単だ、単純に1つ前と2つ前の場合の数を足すだけだから。つまり3段の場合は、1段の1通りと2段の2通りを足した3通り、4段の場合は2通りと3通りで5通り、5段は3+5で8通り。すごい単純明快でエレガントな解法だ。これを即座に思いついたのだとしたら、すごいひらめきだ。


「ねえ。」


彼女の声で我に返った。


「いや、すごいエレガントな答だなと思って。」


僕がそう言うと、彼女は軽く笑ったように見えた。そして階段を足早に登ってきて僕に並んだ。


「最近読んだ本に書いてあったんだけど、ね。」


「へえ。そうなんだ。」


彼女がそういう本を読むというのは意外だった。


「フィナボッチ数とか言うらしいんだけど。」


「フィボナッチ、か。聞いたことがあるような気もするけど、やっぱり知らないか。その本、こんど貸してくれるかな。」


「いいよ。それはそうと、そろそろ行かないとみんな集まってるよ。」


彼女はそう言うと、さっさと歩き出した。


フィボナッチ数とべき乗(2)へつづく)