Skip to content →

バーンサイドの補題

バーンサイドの定理

群 \(G\) を集合 \(X\) に作用する置換群とする。
$$ x^g = x$$ となるペア \((x, g)\) の個数★を二通りに数える。

xを固定する

\(G / \mathrm{stab}_G(x) \cong Gx\) であるからラグランジュの定理より
\(★=\sum_{x \in X}|\mathrm{stab}_G(x) | = \sum_{x \in X}\frac{|G|}{|Gx|}\)
である。

gを固定する

\(★ = \sum_{g \in G} |\mathrm{fix}_X(g) | \)

二つを比較する

二つを比較すると、

$$ \sum_{x \in X} \frac{1}{|Gx|}= \frac{1}{|G|}\sum_{g \in G} |\mathrm{fix}_X(g)|$$
が得られる。各軌道 \(Gx\) は \(X\) の同値類になる(ラグランジュの定理と似た証明)ので、\(Gx\) の元は一度ずつ数えられる。従って、右辺は軌道の個数に等しい。つまり、$$ |X / G|= \frac{1}{|G|}\sum_{g \in G} |\mathrm{fix}_X(g)|$$ が成り立つ。

\(X = [k]^A\) のとき、\(g\) のサイクルの個数を \(c(g)\) と置くと、\(|X / G | = \sum_{g \in G} k^{c(g)}\) となる。

巡回置換

\(k \mathbb{Z} / n \mathbb{Z} = \gcd(k, n) \mathbb{Z} / n\mathbb{Z}\)

二面体群

\(rx = \bar x, sx = e^{i\theta} x\)とする。
\((rs)^2 x = \overline{e^{i\theta} \overline{e^{i\theta} x}} = x\) より \((rs)^2 = e\) である。\(rs = s^{-1}r^{-1}\) なので、二面体群の任意の元は \(r^is^j\) の形で書ける。\(e^{2i\theta} \bar x = e^{i\theta}\overline{e^{-i\theta}x}\) が反時計回り\(\theta\)方向の軸に関する鏡映を表しているので、任意の元は鏡映か回転を表している。

正四面体群

偶置換のみであることにまず気付く。\(A_4\)と同型。

正六面体群

4軸の置換で表せる。ある二軸を含む平面に垂直な回転軸を取るとその二軸は固定され、ほかの二軸はswapされる。従って、\(\mathfrak{S}_4\) と同型。

置換の固定点の個数

置換 \(w \in \mathfrak{S}_n\) の固定点の平均個数は、\(\mathfrak{S}_n\) が \([n]\) に作用したときの軌道の総数に等しい。軌道は一つしかないので、固定点の平均個数は一つである。

第一種スターリング数

\(A\) を人の集合、\(B\) を色の集合とする。人を色で塗り分ける方法は \(G = \mathfrak{S}_n, X = B^A\) としてバーンサイドの補題を適用すると \begin{align} & \left(\!\!{|B|\choose |A|}\!\!\right) = \frac{1}{|A|!}\sum s(n, k)|B|^k \\
\Leftrightarrow& |B|(|B| + 1) \cdots(|B| + |A| – 1) = \sum s(n, k)|B|^k
\end{align}
となる。ただし、\(s(n,k)\) は \(n\) 頂点上のサイクル分解であって、サイクルが \(k\) 個であるものの個数。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA