バーンサイドの補題のソースを表示

'''バーンサイドの補題'''（{{lang-en-short|Burnside's lemma}}）、あるいは'''バーンサイドの数え上げ補題'''、'''コーシー・フロベニウスの補題'''、'''軌道の数え上げ補題'''とは、[[対称性]]を考慮して数学的な対象を数え上げるときに有用な[[群論]]の結果である。

以下では {{mvar|G}} は[[有限群]]で[[集合]] {{mvar|X}} に[[群作用|作用]]しているとする。群 {{mvar|G}} の各元 {{mvar|g}} に対して {{mvar|X<sup>g</sup>}} で元 {{mvar|g}} によって[[固定点|固定]]されるすべての {{mvar|X}} の元からなる集合を表す。バーンサイドの補題は[[群作用#軌道と等方部分群|軌道]]の数 |{{math|''X''/''G''}}| は次の式で表せることを主張している{{sfn|Rotman|1995|loc=Chapter 3}}。
:<math>\vert X/G \vert = \frac{1}{\vert G\vert}\sum_{g \in G}\vert X^g\vert</math>
つまり軌道の数（これは[[自然数]]あるいは[[拡大実数|+&infin;]]）は群 {{mvar|G}} の元による固定点の数の[[算術平均|平均]]（これも自然数あるいは+&infin;）と等しい。もし {{mvar|G}} が無限群ならば |{{mvar|G}}| による除法は定義されないが、その場合には次の[[基数]]に関する主張が成り立つ。
:<math>\vert G\vert \cdot \vert X/G\vert = \sum_{g \in G}\vert X^g\vert</math>

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

{{mvar|X}} をある特定の向きの立方体の面を塗り分ける3<sup>6</sup>通りの彩色からなる集合とし、立方体の回転群 {{math|''G'' (&cong; [[対称群|''S''<sub>4</sub>]])}} は自然に {{mvar|X}} に作用しているとする。このとき集合 {{mvar|X}} の2元が同じ軌道に属するのは一方がもう一方の回転であるとき、かつそのときに限る。したがって塗り分ける数は軌道の数と一致し、それは群 {{mvar|G}} の24元がそれぞれ固定する集合の大きさを数えることで計算できる。

[[Image:Face colored cube.png|thumb|彩色された立方体]]
; [[単位元]]
: 3<sup>6</sup>個の元すべてを固定する
; 面の90度回転（6つ）
: 3<sup>3</sup>個の元（回転軸の通る2面と側面の彩色分）を固定する
; 面の180度回転（3つ）
: 3<sup>4</sup>個の元（回転軸の通る2面と側面の2対面の彩色分）を固定する
; 頂点の120度回転（8つ）
: 3<sup>2</sup>個の元（回転軸に対して上下の彩色分）を固定する
; 辺の180度回転（6つ）
: 3<sup>3</sup>個の元（回転軸の通る辺に接する面の2組と側面の彩色分）を固定する

よって各元が固定する集合の大きさの平均は次の通り。
: <math> \frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57</math>
したがって立方体の面を3色で塗り分ける方法は57通りある。一般に立方体の面を {{mvar|n}} 色で塗り分ける方法は次の通り。
: <math> \frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right)</math>

== 証明 ==
証明の第一歩は群 {{mvar|G}} の元 {{mvar|g}} に関する和を集合 {{mvar|X}} の元 {{mvar|x}} に関する和に書き直すことである（二重数え上げ）。
:<math>\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</math>
（ここで {{mvar|X<sup>g</sup>}} = { {{math|''x'' &isin; ''X'' {{!}} ''gx'' {{=}} ''x''}} } は群 {{mvar|G}} の元 {{mvar|g}} で固定される {{mvar|X}} のすべての元からなる集合で {{mvar|G<sub>x</sub>}} = { {{math|''g'' &isin; ''G'' {{!}} ''gx'' {{=}} ''x''}} } は集合 {{mvar|X}} の元 {{mvar|x}} を固定する {{mvar|G}} のすべての元からなる[[群作用#軌道と等方部分群|固定群]]である。）

[[群作用#軌道と等方部分群|軌道・固定群定理]]により集合 {{mvar|X}} の各元 {{mvar|x}} の軌道 {{mvar|Gx}} = { {{math|''gx'' &isin; ''X'' {{!}} ''g'' &isin; ''G''}} } と固定群 {{mvar|G<sub>x</sub>}} による左[[剰余類]] {{math|''G''/''G<sub>x</sub>''}} の間には自然な[[全単射]]がある。[[ラグランジュの定理 (群論)|ラグランジュの定理]]と合わせると次を得る。
:<math>\vert Gx \vert = [G:G_x] = \vert G \vert / \vert G_x \vert</math>
したがって最初の等式の右辺にある集合 {{mvar|X}} の元に関する和を次のように書き換えることができる。
:<math>\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}</math>

最後に集合 {{mvar|X}} は軌道の[[直和#集合論的直和|直和]]であることに注意すれば直前の {{mvar|X}} に関する和は各軌道に関する和へ分解できる。
:<math>\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</math>
すべてをまとめれば目的の結果を得る。
:<math>\sum_{g \in G}\vert X^g\vert = \vert G\vert \cdot \vert X/G\vert</math>

== 歴史 ==
[[ウィリアム・バーンサイド]]は『有限群論』（1897年）{{sfn|Burnside|1897}}で{{harvtxt|Frobenius|1887}}に拠るものとしてこの補題を述べ、証明した。しかしフロベニウス以前にもこの式は[[オーギュスタン＝ルイ・コーシー|コーシー]]によって1845年には知られていた。実際にはこの補題はよく知られていたのでバーンサイドが単にコーシーへ帰するのを省いたようである。結果としてこの補題はしばしば'''バーンサイドのでない補題'''とも呼ばれる{{sfn|Neumann|1979}}。バーンサイドはこの分野において多くの貢献をしているのでこれは一見感じられるほど曖昧ではない。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* {{citation | last=Burnside | first=William | year = 1897 | title = [http://www.gutenberg.org/ebooks/40395 Theory of Groups of Finite Order] | publisher = [[Cambridge University Press]]}}, at [[Project Gutenberg]] and [https://archive.org/details/theorygroupsfin00burngoog here] at [[Archive.org]].  （これは第一版である。第二版の序文ではバーンサイドの有名な[[表現論]]の有用性に関する方針転換が述べられている。）
* {{citation | last=Frobenius |first=Ferdinand Georg |authorlink=フェルディナント・ゲオルク・フロベニウス |title=Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul |journal=Crelle |volume=CI |year=1887 |page=288 | doi=10.1515/crll.1887.101.273}}.
* {{Citation | last1=Neumann | first1=Peter M. | author1-link=Peter M. Neumann | title=A lemma that is not Burnside's | mr=562002 | zbl=0409.20001 | year=1979 | journal=The Mathematical Scientist | issn=0312-3685 | volume=4 | issue=2 | pages=133–141| ref=harv}}.
* {{citation | last=Rotman |first=Joseph |title=An introduction to the theory of groups |publisher=Springer-Verlag |year=1995 |isbn=0-387-94285-8|ref=harv}}.

== 関連項目 ==
* [[ポーヤの計数定理]]

== 外部リンク ==
* {{MathWorld|title=Cauchy-Frobenius Lemma|urlname=Cauchy-FrobeniusLemma}}
* {{SpringerEOM|title=Burnside Lemma|urlname=Burnside_Lemma|last=Neumann|first=Peter M.}}

{{DEFAULTSORT:はあんさいとのほたい}}
[[Category:補題]]
[[Category:群論]]
[[Category:組合せ論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]