📂抽象代数

バーンサイドの公式の導出

概要

Burnsideの公式は、群の作用と等方部分群に対する代表的な応用で、組み合わせ論を始めとする分野で直ちに使用できる。

公式 ¹

有限群$G$と、$G$-集合である有限集合$X$について、$X$の$G$による軌道の個数を$r$とすると $$r |G| = \sum_{g \in G} \left| X_{g} \right|$$

導出

集合$\left\{ (g,x) \in G \times X | gx = x \right\}$の基数を$N$とすると $$X_{g} = \left\{ x \in X \ | \ gx = x \right\}$$ であり、$G_{x} = \left\{ g \in G \ | \ gx = x \right\}$に対して以下が成り立つ。 $$N = \sum_{g \in G} |X_{g}| = \sum_{x \in X} |G_{x}|$$

等方部分群の性質: $X$が$G$-集合ならば$|Gx| = ( G : G_{x})$。$G$が有限群ならば$|Gx|$は$|G|$の約数である。

$|G| = |G_{x} | |Gx|$より$\displaystyle N = \sum_{x \in X} |G_{x}|$から $$N = \sum_{x \in X} {{|G|} \over {|Gx|}} = |G| \sum_{x \in X} {{1} \over {|Gx|}}$$ ある軌道$\mathscr{O}$については、$x \in \mathscr{O}$に対して$|Gx|$が全て同じ値を持つので、 $$\sum_{x \in \mathscr{O}} {{1} \over {| Gx | }} = 1$$ 軌道の個数は$r$であるから、$N = |G| r$となり、まとめると次のようになる。 $$r |G| = \sum_{g \in G} \left| X_{g} \right|$$

■

例

円卓問題

$7$人が円卓に座る場合の数を計算せよ。

---

$7$人を一列に並べる場合の数は$7!$である。

反時計回りに回転させる「作用」は合計$7$通りである。従って、場合の数は $$r = {{1} \over {|G|}} \sum_{g \in G} | X_{g} | = {{1} \over {7}} 7! = 720$$

数珠問題

$7$個の異なるビーズを糸に通す場合の数を計算せよ。

---

$7$個のビーズを一列に並べる場合の数は$7!$である。反時計回りに回転させて数珠をひっくり返す作用は合計$7 \times 2 = 14$通りである。従って、 $$r = {{1} \over {|G|}} \sum_{g \in G} | X_{g} | = {{1} \over {14}} 7! = 360$$