組合數(shù)學(25)

1、1第八章第八章 Polya計數(shù)法計數(shù)法14.1 置換群于對稱群置換群于對稱群定義：定義： 代數(shù)系統(tǒng)（代數(shù)系統(tǒng)（G，*）若滿足以下條件：）若滿足以下條件： (1) 結(jié)合律：對結(jié)合律：對 a, b, cG, (a*b)*c=a*(b*c)； (2) 幺元：幺元： eG，使對，使對 aG，e*a=a*e=a； (3) 逆元：逆元： 對對G中幺元中幺元e及及 aG， a-1G使使 a-1*a=a* a-1=e， 則稱（則稱（G，*）為群。）為群。2 為醒目起見，群中特異元素為醒目起見，群中特異元素e及求逆也常特及求逆也常特 別寫出，如別寫出，如(G，*)又可記為又可記為(G，*，e )。 (G， *）

2、稱謂代數(shù)系統(tǒng)是指對）稱謂代數(shù)系統(tǒng)是指對 a, bG，有有a*bG，即，即G中元素在運算中元素在運算“*”作用下保持作用下保持封閉性。顯見正整數(shù)連同其上的加法運算構(gòu)成封閉性。顯見正整數(shù)連同其上的加法運算構(gòu)成一代數(shù)系統(tǒng)一代數(shù)系統(tǒng), 正整數(shù)在減法運算下不構(gòu)成代數(shù)正整數(shù)在減法運算下不構(gòu)成代數(shù)系統(tǒng)。系統(tǒng)。 又若僅有又若僅有(1)成立時，稱代數(shù)系統(tǒng)成立時，稱代數(shù)系統(tǒng)(G，*)為半群為半群；3若有若有(2)，(3)同時成立，稱（同時成立，稱（G，*）為幺半群、）為幺半群、 獨異點。獨異點。 此外，因結(jié)合律能保證左逆元就是右逆元，此外，因結(jié)合律能保證左逆元就是右逆元，右逆元就是左逆元，故條件右逆元就是左逆元，

3、故條件(3)常改為對常改為對 aG，a有左逆或有左逆或a有右逆。有右逆。 當當G為有限集時，稱（為有限集時，稱（G，*）為有限群；）為有限群；若若G為無限集，為無限集， 則稱（則稱（G，*）為無限群。有限）為無限群。有限群中群中G的基數(shù)的基數(shù)|G|常稱為群的階數(shù)。常稱為群的階數(shù)。4 為了為了不失一般性，令集合不失一般性，令集合X=1, 2, , n到到 自身的一個雙自身的一個雙射函數(shù)射函數(shù)f: XX稱為一個稱為一個n次次置換，置換， 記作：記作： 我們有：我們有：f(1)=k1; f(2)=k2; . f(n)=kn; 例：例：1,2,3的的3!=6個置換如下：個置換如下：inkifkkknf

4、)(2121或;312321;231321;3213215將將1, 2, , n的所有的所有n!個個置換構(gòu)成的集合記為置換構(gòu)成的集合記為Sn于是，于是，S3是由上述例子列出的是由上述例子列出的6個置換組成。個置換組成。 既然置換是函數(shù)，它們之間就能進行運算。既然置換是函數(shù)，它們之間就能進行運算。如：兩個函數(shù)的復合，就等價于兩個置換的如：兩個函數(shù)的復合，就等價于兩個置換的合成合成;123321;213321;132321nnaaangbbbnf212121;216 f 。g 是按順序合成：是按順序合成： (f 。g) (k)= f (g (k) 那么那么f 。g定義了定義了Sn上的一個二元運算，

5、運算上的一個二元運算，運算的結(jié)果在的結(jié)果在Sn上封閉。上封閉。nnaaanbbbngf21212121ncccngf21217 例：設例：設S4中的置換中的置換f 和和g 為為:13424321;14234321gf求：求：f 。g 和和g 。f :341243211423432113424321214343211342432114234321fggf可以看出，通常情況下合成運算交換律不成立：可以看出，通常情況下合成運算交換律不成立： f 。g g 。f8 我們通常用我們通常用冪運算冪運算來表示一個置換與自身來表示一個置換與自身 的合成運算：的合成運算： f 1 =f , f 2 = f 。f

6、 , f 3 = f 2。f , f 4 = f 3。f , f k = f 。f 。f 。f 。. 。f 。f (k個個)恒等置換恒等置換是各整數(shù)與自身的對應，記為是各整數(shù)與自身的對應，記為 (k) = k, (k = 1,2, .n)同時有：同時有： f 。= 。f = fnn.21.219逆置換逆置換是將對應中的原象與象互換位置后得到是將對應中的原象與象互換位置后得到 的新的置換。記為的新的置換。記為f 1； 如果如果f (s) = k 那么那么f 1 (k) = s ；例：求例：求S4中的置換中的置換 f 的逆置換的逆置換 。421365654321f 置換中第一行是原象，第二行是象，

7、交換置換中第一行是原象，第二行是象，交換兩行后按升序重新排列即得到逆置換：兩行后按升序重新排列即得到逆置換：10 顯然，置換顯然，置換 f 與自身逆置換與自身逆置換f 1的合成是的合成是恒等置換。恒等置換。 f 。f 1 = f 1。f = 如果如果Sn中的置換構(gòu)成的非空子集中的置換構(gòu)成的非空子集G滿足下滿足下列三條性質(zhì)，則定義它為列三條性質(zhì)，則定義它為置換群置換群。 2163546543216543214213651f11 i) 封閉性：如果封閉性：如果 f 和和g G, 那么那么f。g G； ii) 單位元：單位元： Sn中的恒等置換中的恒等置換 G ； iii) 逆元：對逆元：對G中的每

