数论| 组合数学 | Polya定理：学习 笔记
Polya 定理
Redfield-Polya （Pólya enumeration theorem，简称PET）定理是组合数学理论中最重要的定理之一。
其提出者波里亚在众多数学的分支：函数论、变分学、概率论、数论、组合数学以及计算数学和应用数学领域中，都颇有建树，他共发表了200多篇著名论文，以他的名字命名的Polya计数定理，则是近代组合数学的重要工具。波里亚还是杰出的数学教育家，有著丰富的数学教育思想和精湛的数学教学艺术，他对数学思维一般规律的研究，堪称是对人类思想宝库的特殊贡献。
Polya 定理可以用于解决关于集合互异状态的计数问题，是解决此类问题的简洁高效的一个工具
例题引入
描述
把一个 $2\times 2$ 的方格棋盘用黑白两色涂色，规定经过旋转重合的图案是一种图案，问能涂出多少种不同的图案？
分析
不考虑旋转，所有涂色方案如下图：
可以发现图中共有 16 种涂色方案，但是把经过旋转的 $\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}$，$\begin{Bmatrix} 5&6&7&8 \end{Bmatrix}$，$\begin{Bmatrix} 9&10&11&12 \end{Bmatrix}$，$\begin{Bmatrix} 13&14 \end{Bmatrix}$ 都算作一种方案，我们发现方案数其实只有 6 种
问题规模较小时，我们固然可以通过枚举所有可能的情况计算得出满足题目条件的情况数目，但如果我们面对了一个 $20\times 20$，甚至 $200\times 200$，穷举算法在那时将会达到 $O(2^{200})$ 的时间复杂度，就连计算机也不能保证在有生之年给我们问题的答案
于是，数学家就开始研究这类问题的共性，试图得出这类问题的通式，然后就有了 Polya 定理
预备知识
群
若一个一个集合 $G$ 和二元运算 $a \bullet b$ ，满足下列条件：
- 封闭性：对于 $\forall a,\;b\in G$，有 $(a \bullet b)\in G$
- 结合律：对于 $\forall a,\;b,\;c\in G$，有 $(a\bullet b)\bullet c=a\bullet (b\bullet c)$
- 单位元：对于 $\forall a\in G$， 存在 $e\in G$，使得 $a\bullet e=a$
- 逆元：对于 $\forall a\in G$，存在 $f\in G$，使得 $a\bullet f=f\bullet a=e$，且记 $f=a^{-1}$
则称集合 $G$ 是运算法则 $\bullet$ 下的一个群， $\bullet$ 通常表示乘法运算，此时则称 $G$ 是一个乘法群
一个简单的例子：对于 $\forall a\in Z$，即所有整数组成的集合，在加法原则下满足上面四个条件，其中 1，2 很好解释，单位元则是 0，逆元则是 $a$ 的对应相反数，这个群便叫做 整数加法群
群按照集合中元素个数分为 无限群 和 有限群，Polya定理 主要针对有限群进行分析操作
置换和置换群
简单来说，置换就是把集合 $A$ 中的所有元素 $a_i$ 重新排列，形成集合 $B$，然后做映射 $a_i \to b_i,\;i\in[1,\;n]$ ，例如：
$\begin{pmatrix} 1&2&3&4\\2&3&4&1 \end{pmatrix}$，下面的 $\begin{pmatrix} 2&3&4&1 \end{pmatrix}$，就是对上面的 $\begin{pmatrix} 1&2&3&4 \end{pmatrix}$ 的重新排列，并映射 $1\to2$，$2\to3$，$3\to4$，$4\to1$，置换群就是 若干个置换组成的集合和置换之间的二元运算法则构成的群，这种置换之间的二元运算法则可以理解成是 连续映射（或者是向量求和），例如置换之间的运算：（运算符定义为 $\bullet$ ）
$\begin{pmatrix} 1&2&3&4\\3&1&2&4 \end{pmatrix} \bullet \begin{pmatrix} 1&2&3&4\\4&3&2&1 \end{pmatrix}=\begin{pmatrix} 1&2&3&4\\3&1&2&4 \end{pmatrix} \bullet \begin{pmatrix} 3&1&2&4\\2&4&3&1 \end{pmatrix} = \begin{pmatrix} 1&2&3&4\\2&4&3&1\end{pmatrix}$
可以发现运算结果是连续映射的结果，如 $1\to3\to2$，$2\to1\to4$，$3\to2\to3$，$4\to4\to1$
可以证明，这样的运算法则和置换之间构成的集合满足构成群的 4 个条件
现在，设顺时针转动 0度，90度，180度，270度 为原来的 16 种方案的四个置换，可以得到：
$\begin{pmatrix} a_1=&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ a_2=&2&3&4&1&6&7&8&5&12&11&9&10&14&13&15&16\\ a_3=&3&4&1&2&7&8&5&6&10&9&12&11&13&14&15&16\\ a_4=&4&1&2&3&8&5&6&7&11&12&10&9&14&13&15&16 \end{pmatrix}$
下面，我们对上述 4 种置换深入研究
不动置换类：$Z_K$
设 $G$ 是 $1……n$ 的一个置换群，且 $K$ 是 $G$ 的集合中的一个元素，$G$ 中使得 $K$ 映射之后不变的置换组成的集合称之为 K不动置换类：$Z_K$，通常用 $\lvert Z_K \rvert$ 表示这个集合当中的元素个数，如上述例子中：
- K=1 时，使得 1 在映射之后保持不变的置换只有 $a_1$，故 $Z_1=\begin{Bmatrix} a_1 \end{Bmatrix}$，$\lvert Z_1 \rvert=1$
- K=13 时，使得 13 映射之后不变的置换只有 $a1$，$a_3$，故 $Z{13}=\begin{Bmatrix} a1&a_3 \end{Bmatrix}$，$\lvert Z{13} \rvert=2$
- K=15 时，使得 15 映射之保持不变的置换有 $a1$，$a_2$，$a_3$，$a_4$，故 $Z{15}=\begin{Bmatrix} a1&a_2&a_3&a_4 \end{Bmatrix}$，$\lvert Z{15} \rvert=4$
等价置换类：$E_K$
设 $G$ 是 $1……n$ 的一个置换群，且 $K$ 是 $G$ 的集合中的一个元素，$K$ 在 $G$ 中的置换作用下能变化到的元素组成的集合叫做 $K$ 的等价置换类：$E_K$，通常用 $\lvert E_K \rvert$ 表示这个集合当中的元素个数，如上述例子中：
- K=1 时，1 能变化到的元素集合为 $\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}$，故 $\lvert E_1 \rvert=4$
- K=13 时，13 能变化到的元素集合为 $\begin{Bmatrix} 13&14 \end{Bmatrix}$，故 $\lvert E_{13} \rvert=2$
- K=15 时，15 能变化到的元素集合为 $\begin{Bmatrix} 15 \end{Bmatrix}$，故 $\lvert E_{15} \rvert=1$
可以发现对于群 $G$ 中的任一元素 $K$，总有 $\lvert E_K \rvert \times \lvert Z_K \rvert = \lvert G \rvert$，证明过程较为复杂，在此不详细展开
Burnside 引理
若设函数 $f(x,\;y)$ 表示元素 $x$ 在置换 $a_y$ 的映射下是否发生改变，并定义函数 $a_i(x)=y$ 表示 $x$ 在 $a_i$ 置换下的映射
则 $f(x,y)=\begin{cases} 1,\quad a_y(x)=x \\ 0, \quad a_y(x)\neq x \end{cases}$，下面我们看看对于上述 4 个有关旋转的置换中 $f(x,y)$ 的情况
| 元素 / 置换 | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
| …… | …… | …… | …… | …… |
| 16 | 1 | 1 | 1 | 1 |
| Sum() | 16 | 2 | 4 | 2 |
可以发现 $\sum{i=1}^{16}\lvert Z_i \rvert=\sum{j=1}^4Sum(j)$，其中 $Sum(j)$ 为上表中的 $a_j$ 对应列之和，也就是在置换 $a_j$ 下保持不变的元素个数，我们可以称经过旋转重合的多种涂色方案（至少 2 种）组成的集合为一个等价类 $E$，则原来的 16 种涂色方案中实际上包含了 4 个等价类，为 $\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}$，$\begin{Bmatrix} 5&6&7&8 \end{Bmatrix}$，$\begin{Bmatrix} 9&10&11&12 \end{Bmatrix}$，$\begin{Bmatrix} 13&14 \end{Bmatrix}$
可以发现当 $i$ 和 $j$ 同属一个等价类时，$\lvert Z_i \rvert = \lvert Z_j \rvert$，设原方案集合中存在 $m$ 个等价类
则 $\sum{i=1}^n \lvert Z_i \rvert =\sum{i=1}^m\sum{K\in E_i}\lvert Z_K \rvert=\sum{i=1}^m \lvert E_i \rvert \times \lvert Z_i \rvert=m \times \lvert G \rvert$，这个式子只是简单变形，本质和上述式子相同
Burnside 引理：集合中存在的所有互异组合状态的个数就是等价类的个数，即 $m=\frac{\sum{i=1}^n\lvert Z_i \rvert}{\lvert G \rvert}$，由于上述的等价关系也可以写成 $m=\frac{\sum{j=1}^4Sum(j)}{\lvert G \rvert}$，这里的 $\lvert G \rvert$ 是指置换的个数，为 4
结合这个例子，我们发现 $m=\frac{16+2+4+2}{4}=6$，与枚举得到的答案吻合
有了 Burnside 引理，已经可以大大降低计数的时间复杂度了，可是我们发现 $Sum(j)$ 并不是那么的好算，现在直接采用搜索的方法的话将会达到 $O(n\times \lvert G \rvert \times N)$，分别表示元素个数（涂色的方案数），置换个数（此例中为4）和实际的方格数，显然还是会超时，Polya 算法就旨在寻找一种简便的计算 $Sum(j)$ 的方法，进一步优化
Polya 定理
高级循环
记一种对于 $\begin{pmatrix} a_1&a_2&a_3&……&a_n \end{pmatrix}$ 的高级循环为它的一个置换，并满足：
$\begin{pmatrix} a_1&a_2&a_3&……&a_n \end{pmatrix} \Rightarrow \begin{pmatrix} a_1&a_2&a_3&……&a_n \\ a_2&a_3&a_4&……&a_1 \end{pmatrix} $，这样的涉及 $n$ 个元素的高级循环称之为 n阶循环
每个置换都可以由若干个互不相交的循环组成（互不相交是指两个循环没有公共元素）如：
$ \begin{pmatrix} 1&2&3&4&5 \\ 3&5&1&4&2 \end{pmatrix}= \begin{pmatrix} 1&3 \end{pmatrix} \bullet \begin{pmatrix} 2&5 \end{pmatrix} \bullet \begin{pmatrix} 4 \end{pmatrix} = \begin{pmatrix} 1&3 \\ 3&1 \end{pmatrix} \bullet \begin{pmatrix} 2&5 \\ 5&2 \end{pmatrix} \bullet \begin{pmatrix} 4 \\ 4 \end{pmatrix}$，（定义 $\bullet$ 表示连接或合并）
对于每个置换都有且仅有这样一种被表示为循环的方式，且定义循环节的个数 $C$ 为组成的循环个数，如上例中循环节数 $C=3$
按照上述规则，给 $2\times 2$ 的方格编号，旋转之后如图：
定义 4 个置换为：转 0度，90度，180度，270度，用 $g$ 表示置换，$C(g)$ 表示置换对应的循环节个数，则：
转 0 度时，$g_1=\begin{pmatrix} 1&2&3&4 \\ 1&2&3&4 \end{pmatrix}=(1)\bullet(2)\bullet(3)\bullet(4)$，故 $C(g_1)=4$
转 90 度时，$g_2=\begin{pmatrix} 1&2&3&4 \\ 3&2&4&1 \end{pmatrix}=(4\quad 3\quad2\quad 1)$，故 $C(g_2)=1$
转 180 度时，$g_3=\begin{pmatrix} 1&2&3&4 \\ 3&4&1&2 \end{pmatrix}=(1\quad 3)\bullet(2\quad 4)$，故 $C(g_3)=2$
转 270 度时，$g_4=\begin{pmatrix} 1&2&3&4 \\ 2&1&4&3 \end{pmatrix}=(1\quad 2\quad 3\quad 4)$，故 $C(g_4)=1$
进一步研究发现，$Sum(i)=2^{C(g_i)}$，也就是说，该置换下不变的涂色方案数和以它对应的循环节个数为指数，涂色选择数为底数的幂相同，若有 $T$ 种颜色可以涂，则此处应为 $Sum(i)=T^{C(g_i)}$
Polya 定理：设 $G$ 是 $p$ 个对象的一个置换群，用 $T$ 种颜色染色 $p$ 个对象，则本质不同的方案数为：
$m=\frac{1}{\lvert G \rvert}\times \sum_{i=1}^sT^{C(g_i)}$，其中 $s$ 为置换的个数
利用 Polya 定理 的时间复杂度为 $O(s\times N)$，分别为置换的个数和格子总数，在前面的引理上实现了优化
附言
对于一开头提出的例子，利用 Polya 定理 求出表达式之后，其实还可以继续找规律，最后答案的方案数应为：
$m=\frac{1}{4}\times (T^{n^2}+T^{\frac{n^2+3}{4}}+T^{\frac{n^2+1}{2}}+T^{\frac{n^2+3}{4}})$
这与我们前面通过枚举和归纳表达式计算出来的结果完全一致
参考文献：Polya定理——符文杰
