证明 Burnside 引理
蒟蒻君HJT
·
·
算法·理论
从零开始。
考虑满足以下性质的 $A$ 和 $G$：
1.$\forall g_1,g_2\in G, a\in A: (g_1 g_2)a=g_1(g_2 a)$，即结合律
2.$\exist e\in G \forall g\in G: e\cdot g_1 = g_1\cdot e = g_1$，即单位元 $e
3.\forall g\in G \exist g^{-1}\in G: g\times g^{-1} = g^{-1}\times g=e，即逆元
单位元唯一且逆元唯一，读者自证不难。
然后由此可以推出 g 的消去律：g_1 g_2=g_1 g_3\Rightarrow g_2=g_3
轨道-稳定子定理：$\forall a\in A: |O_a||G_a|=|G|$。
这个证明一下。设 $|G_a|=\{g_1,g_2\cdots g_n\}$，不存在其他的 $g$ 满足 $g\cdot a = a$。设 $a'\in O_a\neq a, a'=h\cdot a$。考虑 $h\cdot g_1, h\cdot g_2, \cdots, h\cdot g_n\in G$ 这 $n$ 个运算均不相同，且 $\forall i\in [1, n]: h\cdot g_i\cdot a = a'$。$\forall f \ \text{s.t.} \ f\cdot a=a': h\cdot g_i\cdot a=f\cdot a\Rightarrow (h^{-1}\cdot f)\cdot a = g_i\cdot a=a\Rightarrow \exist j\in[1, n]:h^{-1}\cdot f = g_j\Rightarrow f\in \{ h\cdot g_i\mid i\in[1, n]\}$。即 $|\{g\mid g\cdot a=a'\}|=n$。因此，$|G|=\displaystyle\sum_{a''\in |O_a|} |\{g\mid g\cdot a=a''\}|=|O_a||G_a|$。
由此可以很容易推出 Burnside 引理：设不同的轨道数量为 $x$，则 $x|G|=\displaystyle\sum_{a\in A}\frac{|G|}{|O_a|}=\displaystyle\sum_{a\in A}|G_a|=\displaystyle\sum_{g\in G}|A_g|$，即 $x=\displaystyle\frac{1}{|G|}\sum_{g\in G}|A_g|$。$A_g$ 表示在 $g$ 操作下不变的 $a\in A$ 的对象集合。
由此考虑 Polya 计数。给定 $n$ 个结点均匀分布的环，每个结点涂 $m$ 种颜色中的一种，问有多少种不同的染色方案（旋转后相同的，算一种）。$A$ 表示所有染色方案集合（旋转后相同的，算两种），$G$ 表示顺时针旋转 $i(0\leq i\leq n-1)$ 个结点，得到 $x=\displaystyle\frac{1}{n}\sum_{i=1}^{n} m^{\gcd(n, i)}=\displaystyle\frac{1}{n}\sum_{d\mid n}m^d\phi(\frac{n}{d})$。