解説

方針・初手

1段上る動作を $1$、2段上る動作を $2$ と表すと、求めるものは

$$ 1,2

$$

からなる列で、和が $15$ になり、かつ $2$ が連続しないものの個数である。

$2$ を何回使うかで場合分けすると、条件を整理しやすい。

解法1

$2$ を $k$ 回使うとする。このとき、$2$ によって上る段数は $2k$ 段であるから、$1$ を使う回数は

$$ 15-2k

$$

である。

したがって、全体の動作回数は

$$ k+(15-2k)=15-k

$$

回である。

この $15-k$ 個の位置のうち、$k$ 個の位置に $2$ を置く。ただし、$2$ は連続してはいけない。

長さ $15-k$ の列に、隣り合わないように $k$ 個の $2$ を置く方法の数は

$$ \begin{aligned} {}_{(15-k)-k+1}\mathrm{C}_{k} &= {}_{16-2k}\mathrm{C}_{k} \end{aligned} $$

である。

また、$1$ の個数は $15-2k$ 個であり、$2$ 同士を離すには少なくとも $k-1$ 個の $1$ が必要である。よって

$$ 15-2k \geq k-1

$$

より、

$$ k \leq 5

$$

である。

したがって、求める総数は

$$ \sum_{k=0}^{5}{}_{16-2k}\mathrm{C}_{k}

$$

である。

各項を計算すると、

$$ \begin{aligned} \sum_{k=0}^{5}{}_{16-2k}\mathrm{C}_{k} &= {}_{16}\mathrm{C}_{0} +{}_{14}\mathrm{C}_{1} +{}_{12}\mathrm{C}_{2} +{}_{10}\mathrm{C}_{3} +{}_{8}\mathrm{C}_{4} +{}_{6}\mathrm{C}_{5} \\ &= 1+14+66+120+70+6 \\ &=277 \end{aligned}

$$

よって、求める上り方は $277$ 通りである。

解法2

$n$ 段の階段を上る上り方のうち、最後の動作が $1$ であるものの数を $a_n$、最後の動作が $2$ であるものの数を $b_n$ とする。

このとき、最後が $1$ である上り方は、$n-1$ 段までの任意の上り方の後に $1$ を加えればよいので、

$$ a_n=a_{n-1}+b_{n-1}

$$

である。

一方、最後が $2$ である上り方は、直前が $2$ であってはならない。したがって、$n-2$ 段まで上ったときの最後の動作は $1$ である必要があるから、

$$ b_n=a_{n-2}

$$

である。

初期値は

$$ a_1=1,\quad b_1=0

$$

である。また、$2$ 段の場合は

$$ a_2=1,\quad b_2=1

$$

である。

これを順に計算する。

$$ \begin{array}{c|c|c|c} n & a_n & b_n & a_n+b_n \\ \hline 1 & 1 & 0 & 1 \\ 2 & 1 & 1 & 2 \\ 3 & 2 & 1 & 3 \\ 4 & 3 & 1 & 4 \\ 5 & 4 & 2 & 6 \\ 6 & 6 & 3 & 9 \\ 7 & 9 & 4 & 13 \\ 8 & 13 & 6 & 19 \\ 9 & 19 & 9 & 28 \\ 10 & 28 & 13 & 41 \\ 11 & 41 & 19 & 60 \\ 12 & 60 & 28 & 88 \\ 13 & 88 & 41 & 129 \\ 14 & 129 & 60 & 189 \\ 15 & 189 & 88 & 277 \end{array}

$$

したがって、15段の階段を上る上り方は

$$ a_{15}+b_{15}=277

$$

通りである。

解説

この問題では、単に $1$ と $2$ の和が $15$ になる列を数えるだけでは不十分である。条件「$2$ が連続しない」を正しく処理する必要がある。

解法1では、$2$ の個数を固定して、隣り合わない位置の選び方として数えた。組合せで一気に数えられるため、最も見通しがよい。

解法2では、最後の動作が $1$ か $2$ かで状態を分けた。条件付きの階段問題では、直前の動作によって次にできる動作が変わるため、このように状態を分けるのが典型である。

答え

$$ 277

$$

通り。