同じ記号は 2 つまで、条件が付いた重複順列を数え上げる

0 と 1 を 10 個並べる並べ方は $2^{10}=1024$ 通り。ただし 1 が 2 つ続かないものに限ると 144 通りです。

条件が付くと、指数の式では出せなくなります。末尾で場合分けして、前の答えから次の答えを作る形に切り替えます。

条件がなければ指数

$n$ 個の場所に $k$ 種類の記号を並べる並べ方は $k^n$ 通りでした。各場所を独立に決められるから掛け算になる。

「隣どうしが同じでは困る」という条件が入ると、この独立が崩れます。前に何を置いたかで、次の選択肢が変わる。

隣が違えばよい場合は掛け算で足りる

崩れ方が軽い条件なら、まだ掛け算で押し切れます。

3 色の旗を 5 本立て、隣り合う旗を違う色にする。1 本目は 3 通り、2 本目以降は直前と違えばよいので 2 通りずつ。

$$3\times 2^4=48$$

48 通りです。「直前とだけ比べる」条件なら、段ごとの本数がそろうので掛け算が使えます。

一般に $k$ 色で $n$ 本なら $k(k-1{)}^{n-1}$ 通り^[2]。

2 つ続くのを禁じると崩れる

「1 が 2 つ続かない」という条件は、少し性質が違います。0 の後は 0 と 1 の 2 通りですが、1 の後は 0 の 1 通りだけ。

直前が何かで選択肢の数が変わるので、段ごとの本数がそろいません。掛け算にできない。

そこで、末尾で場合分けします。

漸化式を立てる

$n$ 桁の列のうち、1 が 2 つ続かないものの個数を $a_n$ とします。

末尾が 0 のとき、その前の $n-1$ 桁は条件を満たしていれば何でもよい。$a_{n-1}$ 通りです。

末尾が 1 のとき、その手前は 0 でなければなりません。さらにその前の $n-2$ 桁は自由で、$a_{n-2}$ 通り。

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

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

$a_1=2$、$a_2=3$ から始めると、$2,3,5,8,13,21,34,55,89,144$ と続きます。$a_{10}=144$ です。

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

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

漸化式そのものより、初期値でつまずくことが多い。必ず書き出して決めます。

$a_1$ は 0 と 1 の 2 通り。$a_2$ は 00、01、10 の 3 通りで、11 だけが外れます。

$a_3$ を書き出すと 000、001、010、100、101 の 5 通り。漸化式の $3+2=5$ と合いました。

3 つ目まで合えば、漸化式と初期値の組は正しいと見てよい。

例：同じ記号が 3 つ続かない

条件をゆるめて、2 つまでは続いてよいとします。$k$ 種類の記号で $n$ 個並べる。

末尾の同じ記号の連なりが 1 個か 2 個かで場合分けします。どちらの場合も、その手前は違う記号でなければならない。

$$f_n=(k-1)(f_{n-1}+f_{n-2})$$

2 種類なら $f_1=2$、$f_2=4$ から $f_3=1\times (4+2)=6$。全体 8 通りから 000 と 111 を除いた値と合います。

$f_4=10$、$f_5=16$ と続く。3 種類なら $f_3=2\times (9+3)=24$ で、$27-3=24$ と一致します。

例：階段の上り方

1 段または 2 段ずつ上って $n$ 段を上る方法も、同じ漸化式になります。

最後の一歩が 1 段なら、その前は $n-1$ 段まで上っていた。2 段なら $n-2$ 段まで。

$b_n=b_{n-1}+b_{n-2}$ で、$b_1=1$、$b_2=2$。$1,2,3,5,8,13$ と続き、10 段なら 89 通りです。

初期値が違うだけで、並びは同じ形をしています。

円形に並べる場合

両端がつながると、条件が 1 つ増えます。最初と最後も隣り合うので、そこも違う色でなければならない。

$k$ 色で円形に $n$ 個並べ、隣り合うものを違う色にする個数を $C_n$ とします。

直線に並べる $k(k-1{)}^{n-1}$ 通りのうち、両端が同じ色になっているものを引けばよい。両端が同じなら、その 2 つをまとめて $n-1$ 個の円と見られます。

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

3 色で三角形に並べるなら $3\times 2\times 1=6$ 通り。ここから順に $C_4=24-6=18$、$C_5=48-18=30$、$C_6=96-30=66$。

閉じた式でも書けます^[2]。

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

$k=3$、$n=6$ なら $2^6+2=66$ で、漸化式の値と合いました。

例：0 が 3 つ続かない 2 進の列

$n$ 桁の 0 と 1 の列で、0 が 3 つ続かないものを数えます。

末尾の 0 の連なりが 0 個、1 個、2 個の 3 通りで場合分けする。末尾が 1、末尾が 10、末尾が 100 の形です。

$$g_n=g_{n-1}+g_{n-2}+g_{n-3}$$

$g_1=2$、$g_2=4$、$g_3=7$ から始まり、$13,24,44,81$ と続きます。3 つ前まで足す形になる。

続けてよい個数が増えるほど、足す項が増えていきます。

例：同じ色を続けずに旗を立てる

4 色の旗を 6 本立て、隣り合う旗を違う色にします。

条件が「直前とだけ違えばよい」なので掛け算で済みます。$4\times 3^5=972$ 通り。

これを円形にすると $C_6=3^6+3=732$ 通り。両端がつながるだけで 240 通り減ります。

検算のしかた

漸化式を立てたら、必ず小さい $n$ で書き出して照合します。

$n=3$ まで手で数えれば、初期値と漸化式の両方が確かめられる。$n=4$ まで合えばまず安心です。

答えが全体の $k^n$ を超えていないかも見ます。条件を付けたのに増えていたら、どこかが誤っている。

よくある誤り

直前だけを見ればよい条件なら掛け算、そうでなければ漸化式。境目はここです。

参考文献

^[1] が隣どうしを足す数列、^[2] が一列と円形で隣を違う色にする個数、^[3] が段ごとに掛ける数え方、^[4] と ^[5] が各国語での整理です。