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

10 か所の位置に番号 $0,1,\dots ,9$ を付ける。同一視に使う変換は正十角形の対称移動全体（二面体群）で、回転 10 個と裏返し 10 個の計 20 個である。各変換で動かない並べ方の数を数える。動かない並べ方では、変換の同じ巡回に属する位置は同じ色であり、赤い位置の総数がちょうど 4 でなければならない。

回転. $\frac{360^{\circ }}{10}\times r$ ($r=0,1,\dots ,9$) の回転は、位置を長さ $\frac{10}{d}$ の巡回 $d$ 個に分ける（$d=\gcd (r,10)$、$r=0$ のときは $d=10$）。
- $r=0$（恒等変換）: $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$。
- $d=1$ ($r=1,3,7,9$): 長さ 10 の巡回 1 個。赤 4 個は作れず $0$。
- $d=2$ ($r=2,4,6,8$): 長さ 5 の巡回 2 個。4 は 5 の倍数でないので $0$。
- $d=5$ ($r=5$): 長さ 2 の巡回 5 個。そのうち 2 個を赤にして $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$。

回転の合計は $210+10=220$。

裏返し. 10 は偶数なので裏返しは 2 種類ある。
- 向かい合う 2 つの位置を通る軸に関する裏返し（5 個）: その 2 位置が固定され、残り 8 位置が 4 つの互換をなす。固定点のうち赤にする個数を $s$ とすると、$4-s$ は偶数なので $s=0$ または $s=2$。$s=0$ なら互換 4 個から 2 個を選んで $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$、$s=2$ なら互換 1 個を選んで $\left(\genfrac{}{}{0ex}{}{4}{1}\right)=4$。計 $10$ 通り。
- 隣り合う位置の間を通る軸に関する裏返し（5 個）: 10 位置が 5 つの互換をなし、2 個を赤にして $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通り。

裏返しの合計は $5\cdot 10+5\cdot 10=100$。

バーンサイドの補題.
$$\frac{1}{20}(220+100)=\frac{320}{20}=16.$$

二面体群 $D_{10}$（位数 20）に対するバーンサイドの補題を用いる。回転: 回転角が $2\pi k/10$ のとき、巡回の長さは $d=\gcd (k,10)$ 個の周期。赤 4・青 6 が固定されるには $10/d$ の周期に分けられる必要があり、$g=\gcd (10,4,6)=2$ の約数 $m=10/d$ が条件。固定される配置数は、回転なし: $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$、180 度回転（5 個ずつの 2 周期）: $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$、ほかの回転: 0。回転の合計 $220$。反転（10 個）: 頂点を通る軸 5 本は固定点 2 個と 2 個組 4 つ。固定点がともに青なら青の組が 2 つ: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$、ともに赤なら赤の組が 1 つ: $\left(\genfrac{}{}{0ex}{}{4}{1}\right)=4$、赤青 1 つずつだと赤の個数が奇数になり不可。合計 10。辺の中点を通る軸 5 本は 2 個組 5 つで、赤の組が 2 つ: $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$。反転の合計 $5\cdot 10+5\cdot 10=100$。よって $(220+100)/20=16$。検算: 回転のみのとき $(210+10)/10=22$ 通り（ネックレス）で、裏返しで同一視されるものがあるため 16 は 22 以下で整合する。