巡回指数とポリアの数え上げ

対称移動が面・辺・頂点に引き起こす置換の巡回の型から巡回指数 $Z (s_{1}, s_{2}, \dots)$ を作り、 $k$ 色の塗り方の総数 $Z (k, k, \dots)$ や、各色の枚数を指定した塗り方の数（ $s_{j}$ に $r^{j} + b^{j} + g^{j}$ を代入した多項式の係数）を求められる

前提

バーンサイドの補題（大学数学離散数学・組合せ論）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）

この技能までの道筋（26 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
置換の巡回置換分解と位数（大学数学代数学）
バーンサイドの補題（大学数学離散数学・組合せ論）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）

説明

有限集合 $X$ （図形の頂点・辺・面など）に対称移動の群 $G$ が作用しているとき、各元が $X$ に引き起こす置換の巡回の型をまとめた多項式を巡回指数 $Z (s_{1}, s_{2}, \dots)$ といいます。これを一度作っておけば、対称移動で重なるものを同じとみなしたときの $k$ 色の塗り方の総数が $Z (k, k, \dots)$ で求まります。さらに $s_{j}$ に $r^{j} + b^{j} + g^{j}$ を代入して展開すると、その係数から「赤 $p$ 個・青 $q$ 個・緑 $u$ 個」のように色の個数を指定した塗り方の数も求まります。立方体の面、ネックレスの玉、正多角形の頂点の塗り分けなどで使います。

なぜそうしてよいのか

出発点はバーンサイドの補題です。塗り方の個数は $\frac{1}{∣ G ∣} \sum_{g \in G} ∣ Fix (g) ∣$ と書けます。 $g$ を $X$ 上の置換とみて巡回置換に分解すると、塗り方が $g$ で変わらないのは、各巡回の中の位置がすべて同じ色のとき、かつそのときに限ります。 $g$ は巡回の中の位置を順に次の位置へ送るので、色が変わらないためには巡回の中で色が一定でなければならないからです。したがって $g$ の巡回の個数を $c (g)$ とすると、 $k$ 色では $∣ Fix (g) ∣ = k^{c (g)}$ です。

そこで $g$ の長さ $j$ の巡回の個数を $c_{j} (g)$ とし、 $g$ に単項式 $s_{1}^{c_{1} (g)} s_{2}^{c_{2} (g)} \dots$ を対応させます。これを平均した $Z = \frac{1}{∣ G ∣} \sum_{g} s_{1}^{c_{1} (g)} s_{2}^{c_{2} (g)} \dots$ が巡回指数です。すべての $s_{j}$ に $k$ を代入すると各項は $k^{c_{1} + c_{2} + \dots} = k^{c (g)}$ になるので、 $Z (k, k, \dots)$ はバーンサイドの補題の式そのものです。

色の個数まで区別するには、長さ $j$ の巡回 1 つを「 $j$ 個の位置がすべて赤」「すべて青」「すべて緑」のどれかとみて、 $r^{j} + b^{j} + g^{j}$ で表します（指数は使った個数）。各巡回の色は独立に選べるので、積をとって展開すると、 $r^{p} b^{q} g^{u}$ の係数は $g$ で固定され、赤 $p$ ・青 $q$ ・緑 $u$ 個である塗り方の数になります。対称移動で色の個数は変わらないので、色の個数を指定した塗り方の集合は $G$ で閉じています。この集合にバーンサイドの補題を当てはめると、求める数は $Z (r + b + g, r^{2} + b^{2} + g^{2}, \dots)$ の $r^{p} b^{q} g^{u}$ の係数になります。

手順

塗る対象の集合 $X$ （頂点・辺・面のどれか）と、同一視に使う群 $G$ （回転だけか、裏返しも含むか）を確定し、 $∣ X ∣ = n$ 、 $∣ G ∣$ を確認する。
$G$ の各元 $g$ について、 $X$ 上の置換を巡回置換に分解し、長さ $j$ の巡回の個数 $c_{j}$ を数えて単項式 $s_{1}^{c_{1}} s_{2}^{c_{2}} \dots$ を書く（検算として $\sum_{j} j c_{j} = n$ ）。
同じ型の元をまとめて足し、 $∣ G ∣$ で割って巡回指数 $Z = \frac{1}{∣ G ∣} \sum_{g \in G} s_{1}^{c_{1} (g)} s_{2}^{c_{2} (g)} \dots$ を作る（係数の和が $∣ G ∣$ になるか確かめる）。
$k$ 色の塗り方の総数なら、すべての $s_{j}$ に $k$ を代入して $Z (k, k, \dots)$ を計算する。
色ごとの個数が指定されているなら、 $s_{j}$ に $r^{j} + b^{j} + \dots$ （色ごとに $j$ 乗の和）を代入し、指定に対応する単項式 $r^{p} b^{q} \dots$ の係数を項ごとに求めて足し、 $∣ G ∣$ で割る。

