组合数学5-群论

摘要: 群、置换群、共轭类、对换、等价类、Burnside引理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式；在 组合数学2-母函数,递推关系 中我们详细学习了母函数、递推关系；在文章 组合数学3-特殊计数序列,指数型母函数 中我们详细学习了指数型母函数、特殊计数序列。

本文我们看一下组合数学第 5 部分，关于群论的内容，涉及到的概念比较多，主要包括群的定义和性质、置换和置换群、共轭类、对换、等价类、Burnside引理。主要内容如下：

• 可旋转问题举例
  • 六种不同颜色涂正方体，一个面一色，有多少种涂法
  • 正方形顶点用两种颜色染色
• 伽罗华与群论
• 群的定义
  • 封闭性，结合律，单位元，逆元
• 群相关的概念和性质
  • 有限群，阶数，子群，交换群
  • 单位元唯一，消去律，逆元唯一，逆元的运算
• 置换群 $S_{n}$
  • 置换的定义，置换乘法，置换群的定义
• 共轭类
  • 用循环表示置换
  • 置换的格式, 共轭类
  • 洗牌多少轮回到原样
  • 854. 相似度为 K 的字符串
• 对换
  • 任意循环均可表示为若干对换的乘积
  • 奇置换，偶置换，交错群
  • 判断数字华容道的可行性
• 置换群的应用
  • 正方形的 4 种旋转，4 种翻转
  • 欧拉定理
  • 正凸多面体与多面体群
• 等价类
  • k 不动置换类 $Z_{k}$
  • 等价类 $E_{k}$
• Burnside引理
  • 轨道定理及其证明
  • k 不动置换类与 1 阶循环的关系
  • 等价类的最终结论即Burnside引理

---

$1 可旋转问题举例

问题1：六种不同颜色涂正方体，一个面一色，有多少种涂法。

问题2：正方形的 4 个顶点，用红蓝两种颜色染色，有多少种涂法。这个问题称为正方形红蓝二着色问题，后面介绍群论的内容时会多次以本题为例。

以上两个问题，如果正方形或正方体可以旋转，就不简单了。

回顾组合计数中遇到的困难

在组合计数中，有时找出问题通解的表达式困难，我们引入了母函数；有时不好区分讨论的问题类型(区分同类性，避免重复遗漏)，我们引入了容斥原理。

而目前我们遇到的是正方体、正方形等可以转动的情况，为了处理旋转问题，由伽罗华引入群。

$2 伽罗华与群论

• 伽罗华(1811~1832)
• 有了群论之后，开启了计数新世界
• 代数方程可解性 -> 置换群及其子群的结构分析
• 按照伽罗华的说法，群就是要将数学运算归类。

$3 群定义

给定集合 G 和 G 上的二元运算 $\cdot$，如果 $\cdot$ 满足以下性质，则称 G 为群。

• 封闭性: 若 $a,b \in G$, 则 $\exists c \in G$ 使得 $a \cdot b = c$

• 结合律: $\forall a,b,c \in G$ 有 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$

• 有单位元: $\exists e \in G, \forall a \in G, a \cdot e = e \cdot a = a$

• 有逆元: $\forall a \in G, \exists b \in G, a \cdot b = b \cdot a = e$，记为 $b = a^{-1}$

例子：

1. $G = \{0,1,…,n-1\}$ 在模 n 加法下为群
2. 二维欧式空间中的旋转

$4 群相关的概念

无限群，有限群，阶数 $|G|$

• 无限群：无限群指元素个数为无限的群。拓扑群，李群，代数群，算术群，都是无限群。
• 有限群：有限群是具有有限多个元素的群。有限群可分为两大类：可解群与非可解群。
• 阶数 $|G|$：所含元素的个数，称为有限群的阶。

子群

$H \subseteq G$，若 H 在 G 原有群算下也为群，则 H 为 G 的子群。

交换群(Abel群)

$\forall a,b \in G$ 有 $a \cdot b = b \cdot a$。

群的性质

• 单位元唯一 $e_{1} \cdot e_{2} = e_{1} = e_{2}$

• 消去律

