1 つ前と 2 つ前を足す、場合の数を漸化式で追う

10 段の階段を、1 段または 2 段ずつ上ります。上り方は 89 通り。

$2^{10}$ でも ${}_{10}{\mathrm{C}}_5$ でもありません。公式が当てはまらないときは、前の答えから次の答えを作る形に切り替えます。

最後の 1 手で場合分けする

$n$ 段の上り方を $a_n$ とします。全部を数えるかわりに、最後の一歩だけを見る。

最後が 1 段なら、その前は $n-1$ 段まで上っていました。そこまでの上り方が $a_{n-1}$ 通り。

最後が 2 段なら、その前は $n-2$ 段まで。$a_{n-2}$ 通りです。

この 2 つは同時に起こらないので足します^[3]。

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

初期値は書き出して決める

$a_1$ は 1 段だけなので 1 通り。$a_2$ は「1 段を 2 回」と「2 段を 1 回」で 2 通りです。

そこから $1,2,3,5,8,13,21,34,55,89$ と続きます。10 段で 89 通り。

隣どうしを足して次を作る形なので、フィボナッチ数列と同じ並びになります^[1]。

例：3 段まで上れる場合

1 段、2 段、3 段のいずれかで上れるとすると、最後の一歩が 3 通りに分かれます。

$$a_n=a_{n-1}+a_{n-2}+a_{n-3}$$

$a_1=1$、$a_2=2$、$a_3=4$ から始めて $7,13,24,44,81,149,274$。10 段で 274 通りです。

$a_3=4$ は書き出して確かめます。$1+1+1$、$1+2$、$2+1$、$3$ の 4 通り。

一歩の選択肢が増えると、足す項が増える。この対応は覚えておくと速い。

例：タイルを敷き詰める

縦 2、横 $n$ の長方形を、$1\times 2$ のタイルで埋め尽くします。

いちばん右の列に注目します。縦にタイルを 1 枚置くなら、残りは $2\times (n-1)$。横に 2 枚並べて置くなら、残りは $2\times (n-2)$。

$$b_n=b_{n-1}+b_{n-2}$$

$b_1=1$、$b_2=2$ で、階段とまったく同じ数列になります。$2\times 5$ なら 8 通り。

見た目の違う問題が同じ漸化式に落ちる。これが漸化式で数える利点です。

例：隣り合う数を選ばない部分集合

$1$ から $n$ までの数から、隣り合う 2 数を同時には含まないように選びます。空の選び方も 1 通りと数える。

$n$ を選ぶかどうかで分けます。選ばないなら $1$ から $n-1$ までの問題で $s_{n-1}$ 通り。

選ぶなら $n-1$ は選べないので、$1$ から $n-2$ までの問題になり $s_{n-2}$ 通り。

$s_1=2$、$s_2=3$ から $5,8,13$。$n=5$ なら 13 通りです。

例：円形に並ぶ塗り分け

$n$ 個の領域が輪になっていて、隣り合うものを違う色にします。$k$ 色で塗る。

一列なら $k(k-1{)}^{n-1}$ 通り^[2]。輪では両端も接するので、そこが同じ色になっている場合を引きます。

$$C_n=k(k-1{)}^{n-1}-C_{n-1}$$

3 色なら $C_3=6$ から $C_4=18$、$C_5=30$、$C_6=66$。1 つ前だけを使う形の漸化式です。

等比の形に直す

$a_n=2a_{n-1}+1$ のような形は、両辺に 1 を足すと等比数列になります。

$$a_n+1=2(a_{n-1}+1)$$

$a_1=1$ なら $a_1+1=2$ なので、$a_n+1=2^n$。したがって $a_n=2^n-1$ です。

例：ハノイの塔

3 本の棒と $n$ 枚の円盤があり、小さい円盤の上に大きい円盤を置けないという規則で、全部を別の棒へ移します。

いちばん大きい円盤を動かすには、その上の $n-1$ 枚を先に別の棒へ移す必要があります。移したあと、大きい円盤を 1 回動かし、また $n-1$ 枚を上に戻す。

$$h_n=2h_{n-1}+1$$

$h_1=1$ から $h_2=3$、$h_3=7$、$h_4=15$。閉じた形は $2^n-1$ です。

漸化式を立てるときの型

場合分けの切り口は、たいてい次のどれかになります。

どの切り口でも、残りが「同じ問題の小さい版」になっていることを確かめます。ここが崩れると漸化式になりません。

例：最初の一歩で分けても同じ

階段の問題を、最後ではなく最初の一歩で分けても構造は同じです。

最初が 1 段なら残り $n-1$ 段、2 段なら残り $n-2$ 段。同じ $a_n=a_{n-1}+a_{n-2}$ になります。

どちらで分けてもよいときは、初期値を書き出しやすいほうを選びます。

検算のしかた

漸化式を立てたら、小さい $n$ で書き出して照合します。$n=3$ か $n=4$ まで合えば、まず正しい。

初期値の取り方でつまずくことが多いので、$a_1$ と $a_2$ は必ず書き出して決めます。式から逆算しない。

答えが極端に大きくなっていないかも見ます。階段の上り方が $2^n$ を超えることはありません。

よくある誤り

公式が当てはまらないと感じたら、最後の 1 手で切ってみる。そこから同じ問題の小さい版が現れれば、漸化式で追えます。

参考文献

^[1] が隣どうしを足す数列、^[2] が一列と輪での塗り分けの個数、^[3] が場合分けして足す規則、^[4] と ^[5] が各国語での基本の整理です。