8、個置換中的每個置換f ,它的逆它的逆f 1 G ； 集合集合X=1,2,3,n的所有置換構(gòu)成的集合的所有置換構(gòu)成的集合Sn是一個置換群，稱它為是一個置換群，稱它為n階階對稱群對稱群?？梢赃@樣說：?？梢赃@樣說：給定給定n個元素組成的集合個元素組成的集合X, X上的部分置換所構(gòu)上的部分置換所構(gòu)成的群稱為成的群稱為n次置換群次置換群; X上所有置換構(gòu)成的群上所有置換構(gòu)成的群稱為稱為n次對稱群次對稱群。對稱群是置換群的特殊情況。對稱群是置換群的特殊情況。 12 特別地，僅僅含有恒等置換的集合特別地，僅僅含有恒等置換的集合G=是是 一個置換群。一個置換群。 每個置換群滿足消去律：每個置換群滿足消去律：

9、f 。g = f 。h g = h 對等式左合成對等式左合成f 1： f 1 。(f 。g) = f 1 。(f 。h) (f 1 。f ) 。g = (f 1 。f ) 。h) 。g = 。H g = h 13例：群例：群如右表。不僅如此如右表。不僅如此, 某些部分置換某些部分置換 也可構(gòu)成群也可構(gòu)成群, 例如在例如在S3中中, , , 和和都是群。但都是群。但不是群。不是群。14 例例 ： 給定正三角形給定正三角形123(右圖右圖), 將三角形圍繞將三角形圍繞 重心重心O旋轉(zhuǎn)旋轉(zhuǎn), 分別旋轉(zhuǎn)分別旋轉(zhuǎn)0、120、240。可以把每一旋轉(zhuǎn)看可以把每一旋轉(zhuǎn)看成是三角形的頂點成是三角形的頂點集合集合

10、1, 2, 3的置換的置換, 于是有于是有:13215旋轉(zhuǎn)后置換表達式如下：旋轉(zhuǎn)后置換表達式如下： 旋轉(zhuǎn)120后 旋轉(zhuǎn)240 后1 3, 2 1, 3 2; 1 2, 2 3, 3 113223116 )240(213321)120(132321)0(321321651旋轉(zhuǎn)旋轉(zhuǎn)旋轉(zhuǎn)ppp 再將三角形圍繞直線再將三角形圍繞直線1A、2B、3C翻轉(zhuǎn)。翻轉(zhuǎn)。又得到頂點集合的置換如下又得到頂點集合的置換如下:17 圍繞直線圍繞直線1A翻轉(zhuǎn)得翻轉(zhuǎn)得: 1,3,2; 圍繞直線圍繞直線1B翻轉(zhuǎn)得翻轉(zhuǎn)得: 3,2,1; 圍繞直線圍繞直線1C翻轉(zhuǎn)得翻轉(zhuǎn)得: 2,1,3;得置換如下：得置換如下：)1(231321

11、)2(123321)3(312321432翻轉(zhuǎn)繞翻轉(zhuǎn)繞翻轉(zhuǎn)繞ApBpCp18 正三角形的旋轉(zhuǎn)和翻轉(zhuǎn)在合成運算下可構(gòu)正三角形的旋轉(zhuǎn)和翻轉(zhuǎn)在合成運算下可構(gòu) 成群成群, S3, 就代表這個群。就代表這個群。例：設例：設n是一個正整數(shù)是一個正整數(shù), n表示表示1,2,3,n的置換，的置換，它定義為：它定義為：則當則當 i=1,2,.,n-1; 時有時有n(i) = i +1且且n(n) = 1?？紤]將考慮將1到到n的整數(shù)均勻地放到正的整數(shù)均勻地放到正n邊形的邊形的n個個角點上。我們下面做一個角點上。我們下面做一個n=8的例子：的例子：1.432.321nn19如圖所示，如圖所示，n實際上就是將原圖按順

