対称性で数え上げを楽にする ― バーンサイドの補題とポリアの数え上げ定理

回転や鏡映で同じものを区別しない数え上げ（ネックレスの塗り分けなど）を，群作用の言葉で統一的に扱います．「軌道の数＝固定点数の平均」というバーンサイドの補題の本質を解説します．

2026年2月27日

「3色のビーズで4個のネックレスを作ると何通り？」― こういう問題で難しいのは，回転して同じになるものを同一視しなければならないことです．対称性があると素朴な数え上げではうまくいきません．バーンサイドの補題は，対称性の下での数え上げを「固定点数の平均」という美しい公式に帰着させます．

1 問題の設定 ― なぜ素朴に数えられないのか

例 1 (ネックレスの塗り分け).

4つのビーズからなるネックレスを3色で塗り分ける方法は何通りでしょうか？回転して同じになるものは同一とみなします．

回転を無視すれば

3^{4} = 81

通りですが，4つの回転（

0°, 90°, 180°, 270°

）で移り合うものを同一視する必要があります．

注意 2.

素朴に81通りを4で割ると

81/4 = 20.25

で整数になりません．これは「すべての着色が同じ個数の軌道に属する」わけではないからです．例えば「全色同じ」の着色は回転しても変わらない（軌道のサイズが1）のに対し，4色バラバラの着色は回転で4つの異なる着色を生みます（軌道のサイズが4）．

2 群作用と軌道 ― 対称性の数学的表現

定義 3 (群作用).

群

G

が集合

X

に作用するとは，各

g \in G

に対して写像

g : X \to X

が定まり，

$e \cdot x = x$ （単位元は恒等写像）
$(g h) \cdot x = g \cdot (h \cdot x)$ （結合的）

を満たすことです．

定義 4 (軌道).

x \in X

の軌道（orbit）とは

Orb (x) = {g \cdot x ∣ g \in G}

です．「

G

の作用で

x

から到達できるすべての要素」の集合です．

注意 5.

ネックレスの例では，

G = Z /4 Z

（回転群），

X

は

3^{4} = 81

通りの着色の集合です．「回転して同じ」着色は同じ軌道に属します．求めたいのは軌道の個数です．

3 バーンサイドの補題

定義 6 (固定点集合).

g \in G

に対して，

g

の固定点集合は

Fix (g) = {x \in X ∣ g \cdot x = x}

です．

定理 7 (バーンサイドの補題).

有限群

G

が有限集合

X

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

∣ X / G ∣

は

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ Fix (g) ∣

つまり，固定点数の平均に等しくなります．

証明.

集合

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

の要素数を2通りに数えます．

g

を固定して

x

を動かすと

∣ S ∣ = \sum_{g \in G} ∣ Fix (g) ∣

です．

x

を固定して

g

を動かすと，

g \cdot x = x

を満たす

g

の集合は

x

の安定化群

Stab (x)

です．軌道・安定化群定理（

∣ Orb (x) ∣ \cdot ∣ Stab (x) ∣ = ∣ G ∣

）より

∣ Stab (x) ∣ = ∣ G ∣/∣ Orb (x) ∣

です．

したがって

∣ S ∣ = x \in X \sum ∣ Stab (x) ∣ = x \in X \sum \frac{∣ G ∣}{∣ Orb ( x ) ∣}

各軌道

O

に対して

\sum_{x \in O} \frac{1}{∣ O ∣} = 1

なので，

∣ S ∣ = ∣ G ∣ \cdot (軌道の個数)

です．

2つの表現を等しくおいて割れば定理が得られます． □

4 ネックレス問題の解法

4ビーズ3色のネックレスの問題に戻りましょう． $G = {r^{0}, r^{1}, r^{2}, r^{3}}$ （ $r$ は $90°$ 回転）です．

例 8.

各群元の固定点数を数えます：

$r^{0}$ （恒等変換）：すべての着色を固定 → $∣ Fix (r^{0}) ∣ = 3^{4} = 81$
$r^{1}$ （ $90°$ 回転）：4ビーズがすべて同色のもののみ固定 → $∣ Fix (r^{1}) ∣ = 3$
$r^{2}$ （ $180°$ 回転）：対面のビーズが同色のもの → $∣ Fix (r^{2}) ∣ = 3^{2} = 9$
$r^{3}$ （ $270°$ 回転）： $r^{1}$ と同様 → $∣ Fix (r^{3}) ∣ = 3$

バーンサイドの補題より，

∣ X / G ∣ = \frac{1}{4} (81 + 3 + 9 + 3) = \frac{96}{4} = 24

5 ポリアの数え上げ定理

バーンサイドの補題を精密化したのがポリアの数え上げ定理です．

定義 9 (巡回指標).

群

G

が

{1, 2, \dots, n}

に作用するとき，各

g \in G

の置換をサイクル分解して，長さ

k

のサイクルの個数を

c_{k} (g)

とします．

G

の巡回指標は

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

です．

定理 10 (ポリアの数え上げ定理).

m

色で塗り分けるとき，区別される着色の数は

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

です．さらに各色の使用回数を追跡したいときは，

s_{k}

に適切な変数を代入します．

例 11 (回転対称なビーズの塗り分け).

4ビーズの回転群

Z /4 Z

の巡回指標は

Z (Z /4 Z) = \frac{1}{4} (s_{1}^{4} + s_{4} + s_{2}^{2} + s_{4})

s_{k} = m

（

m

色）とおくと

\frac{1}{4} (m^{4} + 2 m + m^{2})

です．

m = 3

で

\frac{1}{4} (81 + 6 + 9) = 24

と一致します．

6 まとめ

対称性のある数え上げでは，群作用の軌道の数を求めます
バーンサイドの補題： $∣ X / G ∣ = \frac{1}{∣ G ∣} \sum_{g} ∣ Fix (g) ∣$ （固定点数の平均）
ポリアの数え上げ定理は巡回指標を使ったバーンサイドの精密化です
ネックレスの塗り分けなど，回転・鏡映対称性がある問題に威力を発揮します

最後の記事では，組合せ論と DP（動的計画法）の深い関係を探り，シリーズ全体を振り返ります．

組合せ論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

対称性で数え上げを楽にする ― バーンサイドの補題とポリアの数え上げ定理

1 問題の設定 ― なぜ素朴に数えられないのか

2 群作用と軌道 ― 対称性の数学的表現

3 バーンサイドの補題

4 ネックレス問題の解法

5 ポリアの数え上げ定理

6 まとめ

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

Folio公式の他の記事

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

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

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

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