離散數(shù)學(xué)ii63置換群ppt課件

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

2、地， v 若若(ai)=ai, i=1,2,n,(ai)=ai, i=1,2,n,則則為為n n元恒元恒等置換。等置換。 v Sn: n Sn: n！個(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對(duì)對(duì)M中任意元素中任意元素a及及M的任意兩個(gè)置換的任意兩個(gè)置換，規(guī)定規(guī)定a）=a）。）。例例

3、. 設(shè)設(shè) ，則則= ， = 43124321214343211243432121344321v滿足結(jié)合律：滿足結(jié)合律：()=()，, Sn。vSn中有單位元中有單位元: n元恒等置換，設(shè)元恒等置換，設(shè)為為0，有：，有：0=0 ，Snv每個(gè)每個(gè)n元置換在元置換在Sn 中都有逆元素中都有逆元素:v = 12121nnbbbaaannaaabbb2121n元置換的全體作成的集合元置換的全體作成的集合Sn對(duì)置換的乘法作對(duì)置換的乘法作成一個(gè)群，稱為成一個(gè)群，稱為n 次對(duì)稱群。次對(duì)稱群。 n=1，M=a， S1= 在置換的乘法作成在置換的乘法作成1次對(duì)稱群，為次對(duì)稱群，為Abel群。群。 n=2, M=a

4、，b, S2= , .在置換的乘法作在置換的乘法作成成2次對(duì)稱群，為次對(duì)稱群，為Abel群。群。 當(dāng)當(dāng)n 3時(shí)，時(shí)，Sn不是交換群。不是交換群。 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è)輪

5、換 =(a1ar)和和=(b1bs)說(shuō)說(shuō) 是不相雜或不相交，假設(shè)是不相雜或不相交，假設(shè) 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è) a

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

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

8、中不會(huì)有a1，ar出現(xiàn)，出現(xiàn)，即這兩個(gè)輪換不相雜。若即這兩個(gè)輪換不相雜。若M的元素已盡，的元素已盡，則則就等于這兩個(gè)輪換的乘積，否則如上又就等于這兩個(gè)輪換的乘積，否則如上又可得到一個(gè)輪換。如此類推，由于可得到一個(gè)輪換。如此類推，由于M有限，有限，最后必得最后必得=(a1ar)(b1bs) (c1ct) (1) 即即表成了不相雜的輪換的乘積。表成了不相雜的輪換的乘積。 （2唯一性唯一性.設(shè)設(shè)又可表為不相雜的輪換的乘積如下：又可表為不相雜的輪換的乘積如下：=(a1ar)(b1bs) (c1ct) (2)思索思索(1)式中任意輪換式中任意輪換(a1ar)。 不妨設(shè)不妨設(shè) a1a1ar，且，且a1a。

9、于是，于是，a2=a1）=a1）= a2， a3=a2）=a2）= a3，證明證明 可見(jiàn)，（可見(jiàn)，（a1ara1ar必和必和a a1a1ar r）完全相同。這就是說(shuō)，）完全相同。這就是說(shuō)，（1 1中的任意輪換必出現(xiàn)在中的任意輪換必出現(xiàn)在2 2中，同樣中，同樣2 2中的任意輪換必出現(xiàn)中的任意輪換必出現(xiàn)在在1 1中，因之，（中，因之，（1 1和和2 2一一樣，最多排列的方法不同，但不相樣，最多排列的方法不同，但不相雜的輪換相乘適合交換律，所以排雜的輪換相乘適合交換律，所以排列的次序本來(lái)是可以任意顛倒的。列的次序本來(lái)是可以任意顛倒的。例例. 設(shè)設(shè)M=1，2，3，4，M的的24個(gè)置換可寫(xiě)個(gè)置換可寫(xiě)成：

