Pólya定理

Pólya 定理用于在对称情形下计算不等价着色的技术。

这部分内容对初学者非常不友好，定义多且乱，但是理解后能对前人的工作肃然起敬。

此博客旨在帮助我快速理解其中的重点内容，其中部分定义可能阐述的不够严谨。

置换群

若干置换构成的非空集合 \(G\) 和复合运算 \(\circ\) 满足封闭性，单位元，逆元则成为置换群。

不考虑等价的所有可能的染色方案构成的集合，用 \(C\) 表示。

称 \(C\) 中 2 个元素 \(c_1\) ，\(c_2\) 等价当且仅当存在一个 \(f\in G\) ，使得 \(f*c_1=c_2\) 。由 \(G\) 是置换群的条件可以着色等价是一种等价关系，通常情况我们需要统计的就是这种等价关系下的等价类个数，比如本质不同的环染色方案。

设有限群 \(G\) 作用在有限着色集 \(C\) 上，则等价类个数 \(N(G,C)\) 为：

\[N(G,C)=\frac{1}{|G|}\sum_{f\in G}\psi(f)\]

其中 \(\psi(f)\) 表示 \(f(c)=c\) 的着色 \(c\) 的个数。

对于一个置换，考虑一张 \(n\) 个结点的图，并且对于每个 \(i\) ，都在图中连一条 \(i→ p_i\)的有向图。那么整张图会是个有向环森林。因为每个点的入度和出度恰为 1，我们用 \(b_i\) 表示图中长度为 \(i\) 的环的个数。

设 \((G,\circ)\) 是一个 \(n\) 元置换的置换群，则它的轮换指标定义为：

\[P_G(x_1,...,x_n)=\frac{1}{|G|}\sum_{f\in G}x_1^{b_1}...x_n^{b_n}\]

此处 \(\psi(x)\) 表示欧拉函数。

正 \(n\) 边形的旋转群：\(P_G(x_1,...,x_n)=\frac{1}{n}\sum_{d|n}\psi(d)x_d^{n/d}\)
正 \(n\) 边形的二面体群(允许对折和旋转)：\(P_G(x_1,...,x_n)=\frac{1}{2n}\sum_{d|n}\psi(d)x_d^{n/d}+\begin{cases} \frac{1}{2}x_1x_2^{(n-1)/2} & n \bmod 2 = 1 \\ \frac{1}{4}(x_1^2x_2^{(n-2)/2}+x_2^{n/2})& n \bmod2 = 0 \end{cases}\)
正方体的顶点置换群：\(P_G=\frac{1}{24}(x_1^8+8x_1^2x_3^2+9x_2^4+6x_4^2)\)
正方体的边置换群：\(P_G=\frac{1}{24}(x_1^{12}+8x_3^4+6x_1x_2^5+3x_2^6+6x_4^3)\)
正方体的面置换群：\(P_G=\frac{1}{24}(x_1^6+8x_3^2+6x_2^3+3x_1^2x_2^2+6x_1^2x_4)\)

先给出一些基本定义：

则 \(\sum_{F}w(F)=P_G(\sum_{c}w(c),\sum_{c}w^2(c),...,\sum_{c}w^n(c))\) 。

特别地，让所有颜色的权值为 1，则为Burnside定理。

一种常见的用法是让某些元素的权值为变量而非具体值，得到一个生成函数，通过生成函数的系数计算出钦定某种颜色染色次数的方案数。