Burnside 引理

定义

设 $A \times S = B$，其中 $A,B$ 是一个序列，$S$ 是一种置换，例如把 $1$ 号元素放到 $2$ 号元素的位置，把 $2$ 号元素放到 $3$ 号元素的位置等等。

那么若这里有若干个 $S$，这些 $S$ 互相进行变换也不会产生其它的元素，则这些 $S$ 满足：

一定有单位变换，即所变换前后有元素都不变。

并且衍生出了一个定理，若 $A \times S=B$，则称 $A,B$ 等价，设 $sum$ 为所有序列的等价类，则：

$$sum = \dfrac{1}{cnt}\sum_{S} P(S)$$

其中 $cnt$ 是 $S$ 的数量，$P(S)$ 就等于经过 $S$ 这个变换后不变的序列数量。

运用

有一个 $6$ 个面的正方体筛子，每个面可以染成 $k$ 种颜色种的任意一种，如果两个正方体筛子涂色后经过若干次旋转完全相同，则称这两个筛子相同，问不同的筛子有多少个？

首先，直接算肯定会算重，我们考虑利用 Burnside 定理来算。

因为我们讨论所有转的情况：

不转，那么前后不变的染色数就是 $k^6$。

沿着两个相对面的中点的连线转 $90$ 度，前后不变的染色数是 $k^3$，因为选的两个面可以任意染色，并且剩下的四个面颜色必须相同才能通过旋转后相同。两个相对的面有 $3$ 种选择，可以向左或者向右 $90$ 度，所以这部分的代价是 $6 \times k^3$。

沿着两个相对面的中点的连线转 $180$ 度，前后不变的染色数是 $k^4$，因为选的两个面可以任意染色，并且剩下的四个面中相对的面的颜色必须相同才能通过旋转后相同。两个相对的面有 $3$ 种选择，所以这部分的代价是 $3 \times k^4$。

沿着两个相对面棱的中点的连线转 $180$ 度，前后不变的染色数是 $k^3$，因为有一组相对的面要染相同颜色，另外有两对相邻的面要染相同颜色，两个相对的棱有 $3$ 种选择，所以这部分的代价是 $6 \times k^3$。

沿着两个相对顶点的连线转 $120$ 度，前后不变的染色数是 $k^2$，因为这两个顶点连接的 $3$ 个面颜色必须相同，两个相对的顶点有 $4$ 种选择，逆时针或者顺时针有 $2$ 个选择，所以这部分的代价是 $8 \times k^2$。

因此，总的 $cnt=1+6+3+6+8$，答案为：

$$sum=\dfrac{1}{24}(k^6+6 \times k^3+3 \times k^4+6 \times k^3+8 \times k^2)$$

这就是一个经典的 Burnside 定理的运用。

证明可以参考 Aaron_luomiao 的博客 here，写得十分形象生动。