今回は、日本数学オリンピック２０００年予選第４問を取り上げ、解説します。
小学生でも普通に解ける有名問題で、実際、中学入試でも出されています（慶應義塾中等部２００７年算数第６問など）。
トリボナッチ数列であることを見抜いた解法は上の慶應中等部の問題の解説の通りになります。
ここでは、トリボナッチ数列であることに気付かないふりをして解くことにします。
結局のところ、この問題は、１、２、３を何個か足し合わせて７を作る場合の数が何通りありますかということですね。
３の個数、２の個数、１の個数の順で組合せをまず選び出し、その後で並べ替えが何通りあるか考えます。
３、３、１→１がどこに来るかで３通り
３、２、２→３がどこに来るかで３通り
３、２、１、１→３がどこに来るかで４通りあり、そのそれぞれに対して、２がどこに来るかで３通りあるから、４×３＝１２通り
３、１、１、１、１→３がどこに来るかで５通り
２、２、２、１→１がどこに来るかで４通り
２、２、１、１、１→２がどこに来るかで（５×４）/（２×１）＝１０通り
２、１、１、１、１、１→２がどこに来るかで６通り
１、１、１、１、１、１、１→１通り
したがって、石段の登り方は全部で
３＋３＋１２＋５＋４＋１０＋６＋１
＝４４通り
あります。
順列、組合せのいい練習になるとは思いますが、だいぶ面倒ですね。
なお、一歩で１段か２段の石段をのぼる問題であれば、フィボナッチ数列の問題になります。
