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

盤の対称変換群を $G$（位数 $8$）とし、$X$ を「$9$ マスのうち $4$ マスを黒にする塗り方」全体とする。$|X|=\left(\genfrac{}{}{0ex}{}{9}{4}\right)=126$ である。バーンサイドの補題より、求める個数は
$$\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$$
である。変換 $g$ で動かない塗り方とは、$g$ によるマスの巡回（軌道）ごとに同じ色で塗られている塗り方であり、黒マスの個数が $4$ になるには、黒にする巡回の長さの和が $4$ になればよい。

恒等変換：$|\mathrm{Fix}|=\left(\genfrac{}{}{0ex}{}{9}{4}\right)=126$。

$90^{\circ },270^{\circ }$ の回転：マスの巡回は 中央（長さ $1$）、四隅（長さ $4$）、辺の中央の $4$ マス（長さ $4$）。長さの和が $4$ になるのは長さ $4$ の巡回を $1$ つ選ぶときだけで $2$ 通り。よって各 $2$、合計 $4$。

$180^{\circ }$ の回転：巡回は中央（長さ $1$）と長さ $2$ の巡回 $4$ 個。和を $4$ にするには、中央を含めると和が奇数になるので不可。長さ $2$ の巡回を $2$ 個選んで $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通り。

裏返し（$4$ 本の軸それぞれ）：縦・横の軸でも対角線の軸でも、軸上の $3$ マスは動かず（長さ $1$ の巡回 $3$ 個）、残り $6$ マスは $3$ 組の対（長さ $2$ の巡回 $3$ 個）になる。和が $4$ になるのは
- 長さ $2$ を $2$ 個、長さ $1$ を $0$ 個：$\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ 通り
- 長さ $2$ を $1$ 個、長さ $1$ を $2$ 個：$\left(\genfrac{}{}{0ex}{}{3}{1}\right)\left(\genfrac{}{}{0ex}{}{3}{2}\right)=9$ 通り
- 長さ $1$ を $4$ 個：$3$ 個しかないので不可

で、各 $12$ 通り。$4$ 本の軸で合計 $48$。

したがって
$$\frac{1}{8}(126+4+6+48)=\frac{184}{8}=23.$$
よって異なる塗り方は $23$ 通りである。

バーンサイドの補題を使う。各変換で不変な塗り方（黒 4 個）を数える。

• 恒等変換：$\left(\genfrac{}{}{0ex}{}{9}{4}\right)=126$
• 90°、270° 回転：巡回置換の型は、中心 1 個、角の 4 巡回、辺の 4 巡回。黒 4 個になるのは、角 4 個がすべて黒か、辺 4 個がすべて黒のときで、それぞれ 2 通り。
• 180° 回転：中心 1 個と 2 巡回 4 個。中心が黒だと残りの黒は 3 個になり、2 個ずつの組では作れない。よって中心は白で、4 組から 2 組を選ぶので $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通り。
• 4 本の反転（縦、横、2 本の対角線）：不動のマス 3 個と 2 巡回 3 個。不動マスの黒が $k$ 個、2 巡回の黒の組が $j$ 組とすると $k+2j=4$。$(k,j)=(2,1)$ のとき $\left(\genfrac{}{}{0ex}{}{3}{2}\right)\cdot 3=9$ 通り、$(k,j)=(0,2)$ のとき $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ 通り。$(k,j)=(4,0)$ は $k\le 3$ に反するので不可。合計 12 通りで、4 本とも同じ。

合計：$126+2+2+6+4\cdot 12=184$。

$184/8=23$。

検算：黒 4 個と白 5 個の塗り方 126 通りを軌道の大きさで分けたとき、軌道数は 23 通り。バーンサイドの補題の結果が整数になっているので、計算に矛盾はない。