次: 一筆がき［08京大文系］ 上: 直接計算か漸化式か 前: 単語の個数［98名古屋市大改題］

階段の昇り方［07京大理系］

問題     

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする．15段の階段を昇る昇り方は何通りあるか．

方針

1. 2段昇りの回数で場合分けして，それを加える．
2. $n$段の階段の昇り方の漸化式を立て，$n=15$のときの値を求める．

解1

2段昇りを$k$回するとする．1段昇りは$15-2k$回である． 1段昇りの間に2段昇りを組み込めば，一つの昇り方が決まる． 最初や最後が2段昇りでもよい．よって2段昇りを$k$回する昇り方は

$${}_{15-2k+1} \mathrm{C}_k\ (通り)$$

$15-2k+1\ge k$でなければならないので$0\le k\le 5$である． 従ってその総数は

$$\sum_{k=0}^5{}_{16-2k} \mathrm{C}_k =1+14+66+120+70+6=277\ (通り)$$

解2

$n$段を条件を満たして昇る昇り方が$a_n$通りあるとする． $n=1\ ;\ 2\ ;\ 3$に対して， それぞれ昇る段数は， $1,\ ;\ 2,\ 11\ ;\ 111,\ 12,\ 21$となるので， $a_1=1,\ a_2=2,\ a_3=3$である．

$n\ge 4$のとき，$n$段の昇りを最初の昇り方で場合に分ける．

1. 最初1段昇りしたときは残る$n-1$段の昇り方は$a_{n-1}$通り．
2. 最初2段昇りしたときは次は1段昇りで， 残る$n-3$段の昇り方は$a_{n-3}$通り．

これは$n$段の昇り方として排反で，このいずれかである．

$$∴\quad a_n=a_{n-1}+a_{n-3}$$

これによって$a_4〜a_{15}$を順次求める．

$$\begin{array}{c\vert cccccccccccc} n&4&5&6&7&8&9&10&11&12&... ... \hline a_n&4&6&9&13&19&28&41&60&88&129&189&277 \end{array}$$

$a_{15}=277\ (通り)$である，