バーンサイドの補題

バーンサイドの補題（テンプレート:Lang-en-short）、あるいはバーンサイドの数え上げ補題、コーシー・フロベニウスの補題、軌道の数え上げ補題とは、対称性を考慮して数学的な対象を数え上げるときに有用な群論の結果である。

以下では テンプレート:Mvar は有限群で集合 テンプレート:Mvar に作用しているとする。群 テンプレート:Mvar の各元 テンプレート:Mvar に対して テンプレート:Mvar で元 テンプレート:Mvar によって固定されるすべての テンプレート:Mvar の元からなる集合を表す。バーンサイドの補題は軌道の数 |テンプレート:Math| は次の式で表せることを主張しているテンプレート:Sfn。

$|X/G|=\frac{1}{|G|}\sum _{g\in G}|X^g|$

つまり軌道の数（これは自然数あるいは+∞）は群 テンプレート:Mvar の元による固定点の数の平均（これも自然数あるいは+∞）と等しい。もし テンプレート:Mvar が無限群ならば |テンプレート:Mvar| による除法は定義されないが、その場合には次の基数に関する主張が成り立つ。

$|G|\cdot |X/G|=\sum _{g\in G}|X^g|$

例と応用

以下ではこの補題を使って立方体の面を3色で塗り分ける数を決定する。ただし回転させて一致するものは同一視する。

テンプレート:Mvar をある特定の向きの立方体の面を塗り分ける3⁶通りの彩色からなる集合とし、立方体の回転群 テンプレート:Math は自然に テンプレート:Mvar に作用しているとする。このとき集合 テンプレート:Mvar の2元が同じ軌道に属するのは一方がもう一方の回転であるとき、かつそのときに限る。したがって塗り分ける数は軌道の数と一致し、それは群 テンプレート:Mvar の24元がそれぞれ固定する集合の大きさを数えることで計算できる。

彩色された立方体

単位元

3⁶個の元すべてを固定する

面の90度回転（6つ）

3³個の元（回転軸の通る2面と側面の彩色分）を固定する

面の180度回転（3つ）

3⁴個の元（回転軸の通る2面と側面の2対面の彩色分）を固定する

頂点の120度回転（8つ）

3²個の元（回転軸に対して上下の彩色分）を固定する

辺の180度回転（6つ）

3³個の元（回転軸の通る辺に接する面の2組と側面の彩色分）を固定する

よって各元が固定する集合の大きさの平均は次の通り。

$\frac{1}{24}(3^6+6\cdot 3^3+3\cdot 3^4+8\cdot 3^2+6\cdot 3^3)=57$

したがって立方体の面を3色で塗り分ける方法は57通りある。一般に立方体の面を テンプレート:Mvar 色で塗り分ける方法は次の通り。

$\frac{1}{24}(n^6+3n^4+12n^3+8n^2)$

証明

証明の第一歩は群 テンプレート:Mvar の元 テンプレート:Mvar に関する和を集合 テンプレート:Mvar の元 テンプレート:Mvar に関する和に書き直すことである（二重数え上げ）。

$\sum _{g\in G}|X^g|=|\{(g,x)\in G\times X\mid gx=x\}|=\sum _{x\in X}|G_x|$

（ここで テンプレート:Mvar = { テンプレート:Math } は群 テンプレート:Mvar の元 テンプレート:Mvar で固定される テンプレート:Mvar のすべての元からなる集合で テンプレート:Mvar = { テンプレート:Math } は集合 テンプレート:Mvar の元 テンプレート:Mvar を固定する テンプレート:Mvar のすべての元からなる固定群である。）

軌道・固定群定理により集合 テンプレート:Mvar の各元 テンプレート:Mvar の軌道 テンプレート:Mvar = { テンプレート:Math } と固定群 テンプレート:Mvar による左剰余類 テンプレート:Math の間には自然な全単射がある。ラグランジュの定理と合わせると次を得る。

$|Gx|=[G:G_x]=|G|/|G_x|$

したがって最初の等式の右辺にある集合 テンプレート:Mvar の元に関する和を次のように書き換えることができる。

$\sum _{x\in X}|G_x|=\sum _{x\in X}\frac{|G|}{|Gx|}=|G|\sum _{x\in X}\frac{1}{|Gx|}$

最後に集合 テンプレート:Mvar は軌道の直和であることに注意すれば直前の テンプレート:Mvar に関する和は各軌道に関する和へ分解できる。

$\sum _{x\in X}\frac{1}{|Gx|}=\sum _{A\in X/G}\sum _{x\in A}\frac{1}{|A|}=\sum _{A\in X/G}1=|X/G|$

すべてをまとめれば目的の結果を得る。

$\sum _{g\in G}|X^g|=|G|\cdot |X/G|$

歴史

ウィリアム・バーンサイドは『有限群論』（1897年）テンプレート:Sfnでテンプレート:Harvtxtに拠るものとしてこの補題を述べ、証明した。しかしフロベニウス以前にもこの式はコーシーによって1845年には知られていた。実際にはこの補題はよく知られていたのでバーンサイドが単にコーシーへ帰するのを省いたようである。結果としてこの補題はしばしばバーンサイドのでない補題とも呼ばれるテンプレート:Sfn。バーンサイドはこの分野において多くの貢献をしているのでこれは一見感じられるほど曖昧ではない。

参考文献

• テンプレート:Citation, at Project Gutenberg and here at Archive.org. （これは第一版である。第二版の序文ではバーンサイドの有名な表現論の有用性に関する方針転換が述べられている。）
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.

関連項目

• ポーヤの計数定理

外部リンク

• テンプレート:MathWorld
• テンプレート:SpringerEOM