$$a \cdot b = a \cdot c \Rightarrow b = c \\ b \cdot a = c \cdot a \Rightarrow b = c \\$$

• 逆元唯一

$$a \cdot a^{-1} = a^{-1} \cdot a = e$$

• 逆元运算

$$(ab...c)^{-1} = c^{-1}...b^{-1}a^{-1}$$

• 有限群的任何元素，经过若干次自己跟自己运算都会形成单位元：G 有限，$a \in G$，则存在最小正整数 r，使得 $a^{r} = e$，且 $a^{-1} = a^{r-1}$

$5 置换群

任何有限群都可以用置换群($S_{n}$)表示。

置换的定义

$[1,2,…,n]$ 到自身的一一映射称为 n 阶置换， [1,2,…,n] 到目标集的置换表示为：

$$\begin{pmatrix} 1 & 2 & ... & n \\ a_{1} & a_{2} & ... & a_{n} \end{pmatrix}$$

其中 $a_{1},a_{2},…,a_{n}$ 为 [1,2,…,n] 的一个排列，同一个置换用这种表示法共有 $n!$ 种表示法。

n 阶置换共有 $n!$ 个，所有 n 阶置换形成的集合换记为 $S_{n}$ (每种置换都表示 1~n 的一种排列)，$S_{n}$ 中的这些元素之间(即置换之间)的运算是长什么样子 — 置换乘法。

置换乘法

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

则

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

置换在置换乘法下满足封闭性、结合律、有单位元、有逆元的性质，因此构成群：

• 封闭性

• 结合律

• 单位元

$$\begin{pmatrix} 1 & 2 & ... & n \\ 1 & 2 & ... & n \end{pmatrix}$$

• 逆元

$$\begin{pmatrix} 1 & 2 & ... & n \\ a_{1} & a_{2} & ... & a_{n} \end{pmatrix}^{-1} = \begin{pmatrix} a_{1} & a_{2} & ... & a_{n} \\ 1 & 2 & ... & n \end{pmatrix}$$

置换群定义

[1,2…,n] 上由多个置换组成的集合在置换乘法下构成群，称为置换群。

任何有限群均可以用置换群表示。

$6 共轭类

用循环表示置换

一个置换可以用若干个循环来表示。

$$(a_{1}, a_{2}, ..., a_{n}) = \begin{pmatrix} a_{1} & a_{2} & ... & a_{n-1} & a_{n} \\ a_{2} & a_{3} & ... & a_{n} & a_{1} \\ \end{pmatrix}$$

例如：

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

不相交的循环

两个循环没有共同文字，称为不相交的，不相交的循环相乘可交换。

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

若 $p=(a_{1}, a_{2}, …, a_{n})$，则 $p^{n} = (1)(2)…(n) = e$，

$S_{n}$ 的任意一个置换 p 可以分解为若干不相交的循环的乘积：

$$P = (a_{1}, a_{2}, ..., a_{k_{1}})(b_{1}, b_{2}, ..., b_{k_{2}})...(h_{1}, h_{2}, ..., h_{k_{l}})$$

其中 $k_{1} + k_{2} + … + k_{l} = n$，设其中 k 阶循环出现的次数为 $c_{k}$，记为 $(k)^{c_{k}}$

置换的格式, 共轭类

$S_{n}$ 中置换的格式：$(1)^{l_{1}}(2)^{l_{2}}…(n)^{l_{n}}$，$\sum\limits_{k=1}\limits^{n}kl_{k} = n$

两个置换格式相同则属于同一共轭类。

例子：洗牌多少轮回到原样

左边 26 张，右边 26 张。一边一张地取。问多少轮后变回原样。

考察 1 轮后的情况：

1 -> 27 -> 2 -> 28 -> 3 -> 29 -> … -> 26 -> 52

将这种置换规则写成公式

