バーンサイドの補題

バーンサイドの定理（Burnside’s lemma）

群 $G$ を集合 $X$ に作用する置換群とする。
軌道・固定群定理とラグランジュの定理より
\begin{align}
&|G|/|\mathrm{stab}_G(x)| = |Gx| \\
\Longrightarrow&\sum_{x \in X} \frac{1}{|Gx|} = \frac{1}{|G|}\sum_{x \in X} |\mathrm{stab}_G(x)| \\
\iff &|X/G| = \frac{1}{|G|}\sum_{g \in X} |\mathrm{fix}_X(g)|

\end{align}

が得られる。各軌道 $Gx$ は $X$ の同値類になるので、$Gx$ の元は一度ずつ数えられて $\sum_{x \in X} \frac{1}{|Gx|} = |G/X|$ となる。

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

巡回置換

コードを $A$ と置く。長さ $n$ の語の数を $a_n$ と置く。共役を同一視したときの長さ $n$ の語の数を $b_n$ と置く。$f = \sum a_nx^n, g = \sum b_n x^n$ と置く。

$\gcd(k, n) = d$ となる $d$ は $\phi(\frac{n}{d})$ 個ある。$\mathbb Z / (n \mathbb Z \cap k \mathbb Z) = \mathbb Z / \gcd(n, k) \mathbb{Z} = \mathbb Z / d\mathbb{Z}$ となる $d$ をまとめて数える。バーンサイドの補題より

\begin{align}
g(x) &= \sum_{d, n} \frac{\phi(n / d)}{n}f(x^{n / d})^d \\
&=\sum_{d, n} \frac{\phi(k)}{k} \frac{1}{d}f(x^{k})^d \\
&=\sum_{d, n} \frac{\phi(k)}{k} \log\left(\frac{1}{1-f(x^k)}\right) \\
\end{align}

二面体群

$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$ 個であるものの個数。

置換の指数型母関数と多重集合の通常型母関数

サイズ $i$ のオブジェクトが $A_i$ 種類あるとき、オブジェクトの多重集合の通常型母関数は $\prod (1-x^i)^{-A_i} = \exp\left(\sum_{i \geq 1} \frac{1}{i}A(x^i)\right)$ となる。これは、Polyaの数え上げ定理で直接導くことができる。要素数 $n$ のオブジェクトの多重集合 $S$ を一つ取る。$S$ の各要素と $[n]$ の間の全単射（ラベル）に対して、ラベルの置換によって移るもの同士を同一視すると、軌道は1つだけになる。長さ $i$ の巡回置換で不変ならば、その巡回置換に割り当てるオブジェクトは全て同じである必要があるから、重みは $A(x^i)$ になる。

この式を用いると、ラベルなし根付き木の通常型母関数
$T(x)=x\exp\left(\sum_{i \geq 1} \frac{1}{i}T(x^i)\right)$
が直ちに得られる。この式から $T_{n+1} = \frac{1}{n}\sum_j T_{n-j+1} \sum_{d|j} dT_d$ が得られる。右辺では（根以外の頂点に対して印を一つつける場合の数) / n を数えている。これはオンライン畳み込みの形をしているので $O(n \log(n)^2)$ で計算できる。また、ある（unlabelled な）連結グラフの通常型母関数 f とそこから連結性を落としたグラフの通常型母関数 g は $1 + g = \exp\left(\sum \frac{1}{i}(f(x^i))\right)$ を満たす。

グラフ

n頂点のunlabelledな単純グラフの個数を辺の個数の母関数として求めよ。
n頂点のunlabelledな多重グラフの個数を辺の個数の母関数として求めよ。

$\prod (1+x^i)^{A_i} = \exp(\sum A_i\log(1+x^i) = \exp(\sum A_i (-1)^{j+1} x^{ij} / j) =\exp(\sum_j (-1)^{j+1}f(x^i) / j)
= -\exp(\sum_j f(x^j) / j) + \frac{1}{2} \left( 2\exp(\sum_j f(x^i) / j) + 2\exp(\sum_j (-1)^{j+1}f(x^i) / j) \right)$
全単射な関数は A_n によって偶置換と奇置換で分かれるので2回、それ以外は1回数えられる。従って、全単射な関数の個数はZ(A_\infty-S_\infty, f(x)) として上のようになる。