数学A / 場合の数

円環をk色で塗り分ける(数え上げと漸化式)

実戦編数え上げ漸化式塗り分け彩色単元横断

問題

$n$ 個のマスを円形に並べ、隣り合うマスが異なる色になるように $k$ 色で塗る方法の総数 $c_{n}$ を求めよ( $n \geq 3, k \geq 2$ )。

ヒントを見る

1列に並べる塗り方は $k (k - 1)^{n - 1}$ 。そのうち両端が同色のものは、両端をくっつけると $n - 1$ 個の円になる。 $c_{n}$ と $c_{n - 1}$ の関係は?

解答・解説

方針

まず1列(円にしない)の塗り方は $k (k - 1)^{n - 1}$ 。これを「両端が異色(=円としても正しい)」と「両端が同色」に分け、後者を1つ短い円と対応させて漸化式を作る。

解答

⓪ 発想 — どう考え始めるか。 円は端がつながっていて数えにくい。いったん切って1列にするのが定石だ。

1列の塗り方は、左端 $k$ 色、以降は左隣と違う色で $k (k - 1)^{n - 1}$ 通り。

この1列を円に丸めるとき、両端が異色ならそのまま正しい円の塗り( $= c_{n}$ )。両端が同色なら、両端を融合すると1つ短い円の塗り( $= c_{n - 1}$ )に対応する。よって $c_{n} + c_{n - 1} = k (k - 1)^{n - 1}$ — この漸化式を解けば閉じた式が出る。

① 直線の塗り方を分ける。 $n$ マスを1列に隣接異色で塗る方法は $k (k - 1)^{n - 1}$ 。両端の色で $k (k - 1)^{n - 1} = 両端異色 c_{n} + 両端同色 c_{n - 1} .$ (両端同色の並びは、その両端を1マスとみなすと $n - 1$ マスの円の正しい塗りと1対1。)

例(n=5, k=3): 5マスを輪にし、隣どうし異色に3色で塗った一例(青・赤・黒)。総数は (k−1)ⁿ+(−1)ⁿ(k−1)。

② 漸化式を解く。 $c_{n} = k (k - 1)^{n - 1} - c_{n - 1}$ 。両辺に $(- 1)^{n}$ を掛けて整理する、あるいは $c_{n} - (k - 1)^{n}$ を考えると等比になる。 $c_{n} - (k - 1)^{n} = - (c_{n - 1} - (k - 1)^{n - 1})$ が成り立つ(代入で確認)ので、 $d_{n} = c_{n} - (k - 1)^{n}$ は公比 $- 1$ の等比数列。

重要

c_{n} = k (k - 1)^{n - 1} - c_{n - 1}

から

c_{n} - (k - 1)^{n} = - (c_{n - 1} - (k - 1)^{n - 1})

③ 一般項。 $c_{2} = k (k - 1)$ (2マスの円=1列と同じ)より $d_{2} = c_{2} - (k - 1)^{2} = (k - 1)$ 。よって $d_{n} = (k - 1) (- 1)^{n - 2} = (k - 1) (- 1)^{n}$ 。したがって $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1) .$

まとめ 円は直線に開いて数え、両端が同色・異色で場合分けすると $k (k - 1)^{n - 1} = c_{n} + c_{n - 1}$ 。等比化して $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ 。数え上げと漸化式の融合。 $n = 5, k = 3$ なら $32 - 2 = 30$ 。

発展 — 一歩先へ。 $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ は、グラフ理論では「サイクル $C_{n}$ の彩色多項式」と呼ばれる式そのもの。さらに「回転して同じ塗りは1つと数える」(首飾りの問題)に変えると、割る操作が単純な $\div n$ では済まず、バーンサイドの補題(回転ごとの固定点を平均する)が必要になる — 「配置の数え上げ」と「対称性で割る数え上げ」の境目が、この問題のすぐ隣にある。

答

1列(パス)の塗り方 $k (k - 1)^{n - 1}$ を、両端が同色か否かで分けると $k (k - 1)^{n - 1} = c_{n} + c_{n - 1}$ 。解いて $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ 。

別解

端の色で場合分けする第2の漸化式(検算にも使える)。 円を切らずに、 $n$ 番目のマスの色で直接分類する手もある。1列に並べた $1, \dots, n$ 番を考え、円の条件は「隣どうし異色+両端異色」。

$n$ 番目のマスから見ると:

$n - 1$ 番目までが「円として正しい塗り」( $c_{n - 1}$ 通り)のとき、 $n$ 番は「 $n - 1$ 番とも1番とも違う色」— $k - 2$ 色
$n - 1$ 番目までが「1列としては正しいが両端( $1$ 番と $n - 1$ 番)が同色」のとき、 $n$ 番は「その色以外」— $k - 1$ 色。この場合の数は( $n - 1$ 番と1番を融合して) $c_{n - 2}$ 通り

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

本解の $c_{n} + c_{n - 1} = k (k - 1)^{n - 1}$ とは別の漸化式だが、閉じた式 $(k - 1)^{n} + (- 1)^{n} (k - 1)$ は両方を満たす(代入で確認できる)。2本の独立な漸化式で同じ式を挟むと、答えの信頼度は跳ね上がる — 数え上げの検算術として覚えておきたい。

ポイント

直線(1列)の塗り方 $k (k - 1)^{n - 1}$ を両端の色で分ける。
両端同色は $n - 1$ マスの円と対応、 $k (k - 1)^{n - 1} = c_{n} + c_{n - 1}$ 。
等比化して $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ 。

よくある間違い

円の数え上げをいきなり「1列の $\frac{1}{n}$ 」などと回転で割る方向に行く(マスは固定されていて回転同一視はしない問題)。
両端同色の1列と $c_{n - 1}$ の対応(両端を融合して1マス減らす)の説明を落とす。
漸化式を解くとき、 $c_{n} - (k - 1)^{n}$ が公比 $- 1$ の等比になる構造( $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ の由来)を確認せず結果だけ書く。