$$p[i] = \left\{ \begin{align} (i + 1) / 2 \quad i = 1,3,...,51\\ 1 / 2 + 26 \quad i = 2,4,...,52 \end{align} \right.$$

找到其中的每个循环及其阶数，得到 $p = (1)^{2}(2)(8)^{6}$，最大的阶为 8，因此洗牌 8 次回到原样。

854. 相似度为 K 的字符串

题解参考：【搜索难题】力扣854-相似度为K的字符串。

$7 对换

任意循环均可表示为若干对换的乘积，例如：

$$(123) = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3\\ \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\ \end{pmatrix} = (1 2)(1 3)$$

最终结论，对于循环 $(1,2,…,n)$ 有 $(1, 2, 3, …, n) = (1, 2)(1, 3)…(1, n)$，对换的形式不唯一(起点不唯一)，这里用的是 1 为起点，类似地，还可以是 2 为起点，等等。

将循环拆分成对换，拆分的个数并不唯一，例如 $(1, 2, 3) = (1, 2)(1, 3)(3, 1)(1, 3)$。即：不同的对换表示，可能对应同一个置换。

任意置换表示成对换的个数的奇偶性是唯一的。奇置换，可拆成奇数个对换的乘积，例如 $(1)(2, 5)(2, 7)(4, 6)$，偶置换，可拆成偶数个对换的乘积，例如 $(1)(2)(3)(4)(5)$。

应用：判断数字华容道的可行性

如下图，每一步都需要 0 与相邻数字交换，能否从左边变成右边。

解法:

1. 写出图中的置换，并找出循环的表示，进而将循环表示成对换，发现是一个奇置换
2. 每一步都需要 0 与相邻数字交换，是一个偶置换

因此不可能。

773. 滑动谜题 是一道力扣上的相关题目，题解参考：滑动谜题与八数码。

交错群

n 阶置换群的集合 $S_{n}$ 中所有偶置换构成以一个阶数为 $(n!)/2$ 的子群，称为交错群。

偶置换构成的子群记为 $A_{n}$，奇置换构成的子群记为 $B_{n}$。

$$S_{n} = A_{n} + B_{n} \\ |A_{n}| + |B_{n}| = n! \\ |A_{n}| = n!/2 = |B_{n}| \\$$

实际上奇置换和偶置换是一一对应的。

$8 置换群的应用

正凸多边形的转动，旋转、翻转及其对应的置换

正方形 4 种转动

• 0 degree: $\rho_{1}$
• 90 degree: $\rho_{2}$
• 180 degree: $\rho_{3}$
• 270 degree: $\rho_{4}$

正方形 4 种翻转

欧拉定理

任何凸多面体的顶点数 v，面数 f，棱数 e，有 $v + f - e = 2$

5 种正凸多面体(4, 8, 6, 12, 20)。

正凸多边形的转动在三维的推广：多面体群

多面体在空间运动，前后占同一空间位置，所有的这样的运动的集合，对于以两个这样的运动相继施行作为乘法，构成群，称为多面体群。

正四面体群与 4 阶交错群 $A_{4}$ 同构

正八面体群，正六面体群与 4 阶置换群 $S_{4}$ 同构。

这里提到群的同构的概念，参考近世代数的内容。

$9 等价类

图象在置换群作用下的等价类

回到正方形顶点的红蓝二着色问题。

对于染色问题，有图象和着色方案这两个概念。

图象：固定不动，物理位置上具有不同染色的记为不同的图象，对于正方形的红蓝二着色，有 $2^{4}$ 种图象。

着色方案：经过外力变换，可以完全重合的不同图象为同一个方案(等价的)，寻找不同的着色方案就是寻找不同的等价类。

置换就是外力产生的变换，例如转动，翻转。

图象在这种外力变换下构成置换群，图象在置换群作用下的等价类个数即着色方案数。

正方形红蓝二着色的旋转置换群

考虑正方形红蓝二着色的 4 个旋转置换群：

• 0 degree: $p_{0} = (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)$
• 90 degree: $p_{1} = (1)(2,3,4,5)(6,7)(8,9,10,11)(12,13)(14,15)(16)$
• 180 degree: $p_{2} = (1)(2,4)(3,5)(6)(7)(8,10)(9,11)(12,14)(13,15)(16)$
• 270 degree: $p_{3} = (1)(2,5,4,3)(6,7)(8,11,10,9)(12,15,14,13)(16)$

如果置换 $p_{i}$ 使得图象 k 变为 l，则称 k 和 l 属于同一等价类

k 不动置换类 $Z_{k}$

G 是 [1,n] 上的一个置换群，G 是 $S_{n}$ 的一个子群，$k \in [1,n]$，G 中使 k 元素保持不变的置换全体，称为 k 不动置换类，记为 $Z_{k}$

例如 $G = \{e, (1,2), (3,4), (1,2)(3,4)\}$ 这个置换群。

$Z_{1} = \{e, (3,4)\}$
$Z_{2} = \{e, (3,4)\}$
$Z_{3} = Z_{4} = \{e, (1,2)\}$

正方形红蓝二着色的旋转置换群的 k 不动置换类

等价类 $E_{k}$ (一个等价类呈一个循环)

$\{1,2,…,n\}$ 中的 k，若存在置换 $p_{i}$ 使得 k 变为 l，则称 k 和 l 属于同一个等价类，k 所属的等价类记为 $E_{k}$。

正方形红蓝二着色的旋转置换群的等价类

$|Z_{k}||E_{k}| = |G|$

通过正方形顶点2着色例子，发现 $|Z_{k}||E_{k}| = |G|$。

$10 Burnside引理

概念回顾

• 置换群 G, G 中的每个置换为$a_{i}$

$G = \{a_{1}, a_{2}, …, a_{g}\}$，例如 $G = \{e,(1,2),(3,4),(1,2)(3,4)\}$

• 对每个置换，可以用循环表示。G 中某个置换 $a_{i}$ 的 k 阶循环出现的次数为 $c_{k}a_{i}$

• 各阶循环出现次数均一样的置换，属于同一共轭类。

考虑例子 $G = \{e,(1,2),(3,4),(1,2)(3,4)\}$，对于置换 $a_{1} = e = (1)(2)(3)(4)$，因此一阶循环有 4 个 $c_{1}(a_{1}) = 4$，而对于置换 $a_{4} = (1,2)(3,4)$，$c_{1}(a_{4}) = 0$, $c_{2}(a_{4}) = 2$

• G 中使得某个元素 k 不动的置换类，记为 $Z_{k}$

对于例子 $G = \{e,(1,2),(3,4),(1,2)(3,4)\}$，$Z_{1} = \{e, (3,4)\}$

• G 中 k 所属的等价类记为 $E_{k}$

对于例子 $G = \{e,(1,2),(3,4),(1,2)(3,4)\}$，$E_{1} = E_{2} = \{1,2\}$，$E_{3} = E_{4} = \{3,4\}$

轨道定理 $|Z_{k}||E_{k}| = |G|$

轨道定理: G 是 [1,n] 上的一个置换群，$E_{k}$ 是 [1,n] 在 G 的作用下，包含 k 的等价类，$Z_{k}$ 是 k 不动置换类，有 $|Z_{k}||E_{k}| = |G|$

证明过程如下，用到群的陪集分解：

$|E_{k}| = l$, $E_{k} = \{a_{1}(=k),a_{2},…,a_{l}\}$

不妨设 $a_{1}$ 为 k，且经过某置换可以到 $a_{2},…,a_{l}$，即 $k = a_{1} \stackrel{p_{i}}{\longrightarrow} a_{i}$, $i=1,2,…,l$, $P=\{p_{1},p_{2},…,p_{l}\}$

做子集 $G_{i} = Z_{i}p_{i}, i=1,2,…,l$，则 k 在 $Z_{i}p_{i}$ 的作用下变为 $a_{i}$
($Z_{k}$ 使 k 不动，p_{i} 使得 k($a_{1}$) 变为 $a_{i}$)

$G_{i} \subseteq G$ (G 关于 $Z_{k}$ 的陪集分解)，$i \neq j, G_{i} \cup G_{j} = \varnothing$

$G_{1} + G_{2} + … + G_{l} \subseteq G$

另一方面，$\forall p \in G, k \stackrel{p}{\longrightarrow} a_{j} \stackrel{p_{j}^{-1}}{\longrightarrow} k$

$pp_{j}^{-1} \in Z_{k}$, $p \in Z_{k}p_{j} = G_{j}$

因此 $G \subseteq G_{1} + G_{2} + … + G_{l}$

因此：

$$\begin{align} |G| &= |G_{1}| + |G_{2}| + ... + |G_{l}| \\ &= |Z_{k}p_{1}| + |Z_{k}p_{2}| + ... + |Z_{k}p_{l}| \\ &= |Z_{k}l| = |Z_{k}||E_{k}| \\ \end{align}$$

k 不动置换类与 1 阶循环的关系

还是以 $G = \{e,(1,2),(3,4),(1,2)(3,4)\}$ 为例：

$$c_{1}(a_{1}) = 4 \\ c_{1}(a_{2}) = 2 \\ c_{1}(a_{3}) = 2 \\ c_{1}(a_{4}) = 0 \\ E_{1} = E_{2} = \{1,2\} \\ E_{3} = E_{4} = \{3,4\} \\$$

设计一个表格，其中第 j 行第 k 列：

$$S_{jk} = \left\{ \begin{array}{**lr**} 1, k 在 a_{j} 下不变 \\ 0, k 在 a_{j} 变了 \end{array} \right.$$

• 横着看：对应的置换有多少个元素是不变的，即一阶循环有几个
• 竖着看：对应的元素有多少个置换让其不动，即 k 不动置换类的个数

$$\sum\limits_{j=1}\limits^{g}\sum\limits_{k=1}\limits^{n}S_{jk} = \sum\limits_{k=1}\limits^{n}|Z_{k}| = \sum\limits_{j=1}\limits^{g}c_{1}(a_{j})$$

把上面的例子改为更一般的形式，表格如下：

$$\sum\limits_{k=1}\limits^{n}|Z_{k}| = \sum\limits_{j=1}\limits^{g}c_{1}(a_{j})$$

计算等价类个数

在轨道定理和 k 不动置换类与 1 阶循环的关系的基础上计算等价类个数

$$l = \frac{1}{|G|}\sum\limits_{j=1}\limits^{g}c_{1}(a_{j})$$

等价类的最终结论即 Burnside 引理

$G = \{a_{1}, a_{2}, …, a_{g}\}$ 为目标集 [1,n] 上的置换群。每个置换都写成不相交循环的乘积。$c_{1}(a_{k})$ 是在置换 $a_{k}$ 的作用下不动点的个数，也就是长度为 1 的循环的个数。G 将 [1,n] 划分成 l 个等价类。

$$l = \frac{1}{|G|}\sum\limits_{j=1}\limits^{g}c_{1}(a_{j})$$

例子：正方形顶点二着色只考虑旋转的等价类个数

在第 9 小节提到正方形红蓝二着色的旋转置换群：

枚举的结果：等价类的个数为 6，下面看 Burnside 引理的做法。

首先把置换写出类，然后看置换的个数，和 1 阶循环的个数：

$$l = \frac{1}{4}\sum\limits_{f \in G}(16 + 2 + 4 + 2) = 6$$

针对图像集的转动群求解的困难

针对图像集的转动群求解的困难：

当颜色变多时，理论上可以用 Burnside 定理，但极其复杂，Polya 定理可以解决这个困难，我们后面再学习。

最开始的两个问题：

1. 六种不同颜色涂正方体，一个面一色，有多少种涂法
2. 正方形的 4 个顶点，用红蓝两种颜色染色，有多少种涂法。这个问题称为正方形红蓝二着色问题，后面介绍群论的内容时会多次以本题为例。

第一个问题还不能解决，这涉及到正六面体转动群，我们后面再学习。

$11 群论拾遗

各种群：魔方群…

正规子群，商群。

单群：不能继续分解的群，具有素数的性质。

1823年伽罗华：交错群 $A_{n}$ 对于所有 $n >= 5$ 都是单群，代数方程可解性问题解决。

16族有限李群：离散域上的矩阵组成的群。

18个有限单群家族+26个单独存在的有限单群，这就是所有的有限单群。证明跨越百年，2004年解决。

1872年：Sylow定理，开启有限群结构的研究。

最大的散在单群：魔群。

1979: 魔群月光猜想，1992年证明(1998年菲尔茨奖)，天书。

---

---