Burnside和polya定理

Published: December 20, 2020 by Daltao

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)|$

举个简单的例子，将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)!$

是不是很简单啊…

一个置换可以分解为若干个循环节，比如 $(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}$ 的系数。

对于一个四边形，每个顶点都可以用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$ 。