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

石の置き方は 16 マスのうち 4 マスからなる部分集合であり、全部で $\left(\genfrac{}{}{0ex}{}{16}{4}\right)=1820$ 個ある。これに正方形の対称移動の群 $D_4$（位数 8）が作用しており、求めるものは軌道の個数である。バーンサイドの補題
$$(\text{軌道の個数})=\frac{1}{|D_4|}\sum _{g\in D_4}|\mathrm{Fix}(g)|$$
を使う。$g$ で固定される 4 元部分集合は、$g$ によるマスの巡回（サイクル）の和集合で、合計 4 マスになるものである。

• 恒等変換: $|\mathrm{Fix}|=\left(\genfrac{}{}{0ex}{}{16}{4}\right)=1820$。
• $90^{\circ }$・$270^{\circ }$ 回転: 16 マスは長さ 4 のサイクル 4 個（四隅、中央の 4 マス、辺上の 8 マスが 2 個）に分かれる。サイクルを 1 個選べばよいので各 $4$ 通り、合計 $8$。
• $180^{\circ }$ 回転: 固定されるマスはなく、16 マスは長さ 2 のサイクル 8 個に分かれる。2 個選んで $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$。
• 辺の中点を通る軸についての裏返し（縦軸・横軸の 2 つ）: 軸はマスの境界を通るので固定マスはなく、長さ 2 のサイクル 8 個。各 $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$、合計 $56$。
• 対角線についての裏返し（2 つ）: 対角線上の 4 マスが固定され、残り 12 マスは長さ 2 のサイクル 6 個。4 マスの作り方は
• 固定マス 4 個: $1$ 通り
• 固定マス 2 個とサイクル 1 個: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 6=36$ 通り
• サイクル 2 個: $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ 通り

で各 $52$、合計 $104$。

よって
$$\frac{1820+8+28+56+104}{8}=\frac{2016}{8}=252.$$

答えは $252$ 通り。

バーンサイドの補題を二面体群 $D_4$（位数 8）に適用する。固定される配置（16 マスから 4 マスを選ぶ）の数を群の元ごとに数える。

• 恒等: $\left(\genfrac{}{}{0ex}{}{16}{4}\right)=1820$
• 90 度・270 度回転（2 個）: 巡回置換は長さ 4 のサイクル 4 個。4 個の石はちょうど 1 サイクルを選ぶ場合のみ固定され、各 4 通り。計 $4\cdot 2=8$
• 180 度回転: 長さ 2 のサイクル 8 個。そのうち 2 個を選ぶ: $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$
• 縦・横の軸に関する反転（2 個）: 固定マスなし、長さ 2 のサイクル 8 個。各 $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$。計 56
• 対角線に関する反転（2 個）: 固定マス 4 個、長さ 2 のサイクル 6 個。2 サイクル 0 個 + 固定 4: 1、サイクル 1 個 + 固定 2: $6\cdot 6=36$、サイクル 2 個: $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$。合計 52。計 $52\cdot 2=104$

総和 $=1820+8+28+56+104=2016$。$2016/8=252$。