第7章数え上げ — バーンサイドの補題

「回して同じものは1つと数える」を計算する

$4$ つのビーズを赤か青で塗って首飾りを作ります。塗り方は $2^4=16$ 通り。でも首飾りは回せるので、回して重なるものは「同じ」と数えたい。すると本当に異なる首飾りは何通り？——素朴に $16$ を回転の数 $4$ で割って $4$ 通り、とやると間違いです。回転で不変な塗り方（全部同色など）が二重に消えるからです。

正しく数える鍵は、前章の群作用。「回転を除いて異なる首飾り」＝「回転群の作用による軌道の個数」です。軌道の個数を、各群元が固定する点の数の平均として計算するのがバーンサイドの補題。組合せ論・化学（分子の異性体）・デザインの数え上げで絶大な威力を発揮する、群作用の最も実用的な定理です。

「対称性を除いた場合の数」＝軌道の個数。それは各元が固定する点の数の平均（バーンサイドの補題）で数える。

バーンサイドの補題

定義不動点集合

$g\in G$ が集合 $X$ に作用するとき、 $\mathrm{Fix}(g)=\{x\in X:g\cdot x=x\}$ を $g$ の不動点集合という。

定理バーンサイドの補題（軌道数の公式）

有限群 $G$ が有限集合 $X$ に作用するとき、軌道の個数を $|X/G|$ とすると $|X/G|=\frac{1}{|G|}\sum_{g\in G}|\mathrm{Fix}(g)|.$ すなわち軌道の個数＝各元の不動点数の平均。

証明

「固定するペア」の集合 $P=\{(g,x)\in G\times X:g\cdot x=x\}$ を2通りに数える。 $g$ ごとに数えると $|P|=\sum_{g\in G}|\mathrm{Fix}(g)|$ 。 $x$ ごとに数えると $|P|=\sum_{x\in X}|\mathrm{Stab}(x)|$ 。よって $\sum_{g\in G}|\mathrm{Fix}(g)|=\sum_{x\in X}|\mathrm{Stab}(x)|.$ 軌道–安定化群定理（前章）より $|\mathrm{Stab}(x)|=|G|/|\mathrm{Orb}(x)|$ 。同じ軌道 $O$ に属す $x$ では $|\mathrm{Orb}(x)|=|O|$ が共通なので、 $\sum_{x\in O}|\mathrm{Stab}(x)|=|O|\cdot\frac{|G|}{|O|}=|G|$ 。軌道は $X$ を分割するから、軌道ごとに足すと $\sum_{x\in X}|\mathrm{Stab}(x)|=\sum_{\text{軌道}\,O}|G|=|G|\cdot(\text{軌道の個数}).$ 以上を合わせて $\sum_{g}|\mathrm{Fix}(g)|=|G|\cdot|X/G|$ 。両辺を $|G|$ で割る。∎

証明の技法は**「ペアを2通りに数える」**（二重数え上げ）と、前章の軌道–安定化群定理。各軌道からの安定化群の寄与がちょうど $|G|$ にまとまる、というのが核心です。これで冒頭の首飾りを正しく数えられます。

応用：首飾りと彩色

例 4ビーズ2色の首飾り（回転のみ）

$X=\{$ 4ビーズの2色塗り $\}$ 、 $|X|=16$ 。巡回群 $\mathbb Z_4=\{e,r,r^2,r^3\}$ （ $90^\circ$ 回転）が作用する。各元の不動点（回しても変わらない塗り方）を数える：

$e$ ：全部固定、 $|\mathrm{Fix}(e)|=16$ 。
$r$ （1つ分回転）：4つのビーズが同色でないと不変にならない、 $|\mathrm{Fix}(r)|=2$ 。
$r^2$ （半回転）：向かい合うビーズが同色、 $2^2=4$ 。
$r^3$ ： $r$ と同様、 $2$ 。

軌道数 $=\dfrac{1}{4}(16+2+4+2)=\dfrac{24}{4}=6$ 。回転を除いて $6$ 種類の首飾り。素朴な $16/4=4$ は誤り。

例立方体の面を n 色で塗る

立方体の6面を $n$ 色で塗る。回転対称は $24$ 通り（回転群 $\cong S_4$ ）。各回転の不動点数を回転軸の型ごとに数え、バーンサイドで平均すると、異なる塗り方は $\dfrac{1}{24}(n^6+6n^3+3n^4+8n^2+6n^3)=\dfrac{n^6+3n^4+12n^3+8n^2}{24}$ 。 $n=2$ なら $10$ 通り。手作業では絶望的な数え上げが、群作用で機械的に解ける。

「割り算では過小に数えてしまう」問題を、群作用が正確に補正する。化学の異性体の数え上げ（ポリア理論の基礎）や、盤面の対称性を除いた配置の数え上げなど、応用は無数にあります。

共役類の数え上げ（応用）

バーンサイドは共役作用にも使えます。共役作用の軌道は共役類（前章）でした。

命題共役類の個数

有限群 $G$ の共役類の個数 $k$ は、 $G$ の共役作用にバーンサイドを適用して $k=\frac{1}{|G|}\sum_{g\in G}|C_G(g)|.$ （ $g$ の共役作用による不動点は $g$ と可換な元＝中心化群 $C_G(g)$ 。）

共役類の個数は、表現論で「既約表現の個数」に一致するという著しい事実（第7章的な話）につながる基本量です。バーンサイドの補題は、群自身の構造を数えるのにも使えるのです。

注意ポリアの数え上げ定理（発展）

バーンサイドを精密化し、色ごとの個数まで追跡できるようにしたのがポリアの数え上げ定理。各群元の巡回置換の型（サイクル指数）を使い、「赤 $2$ 個・青 $2$ 個の首飾り」のような細かい数え上げを母関数で一括に行う。化学構造の列挙やグラフの数え上げの基礎理論。

つまずきポイント

注意よくある誤解

「全体を群の位数で割る」は誤り。 $|X|/|G|$ ではない。対称で不変な点を過小評価する。正しくは不動点数の平均（バーンサイド）。
不動点は「その元で動かない配置」。 $\mathrm{Fix}(g)$ は $X$ の中で $g$ に固定される要素。恒等元 $e$ の不動点は $X$ 全体。
回転だけか、鏡映も含めるかで答えが変わる。 「裏返しも同じ」とするなら二面体群 $D_n$ 、回転のみなら $\mathbb Z_n$ で作用させる。問題設定で群を選ぶ。

この章のまとめ

「対称性を除いた場合の数」＝軌道の個数。バーンサイドの補題 $|X/G|=\frac1{|G|}\sum_g|\mathrm{Fix}(g)|$ で、各元の不動点数の平均として数える。
証明はペアの二重数え上げ＋軌道–安定化群定理。素朴な $|X|/|G|$ は対称な点を数え損なう。
首飾り・立方体の彩色など実用的数え上げに直結。共役作用に使えば共役類の個数（表現論とつながる）も数えられる。ポリア理論へ発展。

群作用の道具が揃いました。次章は有限群論の頂点——シローの定理を、群作用の力で証明します。

第7章 数え上げ — バーンサイドの補題