置换群 | 您所在的位置:网站首页 › 置换原理 › 置换群 |
置换群引入 置换群通常用来解决一些涉及「本质不同」的计数问题,例如用 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 定理。 本页面最近更新:2023/8/14 20:15:10,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:Enter-tainer, Wajov, Early0v0, Great-designer, iamtwz, Ir1d, MegaOwIer, StudyingFather, Tiphereth-A, warzone-oier, Xeonacid本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用 |
CopyRight 2018-2019 实验室设备网 版权所有 |