離散数学・組合せ論の問題

方針 正六角形を自分自身に重ねる回転全体の群 $G$ が塗り方の集合 $X$ に作用している。回転で重なる塗り方を同じとみなしたときの個数は、バーンサイドの補題により
$$\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$$
で求められる。ここで $\mathrm{Fix}(g)$ は回転 $g$ で変わらない塗り方の集合である。

手順 1: 群 $G$ を書き出す 中心のまわりの $60^{\circ }\times k$ の回転 $r_k$（$k=0,1,2,3,4,5$）の $6$ 個なので $|G|=6$ である。$G$ は巡回群 $\mathbb{Z}/6\mathbb{Z}$ と同じ構造をもつ。

手順 2: 各回転の頂点の巡回置換分解を調べる 頂点を $1,2,\dots ,6$ と順に番号づけると、$r_k$ は頂点 $i$ を頂点 $i+k$（$6$ を法として）に移す。$r_k$ の位数は $\frac{6}{\gcd (k,6)}$ なので、各巡回置換の長さは $\frac{6}{\gcd (k,6)}$ で、巡回置換の個数は $\gcd (k,6)$ である。
- $r_0$（恒等変換）: $\gcd (0,6)=6$ 個（各頂点が長さ $1$）
- $r_1,r_5$（$60^{\circ },300^{\circ }$）: $1$ 個（長さ $6$）
- $r_2,r_4$（$120^{\circ },240^{\circ }$）: $2$ 個（例: $(135)(246)$）
- $r_3$（$180^{\circ }$）: $3$ 個（$(14)(25)(36)$）

手順 3: 固定される塗り方の個数を数える 回転で塗り方が変わらないのは、同じ巡回置換に入る頂点がすべて同じ色のときである。巡回置換ごとに色を $3$ 通り選べるので、積の法則により $|\mathrm{Fix}(r_k)|=3^{\gcd (k,6)}$ となる。
- $r_0$: $3^6=729$
- $r_1,r_5$: $3^1=3$ ずつ
- $r_2,r_4$: $3^2=9$ ずつ
- $r_3$: $3^3=27$

手順 4: 平均をとる
$$\frac{1}{6}(729+3+9+27+9+3)=\frac{780}{6}=130$$

よって、異なる塗り方は $130$ 通りである。

回転群 $C_6$（位数 6）によるバーンサイドの補題を用いる。回転角 $60°\cdot k$ ($k=0,\dots ,5$) による固定される塗り方の数は、頂点の置換のサイクル数を $c$ として $3^c$ 通り。
- $k=0$: サイクル数 6 → $3^6=729$
- $k=1,5$: サイクル数 1 → $3$ ずつ
- $k=2,4$: サイクル数 2 → $9$ ずつ
- $k=3$: サイクル数 3 → $27$
合計 $729+3+3+9+9+27=780$。位数 6 で割って $780/6=130$。
検算: ネックレスの公式 $\frac{1}{6}{\sum }_{d|6}\phi (d)3^{6/d}=\frac{1}{6}(3^6+3^3+2\cdot 3^2+2\cdot 3)=\frac{1}{6}(729+27+18+6)=130$。一致。