12、時針方向?qū)嶋H上就是將原圖按順時針方向 旋轉(zhuǎn)旋轉(zhuǎn)(360/8)度后角點數(shù)之間的對應關系。度后角點數(shù)之間的對應關系。15678432n實際上可視為將原圖按實際上可視為將原圖按順時針方向旋轉(zhuǎn)順時針方向旋轉(zhuǎn)(360/n)度后角點數(shù)之間的對應度后角點數(shù)之間的對應關系。關系。 2n實際上為原圖實際上為原圖的的2(360/n)旋轉(zhuǎn)，更旋轉(zhuǎn)，更一般的有：一般的有：20 當旋轉(zhuǎn)一周后，當旋轉(zhuǎn)一周后， n又重復了。因此又重復了。因此n僅有僅有n個不同的冪個不同的冪:;,.,13210nnnnnn1.1.21.1.21nkknknknkn 當反時針旋轉(zhuǎn)當反時針旋轉(zhuǎn)(360/n)度度后后,我們就有：我們就有：更一般地

13、有：更一般地有：從而從而 是置換群，也是循環(huán)群。是置換群，也是循環(huán)群。;11nnn1,.2 , 1 , 0;)(1nkknnkn對于),.,(1210nnnnn21 例例(二面體群二面體群) 考慮正考慮正n邊形邊形(各頂點依次標以各頂點依次標以 1,2., n)上的兩類運算上的兩類運算:第一類是繞重心第一類是繞重心O(逆時針逆時針)旋轉(zhuǎn)旋轉(zhuǎn)(2k)/n弧度弧度(k=0,1, , n-1)，可產(chǎn)生，可產(chǎn)生n種不同的圖案，對應種不同的圖案，對應于于X的的n個不同的置換。個不同的置換。第二類是當?shù)诙愂钱攏為奇數(shù)時繞各邊的中垂線翻轉(zhuǎn)為奇數(shù)時繞各邊的中垂線翻轉(zhuǎn)180，或當，或當n為偶數(shù)時繞各對角線及各

14、對邊中為偶數(shù)時繞各對角線及各對邊中垂線（共垂線（共n條）翻轉(zhuǎn)條）翻轉(zhuǎn)180。從而無論。從而無論n是奇數(shù)是奇數(shù)22 還是偶數(shù)，又可產(chǎn)生還是偶數(shù)，又可產(chǎn)生n種不同的圖案，種不同的圖案， 對應于對應于 X的的n種不同的置換。種不同的置換。 不難發(fā)現(xiàn)，以上不難發(fā)現(xiàn)，以上2n種置換在相繼運動（旋種置換在相繼運動（旋轉(zhuǎn)或翻轉(zhuǎn)）下構(gòu)成一置換群，這類群常稱為轉(zhuǎn)或翻轉(zhuǎn)）下構(gòu)成一置換群，這類群常稱為2n階的階的二面體群二面體群。 一個幾何圖形關于它的對稱點旋轉(zhuǎn)、對稱一個幾何圖形關于它的對稱點旋轉(zhuǎn)、對稱軸翻轉(zhuǎn)、對稱面反轉(zhuǎn)都看成它在運動。軸翻轉(zhuǎn)、對稱面反轉(zhuǎn)都看成它在運動。23例：正方形角點標以例：正方形角點標以1、2

15、、3、4，邊標以，邊標以a、b、 c、d,那么正方形存在兩種類型的那么正方形存在兩種類型的8個對稱。個對稱。1a432dcb圍繞正方形中心旋轉(zhuǎn)圍繞正方形中心旋轉(zhuǎn)0,90,180, 270,這四個運動都在這四個運動都在平面上平面上,我們稱為我們稱為平面對稱。平面對稱。再關于兩條對角線、兩條中再關于兩條對角線、兩條中位線翻轉(zhuǎn)得到四個對應置換。位線翻轉(zhuǎn)得到四個對應置換。它們是在空間中進行的。它們是在空間中進行的。24 對平面和空間運動產(chǎn)生的置換描述如下：對平面和空間運動產(chǎn)生的置換描述如下： 1.平面旋轉(zhuǎn)得到的四個置換：平面旋轉(zhuǎn)得到的四個置換：;32144321;21434321;14324321;4

