ポリアの計数定理とも呼ばれている。

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

群 \(G\) を集合 \(X\) に作用する置換群とする。
軌道・固定群定理とラグランジュの定理より
\begin{align}
|X/G| &= \sum_{x \in X} \frac{1}{|G \cdot x|}\\
& = \sum_{x \in X} \frac{|G_x|}{|G|} \\
&= \sum_{g \in G} \frac{|X^g|}{|G|}
\end{align}
が得られる。

\(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]\) に作用したときの軌道の総数に等しい。軌道は一つしかないので、固定点の平均個数は一つである。

第一種スターリング数

\(X = [m]^{[n]}\) 、\(G = \mathfrak{S}_n \) を \([n]\) に対する置換として、バーンサイドの補題を適用すると \begin{align} & \left(\!\!{m\choose n}\!\!\right) = \frac{1}{n!}\sum \left[n \atop k\right]m^k \\
\Leftrightarrow& m^{\overline{n}} = \sum \left[n \atop k\right]m^k
\end{align}

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

サイズ \(i\) のオブジェクトが \(A_i\) 種類あるとき、オブジェクトの多重集合の通常型母関数は \(\prod (1-tx^i)^{-A_i} = \exp\left(\sum_{i \geq 1} \frac{t^i}{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な多重グラフの個数を辺の個数の母関数として求めよ。

\begin{align}\prod (1+x^i)^{A_i} &= \exp\left(\sum A_i\log(1+x^i)\right)\\
&= \exp\left(\sum A_i (-1)^{j+1} x^{ij} / j\right)\\&=\exp\left(\sum_j (-1)^{j+1}f(x^j) / j\right)\\
&= -\exp\left(\sum_j f(x^j) / j\right) + \frac{1}{2} \left( 2\exp(\sum f(x^j) / j) + 2\exp(\sum_j (-1)^{j+1}f(x^j) / j) \right)
\end{align}
\(E\) を母関数によって数えるオブジェクトの集合とする。つまり、サイズ \(A_i\) の相異なる要素が \(i\) 個あるような集合である。\(E^{[n]}\) について、始域に \(A_n\) を作用させたときの軌道を考える。単射な関数の場合、像が同じでも、始域と終域の間の転倒数の偶奇によって分裂するので、各像に対して2回数えられる。単射でない場合、同一要素の置換によって転倒数の偶奇をflipできるので、1回だけ数えられる。始域に \(S_n\) を作用させたときは、関数の像と軌道が一対一対応する。従って、全単射な関数の個数は\(Z(A_\infty-S_\infty, f(x))\) として上のようになる。

フェルマーの小定理

\(X=[a]^{[p]},G=\mathbb{Z}/p\mathbb{Z}\) とする。\(G\) は足し算で作用する。すると、\((a^p-(p-1)a)/p\) は整数である。従って、\(a^p=a \pmod p\) である。