组合数学5-群论

  |  

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

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


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

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

  • 可旋转问题举例
    • 六种不同颜色涂正方体,一个面一色,有多少种涂法
    • 正方形顶点用两种颜色染色
  • 伽罗华与群论
  • 群的定义
    • 封闭性,结合律,单位元,逆元
  • 群相关的概念和性质
    • 有限群,阶数,子群,交换群
    • 单位元唯一,消去律,逆元唯一,逆元的运算
  • 置换群 $S_{n}$
    • 置换的定义,置换乘法,置换群的定义
  • 共轭类
  • 对换
    • 任意循环均可表示为若干对换的乘积
    • 奇置换,偶置换,交错群
    • 判断数字华容道的可行性
  • 置换群的应用
    • 正方形的 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}$

  • 消去律

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

$5 置换群

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

置换的定义

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

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

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

置换乘法

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

  • 封闭性

  • 结合律

  • 单位元

  • 逆元

置换群定义

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

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

$6 共轭类

用循环表示置换

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

例如:

不相交的循环

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

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

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

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

其中 $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 = (1)^{2}(2)(8)^{6}$,最大的阶为 8,因此洗牌 8 次回到原样。

854. 相似度为 K 的字符串

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

$7 对换

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

最终结论,对于循环 $(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}$。

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

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

因此:

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

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

设计一个表格,其中第 j 行第 k 列:

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

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

计算等价类个数

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

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

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

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

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

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

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

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

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

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

最开始的两个问题:

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

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

$11 群论拾遗

各种群:魔方群…

正规子群,商群。

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

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

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

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

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

最大的散在单群:魔群。

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

















Share