バーンサイドの補題 （英 : Burnside's lemma ）、あるいはバーンサイドの数え上げ補題 、コーシー・フロベニウスの補題 、軌道の数え上げ補題 とは、対称性 を考慮して数学的な対象を数え上げるときに有用な群論 の結果である。
以下では G は有限群 で集合 X に作用 しているとする。群 G の各元 g に対して Xg で元 g によって固定 されるすべての X の元からなる集合を表す。バーンサイドの補題は軌道 の数 |X /G
|
X
/
G
|
=
1
|
G
|
∑ ∑ -->
g
∈ ∈ -->
G
|
X
g
|
{\displaystyle \vert X/G\vert ={\frac {1}{\vert G\vert }}\sum _{g\in G}\vert X^{g}\vert }
つまり軌道の数（これは自然数 あるいは+∞ ）は群 G の元による固定点の数の平均 （これも自然数あるいは+∞）と等しい。もし G が無限群ならば |G | による除法は定義されないが、その場合には次の基数 に関する主張が成り立つ。
|
G
|
⋅ ⋅ -->
|
X
/
G
|
=
∑ ∑ -->
g
∈ ∈ -->
G
|
X
g
|
{\displaystyle \vert G\vert \cdot \vert X/G\vert =\sum _{g\in G}\vert X^{g}\vert }
以下ではこの補題を使って立方体 の面を3色で塗り分ける数を決定する。ただし回転させて一致するものは同一視する。
X をある特定の向きの立方体の面を塗り分ける36 通りの彩色からなる集合とし、立方体の回転群 G (≅ S 4 X に作用しているとする。このとき集合 X の2元が同じ軌道に属するのは一方がもう一方の回転であるとき、かつそのときに限る。したがって塗り分ける数は軌道の数と一致し、それは群 G の24元がそれぞれ固定する集合の大きさを数えることで計算できる。
彩色された立方体 単位元 36 個の元すべてを固定する
面の90度回転（6つ）
33 個の元（回転軸の通る2面と側面の彩色分）を固定する
面の180度回転（3つ）
34 個の元（回転軸の通る2面と側面の2対面の彩色分）を固定する
頂点の120度回転（8つ）
32 個の元（回転軸に対して上下の彩色分）を固定する
辺の180度回転（6つ）
33 個の元（回転軸の通る辺に接する面の2組と側面の彩色分）を固定する よって各元が固定する集合の大きさの平均は次の通り。
1
24
(
3
6
+
6
⋅ ⋅ -->
3
3
+
3
⋅ ⋅ -->
3
4
+
8
⋅ ⋅ -->
3
2
+
6
⋅ ⋅ -->
3
3
)
=
57
{\displaystyle {\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57}
したがって立方体の面を3色で塗り分ける方法は57通りある。一般に立方体の面を n 色で塗り分ける方法は次の通り。
1
24
(
n
6
+
3
n
4
+
12
n
3
+
8
n
2
)
{\displaystyle {\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right)}
証明の第一歩は群 G の元 g に関する和を集合 X の元 x に関する和に書き直すことである（二重数え上げ）。
∑ ∑ -->
g
∈ ∈ -->
G
|
X
g
|
=
|
{
(
g
,
x
)
∈ ∈ -->
G
× × -->
X
∣ ∣ -->
g
x
=
x
}
|
=
∑ ∑ -->
x
∈ ∈ -->
X
|
G
x
|
{\displaystyle \sum _{g\in G}\vert X^{g}\vert =\vert \{\,(g,x)\in G\times X\mid gx=x\,\}\vert =\sum _{x\in X}\vert G_{x}\vert }
（ここで Xg = { x ∈ X | gx = x G の元 g で固定される X のすべての元からなる集合で Gx = { g ∈ G | gx = x X の元 x を固定する G のすべての元からなる固定群 である。）
軌道・固定群定理 により集合 X の各元 x の軌道 Gx = { gx ∈ X | g ∈ G Gx による左剰余類 G /Gx 全単射 がある。ラグランジュの定理 と合わせると次を得る。
|
G
x
|
=
[
G
:
G
x
]
=
|
G
|
/
|
G
x
|
{\displaystyle \vert Gx\vert =[G:G_{x}]=\vert G\vert /\vert G_{x}\vert }
したがって最初の等式の右辺にある集合 X の元に関する和を次のように書き換えることができる。
∑ ∑ -->
x
∈ ∈ -->
X
|
G
x
|
=
∑ ∑ -->
x
∈ ∈ -->
X
|
G
|
|
G
x
|
=
|
G
|
∑ ∑ -->
x
∈ ∈ -->
X
1
|
G
x
|
{\displaystyle \sum _{x\in X}\vert G_{x}\vert =\sum _{x\in X}{\frac {\vert G\vert }{\vert Gx\vert }}=\vert G\vert \sum _{x\in X}{\frac {1}{\vert Gx\vert }}}
最後に集合 X は軌道の直和 であることに注意すれば直前の X に関する和は各軌道に関する和へ分解できる。
∑ ∑ -->
x
∈ ∈ -->
X
1
|
G
x
|
=
∑ ∑ -->
A
∈ ∈ -->
X
/
G
∑ ∑ -->
x
∈ ∈ -->
A
1
|
A
|
=
∑ ∑ -->
A
∈ ∈ -->
X
/
G
1
=
|
X
/
G
|
{\displaystyle \sum _{x\in X}{\frac {1}{\vert Gx\vert }}=\sum _{A\in X/G}\sum _{x\in A}{\frac {1}{\vert A\vert }}=\sum _{A\in X/G}1=\vert X/G\vert }
すべてをまとめれば目的の結果を得る。
∑ ∑ -->
g
∈ ∈ -->
G
|
X
g
|
=
|
G
|
⋅ ⋅ -->
|
X
/
G
|
{\displaystyle \sum _{g\in G}\vert X^{g}\vert =\vert G\vert \cdot \vert X/G\vert }
ウィリアム・バーンサイド は『有限群論』（1897年）でFrobenius (1887) に拠るものとしてこの補題を述べ、証明した。しかしフロベニウス以前にもこの式はコーシー によって1845年には知られていた。実際にはこの補題はよく知られていたのでバーンサイドが単にコーシーへ帰するのを省いたようである。結果としてこの補題はしばしばバーンサイドのでない補題 とも呼ばれる。バーンサイドはこの分野において多くの貢献をしているのでこれは一見感じられるほど曖昧ではない。
Burnside, William (1897), Theory of Groups of Finite Order Cambridge University Press Project Gutenberg and here at Archive.org . （これは第一版である。第二版の序文ではバーンサイドの有名な表現論 の有用性に関する方針転換が述べられている。）Frobenius, Ferdinand Georg (1887), “Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul”, Crelle CI : 288, doi :10.1515/crll.1887.101.273 Neumann, Peter M. (1979), “A lemma that is not Burnside's”, The Mathematical Scientist 4 (2): 133–141, ISSN 0312-3685 , MR 562002 , Zbl 0409.20001 Rotman, Joseph (1995), An introduction to the theory of groups , Springer-Verlag, ISBN 0-387-94285-8
![{\displaystyle \vert Gx\vert =[G:G_{x}]=\vert G\vert /\vert G_{x}\vert }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dee7ee463f74e6eb941c7a54684875a0a237969)