10、成：I；(1 2),(1 3),(1 4),(2 3),(2 4),(3 4)；(1 2 3),(1 3 2),(1 2 4),(1 4 2),(1 3 4),(1 4 3),(2 3 4),(2 4 3)；(1 2 3 4),(1 2 4 3),(1 3 2 4),(1 3 4 2),(1 4 2 3),(1 4 3 2),(1 2)(3 4),(1 3)(2 4),(1 4)(2 3)。輪換的長(zhǎng)度輪換的長(zhǎng)度 其中所含的元素個(gè)數(shù)。其中所含的元素個(gè)數(shù)。 （a1a2ar長(zhǎng)度長(zhǎng)度為為r。對(duì)換對(duì)換 長(zhǎng)度為的輪換。長(zhǎng)度為的輪換。結(jié)論結(jié)論. 任意輪換可以寫(xiě)成對(duì)換的乘積。任意輪換可以寫(xiě)成對(duì)換的乘積。(a1

11、a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) (3)證明：對(duì)證明：對(duì)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,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)=

12、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è)， 2=(a1a2at)，可表為(a1at)(a1at-1)(a1a2)，所以= (a1at+1) (a1at)(a1at-1)(a1a2)，歸納法完成。有興趣的同學(xué)可以采用直接證明的方法有興趣的同學(xué)可以采用直接證明的方法進(jìn)行證明。進(jìn)行證明。推論推論. 對(duì)任意置換，有一法對(duì)任意置換，有一法(未必只有一未必只有一法法)可將其寫(xiě)成一些對(duì)換的乘積?？蓪⑵鋵?xiě)成一些對(duì)換的乘積。()=(1 2)(1

13、 3)(1 3)=(2 3)(1 3)(2 3)。先把置換表成不相雜輪換之乘積，然后用先把置換表成不相雜輪換之乘積，然后用一組順向圈來(lái)表示一組順向圈來(lái)表示每個(gè)順向圈的長(zhǎng)度，即圈上所含的元素個(gè)每個(gè)順向圈的長(zhǎng)度，即圈上所含的元素個(gè)數(shù)，就是該圈所表示的輪換的長(zhǎng)度。數(shù)，就是該圈所表示的輪換的長(zhǎng)度。 一個(gè)一個(gè)n n元置換對(duì)應(yīng)一組順向圈，這組圈的長(zhǎng)元置換對(duì)應(yīng)一組順向圈，這組圈的長(zhǎng)度之總和為度之總和為n n；反之，一組順向圈表示一置；反之，一組順向圈表示一置換，置換的元素個(gè)數(shù)就是組中各圖長(zhǎng)度之換，置換的元素個(gè)數(shù)就是組中各圖長(zhǎng)度之總和?？偤?。 l 1 3l 2 4 n元置換元置換對(duì)應(yīng)圖形表達(dá)式對(duì)應(yīng)圖形表達(dá)式

