群、Burnside引理与Pόlya定理

搞了整整一天就学了这些玩意

想要学会下面的必须得把基本概念弄清楚啊。。血的教训。。

给定一个集合G={a,b,c,…}和一个G上的二元运算×，

若满足

那么称集合G在×运算下是一个群。

n个元素的置换表示为

$$\begin{pmatrix}
1&2&3&···&n\\
a_1&a_2&a_3&···&a_n
\end{pmatrix}$$

其中a是1到n的一个排列，该置换将原来第$i$位的元素替换为第$a_i$位的元素。

置换群的元素为置换，运算为置换的叠加。

特别的，记

$$(a_1 a_2 ··· a_n)=
\begin{pmatrix}
a_1&a_2&a_3&···&a_n\\
a_2&a_3&a_4&···&a_1
\end{pmatrix}$$

为一个n阶循环。每个置换都可以写成若干互不相交循环的叠加。

如：

$$\begin{pmatrix}
1&2&3&4&5&6\\
3&5&6&4&2&1
\end{pmatrix}=(1 3 6)(2 5)(4)$$

Burnside引理、Pόlya定理都是用来处理这样一个问题：对于一个元素集S，用k种颜色进行染色，并给定置换群G，若$\exists g\in G$使得两种染色方案A、B相同，那么认为A和B等价，记为A~B。问有多少种本质不同的染色方法。

对于两种染色方案A~B，我们称A和B属于同一个等价类。本质不同的染色方法数也就等于不同的等价类的数目。

那么Burnside引理告诉我们，若记在一个置换$g\in G$下保持不变的染色方案数为C(g)，那么总的本质不同的染色方案数为所有$g\in G$的C(g)的平均值。写成公式就是如下定理：

设置换群G作用于有限集合$\chi$上，则$\chi$在G作用下的等价类的数目为：

$$l=\frac{\sum_{g\in G}C(g)}{|G|}$$

其中$\chi$指的是染色方案集。

有了Burnside引理，我们就需要一种行之有效的方法来快速求出每个C(g)的值。

由于每个置换可以表示为若干个不相交循环的叠加，那么我们可以首先把置换g表示出来。

就用上面的例子：

$$\begin{pmatrix}
1&2&3&4&5&6\\
3&5&6&4&2&1
\end{pmatrix}=(1 3 6)(2 5)(4)$$

那么可以发现，在该置换下，若要使染色方案等价，那么136的颜色必须相同，25的颜色必须相同，4单独一个不用考虑

所以我们将这个置换分成了三部分，每个部分可以染一种颜色

总的染色方案就是$k^3$！（k表示颜色数）

若用m(g)表示g用不相交循环表示中循环的个数，那么有如下定理：

如果用k种颜色给有限集S染色，对于一个置换g，

$$C(g)=k^{m(f)}$$

将这个定理直接代入Burnside引理，就得到了Pόlya定理：

对于一个元素集S，用k种颜色进行染色，并给定置换群G，若一个方案通过置换$g\in G$得到另一个方案，则这两个方案等价，那么本质不同的染色方案数为：

$$l=\frac{\sum_{g\in G}k^{m(g)}}{|G|}$$

若用m(g)表示g用不相交循环表示中循环的个数。

那么对于这一类染色方案数问题，若染色方案数为p，就得到了一个复杂度为O(p|S|)的优秀算法。