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

正方形の対称変換全体は位数 $8$ の二面体群 $D_4$ をなし、$16$ マスの集合に作用する。黒く塗る $4$ マスの選び方（$4$ 元部分集合）の集合に誘導される作用の軌道の個数を、バーンサイドの補題
$$\#(\text{軌道})=\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$$
で求める。変換 $g$ で動かない塗り方とは、黒マスの集合が $g$ のマス上の巡回（軌道）の和集合になっているもののことである。

(1) 恒等変換：すべての選び方が不変なので $\left(\genfrac{}{}{0ex}{}{16}{4}\right)=1820$。

(2) $90^{\circ }$, $270^{\circ }$ 回転：固定されるマスはなく、$16$ マスは長さ $4$ の巡回 $4$ 個に分かれる（内側の $2\times 2$ が $1$ 個、外周の $12$ マスが $3$ 個）。黒 $4$ マスは巡回 $1$ 個を丸ごと選ぶ場合に限るので $4$ 通り。$2$ つの回転で計 $8$。

(3) $180^{\circ }$ 回転：固定マスはなく、長さ $2$ の巡回が $8$ 個。そのうち $2$ 個を選んで $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$。

(4) 縦・横の中線に関する裏返し：中線はマスの境界上を通るので固定マスはなく、長さ $2$ の巡回が $8$ 個。それぞれ $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$、$2$ 本で計 $56$。

(5) 対角線に関する裏返し：対角線上の $4$ マスが固定され、残り $12$ マスは長さ $2$ の巡回 $6$ 個に分かれる。黒 $4$ マスの作り方は
- 固定マス $4$ 個：$1$ 通り
- 固定マス $2$ 個と $2$-巡回 $1$ 個：$\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 6=36$ 通り
- $2$-巡回 $2$ 個：$\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ 通り

で計 $52$。$2$ 本で計 $104$。

よって
$$\frac{1820+8+28+56+104}{8}=\frac{2016}{8}=252.$$
答えは $252$ 通り。

バーンサイドの補題を使う。各変換で固定される塗り方（黒 4 マス）の数を数える。

• 恒等変換：$\left(\genfrac{}{}{0ex}{}{16}{4}\right)=1820$
• $90^{\circ }$, $270^{\circ }$ 回転：マスは長さ 4 の巡回 4 個に分かれる。黒 4 マスは 1 つの巡回全体になるので、それぞれ $4$ 通り
• $180^{\circ }$ 回転：長さ 2 の巡回 8 個に分かれる。そのうち 2 個を選ぶので $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$
• 縦・横の中線に関する裏返し（2 本）：固定されるマスはなく、長さ 2 の巡回 8 個に分かれる。それぞれ $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$
• 対角線に関する裏返し（2 本）：固定されるマスが 4 個、長さ 2 の巡回が 6 個ある。固定マス $a$ 個と巡回 $b$ 個を選ぶとき $a+2b=4$ となる。
• $(a,b)=(0,2)$：$\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$
• $(2,1)$：$\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 6=36$
• $(4,0)$：$1$
• 合計 $52$ 通り（対角線 1 本あたり）

固定される塗り方の総和は $1820+4+4+28+28+28+52+52=2016$。

異なる塗り方の数は $2016/8=252$。

確認：総和 $2016$ が $8$ で割り切れ、整数 $252$ になる。