16、3214321342414042.空間翻轉(zhuǎn)得到的四個置換：空間翻轉(zhuǎn)得到的四個置換：;12344321;34124321;41234321;23414321432125 故正方形的角點構(gòu)成的對稱群是：故正方形的角點構(gòu)成的對稱群是： 可以驗證，它們中有下列關系：可以驗證，它們中有下列關系： 那么我們又可以修改對稱群為：那么我們又可以修改對稱群為： 同理，我們用邊的標示同理，我們用邊的標示a,b,c,d替換點對稱后也能替換點對稱后也能得到邊對稱群。得到邊對稱群。,432134241404cG134122143,nn,131412134241404nncG 26 將將前面的結(jié)論推廣到正前面的結(jié)論推廣到

17、正n邊形上去，我們邊形上去，我們 能夠得到能夠得到n個旋轉(zhuǎn)：個旋轉(zhuǎn)： 和和n個翻轉(zhuǎn)：個翻轉(zhuǎn)： 如果如果n為偶數(shù)，則有為偶數(shù)，則有 n/2 個關于對角線和個關于對角線和n/2 個個關于中位線的翻轉(zhuǎn)；如果關于中位線的翻轉(zhuǎn)；如果n為奇數(shù)，則有為奇數(shù)，則有n個個關于角點與對邊中點連線的翻轉(zhuǎn)。關于角點與對邊中點連線的翻轉(zhuǎn)。關于關于1,2,3,.n的的2n個置換構(gòu)成群記為：個置換構(gòu)成群記為：nnnnnn,.,3210n,.,321,.,.,3211241404nnnnD27例例 (四面體群四面體群) 考慮正四面體考慮正四面體(各頂點依次標以各頂點依次標以 1,2,3, 4)，任選一頂點，不妨取，任選一頂點

18、，不妨取4,以以4與與1, 2, 3面的頂垂線為軸面的頂垂線為軸,(逆時針逆時針)旋轉(zhuǎn)旋轉(zhuǎn)2k/3弧度弧度(k=0, 1, 2)可得可得3種不同的圖案。種不同的圖案。由于四面體有由于四面體有4個頂點，個頂點， 故共可故共可產(chǎn)生產(chǎn)生34=12 種不同的圖案，種不同的圖案， 這些圖案在以上動作（旋轉(zhuǎn)）這些圖案在以上動作（旋轉(zhuǎn)）下構(gòu)成的群稱為下構(gòu)成的群稱為四面體群四面體群。432128 顯然易見，顯然易見， 四面體群的階是四面體群的階是12。類似的還有。類似的還有 正六面體、正八面體、正六面體、正八面體、 正十二面體及正正十二面體及正20面體群。面體群。例例(10階二面體群階二面體群) 如圖所示，正

19、五邊形的頂點標如圖所示，正五邊形的頂點標示以示以1,2,3,4,5。它的對稱群。它的對稱群 包含包含5個旋轉(zhuǎn)和個旋轉(zhuǎn)和5個翻轉(zhuǎn)，個翻轉(zhuǎn)， 它們分別是：它們分別是：14325295123454321;34512543211234554321;4512354321;2345154321;4321554321;3215454321;2154354321;1543254321;5432154321543214535251505；和30置換中的輪換置換中的輪換 輪換與對換輪換與對換 設設X=1,2,n, X上的任一置換上的任一置換f都聯(lián)系著一都聯(lián)系著一個有向圖個有向圖G=(X, E)，其中，其中i, j

20、X, (i, j)E當且僅當且僅當當f(i)=j。 由于由于f是從是從X到自身的雙射函數(shù)，故對到自身的雙射函數(shù)，故對iX，其入度和出度都是其入度和出度都是1?？疾煨蛄??？疾煨蛄衚 , f (k), f 2(k), 31 因因X為有限集，故序列中必有重復出現(xiàn)的為有限集，故序列中必有重復出現(xiàn)的 元素，不難證得最早重復出現(xiàn)者必為元素，不難證得最早重復出現(xiàn)者必為k。如若不然，設如若不然，設f t(k)是最早重復出現(xiàn)的元素，即是最早重復出現(xiàn)的元素，即有有f t(k) =f s(k)(1ts)，由最早性知，由最早性知: f t-1(k)fs-1(k)。 但這與但這與f 所具有的性質(zhì)所具有的性質(zhì): ij f

