4. Burnside 引理和Polya定理

joker ... 2022-4-7 大约 15 分钟

# 4. Burnside 引理和Polya定理

用六种不同颜色涂一正方体，一面一色，且每个面颜色不同，会有多少种涂法？？

$6*5*P(4,4)/4 /6=30$

这是会转的物体，记数方式会有点不同？？？？怎么考虑这种旋转类的物体呢？？

这个时候就需要引入置换等一系列的公式了

# 4.0 考点+例题

# 4.1 群相关概念

# 4.1.1 群的定义

群就是它将数学的运算进行归类

定义给定集合 $G$ 和 $G$ 上的二元运算 $\cdot$ ,满足下列条件称为群

满足一下条件

封闭性

若 $a,b\in G$ ,则存在 $c\in G$ ，使得 $a\cdot b=c$
结合律

任意 $a,b,c\in G$ ,有 $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
有单位元

存在 $e\in G$ ，任意 $a\in G,a\cdot e=e\cdot a=a$
有逆元

任意 $a\in G$ ，存在 $b\in G,a\cdot b=b\cdot a=e$ ,记为 $b=a^{-1}$

例子

$1\times 1=?$

$G=\{1\}$ 在普通乘法下是群，因为其满足4个条件

$G=\{1,-1\}$ 在普通乘法下是群，

$G=\{0,1,2,\cdots,n-1\}$ 在mod n的加法下是群

例子

二维欧式空间所有刚体旋转 $T=\{T\alpha \}$ 构成群。其中 $T\alpha=\begin{bmatrix}\cos\alpha & \sin\alpha \\ -\sin \alpha&\cos \alpha\end{bmatrix}$

# 4.1.2 相关概念

群元素的个数是有限的，是有限群

群元素的个数是无限的，是无限群

有限群 $G$ 的元素个数叫做群的阶，记作 $|G|$ .

设 $G$ 是群， $H$ 是 $G$ 的子集，若 $H$ 在 $G$ 原有的运算之下也是一个群，则称为 $G$ 的一个子群

单位元唯一

消去律成立 $ab=ac\to b=c$

# 4.2 置换群

参考资料

https://zhuanlan.zhihu.com/p/35428113

首先你得知道置换，循环，对换概念

# 4.2.1 前期数学准备

置换群是最重要的有限群，所有的有限群都可以用之表示

# 1) 置换概念

有限集 $A$ 上的双射函数称为 $A$ 上的置换或排列

简单的讲

置换就是把n个元素做一个全排列，比如1，2，3，4分别变成3，1，2，4，或者分别变成4，3，2，1。

一般地，1变 $a_1$ ,2变 $a_2$ ,...的置换记为 $\begin{pmatrix} 1&2&\cdots &n\\ a_1&a_2&\cdots &a_n\end{pmatrix}$

$A=\{a_1,a_2,\cdots,a_n\}$ ，即 $|A|=n$ 时，称为 $A$ 上的置换为 $n$ 次置换， $A$ 上的 $n$ 次置换 $p$ 可表示为

$p=\begin{pmatrix}a_1&a_2&\cdots&a_n \\ p(a_1)&p(a_2)&\cdots &p(a_n)\end{pmatrix}$

性质

n阶置换共有 $n!$ 个，同一置换用这样的表示可有 $n!$ 个表示法, $S_n=n!$

如 $A=\{1,2,3\}$ 时

一般的 $|A|=n$ 时，记 $A$ 上所有置换的集合为 $S_n,|S_n|=n!$

置换的合成运算

左合成运算 $p_1\circ p_2$ ，先进行 $p_2$ 运算，在进行 $p_1$ 运算

右合成运算 $p_1\diamond p_2$ ，先进行 $p_1$ 运算，在进行 $p_2$ 运算

例子

$P_1=\begin{bmatrix}1&2&3&4 \\ 3&1&2&4\end{bmatrix},P_2=\begin{bmatrix}1&2&3&4 \\ 4&3&2&1\end{bmatrix}$

$P_1$ 啥意思呢？？？

