置換群（英文：Permutation group）是一類具體的有限群。有限集合到自身的雙射稱為一個(gè)置換，有限集合Ω上的一些置換組成的集合，在置換的乘法下所組成的群，稱為置換群。
群的思想最早可見于古希臘數(shù)學(xué)家歐幾里得（Euclid）的著作《幾何原本》中，但并沒有真正出現(xiàn)群的概念。18世紀(jì)代數(shù)從屬于分析，約瑟夫·路易斯·拉格朗日（Lagrange,Joseph Louis）在討論代數(shù)方程根之間的置換時(shí)，已有置換群的概念。在拉格朗日工作的影響下，約翰·卡爾·弗里德里希·高斯（Gauss）、魯菲尼（Ruffini）等人討論了特殊的代數(shù)方程的可解性問題。在對(duì)于高于四次的一般代數(shù)方程可解性的工作中，魯菲尼的置換理論不再只是起計(jì)算方法的作用，而是可解性的一種結(jié)構(gòu)部分，但仍然沒有給出“群”的概念。直到1830年，法國數(shù)學(xué)家埃瓦里斯特·伽羅瓦（Evariste Galois）在專業(yè)意義上第一次使用“群”這個(gè)術(shù)語，并在《關(guān)于方程根式可解的條件的論文》（Mémoire sur les condictions de résolubilit édes équations parradicaux）中定義“方程的群”，把方程的系數(shù)域?qū)?yīng)到根的某種置換群，用群論的方法來研究代數(shù)方程的解。方程的群是伽羅瓦思想理論的核心概念，它被定義為保持根的有理函數(shù)不變的置換群，后來被稱為伽羅瓦群，揭示了方程的系數(shù)域與根的置換群對(duì)應(yīng)的關(guān)鍵思想。
任何一個(gè)有限群都同構(gòu)于一個(gè)置換群，故置換群比抽象群更加直觀。在研究置換群的過程中，凱萊定理、拉格朗日定理等定理對(duì)于置換群的研究有輔助作用。置換群在物理學(xué)、密碼學(xué)以及生活應(yīng)用等領(lǐng)域中有著廣泛的應(yīng)用。
簡史
早期研究
群的思想最早可見于古希臘數(shù)學(xué)家歐幾里得（Euclid）的著作《幾何原本》中，但并沒有真正出現(xiàn)群的概念。18世紀(jì)代數(shù)從屬于分析，約瑟夫·拉格朗日（Lagrange,Joseph Louis）在討論代數(shù)方程根之間的置換時(shí)，已有置換群的概念。在拉格朗日工作的影響下，約翰·卡爾·弗里德里希·高斯（Gauss）解決了一類特殊的代數(shù)方程的可解性問題；魯菲尼（Ruffini）首先證明高于四次的一般方程不能用根式法求解。在對(duì)于高于四次的一般代數(shù)方程可解性的工作中，魯菲尼的置換理論不再只是起計(jì)算方法的作用，而是可解性的一種結(jié)構(gòu)部分，但仍然沒有給出“群”的概念。
后續(xù)發(fā)展
1830年前后，法國數(shù)學(xué)家埃瓦里斯特·伽羅瓦（Evariste Galois）在專業(yè)意義上第一次使用“群”這個(gè)術(shù)語，并在《關(guān)于方程根式可解的條件的論文》（Mémoire sur les condictions de résolubilit édes équations parradicaux）中定義“方程的群”，把方程的系數(shù)域?qū)?yīng)到根的某種置換群，用群論的方法來研究代數(shù)方程的解。方程的群是伽羅瓦思想理論的核心概念，它被定義為保持根的有理函數(shù)不變的置換群，后來被稱為伽羅瓦群，揭示了方程的系數(shù)域與根的置換群對(duì)應(yīng)的關(guān)鍵思想。
從埃瓦里斯特·伽羅瓦開始，代數(shù)的研究中心由代數(shù)方程逐漸轉(zhuǎn)變?yōu)楦鞣N抽象的代數(shù)結(jié)構(gòu)。數(shù)學(xué)家卡米爾·若爾當(dāng)（Camille Jordan）和戴德金（Dedekind）等人用方程可解性理論的語言闡釋并發(fā)展伽羅瓦的工作，研究代數(shù)方程的可解性理論與置換理論之間的相互關(guān)系，從有關(guān)代數(shù)方程可解性的理論發(fā)展為有關(guān)域和群的結(jié)構(gòu)的一般化理論。
定義
群
一個(gè)群是指·個(gè)非空集合，它滿足下列4個(gè)條件：
(1)在上定義了一個(gè)（二元）代數(shù)運(yùn)算；
(2) 上的運(yùn)算適合結(jié)合律；
(3)中有一個(gè)元素，具有性質(zhì)：,，稱是的單位元素；
(4)中每一個(gè)元素都有逆元。
置換群
定義：有限集合到自身的雙射稱為一個(gè)置換，有限集合上的一些置換組成的集合，在置換的乘法下所組成的群，稱為置換群。
例如：一個(gè)有限集合,有個(gè)元,的全體置換作成一個(gè)群。
性質(zhì)
1.每個(gè)置換都可以分解為若干不相交輪換的乘積；
2.每個(gè)輪換都可以分解為若干對(duì)換的乘積；
3.每一個(gè)有限群都與一個(gè)置換群同構(gòu)；
4.一個(gè)置換總可以表為若干個(gè)對(duì)換的乘積。
5.（同構(gòu)性）設(shè)是上的置換群，是上的置換群，是到上的一一對(duì)應(yīng),，若滿足下列條件，則稱是到的置換同構(gòu)：
(1)是群同構(gòu)；
(2)存在到的一一對(duì)應(yīng)，使得對(duì)，有。
6.（同態(tài)性）若為任意有限群，為一有限集合，則稱到對(duì)稱群內(nèi)的任意同態(tài)為的一個(gè)置換表示。
置換的循環(huán)
定義
設(shè)置換將集合中的換為,換為,換為,換為，稱為階循環(huán)置換（或輪換），記為或。
例如，。
性質(zhì)
1.設(shè)循環(huán)置換，且互不相同，稱與不相交，則滿足交換律，即；
2.每一個(gè)個(gè)元的置換都可以寫成若干個(gè)互相沒有共同數(shù)字的（不相連的）循環(huán)置換的乘積；
3.一個(gè)2階循環(huán)置換稱為對(duì)換（或換位），任何循環(huán)置換都可以表示為若干個(gè)對(duì)換之積，但表示方式不唯一；
4.每個(gè)循環(huán)置換的對(duì)換表示中，對(duì)換個(gè)數(shù)的奇偶性是唯一確定的，從而一個(gè)置換在它的不同的對(duì)換分解表示式中所含的對(duì)換個(gè)數(shù)的奇偶性是不變的；
5.可以分解為奇數(shù)個(gè)對(duì)換之積的置換稱為奇置換，可以分解為偶數(shù)個(gè)對(duì)換之積的置換稱為偶置換。
相關(guān)概念
對(duì)稱群
對(duì)稱群是含置換群為子類的一類具體的有限群。有限集合上全體置換組成的群，稱為上對(duì)稱群，記為或當(dāng)時(shí)，對(duì)稱群和是置換同構(gòu)的，所以也把記為的階為一切次數(shù)為的置換群都可以看成的子群。
軌道
集合在置換群下保持不變的某些子群。設(shè)是集合上的置換群，是子集合，若滿足下列兩個(gè)條件，則稱為的一個(gè)軌道：
1.中任何點(diǎn)在中任何元素下的像都在內(nèi)；
2.對(duì)中任何兩個(gè)點(diǎn)，總有G中一個(gè)元素g，使。
若則集合就是在上包含點(diǎn)的軌道。若是上的置換群，而本身是一個(gè)軌道，則稱是上的傳遞群。
傳遞群的秩
設(shè)是上的傳遞群，而為中的點(diǎn)。是上的置換群，它有軌道，若，而，則在上的軌道就是，這里，這說明一個(gè)點(diǎn)的穩(wěn)定子群在上的軌道個(gè)數(shù)以及這些軌道的長度與點(diǎn)的選取無關(guān)，它們反映了群的性質(zhì)，把任意一點(diǎn)的穩(wěn)定子群的軌道個(gè)數(shù)稱為的秩。
傳遞群的秩總是大于的整數(shù)，秩的重傳遞群稱為雙傳遞群，多重傳遞群是本原群。
本原群
集合上的傳遞置換群，若沒有非平凡完全區(qū)系，則稱為上的本原群，否則，即具有非平凡完全區(qū)系，就稱為非本原群。
在上是本原的當(dāng)且僅當(dāng)對(duì)中的任何兩個(gè)不同的點(diǎn)和的任一非空真子集，都有中一個(gè)元素，使，而。在上是本原群的另一個(gè)充分必要條件是，對(duì)任何,是的極大子群。
弗羅貝尼烏斯群
弗羅貝尼烏斯群是一類重要的傳遞置換群。上的傳遞置換群，若不是正則群，但中除去恒等置換外的各元素至多有一個(gè)不動(dòng)點(diǎn)，則稱為弗羅貝尼烏斯群。當(dāng)時(shí)，在交錯(cuò)群內(nèi)只有恒等置換、二階元素和三階元素，其中二階元素都沒有不動(dòng)點(diǎn)，而三階元素都恰有一個(gè)不動(dòng)點(diǎn)，從而為弗羅貝尼烏斯群。
相關(guān)定理
凱萊定理
定理：若是一個(gè)群，則存在集，使得同構(gòu)于上的一個(gè)置換群。
該定理把對(duì)抽象群的研究歸結(jié)為對(duì)置換群的研究，當(dāng)是階有限群時(shí)，由凱萊定理可知，不同構(gòu)的階群只能有有限多個(gè)。
拉格朗日定理
令的次數(shù)為如果有個(gè)重根，即作用于保持不變的置換的個(gè)數(shù)，則必有一個(gè)次數(shù)為的最簡函數(shù)使得
并且的不同值的個(gè)數(shù)為。如果在方程個(gè)根的全體置換下的不同值為記保持不變的置換構(gòu)成的集合為且
在該定理的證明中，約瑟夫·拉格朗日得到以上這個(gè)置換集所含的置換個(gè)數(shù)相等，且
。于是。
方程個(gè)根的全體置換被劃分成類，且保持根的有理函數(shù)不變的置換的個(gè)數(shù)是全體置換個(gè)數(shù)的因子，即群論中的拉格朗日定理。
弗羅貝尼烏斯定理
定理：若是上的一個(gè)弗羅貝尼烏斯群，則中全部在上沒有不動(dòng)點(diǎn)的元素，連同的單位元素組成的一個(gè)正則的正規(guī)子群。
一個(gè)抽象群，若它有一個(gè)子群，使得對(duì)的任何不包含在內(nèi)的元素等式成立，則也稱是（關(guān)于的）一個(gè)弗羅貝尼烏斯群。弗羅貝尼烏斯群是反映同構(gòu)于一個(gè)傳遞置換群，后者作為置換群是弗羅貝尼烏斯群，并且在同構(gòu)下，的像恰好是一個(gè)點(diǎn)的穩(wěn)定子群。
推廣
穩(wěn)定子群
穩(wěn)定子群是置換群內(nèi)的一種特殊子群。置換群中把某點(diǎn)保持不動(dòng)的全體元素組成的子群。它記為稱為在內(nèi)的穩(wěn)定子群。
若是中另外一個(gè)點(diǎn)，而中元素使，則所以同一軌道內(nèi)的各點(diǎn)互相共軛的穩(wěn)定子群。
置換同構(gòu)
置換同構(gòu)式是一種特殊的群同構(gòu)。兩個(gè)置換群間的一一對(duì)應(yīng)，它是群同構(gòu)且相應(yīng)的置換在本質(zhì)上是相同的。
設(shè)是上的置換群，是上的置換群，是到上的一一對(duì)應(yīng)，若滿足下列條件，則稱是到的置換同構(gòu)：
1.是群同構(gòu)；
2.存在到的一一對(duì)應(yīng)，使得對(duì)，有。
多重傳遞群
多重傳遞群是比傳遞群有著更強(qiáng)的傳遞性質(zhì)的置換群。
設(shè)是一個(gè)自然數(shù)，而是上的一個(gè)置換群，且若對(duì)的任意兩個(gè)有序元子集和都可以找到一個(gè)元素，使得則稱在上是重傳遞的。
應(yīng)用
物理學(xué)
從減少搜索過程中的時(shí)間消耗、增加算法搜索的準(zhǔn)確性和可控性等多方面進(jìn)行考慮，?提出了一種基于置換群的多粒子量子行走搜索算法。?首先分析得到置換群在空間中可看成一個(gè)閉環(huán)，?定義了置換集合，?并且通過同構(gòu)映射將數(shù)據(jù)點(diǎn)所在數(shù)據(jù)集映射到定義的置換集，?使得置換集合中元素?cái)?shù)據(jù)點(diǎn)形成一一對(duì)應(yīng)的關(guān)系。?其次，?根據(jù)給定初始態(tài)和硬幣算符，?在數(shù)據(jù)點(diǎn)集與置換集合張成的搜索空間中利用多粒子的量子行走在環(huán)上進(jìn)行目標(biāo)數(shù)據(jù)搜索。?最后，?根據(jù)函數(shù)找到目標(biāo)數(shù)據(jù)，?并用量子態(tài)存儲(chǔ)數(shù)值，?用于形成搜索算法的反饋控制；同時(shí)通過控制硬幣算符從而控制量子行走在環(huán)上的行走方向，?增加搜索的可操作性與準(zhǔn)確性。
密碼學(xué)
1985年美洲密碼學(xué)年會(huì)上，S.Wolfram首次提出了將細(xì)胞自動(dòng)機(jī)的初始狀態(tài)作為密鑰，使用細(xì)胞自動(dòng)機(jī)前向迭代產(chǎn)生的偽隨機(jī)序列作為序列密碼，從而開創(chuàng)了細(xì)胞自動(dòng)機(jī)在密碼學(xué)中的應(yīng)用研究。P.Guan根據(jù)復(fù)雜系統(tǒng)的多項(xiàng)式方程求逆的困難性，提出了一種基于混合細(xì)胞自動(dòng)機(jī)的公鑰加密技術(shù)”。S.Nandi等人則根據(jù)細(xì)胞自動(dòng)機(jī)循環(huán)群特性提出了基于置換群基本變換的分組加密技術(shù)，但由于其密鑰為所有細(xì)胞單元為不規(guī)則且具有偶置換群特性的細(xì)胞自動(dòng)機(jī)本身，從而使得其密鑰的數(shù)量大大受限。將外部向量引入到具有置換群特性的細(xì)胞自動(dòng)機(jī)中，并提出了具有輸入的細(xì)胞自動(dòng)機(jī)置換群加密技術(shù)，其密鑰由細(xì)胞自動(dòng)機(jī)本身、細(xì)胞自動(dòng)機(jī)的狀態(tài)迭代次數(shù)和細(xì)胞自動(dòng)機(jī)的輸入向量等三部分組成，從而使得本方法比S.Nandi等人的方法具有更大的密鑰空間和更靈活的加解密方式。
生活應(yīng)用
在穿珠中的應(yīng)用。
例：有n個(gè)不同的爆珠，要求用線把這些珠子穿成若干個(gè)環(huán)，而且每個(gè)珠子只能被一條線穿過，不同的穿珠順序是不同的穿法，共有多少種穿珠辦法。
解：把個(gè)珠子分別用來表示構(gòu)成一個(gè)集合，記為則則個(gè)不同的珠子按照規(guī)定的穿珠辦法的總數(shù)等于元有限集的所有置換的個(gè)數(shù)，因?yàn)楹袀€(gè)元素的集合共有個(gè)雙射變換，即元有限集共有個(gè)置換。因此，對(duì)于個(gè)不同的珠子，共有個(gè)穿珠辦法。
參考資料 >