1 基本概念

バーンサイドの補題は、対称性をもつ対象を重複なく数えるための基礎的な道具である。群の作用によって互いに移り合う配置は、組合せ論では同じ型として扱われるため、単純な総数ではなく「本質的に異なる個数」を求める必要がある。この補題は、その考え方を固定点の平均という形で定式化する。

1.1 群の作用

群の作用とは、群の各要素が集合の元に対して、整合的な変換を与えることである。たとえば、正多角形の回転や反転、文字列の位置の入れ替えなどが典型例である。作用は、2つの変換を続けて行う操作が群の積に対応するように定義される。

1.2 軌道と固定点

ある対象に群の要素を順に適用すると、到達可能な対象の集まりができる。これを軌道という。逆に、ある群要素を適用しても変化しない対象は固定点と呼ばれる。固定点の個数は、対称操作ごとの「変化しない配置」の数を表す。

1.3 同値類の数え上げ

群作用によって互いに変換できる対象は、同値類としてまとめられる。数え上げの目的は、元の対象集合の大きさではなく、この同値類の数を求めることにある。バーンサイドの補題は、その同値類の個数を固定点の情報から直接算出できるようにする。

2 補題の主張

バーンサイドの補題は、有限群が有限集合に作用するとき、異なる軌道の数が群要素ごとの固定点数の平均に等しいと述べる。見かけ上は変換の種類ごとに別々の情報を集めるが、最終的には軌道数という単一の量に集約される。

2.1 バーンサイドの補題の公式

有限群 G が集合 X に作用するとき、軌道の数は

X/G= (1/G) Σ(g∈G)Fix(g)
で与えられる。ここでFix(g)は、群要素 g によって不変な X の元の個数である。右辺は各対称操作の固定点数を平均したもので、左辺は同値類の総数を表す。

2.2 証明の考え方

証明は、固定点の総和を二通りに数える発想に基づく。ひとつは群要素ごとに固定される対象を足し合わせる方法であり、もうひとつは対象ごとに、それを固定する群要素を数える方法である。両者を比較すると、軌道の個数が現れる。

2.2.1 固定点の総和

各群要素 g について固定点の数Fix(g)を求め、それを群全体で加える。すると、ある対象 x が何回数えられるかは、x を固定する群要素の個数に一致する。この見方では、対称性の強い対象ほど、総和に多く寄与する。

2.2.2 軌道ごとの寄与

一方、同じ軌道に属する対象は、固定される群要素の数が等しい。したがって、各軌道の中では寄与が均一に分配される。これにより、総和を軌道単位に整理すると、各軌道がちょうど群の大きさに対応する量を与えることが分かる。

2.3 直感的な解釈

この補題は、対称操作が多いほど重複が大きくなることを、平均化によって補正する仕組みと考えられる。単純な総数は見かけの違いを含むが、固定点を平均すると、実質的に異なる形だけが残る。数え上げにおける「重複の除去」を、非常に短い式で表現した結果といえる。

3 関連する理論

バーンサイドの補題は、群論の基本結果と密接に結びついている。特に、軌道と安定化部分群の関係、平均値を用いる視点、そしてより広い一般化の流れの中で理解されることが多い。

3.1 軌道・安定化部分群定理

軌道・安定化部分群定理は、ある対象の軌道の大きさが、その対象を固定する部分群の大きさと群の大きさから決まることを述べる。これは、個々の対象の対称性と、全体の分布を結びつける基本原理である。バーンサイドの補題は、この構造を軌道全体の個数へと拡張したものとみなせる。

3.2 平均化の原理

補題の核心には、対称操作に関する平均化がある。各変換で固定される対象数を均等に扱うことで、局所的な情報から全体の個数を導く。平均化の考えは、確率的な直観にも近いが、ここでは厳密な組合せ論の式として機能する。

3.3 プルーフの一般化

証明の枠組みは、有限群に限らず、他の代数的構造や重み付きの数え上げにも応用されることがある。例えば、固定点に重みを付けた和や、対称性を持つ生成関数の解析へ発展する。こうした一般化は、列挙問題の幅を大きく広げる。

4 応用

バーンサイドの補題は、対称性を伴う数え上げ問題で広く使われる。特に、色分けや配置、並べ替えに関する問題では、見た目の違いと本質的な違いを区別するための標準的手段となっている。

