【算法】Burnside 引理

请注意,本文编写于 134 天前,最后修改于 134 天前,其中某些信息可能已经过时。

Burnside 引理是群论中的一个结论,在组合数学中可用于计算等价类的个数,常用于 Pólya 计数

置换:一个 集合映射到自身 的双射,置换群为 $G$
$eg:$

$$ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix} $$

所谓的元素指的是一种方案,集合即所有方案这个整体
置换可以分解为若干循环,可以连接每个元素置换后对应的元素,从任意点沿着这样的边可以回到原点,即形成一个环。对于没有访问到的其他元素同理

不动点:一个集合在进行置换后的不变元素(变换后仍然等价)

Burnside 引理:用 $D(a_j)$ 表示在所有元素在置换 $a_j$ 下不变的元素个数,$L$ 表示本质不同的元素数

$$ L=\frac{1}{|G|}\sum_{i=1}^{s}D(a_i) $$

比如说 $2*2$ 的方阵着色,旋转同构
一共有 $16$ 个元素,$6$ 种本质不同的方案
可以通过枚举得到

如何利用 Burnside 引理进行计算呢?

首先将所有元素列举出来

burnside1.png
burnside1.png

从左到右,从上到下分别编号为 $1-16$

$$ G=\{\text{旋转0°,旋转90°,旋转180°,旋转270°}\}\\ a_1=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \end{pmatrix}\\ a_2=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ 1 & 3 & 11 & 5 & 13 & 14 & 8 & 16 & 9 & 2 & 10 & 4 & 12 & 6 & 7 & 15 \end{pmatrix}\\ a_3=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ 1 & 11 & 10 & 13 & 12 & 6 & 16 & 15 & 9 & 3 & 2 & 5 & 4 & 14 & 8 & 7 \end{pmatrix}\\ a_4=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ 1 & 10 & 2 & 12 & 4 & 14 & 15 & 7 & 9 & 11 & 3 & 13 & 5 & 6 & 16 & 8 \end{pmatrix} $$

(这就很妙是吧

可以看出 $D(a_1)=16,D(a_2)=2,D(a_3)=4,D(a_4)=2$
所以答案为 $L=\frac{1}{4}(16+2+4+2)=6$
和我们枚举得到的答案一致

考虑如何证明:

先给出一些定义

$Z_k$($K$ 不动置换类):设 $G$ 是元素 $1,2,\cdots,n$ 的置换群,若 $K$ 是其中某个元素, $G$中使得 $K$ 保持不动的全体,记为 $Z_k$

本例中,元素 $1$ 在四个置换中都保持不动,所以 $Z_1=\{a_1,a_2,a_3,a_4\}$
元素 $6$ 在 $a_1,a_3$ 中保持不变,所以 $Z_6=\{a_1,a_3\}$

$E_k$(等价类):设 $G$ 是元素 $1,2,\cdots,n$ 的置换群,若 $K$ 是其中某个元素,$K$ 在 $G$ 作用下的轨迹,记为 $E_k$。即 $K$ 在 $G$ 作用下所能变化成的所有元素的集合

本例中,元素 $1$ 在 $G$ 作用下不变,所以 $E_1=\{1\}$
元素 $6$ 在 $G$ 作用下只会变为元素 $14$,所以 $E_6=\{6.14\}$

引进定理 $|E_i|*|Z_i|=|G|$

显然有 $\sum_{i=1}^{n}|Z_i|=\sum_{i=1}^sD(a_i)$
我们设共有 $L$ 个等价类, $n=\sum_{i=1}^LE_i$
则会有

$$ \sum_{i=1}^sD(a_i)=\sum_{i=1}^n|Z_i|=\sum_{i=1}^L\sum_{k\in E_i}|Z_k| $$

由于有 $a,b\in E_i,|Z_a|=|Z_b|$ ,那么显然有(不要在意 $Z_i$这种细节,感性理解下就好了)

$$ \sum_{i=1}^sD(a_i)=\sum_{i=1}^n|Z_i|=\sum_{i=1}^L\sum_{k\in E_i}|Z_k|=\sum_{i=1}^L|E_i|*|Z_i|=L*|G| $$

那么有

$$ L=\frac{1}{|G|}\sum_{i=1}^sD(a_i) $$

证毕

Comments

添加新评论