Burnside和polya定理

Published: by Creative Commons Licence

  • Tags:

Burnside定理

Burnside定理用于计算集合X的非等价着色数。

设$C$是$X$的着色集合,$G$是$X$的置换群,且$G$作用在$C$上,即$\forall f \in G,c\in C(f \ast c \in C)$。

定义函数$C(f)$:

\[C(f)=\{c|c\in C, f\ast c = c\}\]

记$N(G,C)$表示在$G$作用下,$C$中非等价的着色数目。

Burnside公式如下:

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

例子1

举个简单的例子,将n个不同的对象放在一个环上,有多少种不同的放法。

如果一种方法可以通过另外一种方法通过旋转得到,就认为两种方法等价,比如n=3的情况下,(1,2,3)与(2,3,1),(3,1,2)被认为是等价的方法。

容易发现$G={r^0,r^1,\ldots, r^{n-1}}$,其中$r=(2,3,\ldots, n, 1)$。

由于每个对象都不同,因此一定有$C(r^1)=C(r^2)=\ldots = C(r^{n-1})=\emptyset$。而$C(r^0)$,由于所有着色方案在$r^0$下保持不变,因此$C(r^0)=C$。

带入到Burnside公式中,可以得到:

\[N(G,C)=\frac{1}{|G|}\sum_{f\in G}|C(f)|=\frac{|C(r^0)|}{|G|}=\frac{n!}{n}=(n-1)!\]

是不是很简单啊…

Polya定理

一个置换可以分解为若干个循环节,比如$(2,1,3)$,它可以被分解为两个循环节$[12][3]$。一个置换分解的循环节个数是固定的。

#(f)表示置换$f$分解后的循环节数目。

对于置换$f$,其分解的循环节,长度为$i$的有$e_i$个循环节,定义$type(f)=(e_1,e_2,\ldots, e_n)$。

由于$f$分解的循环节的总长度一定是$n$,因此满足

\[1e_1+2e_2+\ldots + ne_n=n\\ \#(f)=e_1+e_2+\ldots+e_n\]

引入$n$个变量$z_1,z_2,\ldots, z_n$,记$mon(f)=z_1^{e_1}z_2^{e_2}\ldots z_n^{e_n}$。

定义函数$P(G)$如下:

\[P_G(z_1,z_2,\ldots,z_n)=\frac{1}{|G|}\sum_{f\in G}mon(f)\]

Polya定理给出了下面命题:

假设有$k$种不同的颜色,有$N(G,C)=P_G(k,k,\ldots, k)$。

假设有$k$种不同的颜色,限制第i种颜色必须正好出现$p_i$次,我们引入$k$个新的变量$u_1,u_2,\ldots, u_k$代表$k$种颜色,我们可以保证$N(G,C)$的生成函数

\[P_G(\sum_{i=1}^ku_i,\sum_{i=1}^ku_i^2,\ldots, \sum_{i=1}^ku_i^n)\]

即$N(G,C)$是上式展开后项$u_1^{p_1}u_2^{p_2}\ldots u_k^{p_k}$的系数。

例子1

对于一个四边形,每个顶点都可以用k种颜色着色。问有多少种不等价的着色方案。

如果一个着色可以通过另外一种着色方案,通过旋转,则认为两个着色不等价。

首先G由下面元素组成:

\[(1,2,3,4)=[1][2][3][4]\\ (2,3,4,1)=[1,2,3,4]\\ (3,4,1,2)=[1,3][2,4]\\ (4,1,2,3)=[1,4,3,2]\\\]

利用Polya定理计算:

\[P_G(k,k,k,k)=\frac{1}{|G|}\sum_{f\in G}mon(f)=\frac{1}{4}(k^4+k^1+k^2+k^1)\]

设$k=2$带入可以得到$P_G(2,2,2,2)=6$。