4.1 色塗り問題

色塗り問題では、図形の各部分に色を割り当てる。ただし、回転や反転で一致する塗り方は同一視されるため、単純な積の数え方は適切でない。バーンサイドの補題を用いると、対称群の各操作が保つ塗り方を集計して、異なる彩色パターン数を求められる。

4.1.1 円環や正多角形の色分け

円環状のビーズや正多角形の頂点は、回転対称を持つ代表的な対象である。各回転が固定する彩色の数を調べることで、回転同値な配色の個数が分かる。輪状配置は、補題の典型例としてしばしば取り上げられる。

4.1.2 回転対称・反転対称を含む場合

反転を含む場合、対称群の構造はより複雑になるが、手順自体は変わらない。回転だけでなく鏡映が固定する配色も数えることで、より粗い同値関係に基づく分類が可能になる。これにより、左右反転を区別しない数え上げが行える。

4.2 組合せ的列挙

対象が文字列や有限列であっても、位置の入れ替えを対称性として扱うことができる。すると、同じ要素の並び替えに相当するものをまとめ、代表的な列だけを数える問題へ変わる。バーンサイドの補題は、この種の列挙を簡潔に処理する。

4.2.1 符号列の同値類

符号列では、一定の変換を施しても意味が変わらない場合がある。たとえば、反転や循環移動を同一視すると、同じ構造をもつ列が一群にまとまる。固定される変換を調べることで、等価な列の種類数を求められる。

4.2.2 配置問題への応用

マス目、席順、装飾パターンのような配置問題でも、対称性は重複の原因になる。群作用として配置変換を考えると、異なる見かけの案を一つの軌道にまとめられる。これにより、探索や分類の際の無駄が減る。

4.3 化学・図形・パズルへの応用

分子構造の簡略モデル、幾何学図形の彩色、パズルの状態分類などでも、対称性に基づく同一視が重要である。バーンサイドの補題は、こうした場面で状態空間の大きさを整理する助けになる。特に、複数の対称操作を持つ系では、手計算の負担を大きく軽減する。

5 代表的な例

具体例は、この補題の働きを理解するうえで有効である。小さな集合で計算すると、固定点の平均が軌道数に一致することが確認しやすい。

5.1 さいころやビーズの配置

さいころの面やビーズの並びは、回転によって同じ配置とみなされることがある。各回転がどれだけの配置を保つかを数えると、同値な並びの種類が分かる。実際の計算では、対称操作ごとに固定される条件が異なるため、場合分けが必要になる。

5.2 正方形の頂点の色塗り

正方形の4頂点を複数の色で塗る問題は、最も有名な例の一つである。回転と反転を含む対称群が作用すると、見かけ上は多数の彩色が存在するが、補題を使えば本当に異なる塗り方の数が求められる。各対称操作の固定点数を整理すると、結果が明快になる。

5.3 文字列の対称性を考慮した数え上げ

文字列では、反転対称や循環同値を導入することで、同じ型の列をまとめて扱える。たとえば、左右を入れ替えても同じとみなす場合、鏡像で一致する列だけが固定点になる。こうした数え上げは、記号列の分類やパターン認識にも通じる。

6 発展的話題

バーンサイドの補題は、単独で完結する結果である一方、より広い理論への入口でもある。生成関数、対称群、代数的構造の研究と接続することで、数え上げの体系が豊かになる。

6.1 ポリヤの数え上げ定理との関係

ポリヤの数え上げ定理は、バーンサイドの補題を発展させたもので、色の種類ごとの情報をより精密に扱う。単に固定点数を数えるだけでなく、色の分布を反映した生成式を用いる点に特徴がある。彩色問題を体系的に解く際の標準理論として重要である。

6.2 作用群が有限でない場合の注意

群が無限である場合、単純な平均は定義しにくく、補題をそのまま適用できないことがある。集合が有限でも、作用群が無限だと固定点の総和や軌道数の扱いに注意が必要になる。一般には、追加の条件や別の枠組みが求められる。

6.3 代数的組合せ論における位置づけ

この補題は、代数的組合せ論において、群作用と列挙を結ぶ基本命題として位置づけられる。対称性の解析、軌道分解、生成関数の導入など、多くの手法の出発点になる。初等的でありながら応用範囲が広い点に、理論上の価値がある。