対称性で数え上げを楽にする ― バーンサイドの補題とポリアの数え上げ定理
回転や鏡映で同じものを区別しない数え上げ（ネックレスの塗り分けなど）を，群作用の言葉で統一的に扱います．「軌道の数＝固定点数の平均」というバーンサイドの補題の本質を解説します．
「3色のビーズで4個のネックレスを作ると何通り？」― こういう問題で難しいのは，回転して同じになるものを同一視しなければならないことです．対称性があると素朴な数え上げではうまくいきません．バーンサイドの補題は，対称性の下での数え上げを「固定点数の平均」という美しい公式に帰着させます．
1 問題の設定 ― なぜ素朴に数えられないのか
例 1 (ネックレスの塗り分け).
4つのビーズからなるネックレスを3色で塗り分ける方法は何通りでしょうか？ 回転して同じになるものは同一とみなします．回転を無視すれば 通りですが，4つの回転（）で移り合うものを同一視する必要があります．
注意 2.
素朴に81通りを4で割ると で整数になりません．これは「すべての着色が同じ個数の軌道に属する」わけではないからです．例えば「全色同じ」の着色は回転しても変わらない（軌道のサイズが1）のに対し，4色バラバラの着色は回転で4つの異なる着色を生みます（軌道のサイズが4）．
2 群作用と軌道 ― 対称性の数学的表現
定義 3 (群作用).
群 が集合 に作用するとは，各 に対して写像 が定まり，
（単位元は恒等写像）
（結合的）
定義 4 (軌道).
の軌道（orbit）とは です．「 の作用で から到達できるすべての要素」の集合です．
注意 5.
ネックレスの例では，（回転群）， は 通りの着色の集合です．「回転して同じ」着色は同じ軌道に属します．求めたいのは軌道の個数です．
3 バーンサイドの補題
定義 6 (固定点集合).
に対して， の固定点集合は です．
定理 7 (バーンサイドの補題).
有限群 が有限集合 に作用するとき，軌道の個数 は
つまり，固定点数の平均に等しくなります．
証明.
集合 の要素数を2通りに数えます． を固定して を動かすと です． を固定して を動かすと， を満たす の集合は の安定化群 です．軌道・安定化群定理（）より です．したがって
各軌道 に対して なので， です．2つの表現を等しくおいて割れば定理が得られます． □
4 ネックレス問題の解法
4ビーズ3色のネックレスの問題に戻りましょう．（は回転）です．
例 8.
各群元の固定点数を数えます：
（恒等変換）：すべての着色を固定 →
（ 回転）：4ビーズがすべて同色のもののみ固定 →
（ 回転）：対面のビーズが同色のもの →
（ 回転）： と同様 →
5 ポリアの数え上げ定理
バーンサイドの補題を精密化したのがポリアの数え上げ定理です．
定義 9 (巡回指標).
群 が に作用するとき，各 の置換をサイクル分解して，長さ のサイクルの個数を とします． の巡回指標は
です．
定理 10 (ポリアの数え上げ定理).
色で塗り分けるとき，区別される着色の数は です．さらに各色の使用回数を追跡したいときは， に適切な変数を代入します．
例 11 (回転対称なビーズの塗り分け).
4ビーズの回転群 の巡回指標は
（ 色）とおくと です． で と一致します．
6 まとめ
対称性のある数え上げでは，群作用の軌道の数を求めます
バーンサイドの補題：（固定点数の平均）
ポリアの数え上げ定理は巡回指標を使ったバーンサイドの精密化です
ネックレスの塗り分けなど，回転・鏡映対称性がある問題に威力を発揮します
最後の記事では，組合せ論と DP（動的計画法）の深い関係を探り，シリーズ全体を振り返ります．