就是1变成了3,2变成了1 ，3变成2,4还是4

$P_1P_2=\begin{bmatrix}1&2&3&4 \\ 3&1&2&4\end{bmatrix}\begin{bmatrix}3&1&2&4 \\ 2&4&3&1\end{bmatrix}=\begin{bmatrix}1&2&3&4 \\ 2&4&3&1\end{bmatrix}$

啥意思呢？ $P_1$ 是把1变成了3 ，在 $P_2$ 中呢是把3变成了2,所以呢，他们相乘结果就是1变成了2

$P_2P_1=\begin{bmatrix}1&2&3&4 \\ 4&3&2&1\end{bmatrix}\begin{bmatrix} 4&3&2&1 \\ 4&2&1&3\end{bmatrix}=\begin{bmatrix}1&2&3&4 \\ 4&2&1&3\end{bmatrix}$

$P_2P_1\ne P_1P_2$

可以推断出置换不满足结合律

# 2) 循环概念

Rotate(1->4->3->2->1)

其实可以用循环进行表示

$(a_1a_2\cdots a_n)=\begin{bmatrix}a_1&a_2&\cdots &a_{n-1}&a_n\\ a_2&a_3&\cdots&a_n&a_1 \end{bmatrix}$

例子

$\begin{bmatrix}1&2&3&4&5 \\ 5&2&3&1&4\end{bmatrix}=(154)(2)(3)$

若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换

$\begin{bmatrix}1&2&3&4&5 \\ 5&2&3&1&4\end{bmatrix}=(154)(2)(3)$

$\begin{bmatrix}1&2&3&4&5 \\ 5&2&3&1&4\end{bmatrix}=(2)(154)(3)$

任一置换可表示成若干不相交循环的乘积

# 3) 共轭类

设 $S_n$ 为置换群

对于 $\forall p\in S_n$ ，存在一种分解方法使得置换 $p$ 分解为若干不相交的循环乘积

$p=(a_1a_2\cdots a_{k_1})(b_1b_2\cdots b_{k_2})\cdots (h_1h_2\cdots h_{k_i})$

其中 $k_1+k_2+\cdots+k_i=n$ ,

设 $k$ 阶循环出现的次数为 $c_k$ ,用 $(k)^{c_k}$ 表示

则 $S_n$ 中置换的格式为

$\prod_{k=1}^n(k)^{c_k}(1)^{c_1}(2)^{c_2}\cdots (n)^{c_n}$

则 $\sum_{k=1}^nk\times c_k=n$

例子

比如 $(1)(2)(3)$ 的形式 $(1)^3(2)^0(3)^0$

$(1\ 2)(3),(1\ 3)(2),(2\ 3)(1)$ 的形式都是为 $(1)^1(2)^1(3)^0$

在置换群 $S_n$ 中具有相同形式的置换全体，叫做该形式相应的共轭类

注意点

在 $S_n$ 中属于 $\prod_{k=1}^n(k)^{c_k}$ 形式的元素个数为

\frac{n!}{\prod_{k=1}^nc_k!k^{c_k}}

循环在洗牌中应用

54张牌去掉大小王，一共52张牌，然后一分为二，每次洗牌，从左边放一张牌，右边放一张牌。直到两边牌没有，请问这样子的牌洗多少次就可以恢复原样？

答案一共是 8次

# 4) 对换概念

$\begin{bmatrix}1&2&3 \\ 2&3&1\end{bmatrix}=\begin{bmatrix}1&2&3 \\ 2&1&3\end{bmatrix}\begin{bmatrix}1&2&3 \\ 3&2&1\end{bmatrix}$

$=(1\ 2)(1\ 3)$

任一循环都可以表示为对换的积

$(1\ 2\ \cdots n)=(1\ 2)(1\ 3)\cdots (1\ n)$

# 4.2.2 置换群概念

# 1) 置换分解

$S_n$ 中任意元素可以分解为对换之积

任一循环都可以表示为对换的积，每个置换的分解形式不是唯一的

