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

方針 正方形を自分自身に重ねる回転は、中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の $4$ つです。これらは群 $G$（$|G|=4$）をなし、頂点の塗り方の集合に作用します。回転で重なる塗り方を同一視したときの個数（軌道の個数）は、バーンサイドの補題より
$$\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$$
で求められます。ここで $\mathrm{Fix}(g)$ は回転 $g$ で変わらない塗り方の集合です。

各回転で固定される塗り方を数える 頂点を順に $1,2,3,4$ とします。回転 $g$ で塗り方が変わらないのは、$g$ の巡回置換分解の各巡回置換に含まれる頂点がすべて同じ色のときです。したがって、巡回置換の個数を $c(g)$ とすると $|\mathrm{Fix}(g)|=3^{c(g)}$ です。

• $0^{\circ }$（恒等変換）：$(1)(2)(3)(4)$ で $c=4$。$|\mathrm{Fix}|=3^4=81$。
• $90^{\circ }$：$(1234)$ で $c=1$。$|\mathrm{Fix}|=3^1=3$。
• $180^{\circ }$：$(13)(24)$ で $c=2$。$|\mathrm{Fix}|=3^2=9$。
• $270^{\circ }$：$(1432)$ で $c=1$。$|\mathrm{Fix}|=3^1=3$。

平均をとる
$$\frac{1}{4}(81+3+9+3)=\frac{96}{4}=24$$

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

回転群 $C_4$（位数4）によるバーンサイドの補題を使う。
- 恒等（0°回転）: 固定される塗り方は $3^4=81$
- 90°回転: 4頂点が1つの巡回なので $3$
- 180°回転: 2つの巡回（対角の頂点ずつ）なので $3^2=9$
- 270°回転: $3$

$\frac{81+3+9+3}{4}=\frac{96}{4}=24$

検算: 色の個数で分類する。1色のみ: 3通り。ちょうど2色（色の組3通り）の場合、一方の色の個数が1,2,3個のとき、回転で区別した塗り方は、1個:1通り、3個:1通り、2個:隣接と対角の2通りで、計 4 通り。よって $3\times 4=12$。3色すべて使う場合は、1色が2個で他が1個ずつ。2個の色を選ぶ3通りに対し、2個が隣接か対角かで2通り。隣接の場合、残り2つの色の配置は回転で区別され2通り、対角の場合は残り2頂点の入れ替えが回転で同じになり1通り。よって $3\times (2+1)=9$。合計 $3+12+9=24$。一致する。