置换群与Burnside引理 · chx(AT)xjtu

一个 $2\times2$ 的棋盘，给每一个格子黑白染色，如果两种染色方案能通过旋转完全重叠的话，那么这两种方案算一种，那么求总共有几种染色的方法？

这个就没什么好说的了，反正总共四个格子，每个格子两种颜色，那么总共就有 $2^4=16$ 种染色方法，先列出来再去重。

使用Burnside引理来计算。

$N(C,G)=\frac{1}{|G|}\sum_{f\in G}|C(f)|$

其中：

$N(C,G)$ 表示对于染色方案集合 $C$ 以及作用在其上面的置换 $G$ 而言，本质不同的等价类的个数

$C$ 表示染色方案集合

$G$ 表示置换群

$C(f)$ 表示在置换 $f$ 下的稳定核，即所有染色方案 $x \in C$ 满足 $f*c=c$

就像诸多反演、容斥公式一样，一个量直接计算的难度巨大，那么就求出一些与其有关的但是相对容易直接计算的信息，再用这些有关的信息来计算需要的量

首先引入记号：

$C$ , $G$ , $N(C,G)$ , $C(f)$

$G(c)$ 表示在染色 $c$ 下的稳定核，即所有置换 $f\in G$ 满足 $f*c=c$

根据置换的可合并性与消去律，我们容易知道 $G(c)$ 是一个群

然后考虑到与 $c$ 本质相同的染色方案的形式应满足如下条件

$t(某种染色方案)=f*c$

然后想象一下当 $f$ 遍历 $G$ 的时候总共产生了 $|G|$ 种 $f*c$ ，但是 $t$ 可能远远没有那么多种，其原因就在于可能出现这样的情况：

虽然$f\not= g$ ，但是 $f=x \cdot a,g=y\cdot a$ ，而 $x,y \in G(c)$

因此纵使置换 $f\not= g$ ，但是 $f*c=g*c$

设参 $U(c)$ 表示与 $c$ 本质相同的染色方案，那么感性理解一下，假设我先设置 $|U(c)|$ 个置换 $f$ ，使之与这 |U(c)| 个结果一一对应，然后再分别对于这几个 $f$ 使用稳定核 $G(c)$ ，然后就能生成全部的 $G$ ，由此可以得到等式：

$|U(c)|\times |G(c)|=|G|$ => $|U(c)|=\frac{|G|}{|G(c)|}$

组合意义：可以把每个染色方案看做一个点，而置换则看做一条边，而 $U(c)$ 则恰好构成一个团

再考虑这样一个计数常用技巧“算两次”：

计算染色-置换对 $(c,f)$ 满足 $f*c=c$ 的个数：

那么答案等于 $\sum_{c\in C}|G(c)|$ 或者是 $\sum_{f\in G}|C(f)|$

然后就有 $\sum_{c\in C}|G(c)|=\sum_{f\in G}|C(f)|$

根据之前的证明得知 $|G(c)|=\frac{|G|}{|U(c)|}$

因此就有 $\frac{1}{|G|}\sum_{f\in G}|C(f)|=\sum_{c\in C}\frac {1}{|U(c)|}$

然后再仔细考虑一下等式右边，根据刚才的组合意义，每一团点的贡献恰好是 $1$ ，那么答案就是团的数量，再仔细想一想，这不就是 $N(C,G)$ 嘛

因此得到计数公式 :

$N(C,G)=\frac{1}{|G|}\sum_{f\in G}|C(f)|$