polya 计数笔记
前言
因为之前看过这个东西，但是过两天就完全忘记咋回事了，所以下定决心来写笔记。
Burnside 引理
置换
作为 polya 定理的前置知识，Burnside 引理是不可或缺的，所以，我们先从 Burnside 引理开始说起。
首先从置换说起。
对于一个置换来说，我们可以将其表示为若干置换的乘积，我们用 $(a_1, a_2, a_3, \dots, a_n)$ 代表 $a_1$ 位置的数字变为 $a_2$，$a_2$ 位置的数变为 $a_3$，$\dots$，$a_n$ 位置的数变为 $a_1$ 这样的一轮置换。
那么对于任意一个置换我们可以写成若干以上述表达置换的乘积的形式，比如对于
$$ (1,2,3,4,5,6,7,8,9) $$
变为
$$ (2,5,6,4,8,7,3,1,9) $$
我们可以将这个置换写成 $(1,2,5,8)(3,6,7)(4)(9)$。
那么我们把个阶置换的数量单独拿出来，并称上述置换的型为 $1^23^14^1$。
划分等价类和 k 不动置换群
我们设集合 $S = [1,n] \bigcap \mathbb Z$，那么对于 $a,b \in S$，若存在 $p \in G \leq S_n$，使得 $p(a) = b$，那么我们称 $a,b$ 是 $G$ 等价的。
容易证明 $G$ 等价关系为等价关系。
那么我们将元素 $k$ 所在的等价类记为 $E_k$。
如 $G = {e, (1,2), (3,4), (1,2,3,4)}$ 有 $E_1 = E_2 = {1, 2}$，$E_3 = E_4 = {3, 4}$。
另外记 $Z_k = {p|p(k) = k, p \in G}$，那么我们称 $Z_k$ 为 $G$ 上的 $k$ 不动置换群，容易证明 $Z_k$ 为一个群。
以上述 $G$ 为例，$Z_1 = Z_2 = {e, (3, 4)}, Z_3 = Z_4 = {e, (1, 2)}$。
那么我们有 $|E_k||Z_k| = G, k \in \mathbb N^$*。**
以下是证明：
我们设 $|E_k| = l$，$E_k = {a_1 (=k), a_2, \dots, a_l}$，$p_i(a_1) = a_i$。
定义 $p_iZ_k = {p_i \pi|\pi \in Z_k}$
那么有 $|p_jZ_k| = |Z_k|$，这点比较显然。
另外有 $p_iZ_k \bigcap p_jZ_k = \varnothing$，因为所有 $p_iZ_k$ 中的元素把 $a_1$ 置换为 $a_i$，而另一个置换为 $a_j$。
另外的，有 $G = p_1Z_k \bigcup p_2Z_k \bigcup \dots \bigcup p_lZ_k$
首先，显然有 $p_1Z_k \bigcup p_2Z_k \bigcup \dots \bigcup p_lZ_k \subseteq G$，那么我们证明 $G \subseteq p_1Z_k \bigcup p_2Z_k \bigcup \dots \bigcup p_lZ_k$ 即可
任取 $g \in G$，我们设 $g(a_1) = a$，那么 $a$ 与 $a_1$ 等价，即 $a \in E_k$，那么我们设 $a_j = a$。
那么我们有 $p_j^{-1}g(a_1) = p_j^{-1}(a_j) = a_1$
即 $p_j^{-1}g \in Z_k$，则有 $g \in p_jZ_k$
即证。
那么 $|G| = |p_1Z_k| + \dots + |p_lZ_k| = l|Z_k| = |E_k||Z_k|$
证明了这些，我们接下来证明 Burnside 引理
Burnside 引理
设 $G = {a_1, \dots, a_g}$ 是 ${1, 2, \dots, n}$ 上的置换群，则 $G$ 诱导出来的等价类的个数是
$$ l = \frac 1{|G|}\sum_{i = 1}^gc_1(a_i) $$
其中 $c_1(a_i)$ 表示在 $a_i$ 的作用下保持不变的元素个数。
证明：
我们设在 $G$ 的诱导下把集合划分为 $l$ 个等价类 $E_{i_1},E_{i_2},\dots,E_{i_l}$，那么若 $j$ 与 $k$ 等价，有 $|Z_j| = |Z_k|$：
$$|Z_j| = \frac{|G|}{|E_j|} = \frac{|G|}{|E_k|} = |Z_k|$$
那么有
$$ \sum_{i = 1}^gc_1(a_i) = \sum_{i = 1}^g\sum_{j = 1}^n[a_i(j) = j] = \sum_{j = 1}^n\sum_{i = 1}^g[a_i(j) = j] $$
$$ = \sum_{j = 1}^n|Z_j| = \sum_{j = 1}^l|E_{i_j}||Z_{i_j}| = \sum_{i = 1}^l|G| = l|G|$$
即证
置换的分解与型
对于一个置换来说，我们可以把这个置换分解为若干不相交循环的乘积。
例如 $(1,2,3,4,5,6,7,8,9,10)$ 到 $(3,4,7,9,5,1,6,2,10,8)$ 的置换可以写为：$ (1,3,7,6)(2,4,9,10,8)(5) $ 这三个循环的乘积。
我们不难发现其中 $4$ 阶循环，$1$ 阶循环，$5$ 阶循环的个数都为 $1$，于是我们称这个置换的型为 $1^14^15^1$。
类似的，如果我们说一个 $n$ 阶置换 $p$ 的型为 $1^{c_1(p)}2^{c_2(p)}\dots n^{c_n(p)}$ 则意味着这个这个置换含有 $c_1(p)$ 个在 $p$ 的作用下保持不懂的元素，含有 $c_i(p)$ 个 $i$ 阶循环。
Polya 定理
设 $G = {p_1, \dots, p_g}$ 是 $n$ 个对象的置换群，用 $m$ 种颜色染涂这 $n$ 个对象，则不同的方案数为
$$ l = \frac 1{|G|}\sum_{i = 1}^gm^{c(p_i)} $$
其中 $c(p_i)$ 为 $p_i$ 的循环节数，即 $c(p) = \sum_{i = 1}^nc_i(p)$。
其实这个定理也是很显然的。
我们设集合 $S$ 为所有的染色方案组成的集合，显然 $|S| = n^m$，那么对于集合 $S$ 而言的 $c_1(p_i)$ 来说显然当且仅当将 $p_i$ 中的同一个循环节内的所有点涂为同一个颜色的染色方案满足在置换 $p_i$ 的作用下不变。
那么其方案数就为 $m^{c(p_i)}$。
那么这里有一个拓展：
我们设
$$P_G(x_1, \dots, x_n) = \frac 1{|G|}\sum_{p \in G}\sum_{i = 1}^nx_i^{c_i(p)}$$
那么 Polya 定理可表示为 $l = P_G(m,m,\dots,m)$，另外的，所有染色方案可表示为：
$$P_G(\sum_{i = 1}^nb_i, \sum_{i = 1}^nb_i^2, \dots, \sum_{i = 1}^nb_i^n)$$
其中 $b_1^{c_1}b_2^{c_2}\dots b_n^{c_n}$ 的系数为 $n$ 个元素有 $c_1$ 个着 $b_1$ 色，$c_2$ 个着 $b_2$ 色……的方案数。
其实这个结合生成函数很好理解，对于循环节为 $1$ 的，我们可以涂任意色一次，对应为 $\sum_{i = 1}^nb_i$，对于循环节为 $2$ 的，我们可以涂任意色两次，对应为 $\sum_{i = 1}^nb_i^2$，如此下去，系数便是方案数。
总结
Polya 定理非常巧妙地利用了 Burnside 引理避免了因为染色而导致的方案数庞大的结果来计算本质不同的方案数，然而具体应用还是要根据情况具体分析，复杂度有时也挺高的。
Burnside 引理对于没有群论基础的同学来说理解起来可能比较困难，但是如果跳过理解 Burnside 引理这一步直接看 Polya 定理的话还是比较轻松的。