置换群

引入

置换群通常用来解决一些涉及「本质不同」的计数问题,例如用 3 种颜色给一个立方体染色,求本质不同的方案数(经过翻转后相同的两种方案视为同一种)。

有关群的定义、子群的定义,见 群论基础

置换

置换的相关定义可见 置换和排列

置换群

集合 上的所有置换关于置换的乘法满足封闭性、结合律、有单位元(恒等置换,即每个元素映射成它自己)、有逆元(交换置换表示中的上下两行),因此构成一个群。这个群的任意一个 子群 即称为 置换群

循环置换

循环置换是一类特殊的置换,可表示为

若两个循环置换不含有相同的元素,则称它们是 不相交 的。有如下定理:

任意一个置换都可以分解为若干不相交的循环置换的乘积,例如

该定理的证明也非常简单。如果把元素视为图的节点,映射关系视为有向边,则每个节点的入度和出度都为 1,因此形成的图形必定是若干个环的集合,而一个环即可用一个循环置换表示。

Burnside 引理

前面的都算是铺垫,接下来我们进入正题。

定义

为有限集合, 为一些从 的映射组成的集合。
上的置换群,且 中的映射在 中的置换作用下封闭。
表示 作用在 上产生的所有等价类的集合
(若 中的两个映射经过 中的置换作用后相等,则它们在同一等价类中),则

其中 表示集合 中元素的个数,且

是不是觉得很难懂?别急,请看下面的例子。

解释

我们还是以给立方体染色为例子,则上面式子中一些符号的解释如下:

  • :立方体 6 个面的集合
  • :3 种颜色的集合
  • :直接给每个面染色,不考虑本质不同的方案的集合,共有
  • :各种翻转操作构成的置换群
  • :本质不同的染色方案的集合
  • :对于某一种翻转操作 ,所有直接染色方案中,经过 这种翻转后保持不变的染色方案的集合

接下来我们需要对 中的所有置换进行分析,它们可以分为以下几类(方便起见,将立方体的 6 个面分别称为前、后、上、下、左、右):

  • 不动:即恒等变换,因为所有直接染色方案经过恒等变换都不变,因此它对应的
  • 以两个相对面的中心连线为轴的 旋转:相对面有 3 种选择,旋转的方向有两种选择,因此这类共有 6 个置换。假设选择了前、后两个面中心的连线为轴,则必须要满足上、下、左、右 4 个面的颜色一样,才能使旋转后不变,因此它对应的
  • 以两个相对面的中心连线为轴的 旋转:相对面有 3 种选择,旋转方向的选择对置换不再有影响,因此这类共有 3 个置换。假设选择了前、后两个面中心的连线为轴,则必须要满足上、下两个面的颜色一样,左、右两个面的颜色一样,才能使旋转后不变,因此它对应的
  • 以两条相对棱的中点连线为轴的 旋转:相对棱有 6 种选择,旋转方向对置换依然没有影响,因此这类共有 6 个置换。假设选择了前、上两个面的边界和下、后两个面的边界作为相对棱,则必须要满足前、上两个面的颜色一样,下、后两个面的颜色一样,左、右两个面的颜色一样,才能使旋转后不变,因此它对应的
  • 以两个相对顶点的连线为轴的 旋转:相对顶点有 4 种选择,旋转的方向有两种选择,因此这类共有 8 个置换。假设选择了前面的右上角和后面的左下角作为相对顶点,则必须满足前、上、右三个面的颜色一样,后、下、左三个面的颜色一样,才能使旋转后不变,因此它对应的

因此,所有本质不同的方案数为

证明

看懂本部分需要群论的相关知识,如果你没有学习过群论或者对证明过程没有兴趣,建议直接跳过本部分。

为了证明 Burnside 引理,需要先引入轨道稳定子定理(Orbit-Stabilizer Theorem,也称轨道 - 稳定集定理)。

轨道稳定子定理 的定义同上,,其中 称为 稳定子 称为 轨道,则有

轨道稳定子定理的证明 首先可以证明 的子群,因为

  • 封闭性:若 ,则 ,所以
  • 结合律:显然置换的乘法满足结合律
  • 单位元:因为 ,所以 为恒等置换)
  • 逆元:若 ,则 ,所以

则由群论中的拉格朗日定理,可得

其中 不同的左陪集个数。接下来只需证明 ,我们将其转化为证明存在一个从 所有不同左陪集的双射。令 ,下证 为双射

  • ,两边同时左乘 ,可得 ,所以 ,由陪集的性质可得 ,即
  • 反过来可证,若 ,则有
  • 以上两点说明对于一个 ,只有一个左陪集与其对应,即 是一个从 到左陪集的映射
  • 又显然 有逆映射,因此 是一个双射

    Burnside 引理的证明

所以有

Pólya 定理

定义

在与 Burnside 引理相同的前置条件下, 若 所有 的映射,内容修改为

其中 表示置换 能拆分成的不相交的循环置换的数量。

解释

依然考虑立方体染色问题。分析刚才提到的以相对棱的中点连线为轴的 旋转,如果将前、后、上、下、左、右 6 个面依次编号为 1 到 6,则该置换可以表示为(翻转后原来编号为 1 的面的位置变为了编号为 3 的面,以此类推)

因此 ,与刚才在 Burnside 引理中分析的结果相同。

证明

在 Burnside 引理中,显然 的充要条件是 中每个循环置换的元素都映射到了 中的同一元素,所以 ,即可得 Pólya 定理。


评论