この問題の考え方を短い動画にまとめました。動画は問題の提示から始まります。 流れをつかんでから、下の解説を読んでください。
階段の上り方を数える問題。全部書き出すのは \(n\) が小さいときだけです。 漸化式のつくり方はひとつしかありません。最後の1歩で場合分けする。 これなら、もれもなく、重なりもない。
この回で扱う問題（千葉大）
\(n\) 段の階段を上るのに、1歩で1段、2段、または3段を上ることができるとする。 この階段の上り方の総数を \(a_{n}\) とおく。たとえば \(a_{1}=1,\ a_{2}=2,\ a_{3}=4\) である。
(1) \(a_{4},\ a_{5}\) の値を求めよ。
(2) \(a_{n},\ a_{n+1},\ a_{n+2},\ a_{n+3}\ (n\ge 1)\) の間に成り立つ関係式を求めよ。
(3) \(a_{10}\) の値を求めよ。
(1) 小さいところは、書き出して数える
いきなり式を立てないこと。まず手を動かします。歩幅の列として書き出し、 歩数の少ない順に並べると、もれません。
| 段数 | 上り方 | 総数 |
|---|---|---|
| 4段 | (1,1,1,1)／(1,1,2)(1,2,1)(2,1,1)／(1,3)(3,1)／(2,2) | \(a_{4}=7\) |
| 5段 | (1,1,1,1,1)／(1,1,1,2) など4通り／(1,1,3) など3通り／(1,2,2) など3通り／(2,3)(3,2) | \(a_{5}=13\) |
書き出すときは辞書式（小さい歩幅から）に並べる。 思いついた順に書くと必ずダブります。5段の \(13\) 通りは、 歩数5回が1通り、4回が4通り、3回が \(3+3=6\) 通り、2回が2通り、で \(1+4+6+2=13\)。
(2) 漸化式 ― 最後の1歩を見る
\((n+3)\) 段を上りきる最後の瞬間を考えます。最後の1歩は 1段・2段・3段 のどれかで、 この3つは重なりません。
| 最後の1歩 | 直前にいる段 | そこまでの上り方 |
|---|---|---|
| 1段 | \(n+2\) 段目 | \(a_{n+2}\) 通り |
| 2段 | \(n+1\) 段目 | \(a_{n+1}\) 通り |
| 3段 | \(n\) 段目 | \(a_{n}\) 通り |
\[a_{n+3}=a_{n+2}+a_{n+1}+a_{n}\]
「最初の1歩」で分けても同じ式になりますが、途中で分けてはいけません。 たとえば「\(n+1\) 段目を通る場合」で分けようとすると、 \(n+1\) 段目を通る上り方は \(a_{n+2}\) の中にもう入っているので、二重に数えてしまいます。 端（最初か最後）で切るのが鉄則です。
(3) 漸化式で押していくだけ
\(a_{3}=4,\ a_{4}=7,\ a_{5}=13\) から、3つ前までを足し続けます。
| \(n\) | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|
| 計算 | \(13+7+4\) | \(24+13+7\) | \(44+24+13\) | \(81+44+24\) | \(149+81+44\) |
| \(a_{n}\) | 24 | 44 | 81 | 149 | 274 |
\[a_{10}=274\]
直前の3つを足すだけなので、表にして横に流すのが速くて安全です。 1つずつ式を書いていると、どこかで必ず写し間違えます。
つまずきポイント
- (1) を書き出さずに飛ばす。 \(a_{4},a_{5}\) は (3) の出発点。ここを間違えると以降が全部ずれます。
- 書き出しが辞書式でない。 思いついた順だと、ダブりと抜けの両方が起きます。
- 途中の段で場合分けする。 「\(n+1\) 段目を踏むかどうか」などで分けると重複します。切るのは最初か最後の1歩。
- 3項間だと思い込む。 1段・2段・3段の3種類だから4項間（3つ前まで）。歩幅の種類の数＝さかのぼる個数です。
- \(a_{1}=1,\ a_{2}=2,\ a_{3}=4\) を確かめない。 \(a_{3}=4\) は (1,1,1)(1,2)(2,1)(3) の4通り。ここが合っていれば数え方は正しい。
要点まとめ
- 小さい \(n\) は辞書式に書き出す。式より先に手を動かす。
- 漸化式は最後の1歩で場合分け。もれなく、重なりなく。
- 歩幅が3種類 → 3つ前までを足す（4項間漸化式）。
- 途中の段で分けると二重に数える。切るのは端だけ。