任一置换表示成对换的个数的奇偶是唯一的

对换是一种做出来的带有符号的东西。

# 2) 置换群定义

给定n个元素组成的集合 $A$

$A$ 上的若干置换所构成的群称为 $n$ 次置换群

$A$ 上的所有置换构成的群称为 $n$ 次对称群

$n$ 次对称群 $<S_n,\diamond>$ 的子群即为 $n$ 次置换群

置换分成两大类：奇置换与偶置换

$S=(1)(25)(37)(46)$ ,3个换位，奇置换

$S=(1)(2)(3)(4)(5)$ ，0个换位，偶置换

$S_n$ 中所有偶置换构成一阶为 $\frac{n!}{2}$ 的子群称为交错群，记作 $A_n$

# 4.2.3 应用

# 1) 多面体群

正凸多边形

凸多边形中，如果各边相等且各角也相等，这样的多边形叫做正多边形

欧拉定理

任何凸多面体的顶点数 $v$ 与面数 $f$ 的和都较棱数 $e$ 多2，即 $v+f-e=2$ 。

由欧拉定理推出：凸正多面体只有5种，即正四面体，正八面体，正二十面体，正六面体(正方体)，正十二面体

正八面体群或正六面体群由24个运动构成群，它与四次对称群 $S_4$ 同构，所以正八面体群与正六面体群是一致的，都是4次对称群 $S_4$ .有时把四次对称群称为正八面体群或正六面体群

# 2) 着色问题的等价类

例子1

给2×2方格中涂黑白两色，有几种方法？16种

如果规定逆时针旋转90度，180度，270度后相同的方案算一种，那么答案就变成6种

这样的问题称为等价计数问题。也就是说题目会定义一种等价关系，满足等价关系的元素看成同一类，只统计一次。

自反性：每个元素和他自身等价

对称性：如果A和B等价，则B和A等价

传递性：如果A和B等价，B和C等价，则A和C等价

例子二

旋转0度的情况 $p_0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)$

旋转90度状况 $p_1=(1)(2\ 3\ 4\ 5)(6\ 7)(8\ 9\ 10\ 11)(12\ 13\ 14\ 15)(16)$

旋转180度 $p_2=(1)(2\ 4)(3\ 5)(6)(7)(8\ 10)(9\ 11)(12\ 14)(13\ 15)(16)$

旋转270度 $p_3=(1)(2\ 5\ 4\ 3)(6\ 7)(8\ 11\ 10\ 9)(12\ 15\ 14\ 13)(16)$

如果某个置换 $p_i$ 使得图像 $k$ 变成 $l$ ，称 $k$ 和 $l$ 属于同一个等价类

还有一些置换对一些图根本不起作用，比如旋转180度这种置换对于图6不起作用，这种类就叫做 $k$ 不动置换类

# 4.2.4 类总结

根据上面的总结

置换群用 $G$ 表示， $G$ 中每个置换表示为 $a_i$

例子

$G=\{a_1,a_2,\cdots,a_g\}=\{e,(1,2),(3,4),(1,2)(3,4)\}$

$G$ 中某个置换 $a_i$ 的 $k$ 阶循环出现的次数为 $c_k(a_i)$

$a_1=e=(1)(2)(3)(4)$

$c_1(a_1)=4$

$a_4=(12)(34)$

$c_2(a_4)=2$

# 1) k不动置换类

若 $k$ 是 $1\sim n$ 中的某一个整数, $G$ 中使 $k$ 保持不变的置换全体,记作 $Z_k$ ，叫做 $Gk$ 中使元素 $k$ 不动置换类，

比如 $G$ 中的 $Z_1=\{e,(3,4)\}$

$Z_2=\{e,(3,4)\}$

$Z_3=Z_4=\{e,(1,2)\}$

# 2) 等价类

$k$ 在 $G$ 的作用下的“轨迹"形成一个封闭的类，数 $k$ 所属的类成为 $k$ 的等价类，记作 $E_k$

$G$ 中数 $k$ 所属的等价类记作 $E_k$

