Polya定理

群论

今天学习了一点很厉害的知识，我简要记录一下，方便日后再来复习，不过并不是十分地详尽。在了解什么是$Polya$定理之前，先让我们来看一看什么是群。这个知识可以是为后面奠基的。

定义

群是一个集合，它满足运算$*$，这个运算是经过定义的，可以是加法，可以是乘法，也可以是其它的运算法则。作为一个群，它具有以下的性质:

• 封闭性:$\forall a,b\in G,\exists c\in G,a*b=c$

• 结合律: $\forall a,b,c\in G,(ab)c=a(bc)$

• 单位元: $\exists e\in G,\forall a\in G,ae=ea=a$

• 逆元: $\forall a\in G,\exists b\in G,ab=ba=e,b=a^{-1}$

举个例子，所有的整数就可以算作是一个群，这里的运算就是加法，我们带进去看一看，会发现所有的性质是满足的。没错就这样

置换

$N$个元素$1,2,3,\cdots,N$之间的置换，然后把它换成$1,2,3,\cdots,N$的一个全排列就对了，就是这么理解的，写作：
$$
\begin{pmatrix}
1&2&3&\cdots&N\\
a_1&a_2&a_3&\cdots&a_n
\end{pmatrix}
$$
就是长成这个样子的了

置换群

这是一个元素是置换的群，它的运算是置换的连接。这个东西听起来很玄对不对，对了，这个东西听起来就是很玄的，因为它本来就是这么的玄，下面我们看一个例子来理解一下，比如下面两个群我们来运算一下：
$$
\begin{pmatrix}
1&2&3&4\\
3&1&2&4
\end{pmatrix}
\begin{pmatrix}
1&2&3&4\\
4&3&2&1
\end{pmatrix}=
\begin{pmatrix}
1&2&3&4\\
3&1&2&4
\end{pmatrix}
\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置换成了3，到了第二个置换里面，3又是置换成了2，对不对？这就相当于是1置换成了2，其他的元素我们以此类推，就可以得到最后一个置换了。

而这一个置换群，也是满足四个性质的，为什么？我想封闭性是显然的吧，至于其他的？我怎么可能知道？我都是不知道的了，那么我还讲什么

一个神奇的式子和概念

$$
|Z_k|*|E_k|=|G|
$$

首先，这个并不是绝对值的意思，而是说这几个分别是有多少的个数，下面一一说明每一个的意义是什么

• $|Z_k|$:设$G$是$1,2,3,\cdots,N$的置换群，$k$是$1,2,3,\cdots,N$中的某一个元素，$G$中使$k$不变的置换，记作$Z_k$
• $|E_k|$:等价类。$k$在$G$作用下的轨迹，即$k$在$G$作用下，产生的所有元素集合

证明：

请自行百度，谷歌，或者必应。

Polya定理

Burnside引理

我们不妨假设$D(a_j)$是置换$a_j$下面不变的元素个数，那么就很容易就有一个式子
$$
\sum_{i=1}^{n}|Z_j|=\sum_{i=1}^{s}|D(a_i)|
$$
我们接着往下面推
$$
\sum_{i=1}^{n}|Z_j|=\sum_{i=1}^{s}|D(a_i)|\\
=\sum_{i=1}^{L}\sum_{k\in|E_i|}|Z_k|
$$
这里不难理解吧，我们假设一共有$L$个等价类，各个等价类加起来实际上和原来是一样多的，对吧,然后

$$
=\sum_{i=1}^{L}|E_i||Z_i|\\
=\sum_{i=1}^{L}|G|=L|G|\\
L=\frac{1}{|G|}\sum_{i=1}^{n}|Z_i|=\frac{1}{|G|}\sum_{i=1}^{n}|D(a_i)|
$$
可是，虽然我们得到了这一个式子，但是啊，难道这一个$|Z_i|$,或者$D(a_j)$什么的，难道很好算吗？，一点都没有啊，所以说接下来还是得来看一看$Polya$定理

Polya定理

循环

这个真的就是一个很神奇的东西，简单的来说就是一种来表示置换的方法，来看看下面这一个例子
$$
\begin{pmatrix}
1&2&3&4&5\\
3&5&1&4&2
\end{pmatrix}=(13)(25)(4)
$$
这样的表示是唯一的，每一个置换都可以写成若干个互不相交的循环的乘积（我想这里肯定又是重新定义了一下），对于这些循环的个数就叫做循环节数（名字听起来和小学学的小数的循环节差不多，但是要难的多）

Polya定理的表达式

既然我们已经是知道了什么是循环，那么我们终于是可以写出这个该死的$Polya$定理的表达式了
$$
L=\frac{1}{|G|}(m^{c(g1)}+m^{c(g2)}+\cdots+m^{c(g_n)})
$$
其中$G$是${g_1.g_2,g_3\cdots,g_n}$,$c(g_i)$表示置换$g_i$的循环节个数，这一个式子看起来很神奇对吧，实际上和上面的$Burnside$引理是差不多的，只是换了一种表达的方式，这是前人们通过观察证明得出来的结论，这意味着我并不知道如何从$Burnside$引理推到$Polya$定理。

Polya定理的运用

下面让我们来看一道题目，这一道题目和方格子着色有关

对于一个2*2的矩阵，选择用黑白两种颜色来进行着色，如果说经过了旋转以后，得到的图形是相同的话，那么认为是同一种染色的方案。

因为数据很小，所以说可以通过枚举的方式得出所有的可能性：

我们可以看出，如果说是不重复的话，那么一共就有16种方案，但是如果说是要去除掉重复的方案的数量的话，那么就是一共有6种了。尽管说从目前的数据规模来看，这一道题目十分简单，但是如果说数据在扩大个几十倍甚至是上百倍的话，那么就十分不容易解决这一个问题了

因此这里我们就必须要用到刚才的知识来解决现在的问题了

设置换群$G={转0度，转90度，转180度，转270度}$

来标号分别写出四个变化的置换。然后看看，在第一个置换下面，每一个都是不会变的，而对于第二个和第四个置换，第一种和第二种图都是不会变的，对于第三个置换，则是增加了两个对角线填色的图，因此就可以直接代入到式子当中直接得到答案了。

好了，心里面大概也算的上是有一点谱了，差不多就是这么多内容了。（实际上还有一个母函数的内容，但是我自己并不是很懂。）