離散數(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是一個非空的有限集合，是一個非空的有限集合，m的的一個一對一變換稱為一個一個一對一變換稱為一個置換置換。v設(shè)設(shè)m=a1,a2,an,則則m的置換的置換可簡記為可簡記為 ，bi=(ai)，i=1,2,n 結(jié)論：結(jié)論：m的置換共有的置換共有n！個。！個。 m上的置換稱為上的置換稱為n元置換。元置換。 特別地，特別地， 若若(ai)=ai, i=1,2,n,則則為為n元恒等置換。元恒等置換。 sn: n

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

3、vsn中有單位元中有單位元: n元恒等置換，設(shè)元恒等置換，設(shè)為為0，有：，有：0=0 ，snv每個每個n元置換在元置換在sn 中都有逆元素中都有逆元素: = 12121nnbbbaaannaaabbb2121n元置換的全體作成的集合元置換的全體作成的集合sn對置換的乘法作對置換的乘法作成一個群，稱為成一個群，稱為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時，時，s sn n不是交換群。不是交換群。 aababaabba輪換輪換. 設(shè)設(shè)是是m的置換，若可取到的置換，若可取到m的元素的元素a1, ,ar 使使(a1)a2,(a2)=a3,(ar-1)=ar,(ar)=a1，而而不變不變m的其余的元素（自己變換到本身），的其余的元素（自己變換到本身），則則稱為一個輪換，稱為一個輪換， 記為記為 （a1 a2 ar ） l例 =（134）=（341）=（413） 651423654321)2)(46)(135(416523654321 fm的兩個輪換的兩個輪換 =(a1ar)和和=(b1bs)說說 是不相雜或不相交，如果是不相雜

5、或不相交，如果 a1,ar和和b1,bs 都不相同都不相同(即即a1, ,arb1,bs= )結(jié)論結(jié)論：若若和和是是m的兩個不相雜的輪換，的兩個不相雜的輪換，則則=.證明：證明：設(shè)設(shè)=（a1ar），），=（b1bs），）， 和和不相雜。命不相雜。命為為m的任意元的任意元若若a1,ar，設(shè)，設(shè)=ai，則，則 ()=(ai)=(ai)=ai+1， ()=(ai)=(ai+1)= ai+1 。 i=r時時,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有限，故到某一個元素有限，故到某一個元素ar，(ar)必然不必然不能再是新的元素

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

8、素已盡，則就等于這兩個輪換的乘積，否則如上又可就等于這兩個輪換的乘積，否則如上又可得到一個輪換。如此類推，由于得到一個輪換。如此類推，由于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個置換可寫個置換可寫成：成：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)。輪換的長度輪換的長度 其中所含的元素個數(shù)。其中所含的元素個數(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è)r=t時結(jié)論為真，考慮時結(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) )。先把置換表成不相雜輪換之乘積，然后用先把置換表成不相雜輪換之乘積，然后用一組順向圈來表示一組順向圈來表示每個順向圈的長度，即圈上所含的元素個每個順向圈的長度，即圈上所含的元素個數(shù)，就是該圈所表示的輪

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

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

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

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

18、輪換之內(nèi): = =（aaaa1 1a as s）（）（bbbb1 1b bi i） 則則 （abab）= =（aaaa1 1a as sbbbb1 1b bi i） 若若為為h個不相雜輪換之積，則（個不相雜輪換之積，則（abab）為（為（h-1）個）個不相雜輪換之積不相雜輪換之積,故，故，sgnsgn(abab)= = (-1-1)n-(h-1) = -(-1= -(-1)n-h = -sgn= -sgn(2)若若a和和b在在的同一個輪換之內(nèi)的同一個輪換之內(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 總之，以一個對換乘總之，以一個對換乘則將則將sgn變號，變號，今今等于（等于（n-k）個對換之積，故以）個對換之積，故以乘乘將將sgn變號（變號（n-k）次，即）次，即sgn= (-1)n-ksgn=sgnsg

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

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

22、奇置換的個數(shù)和偶置換的個數(shù)相等，于是奇置換的個數(shù)和偶置換的個數(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是一個22的方格圖形，它可以圍繞中心旋轉(zhuǎn)，也可以圍繞對稱軸翻轉(zhuǎn)，但要求經(jīng)過這樣的變動以后的圖形要與原來的圖形重合（方格中的數(shù)字可以改變）。例如，當(dāng)它繞中心逆l時針旋轉(zhuǎn)900以后，原來的數(shù)字1，2，l3，4分別變?yōu)?，3，4和1，可以把l這個變化看作是1，2，3，4上的 圖1l一個置換（4321）。下面給出所有