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

頂点に反時計回りに $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)$。単項式は $s_4$。

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

ポリアの数え上げ定理より、$k$ 色で塗る方法の総数は、すべての $s_j$ に $k$ を代入した値 $Z(k,k,k)$ である。これは、長さ $j$ の巡回に含まれる頂点はすべて同じ色でなければその置換で固定されないので、各巡回ごとに $k$ 通りの色を選べることに対応している。$k=3$ を代入して
$$Z(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=\{e,r,r^2,r^3\}$ が正方形の4頂点に引き起こす置換の巡回指数を求める。
- 恒等置換 $e$: 巡回分解は $(1)(2)(3)(4)$ で、単項式は $x_1^4$。
- 90°回転 $r$ と 270°回転 $r^3$: 4-巡回置換で、単項式は $x_4$（それぞれ）。
- 180°回転 $r^2$: $(13)(24)$ で、単項式は $x_2^2$。

よって巡回指数は $Z=\frac{1}{4}(x_1^4+x_2^2+2x_4)$。

各 $x_k$ に色数 $3$ を代入すると $\frac{1}{4}(3^4+3^2+2\cdot 3)=\frac{81+9+6}{4}=\frac{96}{4}=24$。

検算（バーンサイドの補題）: 固定される塗り方の数は $e$: $81$、$r$: $3$、$r^2$: $9$、$r^3$: $3$ で、合計 $96$、平均 $24$。

また、一般の $n$ 色の場合は $\frac{n^4+n^2+2n}{4}$ で、$n=2$ のとき $\frac{16+4+4}{4}=6$（既知の値と一致）。

答えは $24$。