ホーム >> 組合せ >> 階段をのぼる場合の数
hide or visible

問題の説明

$2007$年度の京都大学の入試問題の類題です.階段を$1$歩または$2$歩で昇る問題は中学受験でもよくある問題ですが,今回は$1$歩で$1$段昇ることは連続しないという条件がついています.この処理がポイントになります.
まずは$15$段ではなくもっと少ない段数を昇る場合の数を求めてみましょう.問題の条件の元で,$n$段の階段を昇る場合の数を$a_n$とします.簡単な計算によって, $$a_1=1,a_2=1,a_3=2,a_4=2$$ が求まります.さて,$2$通りの方法でアプローチしてみましょう.

漸化式を立てる

多くの人が思いつくであろう漸化式を立てるという方法で解いてみます. $n \ge 4$とします.$n$段のぼることを考えると,$1$歩目を$1$段で昇ったときは,$2$歩目は必ず$2$段で昇らなければなりません.残りの$n-3$段の昇り方は$a_{n-3}$通りあります.また,$1$歩目を$2$段で昇ったときは,残りの$n-2$段の昇り方は$a_{n-2}$通りあります.したがって, $$a_n=a_{n-2}+a_{n-3}$$ という漸化式を立てることができます.あとはこの漸化式を用いれば, $$a_5=3,a_6=4,a_7=5,a_8=7,a_9=9...$$ と次々に場合の数が求まっていくので結局$a_{15}=49$となることがわかります.よって求める場合の数は$49$通りです.

文字並べに置き換える

問題を別の問題に置き換えることを考えます.$1$段昇ることを$A$,$2$段昇ることを$B$として,$A,B$をいくつか一列に並べることで$15$段昇ることを表現します.例えば, $$A,B,A,B$$ という並びは$6$段の階段を$1$段,$2$段,$1$段,$2$段の順に昇ったことを表します.さて,$15$段の階段を昇るときは,$B$が$k$個並ぶとき,$A$は$15-2k$個並びます.ただし$A$は連続して並べることはできないので,$B$と$B$の間に多くとも$k+1$個しか並べることはできません. $$\underbrace{B,B,...,B}_{k個}$$ したがって, $$15-2k \le k+1$$ が成り立ちます.これより,$k \ge 5$がわかります.また,$2$段昇ることは最大で$7$回しか行えないので,$5 \le k \le 7$です.$B$が$k$個並んでいるとき,その間に$15-2k$の$A$を並べる場合の数は $$_{k+1} \mathrm{C} _{15-2k}$$ 通りです.したがって,求める場合の数は $$_6 \mathrm{C} _5 + _7 \mathrm{C} _3 + _8 \mathrm{C} _1 =49$$ で,$49$通りです.