Polya定理

群论

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

定义

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

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

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

  • 单位元: $\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度}$

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

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