隐藏
对Burnside引理与Polya定理的理解 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

对Burnside引理与Polya定理的理解

注意,本文并非从组合数学的角度进行解释,文中所用到的名词与定义可能与组合数学不符。
若有不符,欢迎在评论处指出。
另,更严谨的组合数学角度的解释可以参考文末的参考资料1

本文用$\left|S\right|$,表示集合$S$的大小。

置换与循环

置换是一个对一个排列的映射。
$A$是一个排列,$B$是一个排列,$A,B$大小相同,记$f(A)=B$,则称$f$是一个置换。
置换是满射的。

就是一个置换。

置换与每列的相对顺序无关,如:

置换可以拆分为循环,即将第一行到第二行连边。
这样会形成若干个环,每个环称为一个循环。
如:

写作$\begin{pmatrix}4 & 3 & 2 & 1\end{pmatrix}$也可。
显然,一个置换可以拆分为若干个循环。

置换群

记一个群为$G$,记其结合运算符号为 $\cdot$,其需要满足:

  1. 合成运算的封闭性:$\forall f,g\in G,f\cdot g\in G$
  2. 合成运算的结合律:$\forall f,g,h\in G,(f\cdot g)\cdot h=f\cdot(g\cdot h)$
  3. 存在单位元:$\exists e\in G,\forall f\in G,f\cdot e=e\cdot f=f$
  4. 存在合成运算的逆元:$\forall f\in G,\exists f^{-1}\in G,f\cdot f^{-1}=f^{-f}\cdot f=e$。

置换群是由置换形成的群。

着色

着色可以看做是对一个排列的运算,它使得排列中每一个元素具有一个颜色。
设$c$是对于排列$x$的着色,则$x_i$的颜色为$c(x_i)$。

用$f*c$表示对着色进行置换,作用为:
将$f(x)$的颜色变为$x$的颜色。

着色集

定义着色集为着色的集合$C$,置换群为$G$。
$\forall f\in G,c\in C,f*c\in C$。
等价类实际上是针对于着色集进行划分。

不动点

若存在着色集$C$与置换$f$,使得$f(C_i)=C_i$,则称$C_i$是$f$的一个不动点,也就是长度为$1$的循环。
置换$f$关于着色集$C$的不动点集合记为$c(f)$。

Burnside引理

若存在着色集$C$与置换群$G$,那么$C$关于$G$的等价类个数为:

举一个来自百度百科的例子。
有一个$4$格的正方形,有两种颜色,求在旋转同构的情况下等价类数目。
着色集大小为$16$,如下图:

置换群有$4$个元素:

  • 不旋转
  • 旋转$90$度
  • 旋转$180$度
  • 旋转$270$度

将对$C$进行的置换$f\in G$写作循环形式:

  • 不旋转:$f_1(C)=(1)(2)\cdots(16)$
  • 旋转$90$度:$f_2(C)=(1)(2)\begin{pmatrix}3 & 4 & 5 & 6\end{pmatrix}\begin{pmatrix}7 & 8 & 9 & 10\end{pmatrix}\begin{pmatrix}11 & 12\end{pmatrix}\begin{pmatrix}13 & 14 & 15 & 16\end{pmatrix}$
  • 旋转$180$度:$f_4(C)=(1)(2)\begin{pmatrix}3 & 5 \end{pmatrix}\begin{pmatrix}4 & 6 \end{pmatrix}\begin{pmatrix}7 & 9 \end{pmatrix}\begin{pmatrix}8 & 10 \end{pmatrix}(11)(12)\begin{pmatrix}13 & 15 \end{pmatrix}\begin{pmatrix}14 & 16 \end{pmatrix}$
  • 旋转$270$度:$f_3(C)=(1)(2)\begin{pmatrix}6 & 5 & 4 & 3\end{pmatrix}\begin{pmatrix}10 & 9 & 8 & 7\end{pmatrix}\begin{pmatrix}11 & 12\end{pmatrix}\begin{pmatrix}16 & 15 & 14 & 13\end{pmatrix}$

由Burnside引理,共有$\frac{16+2+4+2}4=6$种等价类。

注意,Burnside是对着色集作用置换

Polya定理

Polya定理是对Burnside引理的具体化,提供了计算不动点的具体方法。
在OI题目中着色集一般很大,而不动点也不好计算,因此就需要用到Polya定理。

若存在排列$S$与置换群$G$。
对$S$作用$f\in G$,并将$f$拆解为不相交循环。
根据Polya定理,每个循环应染同一颜色,保留循环间顺序,重新构造排列$\lambda(f)=S’$,$S’$的元素为$f$的循环,统计$S’$的染色方案(不要求不等价)$g(S’)$,则等价类数目为:

通常,若循环之间颜色的选择互不影响,则:

其中$m$为颜色总数。

代换到Burnside引理可以得到:$\left|c(f)\right|=g(\lambda(f))$。

继续举百度百科的例子:

排列$S$(位置集合)有$4$个元素。
置换群有$4$个元素:

  • 不旋转:$f_1(S)=(1)(2)(3)(4)$
  • 旋转$90$度:$f_2(S)=\begin{pmatrix}1 & 2 & 3 & 4\end{pmatrix}$
  • 旋转$180$度:$\begin{pmatrix}1 & 3\end{pmatrix}\begin{pmatrix}2 & 4\end{pmatrix}$
  • 旋转$270$度:$f_2(S)=\begin{pmatrix}1 & 4 & 3 & 2\end{pmatrix}$

由Burnside引理,共有$\frac{2^4+2^1+2^2+2^1}4=6$种等价类。

注意,Polya定理是对原位置集合作用置换

参考资料

姥爷们赏瓶冰阔落吧~