14、（圖型）（圖型）G = =1z1 +2z2 + +rzrzi表示長(zhǎng)度為表示長(zhǎng)度為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è)表為表為k個(gè)不相雜的輪換的乘積個(gè)不相雜的輪換的乘積(包包括長(zhǎng)度為括長(zhǎng)度為1的輪換在內(nèi)的輪換在內(nèi))，長(zhǎng)度分別為，長(zhǎng)度分別為r1，r2，rk。假設(shè)假設(shè) =n-k為奇數(shù)偶數(shù)），則稱為奇數(shù)偶數(shù)），則稱為奇置為奇置換偶置換）。換偶置換）。例如例如 = =（134是偶置換是偶置換 是奇置換是奇置換kjjr1) 1(651423654321)2)(46)(135(416

15、523654321 f因每個(gè)長(zhǎng)度為因每個(gè)長(zhǎng)度為r的輪換可寫(xiě)成的輪換可寫(xiě)成r-1個(gè)對(duì)換的乘個(gè)對(duì)換的乘積：積：(a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) 于是于是可寫(xiě)成可寫(xiě)成 =n-k 個(gè)對(duì)換的乘積。個(gè)對(duì)換的乘積。 結(jié)論：奇置換可表為奇數(shù)個(gè)對(duì)換之積，結(jié)論：奇置換可表為奇數(shù)個(gè)對(duì)換之積， 偶置換可表為偶數(shù)個(gè)對(duì)換之積。偶置換可表為偶數(shù)個(gè)對(duì)換之積。 kjjr1) 1(l定理定理6.3.3 6.3.3 每個(gè)置換都能分解為對(duì)換的每個(gè)置換都能分解為對(duì)換的乘積，但偶置換只能分解為偶數(shù)個(gè)對(duì)換乘積，但偶置換只能分解為偶數(shù)個(gè)對(duì)換的乘積，奇置換只能分解為奇數(shù)個(gè)對(duì)換的乘積，奇置換只能分解為奇數(shù)個(gè)對(duì)換

16、的乘積。的乘積。l證明證明. .只需證明只需證明 “只能分解只能分解”。l任取任取SnSn，設(shè)，設(shè)等于等于k k個(gè)輪換之積，這個(gè)輪換之積，這些些l輪換分別含輪換分別含r1r1，r2r2，rkrk個(gè)元素，于個(gè)元素，于是是l可以寫(xiě)成可以寫(xiě)成 個(gè)對(duì)換之積，個(gè)對(duì)換之積，l定義置換定義置換的符號(hào)的符號(hào)sgnsgn如下：如下：l sgn= sgn= kjjr1) 1(kjjr1)1() 1(kjjr1)1() 1( 顯然，偶置換的符號(hào)為顯然，偶置換的符號(hào)為1 1，奇置換的符，奇置換的符號(hào)為號(hào)為-1-1。首先證明首先證明 sgn=sgnsgn sgn=sgnsgn （4 4） 設(shè)設(shè)等于等于k k個(gè)不相雜輪換

17、之積，個(gè)不相雜輪換之積，等于等于h h個(gè)不相雜輪換之積，且個(gè)不相雜輪換之積，且寫(xiě)成對(duì)換乘積寫(xiě)成對(duì)換乘積時(shí)最后一個(gè)對(duì)換為時(shí)最后一個(gè)對(duì)換為a ba b）。）。以以a ba b乘乘而看其變化。而看其變化。(1)若若a和和b在在的兩個(gè)不同的輪換之內(nèi)的兩個(gè)不同的輪換之內(nèi): =（aa1as）（）（bb1bi） 那么那么 （ab=（aa1asbb1bi） 若若為為h個(gè)不相雜輪換之積，那么個(gè)不相雜輪換之積，那么ab為為h-1個(gè)不相雜輪換之積個(gè)不相雜輪換之積,故，故，sgn(ab)= (-1)n-(h-1) = -(-1)n-h = -sgn(2)若若a和和b在在的同一個(gè)輪換之內(nèi)的同一個(gè)輪換之內(nèi): =（aa1a

18、sbb1bi）那么那么ab=（aa1as）（）（bb1bi） 故，故， sgn(ab)= (-1)n-(h+1) = -(-1)n-h = -sgnl(ab)=(ab)(aa1as)(bb1bi)l=.1112111211111211121111121111111isissisiissisiisisisbbbaaaabbaabbbaaabbbaaabbbaaabbabaabbbaaabbbaaabbbaaababbaabbbaaabbabaabbaaba 總之，以一個(gè)對(duì)換乘總之，以一個(gè)對(duì)換乘則將則將sgn變號(hào)，變號(hào)，今今等于等于n-k個(gè)對(duì)換之積，故以個(gè)對(duì)換之積，故以乘乘將將sgn變號(hào)變號(hào)n-k

19、次，即次，即sgn= (-1)n-ksgn=sgnsgn因此，因此，和和的奇偶性與其乘積的奇偶性與其乘積的奇偶性的奇偶性之關(guān)系如下：之關(guān)系如下： 偶偶偶偶=偶，偶， 奇奇奇奇=偶，偶， 奇奇偶偶=奇，奇， 偶偶奇奇=奇。奇。 因?yàn)閷?duì)換是奇置換，所以只有奇數(shù)個(gè)因?yàn)閷?duì)換是奇置換，所以只有奇數(shù)個(gè)對(duì)換之積是奇置換，偶數(shù)個(gè)對(duì)換之積是偶對(duì)換之積是奇置換，偶數(shù)個(gè)對(duì)換之積是偶置換。置換。 l定理定理6.3.4 6.3.4 設(shè)設(shè)M M的元數(shù)為的元數(shù)為n n，若，若n1n1，則奇，則奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，都等置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，都等于于 。l證明：命證明：命 1 1，22，m m （5 5）l

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

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