$E_1=E_2=\{1,2\}$

$E_3=E_4=\{3,4\}$

我们思考一个问题

$|E_k|\cdot |Z_k|=|G|????$

# 3) orbit定理

$\forall k\in [1,n],|E_k||Z_k|=|G|$

# 4.2 Burnside 引理

是根据orbit定理推演出来的

# 4.2.1 概念

对于一个置换 $f$ ，若一个着色方案 $s$ 经过置换后不变，称 $s$ 为 $f$ 的不动点。

将 $f$ 的不动点数目记为 $C(f)$ ，则可以证明等价类数目为所有 $C(f)$ 的平均值。

$[1,n]$ 分成了 $l$ 个等价类， $[1,n]=E_{a_1}+E_{a_2}+\cdots+E_{a_l}$

可以推断出

l=\frac{1}{|G|}\sum_{k=1}^n|Z_k|=\frac{1}{|G|}\sum_{j=1}^gc_1(a_j)

等价类的个数=所有置换中一阶循环的个数/所有置换的个数

# 4.2.2 应用

正方形顶点二着色只考虑旋转的等价类个数是6，一共是4个置换

旋转0度的情况 $p_0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)$ ，一阶循环是16

旋转90度状况 $p_1=(1)(2\ 3\ 4\ 5)(6\ 7)(8\ 9\ 10\ 11)(12\ 13\ 14\ 15)(16)$ ，一阶循环是2个

旋转180度 $p_2=(1)(2\ 4)(3\ 5)(6)(7)(8\ 10)(9\ 11)(12\ 14)(13\ 15)(16)$ ，一阶循环是4个

旋转270度 $p_3=(1)(2\ 5\ 4\ 3)(6\ 7)(8\ 11\ 10\ 9)(12\ 15\ 14\ 13)(16)$ ，一阶循环是2个

所以对应的引理公式为 $6=\frac{1}{4}\sum_{f\in G}(16+2+4+2)$

# 4.3 Polya定理

用六种不同颜色涂一正方体，一面一色，且每面颜色不同，会有多少种涂法？？

burnside 引理针对着色图像集的转动群来求解的

求解2着色的不同方案，可以用burnside引理

用六种不同颜色涂一正方体一面一色，不同面可以同色，会有多少种涂法？？

# 4.3.1 概念

设 $\overline{G}=\{\overline{p_1},\overline{p_2},\cdots,\overline{p_g}\}$ 是 $n$ 个对象的一个置换群， $C(\overline{p_k})$ 是置换 $\overline{p_k}$ 的循环的个数，对m种颜色对 $n$ 个对象着色，着色方案数为

l=\frac{1}{|\overline{G}|}\sum_{i=1}^gm^{c(\overline{p_i})}

二者比较

polya定理中的群是作用在 $n$ 个对象上的置换群

Burnside引理中的群是对这 $n$ 个对象染色后的方案集合上的置换群

# 4.3.2 平面题目总结

例子

等边三角形的3个顶点用红，蓝，绿3着色，有多少种方案？？

解；在3维空间考虑，3顶点的置换群 $S_3$

转120度， $(3)^1=2$ 个

对称轴翻转 $(1)(23);(2)(13);(3)(12)=(1)^1(2)^1=3$ 个

不动 $(1)(2)(3)=(1)^3=1$ 个

结果就是 $l=\frac{(2\cdot 3^1+3\cdot 3^2+3^3)}{6}=10$

例子

有3种不同颜色的珠子串成4颗珠子的项链

绕中心转 $\pm 90$ ,为4阶循环 $(4)^1$ ,2个

绕中心转 $180$ ,为2阶循环 $(2)^2$ ,1个

不动 $(1)^4$ ,1个

一共4个置换，方案数 $m=(2\times 3^1+1\times 3^2+1\times 3^4)/4=24$

# 4.3.2 正四面体总结

# 正四面体-顶点的转动群

例子

甲烷 $CH_4$ 的4个键任意用

$H,CI,CH_3,C_2H_5$ 链接，有多少种方案？

