WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
置换群 - 数学
author: Wajov 置换群通常用来解决一些涉及“本质不同”的计数问题,例如用 3 种颜色给一个立方体染色,求本质不同的方案数(经过翻转后相同的两种方案视为同一种)。 ## 群 ### 群的定义 若集合 $S\neq\varnothing$ 和 $S$ 上的运算 $\cdot$ 构成的代数结构 $(S,\cdot)$ 满足以下性质: - 封闭性: $\forall a,b\in S,a\cdot b\in S$ - 结合律: $\forall a,b,c\in S,(a\cdot b)\cdot c=a\cdot(b\cdot c)$ - 单位元: $\exists e\in S,\forall a\in S,e\cdot a=a\cdot e=a$ - 逆元: $\forall a\in S,\exists b\in S,a\cdot b=b\cdot a=e$ ,称 $b$ 为 $a$ 的逆元,记为 $a^{-1}$ 则称 $(S,\cdot)$ 为一个 **群** 。例如,整数集和整数间的加法 $(\mathbb{Z},+)$ 构成一个群,单位元是 0,一个整数的逆元是它的相反数。 ### 子群的定义 若 $(S,\cdot)$ 是群, $T$ 是 $S$ 的非空子集,且 $(T,\cdot)$ 也是群,则称 $(T,\cdot)$ 是 $(S,\cdot)$ 的 **子群** 。 ## 置换 ### 置换的定义 有限集合到自身的双射(即一一对应)称为置换。集合 $S=\\{a_1,a_2,\dots,a_n\\}$ 上的置换可以表示为 $$ f=\begin{pmatrix}a_1,a_2,\dots,a_n\\\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix} $$ 意为将 $a_i$ 映射为 $a_{p_i}$ ,其中 $p_1,p_2,\dots,p_n$ 是 $1,2,\dots,n$ 的一个排列。显然 $S$ 上所有置换的数量为 $n!$ 。 ### 置换的乘法 对于两个置换 $f=\begin{pmatrix}a_1,a_2,\dots,a_n\\\\a_{p_1},a_{p_2},\dots,a_{p_n}\end{pmatrix}$ 和 $g=\begin{pmatrix}a_{p_1},a_{p_2},\dots,a_{p_n}\\\\a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix}$ , $f$ 和 $g$ 的乘积记为 $f\circ g$ ,其值为 $$ f\circ g=\begin{pmatrix}a_1,a_2,\dots,a_n\\\\ a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix} $$ 简单来说就是先后经过 $f$ 的映射,再经过 $g$ 的映射。 ### 置换群 易证,集合 $S$ 上的所有置换关于置换的乘法满足封闭性、结合律、有单位元(恒等置换,即每个元素映射成它自己)、有逆元(交换置换表示中的上下两行),因此构成一个群。这个群的任意一个 **子群** 即称为 **置换群** 。 ### 循环置换 循环置换是一类特殊的置换,可表示为 $$ (a_1,a_2,\dots,a_m)=\begin{pmatrix}a_1,a_2,\dots,a_{m-1},a_m\\\\ a_2,a_3,\dots,a_m,a_1\end{pmatrix} $$ 若两个循环置换不含有相同的元素,则称它们是 **不相交** 的。有如下定理: 任意一个置换都可以分解为若干不相交的循环置换的乘积,例如 $$ \begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\\\ a_3,a_1,a_2,a_5,a_4\end{pmatrix}=(a_1,a_3,a_2)\circ(a_4,a_5) $$ 该定理的证明也非常简单。如果把元素视为图的节点,映射关系视为有向边,则每个节点的入度和出度都为 1,因此形成的图形必定是若干个环的集合,而一个环即可用一个循环置换表示。 ## Burnside 引理 前面的都算是铺垫,接下来我们进入正题。 ### 描述 设 $A$ 和 $B$ 为有限集合, $X=B^A$ 表示所有从 $A$ 到 $B$ 的映射。 $G$ 是 $A$ 上的置换群, $X/G$ 表示 $G$ 作用在 $X$ 上产生的所有等价类的集合(若 $X$ 中的两个映射经过 $G$ 中的置换作用后相等,则它们在同一等价类中),则 $$ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| $$ 其中 $|S|$ 表示集合 $S$ 中元素的个数,且 $$ X^g=\\{x|x\in X,g(x)=x\\} $$ 是不是觉得很难懂?别急,请看下面的例子。 ### 举例 我们还是以给立方体染色为例子,则上面式子中一些符号的解释如下: - $A$ :立方体 6 个面的集合 - $B$ :3 种颜色的集合 - $X$ :直接给每个面染色,不考虑本质不同的方案的集合,共有 $3^6$ 种 - $G$ :各种翻转操作构成的置换群 - $X/G$ :本质不同的染色方案的集合 - $X^g$ :对于某一种翻转操作 $g$ ,所有直接染色方案中,经过 $g$ 这种翻转后保持不变的染色方案的集合 ![](../images/cube.png) 接下来我们需要对 $G$ 中的所有置换进行分析,它们可以分为以下几类(方便起见,将立方体的 6 个面分别称为前、后、上、下、左、右): - 不动:即恒等变换,因为所有直接染色方案经过恒等变换都不变,因此它对应的 $|X^g|=3^6$ - 以两个相对面的中心连线为轴的 $90^\circ$ 旋转:相对面有 3 种选择,旋转的方向有两种选择,因此这类共有 6 个置换。假设选择了前、后两个面中心的连线为轴,则必须要满足上、下、左、右 4 个面的颜色一样,才能使旋转后不变,因此它对应的 $|X^g|=3^3$ - 以两个相对面的中心连线为轴的 $180^\circ$ 旋转:相对面有 3 种选择,旋转方向的选择对置换不再有影响,因此这类共有 3 个置换。假设选择了前、后两个面中心的连线为轴,则必须要满足上、下两个面的颜色一样,左、右两个面的颜色一样,才能使旋转后不变,因此它对应的 $|X^g|=3^4$ - 以两条相对棱的中点连线为轴的 $180^\circ$ 旋转:相对棱有 6 种选择,旋转方向对置换依然没有影响,因此这类共有 6 个置换。假设选择了前、上两个面的边界和下、后两个面的边界作为相对棱,则必须要满足前、上两个面的颜色一样,下、后两个面的颜色一样,左、右两个面的颜色一样,才能使旋转后不变,因此它对应的 $|X^g|=3^3$ - 以两个相对顶点的连线为轴的 $120^\circ$ 旋转:相对顶点有 4 种选择,旋转的方向有两种选择,因此这类共有 8 个置换。假设选择了前面的右上角和后面的左下角作为相对顶点,则必须满足前、上、右三个面的颜色一样,后、下、左三个面的颜色一样,才能使旋转后不变,因此它对应的 $|X^g|=3^2$ 因此,所有本质不同的方案数为 $$ \frac{1}{1+6+3+6+8}(3^6+6\times3^3+3\times3^4+6\times3^3+8\times3^2)=57 $$ ### 证明 看懂本部分需要群论的相关知识,如果你没有学习过群论或者对证明过程没有兴趣,建议直接跳过本部分。 为了证明 Burnside 引理,需要先引入轨道稳定子定理(Orbit-Stabilizer Theorem,也称轨道 - 稳定集定理)。 **轨道稳定子定理** $G$ 和 $X$ 的定义同上, $\forall x\in X,G^x=\\{g|g(x)=x,g\in G\\},G(x)=\\{g(x)|g\in G\\}$ ,其中 $G^x$ 称为 $x$ 的 **稳定子** , $G(x)$ 称为 $x$ 的 **轨道** ,则有 $$ |G|=|G^x||G(x)| $$ **轨道稳定子定理的证明** 首先可以证明 $G^x$ 是 $G$ 的子群,因为 - 封闭性:若 $f,g\in G$ ,则 $f\circ g(x)=f(g(x))=f(x)=x$ ,所以 $f\circ g\in G^x$ - 结合律:显然置换的乘法满足结合律 - 单位元:因为 $I(x)=x$ ,所以 $I\in G^x$ ( $I$ 为恒等置换) - 逆元:若 $g\in G^x$ ,则 $g^{-1}(x)=g^{-1}(g(x))=g^{-1}\circ g(x)=I(x)=x$ ,所以 $g^{-1}\in G^x$ 则由群论中的拉格朗日定理,可得 $$ |G|=|G^x|[G:G^x] $$ 其中 $[G:G^x]$ 为 $G^x$ 不同的左陪集个数。接下来只需证明 $|G(x)|=[G:G^x]$ ,我们将其转化为证明存在一个从 $G(x)$ 到 $G^x$ 所有不同左陪集的双射。令 $\varphi(g(x))=gG^x$ ,下证 $\varphi$ 为双射 - 若 $g(x)=f(x)$ ,两边同时左乘 $f^{-1}$ ,可得 $f^{-1}\circ g(x)=I(x)=x$ ,所以 $f^{-1}\circ g\in G^x$ ,由陪集的性质可得 $(f^{-1}\circ g)G^x=G^x$ ,即 $gG^x=fG^x$ - 反过来可证,若 $gG^x=fG^x$ ,则有 $g(x)=f(x)$ - 以上两点说明对于一个 $g(x)$ ,只有一个左陪集与其对应,即 $\varphi$ 是一个从 $G(x)$ 到左陪集的映射 - 又显然 $\varphi$ 有逆映射,因此 $\varphi$ 是一个双射 **Burnside 引理的证明** $$ \begin{align} \sum_{g\in G}|X^g|&=|\\{(g,x)|(g,x)\in G\times X,g(x)=x\\}|\\\\ &=\sum_{x\in X}|G^x|\\\\ &=\sum_{x\in X}\frac{|G|}{|G(x)|}\quad\quad\quad(轨道稳定子定理)\\\\ &=|G|\sum_{x\in X}\frac{1}{|G(x)|}\\\\ &=|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|G(x)|}\\\\ &=|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|Y|}\\\\ &=|G|\sum_{Y\in X/G}1\\\\ &=|G||X/G| \end{align} $$ 所以有 $$ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| $$ ## Pólya 定理 ### 描述 前置条件与 Burnside 引理相同,内容修改为 $$ |X/G|=\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)} $$ 其中 $c(g)$ 表示置换 $g$ 能拆分成的不相交的循环置换的数量。 ### 举例 依然考虑立方体染色问题。分析刚才提到的以相对棱的中点连线为轴的 $180^\circ$ 旋转,如果将前、后、上、下、左、右 6 个面依次编号为 1 到 6,则该置换可以表示为(翻转后原来编号为 1 的面的位置变为了编号为 3 的面,以此类推) $$ \begin{pmatrix}1,3,2,4,5,6\\\\ 3,1,4,2,6,5\end{pmatrix}=(1,3)\circ(2,4)\circ(5,6) $$ 因此 $c(g)=3,|B|^{c(g)}=3^3$ ,与刚才在 Burnside 引理中分析的结果相同。 ### 证明 在 Burnside 引理中,显然 $g(x)=x$ 的充要条件是 $x$ 将 $g$ 中每个循环置换的元素都映射到了 $B$ 中的同一元素,所以 $|X^g|=|B|^{c(g)}$ ,即可得 Pólya 定理。