離散數(shù)學(xué)ii李占山6.3置換群

1、v 6.3.1 置換的定義置換的定義 v 6.3.2 置換的輪換表法置換的輪換表法 v 6.3.3 置換的順向圈表示置換的順向圈表示 v 6.3.4 置換的奇偶性置換的奇偶性 v定義定義. . 設(shè)設(shè)m是一個(gè)非空的有限集合，是一個(gè)非空的有限集合，m的的一個(gè)一對一變換稱為一個(gè)一個(gè)一對一變換稱為一個(gè)置換置換。v設(shè)設(shè)m=a1,a2,an,則則m的置換的置換可簡記為可簡記為 ，bi=(ai)，i=1,2,n 結(jié)論：結(jié)論：m的置換共有的置換共有n！個(gè)。！個(gè)。 m上的置換稱為上的置換稱為n元置換。元置換。 特別地，特別地， 若若(ai)=ai, i=1,2,n,則則為為n元恒等置換。元恒等置換。 sn: n

2、！個(gè)置換作成的集合。！個(gè)置換作成的集合。nnbbbaaa2121nnbbbaaa2121設(shè)設(shè)m=1，2，3，則有，則有3！=6個(gè)個(gè)3元置換，元置換，所有元素不動(dòng)：所有元素不動(dòng)：1一個(gè)元素不動(dòng)：一個(gè)元素不動(dòng)：2 34 0個(gè)元素不動(dòng)：個(gè)元素不動(dòng)：5 6故，故，s3 = 1，2，3，4，5，6321321231321123321312321132321213321對對m中任意元素中任意元素a及及m的任意兩個(gè)置換的任意兩個(gè)置換，規(guī)定規(guī)定（a）=（a）。）。例例. 設(shè)設(shè) ，則則= ， = = 43124321214343211243432121344321v滿足結(jié)合律：滿足結(jié)合律：()=()，, sn。

3、vsn中有單位元中有單位元: n元恒等置換，設(shè)元恒等置換，設(shè)為為0，有：，有：0=0 ，snv每個(gè)每個(gè)n元置換在元置換在sn 中都有逆元素中都有逆元素: = 12121nnbbbaaannaaabbb2121n元置換的全體作成的集合元置換的全體作成的集合sn對置換的乘法作對置換的乘法作成一個(gè)群，稱為成一個(gè)群，稱為n 次對稱群。次對稱群。 n=1，m=a， s1= = 在置換的乘法作成在置換的乘法作成1 1次對稱群，為次對稱群，為abelabel群。群。 n=2, n=2, m=a，b, s2= , .= , .在置換在置換的乘法作成的乘法作成2 2次對稱群，為次對稱群，為abelabel群。群

