最近，研究了两天的Burnside引理和Polya定理之间的联系，百思不得其解，然后直到遇到下面的问题：
对颜色限制的染色
例：对正五边形的三个顶点着红色，对其余的两个顶点着蓝色，问有多少种非等价的着色？
其中置换的方法有旋转 \(0^{\circ}, 72^{\circ}, 144^{\circ}, 216^{\circ}, 288^{\circ}\), 穿过一个点做对称轴进行翻转。
Burnside引理的证明
那么，在解决这个问题之间，我们首先要定义和证明一些东西：
在集合\(X\)的置换群的作用下，设\(G\)是\(X\)的置换群，\(C\)是\(X\)的着色集，且\(G\)作用在\(C\)下。
定义\(c\)（小写）保持不变的\(G\)中所有的置换的集合：
\[
G(c) = \{f: f\in G, f*c=c\}
\]
上面的公式含义就是：对于每一个确认的着色方案，我们都能确定一个置换的集合，使得集合内任意元素和\(c\)运算后的结果保持不变(感觉可以看成一个等价类)。
使着色\(c\)保持不变的所有的置换群的集合\(G(c)\)称为\(c\)的稳定核。
在\(f\)的作用下使着色\(c\)保持不变的\(C\)中的所有的着色集,(确定一个\(f\),就能得到一个\(c\)的集合)
\[
C(f) = \{c: c\in C, f*c=c\}
\]
这个就是后面的求解过程中，对于每一种置换，统计不动点的方式。
推论1：设\(c\)为\(C\)中的一种着色，那么与\(c\)等价的着色数
\[
\left | \{ f*c:f \in G\}\right |
\]
等于\(G\)中的置换数除以\(c\)的稳定核中的置换数的个数：
\[
\frac{|G|}{|G(c)|}
\]
证明：
对于每一个置换\(f\)，恰好存在\(|G(c)|\)个置换，这些置换作用在\(c\)上与\(f\)有相同的效果。因为总共有\(|G|\)个置换，所以与\(c\)等价的着色数为
\[
\frac{|G|}{|G(c)|}
\]
是不是感觉一头雾水。。。没关系，我们通过一个典型的例子来进一步的解读：
例：对正方形的4个小格用两种颜色着色，可得多少种不同的图像？置换的方式有旋转0°，90°，180°，270°。
先画出所有的涂色方案：
假设我们选择涂色方案\(f_1\),在16中涂色的方案中，有多少的涂色方案预期等价呢？
\[
G(f_1) = \{旋转0°， 旋转90°，旋转180°，旋转270°\}\\
|G(f_1)| = 4 \\
\therefore 16中涂色方案中，有\frac{|G|}{|G(f_1)|} = 1种方案与其等价\\
同理：G(f_3) = {旋转0°}\\
|G(f_3)| = 1\\
\therefore 16中涂色方案中，有\frac{|G|}{|G(f_3)|} = 4种方案与其等价, 它们分别是f_3, f_4, f_5, f_6\\
\]
下面就是关键了！！
Burnside定理：设\(G\)是\(X\)的置换群，而\(C\)是\(X\)中一个满足下面条件的着色集合：对于\(G\)中所有的\(f\)和\(C\)中的所有的\(c\)都有\(f*c\)仍在C中，则\(C\)中非等价的着色数\(N(G, C)\):
\[
N(G, C) = \frac{1}{|G|}\sum_{f\in G}|C(f)|
\]
证明：
采用两种不同的计数的方法，然后使计数相等，最后化简求解。
一种方式是考察\(G\)中的每一个\(f\)，并计算\(f\)保持着色不变的着色数然后求和。
\[
\sum_{f \in G}|C(f)|
\]
另外一种方式就是考察\(C\)中的每一个\(c\)，对保持不变的着色方案数求和：
\[
\sum_{c \in C}|G(c)|
\]
两种计数方式的总和相等：
\[
\sum_{f \in G}|C(f)| = \sum_{c \in C}|G(c)|
\]
由推论1：
\[
|G(c)| = \frac{|G|}{与c等价的着色数}
\]
因此：
\[
\sum_{c \in C}|G(c)| = |G|\sum_{c \in C}\frac{1}{与c等价的着色数}
\]
又在一个等价类里面，每一个元素的贡献都是：
\[
\frac{1}{与c等价的着色数}
\]
一个等价类的和就是1。
所以：
\[
\sum_{c \in C}|G(c)| = |G|*N(G,C)\\
\therefore \sum_{f \in G}|C(f)| = |G|*N(G,C)\\
\therefore N(G,C) = \frac{\sum_{f \in G}|C(f)|}{|G|}
\]
是不是感觉一脸懵逼，没关系，我们继续用上面的例子来说明：
\[
两种等价的计数方式为：\\
(16+4+2+2) = (4+4+1+1+1+1+1+1+1+1+2+2+1+1+1+1)\\
24 = (4*2+1*4+1*4+2*2+1*4)，右边的为(权重*个数)，个数和为16\\
24 = 24\\
以上我们解释了两种计数方案的相等性。\\
\\
\\
\\
继续：\\
24 = 4*(\frac{1}{1}+\frac{1}{1}+\frac{1}{4}*4+\frac{1}{4}*4+\frac{1}{2}*2+\frac{1}{4}*4)\\
发现右边的每一个等价类的权重和都为1
\]
好了，我们这样就证明好了Burnside引理。
Polya定理
实际上，Polya定理仅仅是改变了Burnside引理右边的计数的方法，这使得计数变得更加的简单。
我们知道，在使用Burnside引理的时候我们首先要枚举出来所有的染色方案数，然后在每种置换的情况下，统计所有的染色方案不变的情况。这样的时间复杂度为置换数染色方案数\(O(置换数*染色方案数)\)，进一步可知，我们的染色的方案数的时间空间复杂度是幂次级别的。
以例1为例，我们仅考虑每一个格点，不考虑位置，我们进行下面的计算：
\[
Q:\left\{\begin{matrix}
q_1 = (1)\quad(2)\quad(3)\quad(4), & 旋转0°\\
q_2 = (1\quad 2\quad 3\quad 4) &, 逆时针旋转90°\\
q_3 = (1\quad 3)\quad(2\quad 4), & 逆时针旋转180°\\
q_4 = (4\quad 3\quad 2\quad 1)& 逆时针旋转270°
\end{matrix}\right.
\]
注意\(q_2, q_4\)是两种不同的方案，他们是这样产生的：
\[
q_2 = \begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1
\end{pmatrix} = (2\quad 3\quad 4\quad 1) = (1\quad 2\quad 3\quad 4), 可以进行轮换换序\\
q_4 = \begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 1 & 2 & 3
\end{pmatrix} = (4\quad 3\quad 2\quad 1)
\]
置换\(f\)的循环分解中的循环个数记为
\[
\#(f)
\]
定理2：
设\(f\)是集合\(X\)的置换。如果我们用\(k\)种颜色对\(X\)的元素进行着色。设\(C\)是\(X\)所有的着色的集合。则\(f\)中保持着色不变的着色数为：
\[
|C(f)| = k^{\#(f)}
\]
这个式子并没有证明，意思就是每一个循环节看成一个等价类，这个等价类里面的元素的颜色全都相同。
然后我们就可以愉快的给出Polya的表示的形式了：
Polya定理：
设\(Q\)(为了区分\(G\)，实际上它们两的数量是相等的)是n个对象的一个置换群，用m种颜色涂染这n个对象，一个对象涂任意一种颜色，则在\(Q\)作用下不等价的方案数为：
\[
L = \frac{1}{|G|}\sum_{f \in G}m^{\#(f)}
\]
有了上面的这些定理之后呢，我们还是不能证明我们最初的问题，还需要一个工具：母函数！！！
母函数求解本质不同的染色问题
例2：用4种颜色涂3个编号分别为1,2,3的求，设颜色为b(蓝)，g(绿)，r(红)，y(黄)。
解：
\[
P(b_1, b_2, b_3, g_1, g_2, g_3, r_1, r_2, r_3, y_1, y_2, y_3)\\
=(b_1+g_1+r_1+y_1)(b_2+g_2+r_2+y_2)(b_3+g_3+r_3+y_3)
\]
展开后就能得到所有的64种方案了。
那么我们仅仅关系用了哪些颜色，而不关心在哪些球上染色呢？
我们可以有：
\[
P(b, g, r, y) = (b+g+r+y)^3 \\
=(b^3+g^3+r^3+y^3)+[(3b^2g+3b^2r+3b^2y)+(3g^2b+3g^2r+3g^2y)+(3r^2b+3r^2g+3r^3y)+\\
(3y^2b+3y^2g+3y^2r)+(6bgr+6bgy+6bry+6gry)]
\]
它们的系数和是64，将使用颜色相同的视为同一种方案的话，本质不同的染色方案数为20，因为有20个项。
例3：用3种颜色b(蓝)，r(红色)，y(黄色)染4个不同的球， 将4个球分为2组，每组2个，要求同组的球色相同。
\[
P(b_1, b_2, r_1, r_2, y_1, y_2)\\
=(b_1^2+r_1^2+y_1^2)(b_2^2+r_2^2+y_2^2)
\]
展开后可以得到所有的方案。
我们改变Polya的表示方式，使之便于代入母函数。
Polya定理的母函数表示
我们将一个置换分解成若干的循环节之后。假设f的循环因子分解有\(e_1\)个1循环，\(e_2\)个2循环，\(\dots, e_n\)个n循环。
\[
1*e_1+2*e_2+\dots+i*e_i+\dots+n*e_n=n
\]
那么循环数\(\#(f)\)为
\[
\#(f) = e_1+e_2+\dots+e_n
\]
因为循环的类型仅取决于循环因子分解中的循环的阶数，与元素在哪一个循环中无关。所以，不同的置换可以有相同的类型，我们试图定义不同的类型来群分置换，所以引进n个未定的变元：
\[
z_1, z_2,\dots,z_n
\]
定义f的多项式为:
注释：它的定义是为了后面运用母函数的方便。
\[
mon(f) = z_1^{e_1}*z_2^{e_2}\dots z_n^{e_n}
\]
于是， 对于\(G\)中的每一个置换\(f\)的单项式进行求和，我们得到关于\(G\)中的置换按照类型的生成函数
\[
\sum_{f \in G}mon(f) = \sum_{f \in G}z_1^{e_1}z_2^{e_2}\dots z_n^{e_n}
\]
合并同类项，\(z_1^{e_1}z_2^{e_2}\dots z_n^{e_n}\)的系数等于同种置换类型的个数。
于是\(G\)的循环指数定义为该生成函数除以\(G\)中的置换的个数\(|G|\),
\[
P_G(z_1, z_2, \dots, z_n) = \frac{1}{|G|}\sum_{f \in G}z_1^{e_1}z_2^{e_2}\dots z_n^{e_n}
\]
我们以例1进行相应的说明：
| 变换的类型 | 置换拆分 | 置换的类型 | 单项式 |
|---|---|---|---|
| 旋转0° | (1) (2) (3) (4) | (4, 0, 0, 0) | \(z_1^4\) |
| 旋转90° | (1 2 3 4) | (0, 0, 0, 1) | \(z_4\) |
| 旋转180° | (1 3) (2 4) | (0, 2, 0, 0) | \(z_2^2\) |
| 旋转270° | (4 3 2 1) | (0, 0, 0, 1) | \(z_4\) |
定理3：
设\(X\)是元素集合，\(G\)是\(X\)的置换群，\(\{u_1, u_2, \dots, u_k\}\)是k种颜色的集合，C是X的任意着色集。这时，针对各颜色的数目C的非等价着色数的生成函数是
\[
P_G(z_1=u_1+u_2+\dots+u_k, z_2=u_1^2+u_2^2+\dots u_k^2, \dots, z_n = u_1^n+u_2^n+\dots+u_k^n)
\]
这里其实就是将\((z_1, z_2, \dots, z_n)\)替换成多项式，至于为什么可以这样替换，可以体会一下前面举的一些关于生成函数统计不同的方案数的例子。
我们还是用例1来体会：
设颜色为w(白色)，b(黑色)
\[
P_G(z_1 = w+b, z_2=w^2+b^2, z_3 = w^3+b^3, z_4=w^4+b^4) \\
=\frac{1}{4}(z_1^4+z_2^2+2z_4) = w^4+w^3b+2w^2b^2+wb^3+b^4
\]
我们将它的系数相加，得到答案为6，与Burnside引理和前面的一般的Polya公式的计算结果一致！
实际上，我们为什么可以用\(m^{\#(f)}\)代入一开始的Polya公式呢？实际上生成函数也可以解释，生成函数的系数和必然为\(m^{\#(f)}\)
哈哈，终于把所有的知识和需要用的定理铺盖完毕！
下面，我们来解决我们最初的问题：
例：对正五边形的三个顶点着红色，对其余的两个顶点着蓝色，问有多少种非等价的着色？
其中置换的方法有旋转 \(0^{\circ}, 72^{\circ}, 144^{\circ}, 216^{\circ}, 288^{\circ}\), 穿过一个点做对称轴进行翻转。
Burnside引理的解法
| 置换方式P | 循环因子分解(Polya定理使用) | 不变的着色数 |
|---|---|---|
| 旋转\(0^{\circ}\) | ||
| 旋转\(72^{\circ}\) | ||
| 旋转\(144^{\circ}\) | ||
| 旋转\(216^{\circ}\) | ||
| 旋转\(288^{\circ}\) | ||
| 过1号点翻转 | ||
| 过2号点翻转 | ||
| 过3号点翻转 | ||
| 过4号点翻转 | ||
| 过5号点翻转 |
首先表示出所有的情况：
我们按照Burnside的定义，填写第三列的值：
旋转\(0^{\circ}\):
\[
p_1 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10
\end{pmatrix}
= (f_1)(f_2)(f_3)(f_4)(f_5)(f_6)(f_7)(f_8)(f_9)(f_{10})
\]
发现有16个不动点。
顺时针旋转\(72^{\circ}\) :
\[
p_2 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
5& 6 & 7 & 1 & 8 & 9 & 2 & 10 & 3 & 4
\end{pmatrix}
= (f_5 f_8 f_{10} f_4 f_1)(f_6 f_9 f_3 f_7 f_2)
\]
发现有0个不动点。
顺时针旋转\(144^{\circ}\):
\[
p_3 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
8& 9 & 2 & 5 & 10 & 3 & 6 & 4 & 7 & 1
\end{pmatrix}
= (f_8 f_4 f_{5} f_{10} f_1)(f_9 f_7 f_6 f_3 f_2)
\]
发现有0个不动点。
同理我们算出旋转\(216^{\circ}, 288^{\circ}\) 的不动点的个数都是0。
穿过1号点(最上面的点，顺时针依次标号为1, 2, 3, 4, 5)的对称轴：
\[
p_6 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
5& 2 & 9 & 8 & 1 & 7 & 6 & 4 & 3 & 10
\end{pmatrix}
= (f_5 f_1)(f_2)(f_3 f_9)(f_8 f_4)(f_7 f_6)(f_{10})
\]
有两个不动点。
同理，依次通过2, 3, 4, 5号点的对称轴，进行翻转的不动点都为2个。
于是我们可以填写下面的表：
| 置换方式 | 循环因子分解(Polya定理使用) | 不变的着色数 |
|---|---|---|
| 旋转\(0^{\circ}\) | 10 | |
| 旋转\(72^{\circ}\) | 0 | |
| 旋转\(144^{\circ}\) | 0 | |
| 旋转\(216^{\circ}\) | 0 | |
| 旋转\(288^{\circ}\) | 0 | |
| 过1号点翻转 | 2 | |
| 过2号点翻转 | 2 | |
| 过3号点翻转 | 2 | |
| 过4号点翻转 | 2 | |
| 过5号点翻转 | 2 |
由Burnside引理，我们可以计算出不同等价类的染色数目为：
\[
L = \frac{10+0*4+2*5}{10} = 2
\]
实际上，我们有一个很直观的理解：
两个蓝色要么连在一起，要么两个蓝色中间间隔一个红色，总共有两种本质不同染色方案数。
Polya定理解法
Polya定理的基本形式：用m种颜色\(C ={c_1, c_2, \dots, c_m} 涂染个对象涂染n个对象S = {1, 2, \dots, n}\), 在S的置换群Q作用下， 不等价的方案数为：
\[
L = \frac{1}{\left | Q \right |}\sum_{q\in Q} m^{\lambda(q)}
\]
我们先填写第二列的表：
仅仅对节点进行变换，不考虑颜色。
旋转\(0^{\circ}\):
\[
p_1 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 \\
1& 2 & 3 & 4 & 5
\end{pmatrix}
= (1)(2)(3)(4)(5)
\]
旋转\(72^{\circ}\):
\[
p_1 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 \\
2& 3 & 4 & 5 & 1
\end{pmatrix}
= (2\quad 3 \quad4\quad 5\quad 1) = (1\quad 2 \quad3\quad 4\quad 5)
\]
旋转\(144^{\circ}\):
\[
p_1 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 \\
3& 4 & 5 & 1 & 2
\end{pmatrix}
= (3\quad 5 \quad2\quad 4\quad 1) = (1\quad 3 \quad5\quad 2\quad 4)
\]
同理我们可以算出旋转\(216^{\circ}, 288^{\circ}\)的循环节。
经过1号节点的对称轴：
\[
p_1 = \begin{pmatrix}
1& 2 & 3 & 4 & 5 \\
1& 5 & 4 & 3 & 2
\end{pmatrix}
= (1)(2\quad 5)(3\quad 4)
\]
同理可以计算经过其他的节点进行翻转的循环节。
然后我们就可以填写下面的表了：
| 置换方式P | 循环因子分解(Polya定理使用) | 循环节的类型\((z_1, z_2, z_3, z_4, z_5)\) |
|---|---|---|
| 旋转\(0^{\circ}\) | (1) (2) (3) (4) (5) | (5, 0, 0, 0, 0) |
| 旋转\(72^{\circ}\) | (1 2 3 4 5) | (0, 0, 0, 0, 1) |
| 旋转\(144^{\circ}\) | (1 3 5 2 4) | (0, 0, 0, 0, 1) |
| 旋转\(216^{\circ}\) | (1 4 2 5 3) | (0, 0, 0, 0, 1) |
| 旋转\(288^{\circ}\) | (1 5 4 3 2) | (0, 0, 0, 0, 1) |
| 过1号点翻转 | (1) (2 5) (3 4) | (1, 2, 0, 0, 0) |
| 过2号点翻转 | (1 3) (2) (4 5) | (1, 2, 0, 0, 0) |
| 过3号点翻转 | (1 5) (3) (2 4) | (1, 2, 0, 0, 0) |
| 过4号点翻转 | (1 2) (3 5) (4) | (1, 2, 0, 0, 0) |
| 过5号点翻转 | (1 4) (2 3) (5) | (1, 2, 0, 0, 0) |
1个(5, 0, 0, 0, 0), 4个(0, 0, 0, 0, 1), 5个(1, 2, 0, 0, 0)类型的
然后我们代入母函数：
\[
P_Q (Z_1, Z_2, Z_3, Z_4, Z_5) = \frac{1}{\left |Q \right |}*(Z_1^5+4*Z_5+5*Z_1Z_2^2) \\
P_Q (r+b, r^2+b^2, r^3+b^3, r^4+b^4, r^5+g^5) = \frac{1}{10}((r+b)^5+4(r^5+b^5)+5(r+b)(r^2+b^2)^2) \\
=\frac{1}{10}(10r^5+10r^4b+20r^3b^2+20r^2b^3+10rb^4+10b^5)
\]
我们单独观察\(r^3b^2\)的系数，发现是\(\frac{20}{10} = 2\)，与我们的Burnside引理的计算结果一致！！