置换群
置换群（英文：Permutation group）是一类具体的有限群。有限集合到自身的双射称为一个置换，有限集合Ω上的一些置换组成的集合，在置换的乘法下所组成的群，称为置换群。
群的思想最早可见于古希腊数学家欧几里得（Euclid）的著作《几何原本》中，但并没有真正出现群的概念。18世纪代数从属于分析，约瑟夫·路易斯·拉格朗日（Lagrange,Joseph Louis）在讨论代数方程根之间的置换时，已有置换群的概念。在拉格朗日工作的影响下，约翰·卡尔·弗里德里希·高斯（Gauss）、鲁菲尼（Ruffini）等人讨论了特殊的代数方程的可解性问题。在对于高于四次的一般代数方程可解性的工作中，鲁菲尼的置换理论不再只是起计算方法的作用，而是可解性的一种结构部分，但仍然没有给出“群”的概念。直到1830年，法国数学家埃瓦里斯特·伽罗瓦（Evariste Galois）在专业意义上第一次使用“群”这个术语，并在《关于方程根式可解的条件的论文》（Mémoire sur les condictions de résolubilit édes équations parradicaux）中定义“方程的群”，把方程的系数域对应到根的某种置换群，用群论的方法来研究代数方程的解。方程的群是伽罗瓦思想理论的核心概念，它被定义为保持根的有理函数不变的置换群，后来被称为伽罗瓦群，揭示了方程的系数域与根的置换群对应的关键思想。
任何一个有限群都同构于一个置换群，故置换群比抽象群更加直观。在研究置换群的过程中，凯莱定理、拉格朗日定理等定理对于置换群的研究有辅助作用。置换群在物理学、密码学以及生活应用等领域中有着广泛的应用。
简史
早期研究
群的思想最早可见于古希腊数学家欧几里得（Euclid）的著作《几何原本》中，但并没有真正出现群的概念。18世纪代数从属于分析，约瑟夫·拉格朗日（Lagrange,Joseph Louis）在讨论代数方程根之间的置换时，已有置换群的概念。在拉格朗日工作的影响下，约翰·卡尔·弗里德里希·高斯（Gauss）解决了一类特殊的代数方程的可解性问题；鲁菲尼（Ruffini）首先证明高于四次的一般方程不能用根式法求解。在对于高于四次的一般代数方程可解性的工作中，鲁菲尼的置换理论不再只是起计算方法的作用，而是可解性的一种结构部分，但仍然没有给出“群”的概念。
后续发展
1830年前后，法国数学家埃瓦里斯特·伽罗瓦（Evariste Galois）在专业意义上第一次使用“群”这个术语，并在《关于方程根式可解的条件的论文》（Mémoire sur les condictions de résolubilit édes équations parradicaux）中定义“方程的群”，把方程的系数域对应到根的某种置换群，用群论的方法来研究代数方程的解。方程的群是伽罗瓦思想理论的核心概念，它被定义为保持根的有理函数不变的置换群，后来被称为伽罗瓦群，揭示了方程的系数域与根的置换群对应的关键思想。
从埃瓦里斯特·伽罗瓦开始，代数的研究中心由代数方程逐渐转变为各种抽象的代数结构。数学家卡米尔·若尔当（Camille Jordan）和戴德金（Dedekind）等人用方程可解性理论的语言阐释并发展伽罗瓦的工作，研究代数方程的可解性理论与置换理论之间的相互关系，从有关代数方程可解性的理论发展为有关域和群的结构的一般化理论。
定义
群
一个群是指·个非空集合，它满足下列4个条件：
(1)在上定义了一个（二元）代数运算；
(2) 上的运算适合结合律；
(3)中有一个元素，具有性质：,，称是的单位元素；
(4)中每一个元素都有逆元。
置换群
定义：有限集合到自身的双射称为一个置换，有限集合上的一些置换组成的集合，在置换的乘法下所组成的群，称为置换群。
例如：一个有限集合,有个元,的全体置换作成一个群。
性质
1.每个置换都可以分解为若干不相交轮换的乘积；
2.每个轮换都可以分解为若干对换的乘积；
4.一个置换总可以表为若干个对换的乘积。
5.（同构性）设是上的置换群，是上的置换群，是到上的一一对应,，若满足下列条件，则称是到的置换同构：
(1)是群同构；
(2)存在到的一一对应，使得对，有。
6.（同态性）若为任意有限群，为一有限集合，则称到对称群内的任意同态为的一个置换表示。
置换的循环
定义
设置换将集合中的换为,换为,换为,换为，称为阶循环置换（或轮换），记为或。
例如，。
性质
1.设循环置换，且互不相同，称与不相交，则满足交换律，即；
2.每一个个元的置换都可以写成若干个互相没有共同数字的（不相连的）循环置换的乘积；
3.一个2阶循环置换称为对换（或换位），任何循环置换都可以表示为若干个对换之积，但表示方式不唯一；
4.每个循环置换的对换表示中，对换个数的奇偶性是唯一确定的，从而一个置换在它的不同的对换分解表示式中所含的对换个数的奇偶性是不变的；
5.可以分解为奇数个对换之积的置换称为奇置换，可以分解为偶数个对换之积的置换称为偶置换。
相关概念
对称群
对称群是含置换群为子类的一类具体的有限群。有限集合上全体置换组成的群，称为上对称群，记为或当时，对称群和是置换同构的，所以也把记为的阶为一切次数为的置换群都可以看成的子群。
轨道
集合在置换群下保持不变的某些子群。设是集合上的置换群，是子集合，若满足下列两个条件，则称为的一个轨道：
1.中任何点在中任何元素下的像都在内；
2.对中任何两个点，总有G中一个元素g，使。
若则集合就是在上包含点的轨道。若是上的置换群，而本身是一个轨道，则称是上的传递群。
传递群的秩
设是上的传递群，而为中的点。是上的置换群，它有轨道，若，而，则在上的轨道就是，这里，这说明一个点的稳定子群在上的轨道个数以及这些轨道的长度与点的选取无关，它们反映了群的性质，把任意一点的稳定子群的轨道个数称为的秩。
传递群的秩总是大于的整数，秩的重传递群称为双传递群，多重传递群是本原群。
本原群
集合上的传递置换群，若没有非平凡完全区系，则称为上的本原群，否则，即具有非平凡完全区系，就称为非本原群。
在上是本原的当且仅当对中的任何两个不同的点和的任一非空真子集，都有中一个元素，使，而。在上是本原群的另一个充分必要条件是，对任何,是的极大子群。
弗罗贝尼乌斯群
弗罗贝尼乌斯群是一类重要的传递置换群。上的传递置换群，若不是正则群，但中除去恒等置换外的各元素至多有一个不动点，则称为弗罗贝尼乌斯群。当时，在交错群内只有恒等置换、二阶元素和三阶元素，其中二阶元素都没有不动点，而三阶元素都恰有一个不动点，从而为弗罗贝尼乌斯群。
相关定理
凯莱定理
定理：若是一个群，则存在集，使得同构于上的一个置换群。
该定理把对抽象群的研究归结为对置换群的研究，当是阶有限群时，由凯莱定理可知，不同构的阶群只能有有限多个。
拉格朗日定理
令的次数为如果有个重根，即作用于保持不变的置换的个数，则必有一个次数为的最简函数使得
并且的不同值的个数为。如果在方程个根的全体置换下的不同值为记保持不变的置换构成的集合为且
在该定理的证明中，约瑟夫·拉格朗日得到以上这个置换集所含的置换个数相等，且
。于是。
方程个根的全体置换被划分成类，且保持根的有理函数不变的置换的个数是全体置换个数的因子，即群论中的拉格朗日定理。
弗罗贝尼乌斯定理
定理：若是上的一个弗罗贝尼乌斯群，则中全部在上没有不动点的元素，连同的单位元素组成的一个正则的正规子群。
一个抽象群，若它有一个子群，使得对的任何不包含在内的元素等式成立，则也称是（关于的）一个弗罗贝尼乌斯群。弗罗贝尼乌斯群是反映同构于一个传递置换群，后者作为置换群是弗罗贝尼乌斯群，并且在同构下，的像恰好是一个点的稳定子群。
推广
稳定子群
稳定子群是置换群内的一种特殊子群。置换群中把某点保持不动的全体元素组成的子群。它记为称为在内的稳定子群。
若是中另外一个点，而中元素使，则所以同一轨道内的各点互相共轭的稳定子群。
置换同构
置换同构式是一种特殊的群同构。两个置换群间的一一对应，它是群同构且相应的置换在本质上是相同的。
设是上的置换群，是上的置换群，是到上的一一对应，若满足下列条件，则称是到的置换同构：
1.是群同构；
2.存在到的一一对应，使得对，有。
多重传递群
多重传递群是比传递群有着更强的传递性质的置换群。
设是一个自然数，而是上的一个置换群，且若对的任意两个有序元子集和都可以找到一个元素，使得则称在上是重传递的。
应用
物理学
从减少搜索过程中的时间消耗、增加算法搜索的准确性和可控性等多方面进行考虑， 提出了一种基于置换群的多粒子量子行走搜索算法。 首先分析得到置换群在空间中可看成一个闭环， 定义了置换集合， 并且通过同构映射将数据点所在数据集映射到定义的置换集， 使得置换集合中元素数据点形成一一对应的关系。 其次， 根据给定初始态和硬币算符， 在数据点集与置换集合张成的搜索空间中利用多粒子的量子行走在环上进行目标数据搜索。 最后， 根据函数找到目标数据， 并用量子态存储数值， 用于形成搜索算法的反馈控制；同时通过控制硬币算符从而控制量子行走在环上的行走方向， 增加搜索的可操作性与准确性。
密码学
1985年美洲密码学年会上，S.Wolfram首次提出了将细胞自动机的初始状态作为密钥，使用细胞自动机前向迭代产生的伪随机序列作为序列密码，从而开创了细胞自动机在密码学中的应用研究。P.Guan根据复杂系统的多项式方程求逆的困难性，提出了一种基于混合细胞自动机的公钥加密技术”。S.Nandi等人则根据细胞自动机循环群特性提出了基于置换群基本变换的分组加密技术，但由于其密钥为所有细胞单元为不规则且具有偶置换群特性的细胞自动机本身，从而使得其密钥的数量大大受限。将外部向量引入到具有置换群特性的细胞自动机中，并提出了具有输入的细胞自动机置换群加密技术，其密钥由细胞自动机本身、细胞自动机的状态迭代次数和细胞自动机的输入向量等三部分组成，从而使得本方法比S.Nandi等人的方法具有更大的密钥空间和更灵活的加解密方式。
生活应用
在穿珠中的应用。
例：有n个不同的爆珠，要求用线把这些珠子穿成若干个环，而且每个珠子只能被一条线穿过，不同的穿珠顺序是不同的穿法，共有多少种穿珠办法。
解：把个珠子分别用来表示构成一个集合，记为则则个不同的珠子按照规定的穿珠办法的总数等于元有限集的所有置换的个数，因为含有个元素的集合共有个双射变换，即元有限集共有个置换。因此，对于个不同的珠子，共有个穿珠办法。