1歩で1段または2段のいずれかで階段を昇るとき、1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか。
解答例
ある段を
- 踏む場合を○
- 踏まない場合を✕
で表すと、15段の階段を昇る様子は合計16個の○と✕で表すことができます。
1個目(0段目)と16個目(15段目)は必ず○になります。
また、2段昇りが連続しないという条件のため、○✕○の塊と○の組合せで昇り方を表現できます。
○✕○の塊と○の数と昇り方をまとめると次の表のようになります。
\begin{array}{|crcr|}
\hline
\circ \times \circ & \circ & \mbox{組合せ} & \\ \hline
0 & 16 && 1 \\
1 & 13 && 13 \\
2 & 10 & {}_{12} C_2 = & 66 \\
3 & 7 & {}_{10} C_3 = & 120 \\
4 & 4 & {}_8 C_4 = & 70 \\
5 & 1 && 6 \\ \hline
\mbox{合計} &&& 277 \\ \hline
\end{array}
よって、求める組合せは277通りです。
解説
この手の問題は、提示された条件をどのように表現するかにかかっています。
簡単に書いていますが、苦労して絞り出しています。
漸化式で表現できるか試しましたが、上手くいきませんでした。
○○、○✕、✕○の組合せを考えましたが、樹形図が膨大になりそうだったので断念しました。
あれこれ試行錯誤して本文の記述に至りましたが、これでは2時間30分の試験時間では間に合いませんね。
