1・2・3段の上り方(トリボナッチ数列)

方針

解答

⓪ 発想 — どう考え始めるか。 $n$ 段の上り方を、最後の1歩で場合分けするのが漸化式の常道だ。

最後の1歩が $1$ 段なら、その前は $n-1$ 段を上っている。$2$ 段なら $n-2$ 段、$3$ 段なら $n-3$ 段。

この3つは重ならず、全体を覆い尽くす。だから $a_n=a_{n-1}+a_{n-2}+a_{n-3}$(トリボナッチ数列)。初期値 $a_1=1,a_2=2,a_3=4$ から順に計算する。

① 漸化式を立てる。 最後の $1$ 歩で分けると $$a_n=\underset{\text{最後1段}}{\underbrace{a_{n-1}}}+\underset{\text{最後2段}}{\underbrace{a_{n-2}}}+\underset{\text{最後3段}}{\underbrace{a_{n-3}}}(n\ge 4).$$ ② 初期値。 $a_1=1$($1$)、$a_2=2$($1+1,2$)、$a_3=4$($1+1+1,1+2,2+1,3$)。

③ 順に計算。 $$a_4=a_3+a_2+a_1=4+2+1=7,$$ $$a_5=a_4+a_3+a_2=7+4+2=13,$$ $$a_6=a_5+a_4+a_3=13+7+4=24.$$ よって $a_6=24$。

まとめ 最後の $1$ 歩($1\cdot 2\cdot 3$ 段)で場合分けすると $a_n=a_{n-1}+a_{n-2}+a_{n-3}$(トリボナッチ)。$a_1=1,a_2=2,a_3=4$ から $a_6=24$。漸化式と数え上げの融合。

発展 — 一歩先へ。 上れる歩幅を $1,2$ に限るとフィボナッチ、$1,2,3$ でトリボナッチ、$1,2,3,4$ でテトラナッチと、$k$ 種類なら「直前 $k$ 項の和」の漸化式になる。歩幅の種類が増えるほど場合分けの項が増え、数列の増え方も速くなる。カウント問題は「最後の1手」で場合分けする、が共通の型だ。

別解

別解 — 直接「$1,2,3$ の順序つき和」を数える(苦手な人向け)。 $6$ 段の上り方は、「$1,2,3$ を並べて合計 $6$ にする並べ方」の数だ。使う段数の組(何を何回使うか)で分類して数える。

• $1$ を $6$ 回: $\frac{6!}{6!}=1$ 通り
• $1$ を $4$ 回・$2$ を $1$ 回: $\frac{5!}{4!1!}=5$ 通り
• $1$ を $2$ 回・$2$ を $2$ 回: $\frac{4!}{2!2!}=6$ 通り
• $2$ を $3$ 回: $\frac{3!}{3!}=1$ 通り
• $1$ を $3$ 回・$3$ を $1$ 回: $\frac{4!}{3!1!}=4$ 通り
• $1$ を $1$ 回・$2$ を $1$ 回・$3$ を $1$ 回: $3!=6$ 通り
• $3$ を $2$ 回: $\frac{2!}{2!}=1$ 通り

合計 $1+5+6+1+4+6+1=24$ 通り。漸化式(本解)の $a_6=24$ と一致する。

漸化式は速いが、この直接数え上げは「なぜ $24$ か」を具体的に見せてくれる。組の数え落としがないか、漸化式の答えと突き合わせて確かめられるのも利点だ。