Burnside和polya定理
Burnside定理
Burnside定理用于计算集合X的非等价着色数。
设$C$是$X$的着色集合，$G$是$X$的置换群，且$G$作用在$C$上，即$\forall f \in G,c\in C(f \ast c \in C)$。
定义函数$C(f)$:
\[C(f)=\{c|c\in C, f\ast c = c\}\]记$N(G,C)$表示在$G$作用下，$C$中非等价的着色数目。
Burnside公式如下：
\[N(G,C)=\frac{1}{|G|}\sum_{f\in G}|C(f)|\]例子1
举个简单的例子，将n个不同的对象放在一个环上，有多少种不同的放法。
如果一种方法可以通过另外一种方法通过旋转得到，就认为两种方法等价，比如n=3的情况下，(1,2,3)与(2,3,1)，(3,1,2)被认为是等价的方法。
容易发现$G={r^0,r^1,\ldots, r^{n-1}}$，其中$r=(2,3,\ldots, n, 1)$。
由于每个对象都不同，因此一定有$C(r^1)=C(r^2)=\ldots = C(r^{n-1})=\emptyset$。而$C(r^0)$，由于所有着色方案在$r^0$下保持不变，因此$C(r^0)=C$。
带入到Burnside公式中，可以得到：
\[N(G,C)=\frac{1}{|G|}\sum_{f\in G}|C(f)|=\frac{|C(r^0)|}{|G|}=\frac{n!}{n}=(n-1)!\]是不是很简单啊…
Polya定理
一个置换可以分解为若干个循环节，比如$(2,1,3)$，它可以被分解为两个循环节$[12][3]$。一个置换分解的循环节个数是固定的。
记$#(f)$表示置换$f$分解后的循环节数目。
对于置换$f$，其分解的循环节，长度为$i$的有$e_i$个循环节，定义$type(f)=(e_1,e_2,\ldots, e_n)$。
由于$f$分解的循环节的总长度一定是$n$，因此满足
\[1e_1+2e_2+\ldots + ne_n=n\\ \#(f)=e_1+e_2+\ldots+e_n\]引入$n$个变量$z_1,z_2,\ldots, z_n$，记$mon(f)=z_1^{e_1}z_2^{e_2}\ldots z_n^{e_n}$。
定义函数$P(G)$如下：
\[P_G(z_1,z_2,\ldots,z_n)=\frac{1}{|G|}\sum_{f\in G}mon(f)\]Polya定理给出了下面命题：
假设有$k$种不同的颜色，有$N(G,C)=P_G(k,k,\ldots, k)$。
假设有$k$种不同的颜色，限制第i种颜色必须正好出现$p_i$次，我们引入$k$个新的变量$u_1,u_2,\ldots, u_k$代表$k$种颜色，我们可以保证$N(G,C)$的生成函数
\[P_G(\sum_{i=1}^ku_i,\sum_{i=1}^ku_i^2,\ldots, \sum_{i=1}^ku_i^n)\]即$N(G,C)$是上式展开后项$u_1^{p_1}u_2^{p_2}\ldots u_k^{p_k}$的系数。
例子1
对于一个四边形，每个顶点都可以用k种颜色着色。问有多少种不等价的着色方案。
如果一个着色可以通过另外一种着色方案，通过旋转可以得到，则认为两个着色等价。
首先G由下面元素组成：
\[(1,2,3,4)=[1][2][3][4]\\ (2,3,4,1)=[1,2,3,4]\\ (3,4,1,2)=[1,3][2,4]\\ (4,1,2,3)=[1,4,3,2]\\\]利用Polya定理计算：
\[P_G(k,k,k,k)=\frac{1}{|G|}\sum_{f\in G}mon(f)=\frac{1}{4}(k^4+k^1+k^2+k^1)\]设$k=2$带入可以得到$P_G(2,2,2,2)=6$。