例題

正六角形の 6 個の頂点を、赤 3 個・青 3 個で塗る。正六角形の回転と裏返し（位数 12 の群）で重なる塗り方は同じとみなすとき、塗り方は何通りあるか求めよ。

例題の解答

手順1: $X$ は 6 個の頂点（ $n = 6$ ）、 $G$ は回転 6 個と裏返し 6 個からなる位数 12 の群。

手順2: 各元の巡回の型を求める。恒等変換は $s_{1}^{6}$ 。 $6 0^{\circ}, 30 0^{\circ}$ 回転は 6 頂点を 1 つの巡回で回すので $s_{6}$ （2 個）。 $12 0^{\circ}, 24 0^{\circ}$ 回転は長さ 3 の巡回が 2 つで $s_{3}^{2}$ （2 個）。 $18 0^{\circ}$ 回転は向かい合う頂点の入れかえ 3 つで $s_{2}^{3}$ 。向かい合う頂点を通る軸での裏返しは、軸上の 2 頂点を固定し残りを 2 組入れかえるので $s_{1}^{2} s_{2}^{2}$ （3 個）。向かい合う辺の中点を通る軸での裏返しは固定点がなく $s_{2}^{3}$ （3 個）。どの型も $\sum j c_{j} = 6$ を満たす。

手順3: $Z = \frac{1}{12} (s_{1}^{6} + 2 s_{6} + 2 s_{3}^{2} + 4 s_{2}^{3} + 3 s_{1}^{2} s_{2}^{2})$ 係数の和は $1 + 2 + 2 + 4 + 3 = 12$ で合っている。

手順5: $s_{j} = r^{j} + b^{j}$ を代入し、各項の $r^{3} b^{3}$ の係数を求める。
・ $(r + b)^{6}$ ： $(3 6) = 20$
・ $r^{6} + b^{6}$ ： $0$
・ $(r^{3} + b^{3})^{2} = r^{6} + 2 r^{3} b^{3} + b^{6}$ ： $2$ 。係数 2 を掛けて $4$
・ $(r^{2} + b^{2})^{3}$ ：指数がすべて偶数なので $0$
・ $(r + b)^{2} (r^{2} + b^{2})^{2} = (r^{2} + 2 r b + b^{2}) (r^{4} + 2 r^{2} b^{2} + b^{4})$ ： $r^{3} b^{3}$ は $2 r b \cdot 2 r^{2} b^{2}$ からだけ出るので $4$ 。係数 3 を掛けて $12$
合計は $20 + 0 + 4 + 0 + 12 = 36$ 。これを 12 で割って $36 \div 12 = 3$ 。
（確認: 赤が 3 個連続、2 個連続と 1 個、交互の 3 通りで、実際に一致する。）

答え: $3$

よくある誤り

$k$ 色の総数を求めるとき、 $s_{j}$ に $k^{j}$ を代入してしまう誤り。長さ $j$ の巡回 1 つは 1 色で塗るので選び方は $k$ 通り。正しくは $s_{j} = k$ とし、例えば正方形の頂点（回転と裏返し）を 3 色で塗るなら $\frac{1}{8} (3^{4} + 2 \cdot 3 + 3 \cdot 3^{2} + 2 \cdot 3^{2} \cdot 3) = 21$ 。
色の個数を指定するとき、 $s_{j}$ に $r + b + g$ を代入してしまう誤り。長さ $j$ の巡回は $j$ 個の位置が同じ色になるので、正しくは $s_{j} = r^{j} + b^{j} + g^{j}$ （例: $s_{2} = r^{2} + b^{2} + g^{2}$ ）。
裏返しの巡回の型を 1 種類だと思い込む誤り。正六角形（頂点の数が偶数の正多角形）では、頂点を通る軸の裏返しは $s_{1}^{2} s_{2}^{2}$ 、辺の中点を通る軸の裏返しは $s_{2}^{3}$ と型が異なる。正しくは各軸の位置ごとに固定点を確認し、係数の和が $∣ G ∣$ になるかを確かめる。
塗る対象を取り違える誤り。面を塗るのに頂点の置換の型を使うなど。例えば立方体の面の 4 回回転軸まわりの $9 0^{\circ}$ 回転は、面に対しては $s_{1}^{2} s_{4}$ 、頂点に対しては $s_{4}^{2}$ である。正しくは実際に塗る集合 $X$ 上の置換で型を求め、 $\sum_{j} j c_{j} = ∣ X ∣$ で検算する。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

巡回指数とポリアの数え上げ

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題