4、。 當(dāng)當(dāng)n n 3 3時(shí)，時(shí)，s sn n不是交換群。不是交換群。 aababaabba輪換輪換. 設(shè)設(shè)是是m的置換，若可取到的置換，若可取到m的元素的元素a1, ,ar 使使(a1)a2,(a2)=a3,(ar-1)=ar,(ar)=a1，而而不變不變m的其余的元素（自己變換到本身），的其余的元素（自己變換到本身），則則稱為一個(gè)輪換，稱為一個(gè)輪換， 記為記為 （a1 a2 ar ） l例 =（134）=（341）=（413） 651423654321)2)(46)(135(416523654321 fm的兩個(gè)輪換的兩個(gè)輪換 =(a1ar)和和=(b1bs)說說 是不相雜或不相交，如果是不相雜

5、或不相交，如果 a1,ar和和b1,bs 都不相同都不相同(即即a1, ,arb1,bs= )結(jié)論結(jié)論：若若和和是是m的兩個(gè)不相雜的輪換，的兩個(gè)不相雜的輪換，則則=.證明：證明：設(shè)設(shè)=（a1ar），），=（b1bs），）， 和和不相雜。命不相雜。命為為m的任意元的任意元若若a1,ar，設(shè)，設(shè)=ai，則，則 ()=(ai)=(ai)=ai+1， ()=(ai)=(ai+1)= ai+1 。 i=r時(shí)時(shí),ai+1應(yīng)改為應(yīng)改為a1。 故故,()=()。同理可證，同理可證，若若 b1,bs， ，也有，也有（）=（）。）。設(shè)設(shè) a1,ar,b1,bs, 于是，于是， （）=（）=， （）=（）=。 綜上

6、，綜上，（）=（），故），故 =。 定理定理6 6.3.2 任意置換任意置換恰有一法寫成不相雜的恰有一法寫成不相雜的輪換乘積。輪換乘積。即，任意置換即，任意置換可以寫成不相雜的可以寫成不相雜的輪換的乘積（可表性），如果不考慮乘積的順輪換的乘積（可表性），如果不考慮乘積的順序，則寫法是唯一的序，則寫法是唯一的(唯一性唯一性)。證明：證明： （1）可表性。）可表性。設(shè)設(shè)是是m上置換，任取上置換，任取a1m。若若（a1） = a1，則有輪換（，則有輪換（a1）。）。設(shè)設(shè)（a1）= a2， （a2）= a3，。由于。由于m有限，故到某一個(gè)元素有限，故到某一個(gè)元素ar，(ar)必然不必然不能再是新的元素

7、能再是新的元素,即即(ar) a1,ar。由于由于是一對一的，已有是一對一的，已有（ai）= ai+1，i=1，2， ，r-1，所以，所以(ar)只能是只能是a1。于是得到一個(gè)輪換（于是得到一個(gè)輪換（a1ar）。）。 若若m已經(jīng)沒有另外的元素，則已經(jīng)沒有另外的元素，則就等于這個(gè)就等于這個(gè)輪換，否則設(shè)輪換，否則設(shè)b1不在不在a1，ar之內(nèi)，則同之內(nèi)，則同樣作法又可得到一個(gè)輪換（樣作法又可得到一個(gè)輪換（b1bs）。因）。因?yàn)闉閍1，ar各自已有變到它的元素，所各自已有變到它的元素，所以以b1，bs中不會(huì)有中不會(huì)有a1，ar出現(xiàn)，即出現(xiàn)，即這兩個(gè)輪換不相雜。若這兩個(gè)輪換不相雜。若m的元素已盡，則的元

8、素已盡，則就等于這兩個(gè)輪換的乘積，否則如上又可就等于這兩個(gè)輪換的乘積，否則如上又可得到一個(gè)輪換。如此類推，由于得到一個(gè)輪換。如此類推，由于m有限，有限，最后必得最后必得=(a1ar)(b1bs) (c1ct) (1) 即即表成了不相雜的輪換的乘積。表成了不相雜的輪換的乘積。 （2）唯一性）唯一性.設(shè)設(shè)又可表為不相雜的輪換的乘積如下：又可表為不相雜的輪換的乘積如下：=(a1ar)(b1bs) (c1ct) (2)考慮考慮(1)(1)式中任意輪換式中任意輪換( (a1ar) )。 不妨設(shè)不妨設(shè) a1 a1ar ，且，且a1a。于是，于是，a2=（a1）=（a1）= a2， a3=（a2）=（a2）

9、= a3，證明證明 可見，（可見，（a1ar）必和（）必和（a1ar）完全相同。這就是說，（完全相同。這就是說，（1）中的任意輪）中的任意輪換必出現(xiàn)在（換必出現(xiàn)在（2）中，同樣（）中，同樣（2）中的任）中的任意輪換必出現(xiàn)在（意輪換必出現(xiàn)在（1）中，因之，（）中，因之，（1）和（和（2）一樣，最多排列的方法不同，但）一樣，最多排列的方法不同，但不相雜的輪換相乘適合交換律，所以排不相雜的輪換相乘適合交換律，所以排列的次序本來是可以任意顛倒的。列的次序本來是可以任意顛倒的。例例. 設(shè)設(shè)m m=1，2，3，4，m m的的2424個(gè)置換可寫個(gè)置換可寫成：成：i i；(1 2),(1 3),(1 4),(

10、2 3),(2 4),(3 4)(1 2),(1 3),(1 4),(2 3),(2 4),(3 4)；(1 2 31 2 3),(1 3 21 3 2),(1 2 41 2 4),(1 4 21 4 2),(1 3 41 3 4),(1 4 31 4 3),(2 3 42 3 4),(2 4 32 4 3)；(1 2 3 41 2 3 4),(1 2 4 31 2 4 3),(1 3 2 41 3 2 4),(1 31 3 4 2 4 2),(1 4 2 31 4 2 3),(1 4 3 21 4 3 2),(1 2)(3 4),(1 3)(2 4),(1 4)(2 3)(1 2)(3 4)

11、,(1 3)(2 4),(1 4)(2 3)。輪換的長度輪換的長度 其中所含的元素個(gè)數(shù)。其中所含的元素個(gè)數(shù)。 （a1a2ar）長度為）長度為r。對換對換 長度為的輪換。長度為的輪換。結(jié)論結(jié)論. 任意輪換可以寫成對換的乘積。任意輪換可以寫成對換的乘積。(a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) (3)證明：對證明：對r進(jìn)行歸納，當(dāng)進(jìn)行歸納，當(dāng)r=2時(shí)命題顯然成立，假設(shè)時(shí)命題顯然成立，假設(shè)r=t時(shí)結(jié)論為真，考慮時(shí)結(jié)論為真，考慮=(a1a2arat+1)的情況。令的情況。令1=(a1at+1)， 2=(a1a2at)，下面證明，下面證明= 1 2。l任取ls,若l a1,a2

12、,at-1，不妨設(shè)l=am,則(l)= (am)=am+1， 1 2(l)= 1 (am+1)=am+1；l若若l=at，則，則(l)=at+1= 1(a1)= 1 (2(at)= l1 2(at)= 1 2(l)；l若若l=at+1，則，則(l)= (at+1)= a1=1 (at+1)= l1 (2(at+1)= 1 2(l)；l若若l a1,a2,at+1，則l(l)=l= 1(l)= 1 (2(l)= 1 2(l)，即，即l= 1 2 =(a1at+1) 2。由歸納假設(shè)，。由歸納假設(shè)， 2=(a1a2at)，可表為可表為(a1at)(a1at-1)(a1a2)，所以，所以= (a1at

13、+1) (a1at)(a1at-1)(a1a2)，歸納法完成。，歸納法完成。有興趣的同學(xué)可以采用直接證明的方法有興趣的同學(xué)可以采用直接證明的方法進(jìn)行證明。進(jìn)行證明。推論推論. 對任意置換，有一法對任意置換，有一法(未必只有一未必只有一法法)可將其寫成一些對換的乘積。可將其寫成一些對換的乘積。( () )=( (1 2)()(1 3)()(1 3) )=( (2 3)()(1 3)()(2 3) )。先把置換表成不相雜輪換之乘積，然后用先把置換表成不相雜輪換之乘積，然后用一組順向圈來表示一組順向圈來表示每個(gè)順向圈的長度，即圈上所含的元素個(gè)每個(gè)順向圈的長度，即圈上所含的元素個(gè)數(shù)，就是該圈所表示的輪

14、換的長度。數(shù)，就是該圈所表示的輪換的長度。 一個(gè)一個(gè)n元置換對應(yīng)一組順向圈，這組圈的長元置換對應(yīng)一組順向圈，這組圈的長度之總和為度之總和為n；反之，一組順向圈表示一置；反之，一組順向圈表示一置換，置換的元素個(gè)數(shù)就是組中各圖長度之換，置換的元素個(gè)數(shù)就是組中各圖長度之總和?？偤汀?l 1 3l 2 4 n元置換元置換對應(yīng)圖形表達(dá)式對應(yīng)圖形表達(dá)式 （圖型）（圖型）g = =1z1 +2z2 + +rzrzi表示長度為表示長度為i的圈的圈, ,而而zi的系數(shù)的系數(shù)i表示如此的表示如此的zi的個(gè)的個(gè)數(shù)數(shù); ;諸諸為非負(fù)整數(shù)為非負(fù)整數(shù),01n,n=0或或1； 1+22+rr = n niiiz1設(shè)設(shè)表為表

15、為k個(gè)不相雜的輪換的乘積個(gè)不相雜的輪換的乘積(包包括長度為括長度為1的輪換在內(nèi)的輪換在內(nèi)) )，長度分別為，長度分別為r1，r2，rk。若若 =n-k為奇數(shù)（偶數(shù)），則稱為奇數(shù)（偶數(shù)），則稱為為奇奇置換（偶置換）。置換（偶置換）。例如例如 = =（134）是偶置換）是偶置換 是奇置換是奇置換kjjr1) 1(651423654321)2)(46)(135(416523654321 f因每個(gè)長度為因每個(gè)長度為r的輪換可寫成的輪換可寫成r-1個(gè)對換的乘個(gè)對換的乘積：積：(a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) 于是于是可寫成可寫成 =n-k 個(gè)對換的乘積。個(gè)對換的乘積。

16、結(jié)論：結(jié)論：奇置換可表為奇數(shù)個(gè)對換之積，奇置換可表為奇數(shù)個(gè)對換之積， 偶置換可表為偶數(shù)個(gè)對換之積。偶置換可表為偶數(shù)個(gè)對換之積。 kjjr1) 1(l定理定理6 6.3.3 每個(gè)置換都能分解為對換的乘每個(gè)置換都能分解為對換的乘積，但偶置換只能分解為偶數(shù)個(gè)對換的積，但偶置換只能分解為偶數(shù)個(gè)對換的乘積，奇置換只能分解為奇數(shù)個(gè)對換的乘積，奇置換只能分解為奇數(shù)個(gè)對換的乘積。乘積。證明證明. .只只需證明需證明 “只能分解只能分解”。任取任取ssn n，設(shè)，設(shè)等于等于k個(gè)輪換之積，這些個(gè)輪換之積，這些輪換分別含輪換分別含r1，r2，rk個(gè)元素，于是個(gè)元素，于是可以寫成可以寫成 個(gè)對換之積，個(gè)對換之積，定義

17、置換定義置換的符號的符號sgnsgn如下：如下： sgnsgn= = kjjr1) 1(kjjr1)1() 1(kjjr1)1() 1( 顯然，偶置換的符號為顯然，偶置換的符號為1 1，奇置換的符，奇置換的符號為號為-1-1。首先證明首先證明 sgn=sgnsgnsgn=sgnsgn （4 4） 設(shè)設(shè)等于等于k個(gè)個(gè)不相雜不相雜輪換之積，輪換之積，等于等于h h個(gè)個(gè)不相雜輪換之積，且不相雜輪換之積，且寫成對換乘積時(shí)最寫成對換乘積時(shí)最后一個(gè)對換為（后一個(gè)對換為（a ba b）。）。以（以（a ba b）乘）乘而看其變化。而看其變化。(1 1)若若a a和和b b在在的兩個(gè)不同的輪換之內(nèi)的兩個(gè)不同的

18、輪換之內(nèi): = =（aaaa1 1a as s）（）（bbbb1 1b bi i） 則則 （abab）= =（aaaa1 1a as sbbbb1 1b bi i） 若若為為h個(gè)不相雜輪換之積，則（個(gè)不相雜輪換之積，則（abab）為（為（h-1）個(gè)）個(gè)不相雜輪換之積不相雜輪換之積,故，故，sgnsgn(abab)= = (-1-1)n-(h-1) = -(-1= -(-1)n-h = -sgn= -sgn(2)若若a和和b在在的同一個(gè)輪換之內(nèi)的同一個(gè)輪換之內(nèi): =（aa1asbb1bi）則（則（ab）=（aa1as）（）（bb1bi） 故，故， sgnsgn(abab)= = (-1-1)n-

19、(h+1) = -(-1= -(-1)n-h = -sgn= -sgn補(bǔ)充證明l(ab)=(ab)(aa1as)(bb1bi)l=.1112111211111211121111121111111isissisiissisiisisisbbbaaaabbaabbbaaabbbaaabbbaaabbabaabbbaaabbbaaabbbaaababbaabbbaaabbabaabbaaba 總之，以一個(gè)對換乘總之，以一個(gè)對換乘則將則將sgn變號，變號，今今等于（等于（n-k）個(gè)對換之積，故以）個(gè)對換之積，故以乘乘將將sgn變號（變號（n-k）次，即）次，即sgn= (-1)n-ksgn=sgnsg

20、n因此，因此，和和的奇偶性與其乘積的奇偶性與其乘積的奇偶的奇偶性之關(guān)系如下：性之關(guān)系如下： 偶偶偶偶= =偶，偶， 奇奇奇奇= =偶，偶， 奇奇偶偶= =奇，奇， 偶偶奇奇= =奇。奇。 因?yàn)閷Q是奇置換，所以只有奇數(shù)個(gè)因?yàn)閷Q是奇置換，所以只有奇數(shù)個(gè)對換之積是奇置換，偶數(shù)個(gè)對換之積是偶對換之積是奇置換，偶數(shù)個(gè)對換之積是偶置換。置換。 l定理定理6 6.3.4 設(shè)設(shè)m的元數(shù)為的元數(shù)為n，若，若n1，則奇置，則奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，都等于換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，都等于 。證明：證明：命命 1，2，m （5）為為m的所有偶置換，由于的所有偶置換，由于n1，故可取到一，故可取到一個(gè)對換

21、個(gè)對換，而作下列乘積：，而作下列乘積： 1，2，m （6）顯然顯然i是奇置換，而且諸是奇置換，而且諸i互不相同，互不相同，即（即（6）中無重復(fù)元素。反證，若）中無重復(fù)元素。反證，若i=j，則以則以-1左乘得左乘得i=j，矛盾，這說明，矛盾，這說明m的的奇置換不少于偶置換奇置換不少于偶置換。2! n 反之，若反之，若為為m的任意奇置換，則的任意奇置換，則-1為偶置換，故必等于某一個(gè)為偶置換，故必等于某一個(gè)i，-1=i，因而，因而=i，這說明，這說明m的的任意奇置換必在（任意奇置換必在（6）中）中，（，（6）就是）就是m的的所有奇置換，所有奇置換，m的奇置換不多于偶置換。的奇置換不多于偶置換。于是

22、奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，于是奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，各占置換總數(shù)各占置換總數(shù)n！的一半。！的一半。 定義定義之奇偶性的整數(shù)之奇偶性的整數(shù) = n-k稱為稱為的定性的定性數(shù)數(shù)。定理定理6.3.5 設(shè)設(shè)n元置換元置換有圖型有圖型g=則則之定性數(shù)等于之定性數(shù)等于=證明證明.n=1+22+rr+nn k=1+2+r+n n-k=2+（r-1）r+（n-1）n =nrrrz1nrrr2) 1(kjjr1) 1(nrrr2) 1(例子l圖1是一個(gè)22的方格圖形，它可以圍繞中心旋轉(zhuǎn)，也可以圍繞對稱軸翻轉(zhuǎn)，但要求經(jīng)過這樣的變動(dòng)以后的圖形要與原來的圖形重合（方格中的數(shù)字可以改變）。例如，當(dāng)它繞中心逆l時(shí)針旋轉(zhuǎn)900以后，原來的數(shù)字1，2，l3，4分別變?yōu)?，3，4和1，可以把l這個(gè)變化看作是1，2，3，4上的 圖1l一個(gè)置換（4321）。下面給出所有