バーンサイドの補題とポリアの数え上げ定理 ― 対称性を考慮した数え上げ

群作用・軌道・固定部分群の定義からバーンサイドの補題を証明し，巡回指標を定義してポリアの定理を導く．ネックレス・ブレスレットの数え上げに応用する．

2026年2月27日

1 群作用・軌道・安定化群

定義 1 (群作用).

群

G

が集合

X

に作用する（act on）とは，写像

G \times X \to X

（

(g, x) \mapsto g \cdot x

）が

$e \cdot x = x$ （ $e$ は単位元， $x \in X$ ），
$(g h) \cdot x = g \cdot (h \cdot x)$ （ $g, h \in G$ ， $x \in X$ ）

を満たすことをいう．

定義 2 (軌道・安定化群).

x \in X

の軌道（orbit）とは

G \cdot x = {g \cdot x ∣ g \in G}

である．

x

の安定化群（stabilizer）とは

G_{x} = {g \in G ∣ g \cdot x = x}

である．

定理 3 (軌道・安定化群定理).

∣ G \cdot x ∣ = \frac{∣ G ∣}{∣ G _{x} ∣} = [G : G_{x}]

証明.

写像

g G_{x} \mapsto g \cdot x

は

G / G_{x}

から

G \cdot x

への全単射である．

g G_{x} = h G_{x} ⟺ h^{- 1} g \in G_{x} ⟺ g \cdot x = h \cdot x

であるから well-defined かつ単射．全射は明らか． □

定義 4 (固定点集合).

g \in G

に対して

X^{g} = {x \in X ∣ g \cdot x = x}

を

g

の固定点集合という．

2 バーンサイドの補題

定理 5 (バーンサイドの補題（Cauchy–Frobenius の定理）).

有限群

G

が有限集合

X

に作用するとき，軌道の個数

∣ X / G ∣

は

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣

で与えられる．

証明.

集合

S = {(g, x) \in G \times X ∣ g \cdot x = x}

の元の数を2通りに数える．

g

を固定して和をとると

∣ S ∣ = \sum_{g \in G} ∣ X^{g} ∣

．

x

を固定して和をとると

∣ S ∣ = \sum_{x \in X} ∣ G_{x} ∣

．軌道・安定化群定理より

∣ G_{x} ∣ = ∣ G ∣/∣ G \cdot x ∣

であるから，

x \in X \sum ∣ G_{x} ∣ = x \in X \sum \frac{∣ G ∣}{∣ G \cdot x ∣} = ∣ G ∣ x \in X \sum \frac{1}{∣ G \cdot x ∣}

同じ軌道

O

に属する

∣ O ∣

個の元はそれぞれ

1/∣ O ∣

を寄与するので，各軌道の寄与は

1

．よって

\sum_{x \in X} 1/∣ G \cdot x ∣ = ∣ X / G ∣

．

以上より

\sum_{g \in G} ∣ X^{g} ∣ = ∣ G ∣ \cdot ∣ X / G ∣

，すなわち

∣ X / G ∣ = \frac{1}{∣ G ∣} \sum_{g \in G} ∣ X^{g} ∣

． □

3 巡回指標

定義 6 (巡回指標).

有限群

G

が集合

{1, 2, \dots, n}

に作用するとき，

g \in G

を置換と見なし，その巡回分解における長さ

k

の巡回の個数を

j_{k} (g)

とする．

G

の巡回指標（cycle index）を

Z (G; s_{1}, s_{2}, \dots, s_{n}) = \frac{1}{∣ G ∣} g \in G \sum s_{1}^{j_{1} (g)} s_{2}^{j_{2} (g)} \dots s_{n}^{j_{n} (g)}

で定める．

4 ポリアの数え上げ定理

定理 7 (P\'olya の数え上げ定理).

n

個の位置に

m

種類の色を塗る配色のうち，群

G

の作用で同一視したものの個数は

Z (G; m, m, \dots, m)

で与えられる．より一般に，重み付き母関数は

Z (G; s_{1} = i \sum w_{i}, s_{2} = i \sum w_{i}^{2}, \dots, s_{k} = i \sum w_{i}^{k}, \dots)

で得られる．ここで

w_{1}, \dots, w_{m}

は各色に対応する重みである．

証明.

バーンサイドの補題より軌道数は

\frac{1}{∣ G ∣} \sum_{g \in G} ∣ X^{g} ∣

．

g

の巡回分解が長さ

c_{1}, c_{2}, \dots

の巡回からなるとき，

g

で固定される彩色の数は各巡回内で同色であることから

m^{j_{1} (g) + j_{2} (g) + \dots}

である（巡回の個数の和は巡回分解の巡回総数）．これを

s_{k} = m

として巡回指標に代入した結果に等しい． □

5 応用：ネックレスとブレスレット

例 8 (ネックレスの数え上げ).

n

個のビーズからなるネックレスに

m

色を塗る場合を考える．回転のみで同一視する場合，群は巡回群

C_{n}

であり，

Z (C_{n}) = \frac{1}{n} d ∣ n \sum φ (d) s_{d}^{n / d}

s_{k} = m

を代入すれば，ネックレスの色分けの数

\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}

が得られる．

例 9 (ブレスレットの数え上げ).

裏返しも許す場合，群は二面体群

D_{n}

（

∣ D_{n} ∣ = 2 n

）となる．

n

が奇数のとき

Z (D_{n}) = \frac{1}{2} Z (C_{n}) + \frac{1}{2} s_{1} s_{2}^{(n - 1) /2}

n

が偶数のとき

Z (D_{n}) = \frac{1}{2} Z (C_{n}) + \frac{1}{4} s_{1}^{2} s_{2}^{(n - 2) /2} + \frac{1}{4} s_{2}^{n /2}

s_{k} = m

と代入すればブレスレットの個数が得られる．

バーンサイドの補題とポリアの数え上げ定理 ― 対称性を考慮した数え上げ

1 群作用・軌道・安定化群

2 バーンサイドの補題

3 巡回指標

4 ポリアの数え上げ定理

5 応用：ネックレスとブレスレット

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