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

正方形の頂点に反時計回りに $1,2,3,4$ と番号をつけ、$4$ つの回転が頂点に引き起こす置換を巡回置換の積に分解する。

• $0^{\circ }$ 回転（恒等変換）：$(1)(2)(3)(4)$。長さ $1$ の巡回が $4$ 個なので、単項式は $s_1^4$。
• $90^{\circ }$ 回転：$(1234)$。長さ $4$ の巡回が $1$ 個なので $s_4$。
• $180^{\circ }$ 回転：$(13)(24)$。長さ $2$ の巡回が $2$ 個なので $s_2^2$。
• $270^{\circ }$ 回転：$(1432)$。長さ $4$ の巡回が $1$ 個なので $s_4$。

群の位数は $4$ なので、これらの単項式の平均をとって巡回指数は
$$Z(s_1,s_2,s_3,s_4)=\frac{1}{4}\left(s_1^4+s_2^2+2s_4\right).$$

ポリアの数え上げ定理により、$k$ 色での塗り方の総数は、すべての $s_j$ に $k$ を代入した $Z(k,k,k,k)$ である。各巡回の頂点は同じ色でなければ回転で固定されないので、巡回 $1$ つにつき $k$ 通りの色の選び方があるからである。$k=3$ を代入すると
$$Z(3,3,3,3)=\frac{1}{4}\left(3^4+3^2+2\cdot 3\right)=\frac{1}{4}(81+9+6)=\frac{96}{4}=24.$$

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

回転群 $C_4$ の頂点への作用を考える。恒等変換(0°)は $s_1^4$、90°と270°は4-サイクル1つで $s_4$ がそれぞれ1つずつ、180°は2-サイクル2つで $s_2^2$ である。したがって巡回指数は $Z=\frac{1}{4}(s_1^4+s_2^2+2s_4)$。

3色で塗るので各 $s_k$ に $3$ を代入する（$s_k\to 3$）。すると $Z(3,3,3,3)=\frac{1}{4}(3^4+3^2+2\cdot 3)=\frac{1}{4}(81+9+6)=\frac{96}{4}=24$。

検算：バーンサイドの補題より、各変換で固定される塗り方の数は、恒等で $3^4=81$、90°と270°で $3$ 通りずつ、180°で $3^2=9$ 通り。合計 $81+3+9+3=96$ を群の位数4で割って $24$。これは3色のネックレス（長さ4、回転のみ）の個数 $\frac{1}{4}\sum \phi (d)3^{4/d}=\frac{1}{4}(81+9+2\cdot 3)=24$ と一致する。