21、(i)f(j)相矛盾。相矛盾。 設設f m(k) = k是最早重復出現(xiàn)的元素，是最早重復出現(xiàn)的元素，32 則稱則稱k, f(k), f 2(k), , f m(k)是一個是一個輪換輪換，記作，記作:( k f (k) f 2(k) f m-1(k) ) m常稱為該輪換的常稱為該輪換的長度長度。長度為。長度為2的輪換又稱為的輪換又稱為對換對換或或換位換位。顯見，由。顯見，由 f 決定的有向圖決定的有向圖G=(X, E)的每個連通分支是一個輪換，且的每個連通分支是一個輪換，且f的所有不同的的所有不同的輪換形成集合輪換形成集合X的一個劃分。的一個劃分。 設設:654213654321f33 則可產(chǎn)生

22、四個輪換則可產(chǎn)生四個輪換: (132)、 (4)、 (5)、 (6)。 置換常記為若干輪換的乘積形式，且如不置換常記為若干輪換的乘積形式，且如不記順序，這種表示還是惟一的。記順序，這種表示還是惟一的。 例如例如, f 可記可記為為f=(132)(4)(5)(6)，或更簡單的記作，或更簡單的記作f=(132)。 上述記法對于直接計算若干置換的乘積上述記法對于直接計算若干置換的乘積是很方便的。是很方便的。 設有如下置換：設有如下置換： f=(134)(26); g=(152)(364) ; h=(1456) 則則f 。g 。h=(134) (26) (152) (364) (1456)34 先看數(shù)

23、字先看數(shù)字1， 從右向左依次考察各輪換，從右向左依次考察各輪換， 即可得出即可得出1所經(jīng)歷的變換所經(jīng)歷的變換:143334記下（記下（14）；）； 再考察再考察4所經(jīng)歷的變換所經(jīng)歷的變換:455266記下（記下（146）；）； 再考察再考察6所經(jīng)歷的變換所經(jīng)歷的變換:611555接下去是接下去是: 564441 35因此，第一個輪換是（因此，第一個輪換是（1465）；）； 然后取出不在然后取出不在 這個輪換中的最小整數(shù)（這里是這個輪換中的最小整數(shù)（這里是2），用同），用同樣方法作出第二個輪換，即樣方法作出第二個輪換，即 22113 336622因此因此 f 。g 。h=(1465) (23)

24、結(jié)合以上過程不難給出一般情況下求置換的結(jié)合以上過程不難給出一般情況下求置換的不交輪換乘積表示的算法。該算法反過來即為不交輪換乘積表示的算法。該算法反過來即為36置換可表示為不交輪換之積的證明。置換可表示為不交輪換之積的證明。 對置換對置換:)5)(43)(21 (53412543215432154321,5342154312,5431254321 即不在各輪換中出現(xiàn)的元素保持不變。即不在各輪換中出現(xiàn)的元素保持不變。 (1 2), (3 4)及及(5)之間的乘積關系可解釋為輪換之間的乘積關系可解釋為輪換（即相應置換）間的合成運算。（即相應置換）間的合成運算。 亦即亦即:中的輪換中的輪換(1 2)

25、, (3 4)及及(5)， 可分別獨立解釋為可分別獨立解釋為37 更進一步，更進一步， 還可把輪換分解成若干對換之積，還可把輪換分解成若干對換之積， 但這種分解并不惟一，但這種分解并不惟一， 其一般分解可用歸納法其一般分解可用歸納法證明，這里從略。證明，這里從略。 如下僅給出一個例子：如下僅給出一個例子： (4 3 2 1)=(1 2)(1 3)(1 4)=(2 3)(2 4)(2 1) =(2 3)(2 4)(2 1)(1 3)(3 1)53412543215432154321,5342154312,5431254321) 5)(43)(21 (38 雖然輪換雖然輪換(4 3 2 1)可有多個不同形式對換積可有多個不同形式對換積 的分解式，但在這些分解式中，對換因子個的分解式，但在這些分解式中，對換因子個數(shù)的奇偶性卻是不變的。如數(shù)的奇偶性卻是不變的。如(4 3 2 1)的各種對的各種對換乘積分解式中對換的數(shù)目均為奇數(shù)。換乘積分解式中對換的數(shù)目均為奇數(shù)。 任意置換的階等于它