Pólya 定理
Pólya 定理的中文名是波利亚计数定理。
传送门：洛谷P4980 【模板】Polya 定理 题解 （在这篇文章里会讲解 Pólya 定理 的运用）
置换
一个有限集合 $S$ 到自身的双射称为 $S$ 的一个置换。集合 $S=\{a_1,a_2,\cdots,a_n\}$ 上的置换可以表示为
意为将 $a_i$ 映射为 $a_{p_i}$ ，其中 $p_1,p_2,\cdots,p_n$ 是 $1,2,\cdots,n$ 是一个排列。显然 $S$ 上置换的总数为 $n!$ 。
对于两个置换 $f = \left(\begin{array}{c}a_1, a_2, \ldots, a_n \\a_{p_1}, a_{p_2}, \ldots, a_{p_n}\end{array}\right)$ 和 $g=\left(\begin{array}{c}a_{p_1}, a_{p_2}, \ldots, a_{p_n} \\a_{q_1}, a_{q_2}, \ldots, a_{q_n}\end{array}\right)$ ，$f$ 和 $g$ 的乘积记为 $f \circ g$ ，其值为
简单来说就是先经过 $f$ 的映射，再经过 $g$ 的映射。
这里也有人用 $g\circ f$ 来表示同样含义的，
不愧是数学。
置换群
集合 $S$ 上的所有置换关于置换的乘法满足封闭性、结合律、有单位元、有逆元，因此构成一个群。
这个群的任意一个子群即称为置换群。
循环置换
循环置换是一类特殊的置换，可表示为
若两个循环置换不含有相同的元素，则称它们是不相交的。有如下定理：
任意一个置换都可以分解为若干不相交的循环置换的乘积，例如
该定理的证明也非常简单。如果把元素视为图的节点，映射关系视为有向边，则每个节点的入度和出度都为 $1$，因此形成的图形必定是若干个环的集合，而一个环即可用一个循环置换表示。
Burnside 引理
定义
设 $A,B$ 为有限集合，$X$ 为一些从 $A$ 到 $B$ 的映射组成的集合。
$G$ 是 $A$ 上的置换群，且 $X$ 中的映射在 $G$ 中的置换作用下封闭。
$X / G$ 表示 $G$ 作用在 $X$ 上产生的所有等价类的集合1，则
其中 $X^g=\{x \mid x \in X,~g(x)=x\}$ 。
证明
在这之前先引入轨道稳定子定理以及它的证明。
轨道稳定子定理：$G$ 和 $X$ 的定义同上，有
其中 $G^x$ 称为 $x$ 的稳定子，$G(x)$ 称为 $x$ 的轨道，则有
轨道稳定子定理的证明：
首先可以证明 $G^x$ 是 $G$ 的子群，因为
- 封闭性：若 $f,g \in G$ ，则 $f \circ g(x) = f(g(x)) = f(x) = x$ ，所以 $f \circ g \in G^x$
- 结合律：显然置换的乘法满足结合律。
- 单位元：因为 $I(x)=x$ ，所以 $I \in G^x$ （$I$ 为恒等置换）
- 逆元：若 $g \in G^x$ ，则 $g^{-1}(x) = g^{-1}(g(x)) = g^{-1}\circ g(x) = I(x) = x$ ，所以 $g^{-1} \in G^x$
则由群论中的拉格朗日定理可得
其中 $[G:G^x]$ 为 $G^x$ 不同的左陪集个数。
接着仅需证明 $|G(x)| = [G : G^x]$ 。
我们将其转化为：证明存在一个从 $G(x)$ 到 $G^x$ 所有不同左陪集的双射。
令 $\varphi(g(x)) = gG^x$ ，下证 $\varphi$ 为双射
- 若 $g(x) = f(x)$ ，两边同乘 $f^{-1}$ 可得 $f^{-1} \circ g(x)=I(x)=x$ ，所以 $f^{-1} \circ g \in G^x$ ，由陪集的性质可得 $(f^{-1}\circ g)G^x = G^x$ ，即 $gG^x = fG^x$
- 反之可证，若 $gG^x = fG^x$ ，则有 $g(x) = f(x)$
- 以上两点说明对于一个 $g(x)$ ，只有一个左陪集与其对应，即 $\varphi$ 是一个从 $G(x)$ 到左陪集的映射
- 又显然 $\varphi$ 有逆映射，因此 $\varphi$ 是一个双射。
于是我们可以利用轨道稳定子定理来证明 Burnside 引理了
即
解释
讲了半天这个定理到底有什么用呢？
我们以给立方体染色为例，来解释这个定理的用法。
- $A$ ：立方体 $6$ 个面的集合。
- $B$ ：$3$ 种颜色的集合。
- $X$ ：直接给每个面染色，不考虑本质不同的方案数的集合，共有 $3^6$ 种
- $G$ ：各种翻转操作构成的置换群
- $X/G$ ：本质不同的染色方案的集合
- $X^g$ ：对于翻转操作 $g$ ，所有直接染色方案中，经过 $g$ 这种翻转后保持不变的染色方案的集合。
接着我们需要对 $G$ 中的所有置换进行分析，它们可以分为以下几类：
不动：即恒等变换，显然有 $|X^g| = 3^6$ 。
以两个相对面的中心连线为轴旋转 $90^{\circ}$ ：相对面有 $3$ 种选择，旋转的方向有 $2$ 种选择，因此有 $6$ 个置换。
假设选择了前后两个面的中心连线为轴，则必须要满足上下左右 $4$ 个面的颜色一样，因此有 $|X^g|=3^3$ 。
以两个相对面的中心连线为轴旋转 $180^{\circ}$ ：相对面有 $3$ 种选择，旋转无影响，因此有 $3$ 个置换。
假设选择了前后两个面的中心连线为轴，则必须要满足上下相同，左右相同，因此有 $|X^g| = 3^4$ 。
以两条相对棱的中点连线为轴旋转 $180^{\circ}$ ：相对棱有 $6$ 种选择，旋转无影响，因此有 $6$ 个置换。
假设选择了 前面与上面的交 和 下面与后面的交 作为相对棱，
则必须要满足前、上两个面相同，下、后两个面相同，左右两个面相同，因此有 $|X^g|=3^3$ 。
以两个相对顶点的连线为轴旋转 $120^{\circ}$ ：相对顶点为 $4$ 种选择，旋转的方向有 $2$ 种选择，因此有 $8$ 个置换。
假设选择了 前面的右上角 和 后面的左下角 为相对顶点，
则必须满足 前、上、右相同 且 后、下、左相同，因此有 $|X^g| = 3^2$ 。
因此，所有本质不同的方案数为
Pólya 定理
定义
在与 Burnside 引理相同的前置条件下， 若 $X$ 为所有从 $A$ 到 $B$ 的映射，则
其中 $c(g)$ 表示置换 $g$ 能拆分成的不相交的循环置换的数量。
证明
在 Burnside 引理中，显然 $g(x)=x$ 的充要条件是 $x$ 将 $g$ 中每个循环置换的元素都映射到了 $B$ 中的同一元素
所以 $|X^g| = |B|^{c(g)}$ ，即可得 Pólya 定理。
解释
依然考虑立方体染色问题。
分析刚才提到的以相对棱的中点连线为轴旋转 $180^{\circ}$ 的情况。
如果将前后上下左右 $6$ 个面编号 $1$ 到 $6$ ，则该置换可以表示为
因此 $c(g)=3,|B|^{c(g)}=3^3$ ，与 Burnside 引理中的分析结果相同
参考文献：
[1] https://oi-wiki.org/math/permutation-group/
1. 若 $X$ 中的两个映射经过 $G$ 中的置换作用后相等，则它们在同一等价类中 ↩