$CH_4$ 的结构是一个空间正4面体， $C$ 原则居于正4面体的中心。正4面体的转动群按转动轴分类：

情况	循环	个数
不动旋转 $(A)(B)(C)(D)$	$(1)^4$	1
以顶点与对面的中心连线为轴，按反时针方向旋转120度	$(1)^1(3)^1$	8
以正四面体的 $3$ 对对边之中点联线为旋转转180度	$(2)^2$	2

$(1\times 4^4+8\times 4^2+3\times 4^2)/12=36$

1表示不动循环有1个， $4$ 表示进行的4着色，上面的4表示有多少个循环，不动旋转中有4个循环，所以写4

# 4.3.3 正六面体总结

对象不同，对应的置换不同

对于正六面体转动群

面的置换 6个面
顶点的置换 8个顶点
棱的置换 12条棱

# 1) 正六面体-顶点的转动群

现在研究一下正六面体顶点的置换

情况	循环情况	个数
不动	$(1)^8$	1
面面中心旋转 $\pm 90$ 度	$(4)^2$	$2\times 3=6$ 个
面面中心转180度	$(2)^4$	3
棱中对棱中转180度	$(2)^4$	6
对角线为轴转 $\pm 120$ 度	$(1)^2(3)^2$	$2\times 4=8$

正六面体转动群的阶数为24个

用2种颜色给正6面体的8个顶点着色，有多少种方案？

整理一下的

\frac{((3+6+8)\times 2^4+6\times 2^2+2^\times 8)}{24}=\frac{34+3+32}{3}=23

# 2) 正六面体-面的转动群

现在研究一下正六面体的面的置换

情况	循环	个数
面的置换不动 $(1)(2)(3)(4)(5)(6)$	$(1)^6$	1
面面中心转 $\pm 90$ 度	$(1)^2(4)^1$	$2\times 3=6$ 个
面面中新转 $180$ 度	$(1)^2(2)^2$	3
棱中对棱中转180度	$(2)^3$	6
对角线为轴转 $\pm 120$ 度	$(3)^2$	$2\times 4$

正六面体转动群的阶数为24

\frac{(2^6+6\times 2^3+3\times 2^4+6\times 2^3+8\times 2^2)}{24}=10

如果题目变成用6种不同颜色涂一正方体，一面一色，不同面可以同色，会有多少种涂法？？

\frac{(6^6+6\times 6^3+3\times 6^4+6\times 6^3+8\times 6^2)}{24}

骰子的6个面分别有 $1,2\cdots,6$ 点，有多少种不同的方案？？

# 4.4 母函数型的Polya定理

母函数可以对着色方案进行枚举

比如对3个相同的球用四种颜色(红色，黄色，蓝色，绿色) 涂染，所有可能的颜色组合是？？

有3种不同颜色的珠子，串成4颗珠子的项链，有哪些方案？？、

一共8个置换

方案数为 $m=(2\times 3^1+1\times 3^2+2\times 3^2+2\times 3^3+1\times 3^4)/8=21$

# 4.4.1 概念

母函数的Polya定理得出的方案数为

P(G)=\frac{1}{|\overline{G}|}\sum_{j=1}^g\prod_{k=1}^n S_k^{c_k(\overline{p_j})}

# 4.4.2 例子

例子

等边三角形的3个顶点用红，蓝，绿3着色，有多少种方案？？

它所对应的置换群很简单，如下

旋转 $\pm 120$ 度， $(3)^1$ ,2个。对应的母函数为 $2(r^3+b^3+g^3)$

按照对称轴翻转 $(1)(2)^1$ ，3个,对应的母函数为 $3(r+b+g)(r^2+b^2+g^2)$

不动 $(1)^3$ ，1个，对应的母函数为 $(r+b+g)^3$

一共是6个不同的置换

$l=(2\cdot 3^1+3\cdot 3^2+3^3)/6=10$

$r^3$ 的系数为 $(2+3+1)/6=1$

$rgb$ 的系数 $(3!/(1!1!1!))/6=1$