組合數(shù)學(xué)課件(經(jīng)典)第四章

1、第四章 Plya定理 群的概念 置換群 循環(huán)、奇循環(huán)與偶循環(huán) Burnside引理 Plya定理 例 母函數(shù)型的Plya定理 圖的計數(shù)4.1 群的概念(1)群群定義定義 給定集合G和G上的二元運算 ，滿足下列條件稱為群。(a)封閉性：若a,bG,則存在cG,使得ab=c.(b)結(jié)合律成立：任意a,b,cG,有(ab)c=a(bc).(c)有單位元：存在eG,任意aG.ae=ea=a.(d)有逆元：任意aG,存在bG, ab=ba=e. b=a.由于結(jié)合律成立，(ab)c=a(bc)可記做abc. 例例 證明對于a1,a2,an的乘積，結(jié)合律成立. aaa=a (共n個a相乘).-1n4.1 群

2、的概念(2) 簡單例子例例 G=1,-1在普通乘法下是群。例例 G=0,1,2,n-1在mod n的加法下是群.例例 二維歐氏空間所有剛體旋轉(zhuǎn)T=Ta構(gòu)成群。其中Ta = cosa sina -sina cosa TbTa= cosb sinb cosa sina -sinb cosb -sina cosa4.1 群的概念= cosacosb-sinasinb sinacosb+cosasinb -sinacosb-cosasinb cosacosb-sinasinb= cos(a+b) sin(a+b) =Ta+b -sin(a+b) cos(a+b) 從而有(a)封閉性; (b)結(jié)合律成立

3、：(TT)T = T(TT) = TTT ; (c)有單位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sina sina cosa1 00 14.1 群的概念 前兩例群元素的個數(shù)是有限的，所以是有限群；后一例群元素的個數(shù)是無限的，所以是無限群。 有限群G的元素個數(shù)叫做群的階,記做|G|。 若群G的任意二元素a,b恒滿足ab=ba。責稱G為交換群，或Abel群。 設(shè)G是群,H是G的子集,若H在G原有的運算之下也是一個群,則稱為G的一個子群。4.1 群的概念 基本性質(zhì) 單位元唯一 e1e2=e2=e1 消去律成立 ab=ac b=c, ba=ca b=c 每個元的逆元唯一 a

4、a =a a = e, ab = ba = e , aa = ab , a = b (d)(ab.c) =c b a . c b a abc = e-1-1-1-1-1-1-1 -1-1-1 -14.1 群的概念(e) G有限，aG，則存在最小正整數(shù)r，使得a = e.且a = a .證證 設(shè)|G|=g,則a,a ,a ,a G,由鴿巢原理其中必有相同項。設(shè)a =a ,1mlg+1, e=a ,1l-mg，令l-m=r.則有a =a a=e.即a =a .既然有正整數(shù)r使得a =e,其中必有最小者，不妨仍設(shè)為r. r稱為a的階。易見 H=a,a ,a ,a =e在原有運算下也是一個群。r-1r

5、-12gg+1mll-mrr-1r-1-1r2r-1 r4.2 置換群 置換群是最重要的有限群，所有的有限群都可以用之表示。 置換：1,n到自身的1-1變換。n階置換。1,n目標集。( ), a1a2an是1,n中元的一個排列。n階置換共有n!個，同一置換用這樣的表示可有n!個表示法。例如 p1=( )=( )，n階置換又可看作1,n上的一元運算，一元函數(shù)。 1 2 na1 a2 an1 2 3 43 1 2 43 1 4 22 3 4 14.2 置換群 置換乘法 P1=( ),P2=( )P1P2=( )( )=( ) 注意：既然先做P1的置換，再做P2的置換就規(guī)定了若作為運算符或函數(shù)符應(yīng)是

6、后置的。這與一般習慣的前置不一樣。 一般而言，對1,n上的n階置換，i1,n要寫成(i)P1P2，而不是P1P2(i). (i)P有時寫成i 在上面例中，132,214,323,441.也可寫(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1. P2P1=( )( )=( )P1P2.1 2 3 43 1 2 41 2 3 43 1 2 41 2 3 44 3 2 13 1 2 42 4 3 11 2 3 42 4 3 1P1P1P2P1P1P2P2P21 2 3 44 3 2 14 3 2 14 2 1 31 2 3 44 2 3 14.2 置換群 (1)置換群

7、1,n上的所有n階置換在上面的乘法定義下是一個群。 (a)封閉性 ( )( )=( ) (b)可結(jié)合性 ( )( )( ) =( )=( )( )( ) (c) 有單位元 e=( ) (d) ( ) =( )1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 nb1 b2 bn1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 nc1 c2 cnb1 b2 bnc1 c2 cnb1 b2 bnc1 c2 cn1 2 n1 2 n1 2 na1 a2 ana1 a2 an1 2 n-14.2 置換群 (2)例

8、等邊三角形的運動群。 繞中心轉(zhuǎn)動120，不動， 繞對稱軸翻轉(zhuǎn)。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 1,n上的所有置換(共n!個)構(gòu)成一個群，稱為對稱群，記做Sn. 注意：一般說1,n上的一個置換群，不一定是指Sn.但一定是Sn的某一個子群。1 2 31 2 31 2 32 3 11 2 33 1 21 2 31 3 21 2 33 2 11 2 32 1 3 12 34.2 置換群 任一n階群同構(gòu)于一個n個文字的置換群。設(shè)G=a1,a2,an，指定G中任一元ai, 任意ajG，Pi：aj aj ai ，則Pi是G上的一個置換，即以G為目標集

9、。Pi=( )， G的右正則表示f：ai( )=Pi。f是單射：aiaj，則PiPj f(aiaj) = ( ) =( )( )=f(ai)f(aj) 令P=Pi=( )|a,aiG,則PG a1 a2 ana1ai a2ai anai ai aai a1 a2 ana1(aiaj) a2(aiaj) an(aiaj) a1 a2 ana1ai a2ai anai a1 a2 an(a1ai)aj (a2ai)aj (anai)aj ai aai4.3循環(huán)、奇循環(huán)與偶循環(huán) (a1a2am)=( ) 稱為置換的循環(huán)表示。 于是( )=(14523), ( )=(132)(45), ( )=(15

10、4)(2)(3). (a1a2am)=(a2a3ama1)=(ama1am-1)有m種表示方法。a1a2am-1ama2 a3am a11234543152123453125412345523144.3循環(huán)、奇循環(huán)與偶循環(huán) 若兩個循環(huán)無共同文字，稱為不相交的，不相交的循環(huán)相乘可交換。如(132)(45)= (45)(132). 若p=(a1a2am),則p =(1)(2)(n)=e. 定理定理 任一置換可表成若干不相交循環(huán)的乘積。證證 對給定的任一置換p=( )，從1開始搜索1ai1ai2ai3aik1得一循環(huán)(1 ai1 ai2aik),若(1 ai1 aik)包含n1 2 na1 a2an

11、pppppp4.3循環(huán)、奇循環(huán)與偶循環(huán)了1,n的所有文字，則命題成立。否則在余下的文字中選一個，繼續(xù)搜索,又得一循環(huán)。直到所有文字都屬于某一循環(huán)為止。因不相交循環(huán)可交換，故除了各個循環(huán)的順序外，任一置換都有唯一的循環(huán)表示。例例 一副撲克牌，一分為二，交錯互相插入(洗牌)，這樣操作一次相當于一個置換p。i =p(i+1)/2,i=1,3,5,51. i/2+26,i=2,4,6,52.p=( ),第i個位置被i 號牌占據(jù).pipp4.3循環(huán)、奇循環(huán)與偶循環(huán)26 . . . 5 3 3 2 1 152 52 . . . 29 6 28 4 27 2p = (2 27 14 33 17 9 5 3)

12、(4 28 40 46 49 25 13 7) (6 29 15 8 30 41 21 11)(10 31 16 34 43 22 37 19) (12 32 42 47 24 38 45 23)(18 35) (20 36 44 48 50 51 26 39)(52)p = e2階循環(huán)叫做對換。84.3循環(huán)、奇循環(huán)與偶循環(huán) 定理定理 任一循環(huán)都可以表示為對換的積。(1 2 n)=(1 2)(1 3)(1 n)=(2 3)(2 4)(2 n)(2 1)表示不唯一。sgn(p)1,-1. (1)sgn(p) (2)sgn(pq)=sgn(p)sgn(q) (3)sgn(i,i+1)=-1, p=

13、(i,i+1) (4)sgn(l k)=-1 奇數(shù)個鄰位對換。 故任一置換表示成對換的個數(shù)的奇偶性是唯一的置換分成兩大類：奇置換與偶置換。循環(huán)長度減1的奇偶性即置換奇偶性。=i - j i-jppij4.3循環(huán)、奇循環(huán)與偶循環(huán) 例 0表示空格，任一變動都是與0做相鄰的對換。 p=(0)(1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8) 奇置換。0從右下角出發(fā)回到右下角，水平方向上，垂直方向上都做了偶數(shù)次對換。一個奇置換不會等于一個偶置換。 1 2 3 4 5 6 7 8 9 10 11 1213 14 15 015 14 13 1211 10 9 8 7

14、6 5 4 3 2 1 04.3循環(huán)、奇循環(huán)與偶循環(huán) 定理 Sn中所有偶置換構(gòu)成一階為(n!)/2的子群稱為交錯群，記做An. 證 (1)封閉性 (2)單位元 (3)逆元 (i k) = (i k) 設(shè) p = (i1 j1)(i2 j2)(ii ji),則p = (ii ji)(i1 j1)令Bn=Sn-An, |Bn|+|An|=n!, 則(i j) Bn包含于An |Bn|An|， (i j) Bn包含于An |An|Bn| |An|=|Bn|=(n!)/2-14.4 Burnside引理 (1)共軛類 先觀察S3,A3,S4,A4,以增加感性認識。S3=(1)(2)(3),(23),(

15、13),(123)(132). A3=(1)(2)(3),(123),(132). S4=(1)(2)(3)(4),(12),(13),(14),(23),(24),(34), (123),(124),(132),(134),(142),(143),(234),(243), (1234),(1243),(1324),(1342),(1423),(1432), (12)(34),(13)(24),(14)(23). A4=(1)(2)(3)(4),(123),(124),(132),(134),(142), (143),(234),(243),(12)(34),(13)(24),(14)(23)

16、.4.4 Burnside引理 Sn中P的循環(huán)格式(1) (2) (n) , kCk= n Sn中有相同格式的置換全體構(gòu)成一個共軛類。 定理定理1 Sn中屬(1) (2) (n) 共軛類的元的個數(shù)為C1 C2 Cn nk=1C1 C2 Cn n！C1!C2!Cn!1 2 n C1 C2 Cn4.4 Burnside引理 證 (1) (2) (n) 即 C1 C2 Cn()()()() ()() _/ 1個 _/ 2個 _/ n個_ _/ / C1個_ _/ / C2個_ _/ / Cn個 一個長度為k的循環(huán)有k種表示，Ck個長度為k的循環(huán)有Ck!k 種表示.1,2,n的全排列共有n!個，給定一

17、個排列，裝入格式得一置換，除以前面的重復(fù)度得 n!/(C1!C2!Cn!1 2 n )個不同的置換.CkC1 C2 Cn4.4 Burnside引理 例例1 S4中 (2) 共軛類有4!/(2!2 )=3 (1) (3) 共軛類有4!/(C1!C3!1 3 )=8 (1) (2) 共軛類有4!/(C1!C2!1 2 )=6 (2)k不動置換類 設(shè)G是1,n上的一個置換群。GSn. K1,nG中使k保持不變的置換全體，稱為k不動置換類，記做Zk.2C1 C3C1 C21 11 124.4 Burnside引理 定理 置換群G的k不動置換類Zk是G的一個子群。封閉性：kkk,kk. 結(jié)合性：自然。

18、有單位元：G的單位元屬于Zk.有逆元：PZk,kk,則kk,PZk.ZkG.P1 P2P1P2PP-14.4 Burnside引理 (3)等價類舉一個例子。G=(1)(2)(3)(4),(12),(34),(12)(34).在G下，1變2，3變4，但1不變3。Z1=Z2=e,(34), Z3=Z4=e,(12).對于A4, Z1=e,(234),(243),Z2=e,(134),(143) Z3=e,(124),(142),Z4=e,(123),(132) 一般1,n上G將1,n分成若干等價類，滿足等價類的3個條件.(a)自反性;(b)對稱性;(c)傳遞性。4.4 Burnside引理 一個由

19、G定義的關(guān)系k：若存在pG,使得kj則稱kRj.顯然kRk；kRj則jRk；kRj,jRl則kRl。R是1,n上的一個等價關(guān)系。將1,n劃分成若干等價類。 含目標集元素k的在G作用下的等價類也稱為含k的軌道。p4.4 Burnside引理 定理定理 設(shè)G是1,n上的一個置換群，Ek是1,n在G的作用下包含k的等價類，Zk是k不動置換類。有|Ek|Zk|=|G|. 證證 設(shè)|Ek|=l,Ek=a1(=k),a2,al k=a1ai,i=1,2,l. P=p1,p2,pl令Gi=ZkPi,i=1,2,l. Gi包含于G(G關(guān)于Zk的陪集分解)ij,GiGj=. G1+G2+Gl包含于G.另一方面，

20、任意PG. kajkPPj Zk, PZkPj=Gj. G包含于G1+Gl.從而，G=G1+G2+Gl.|G|=|G1|+|G2|+|Gl|=|Zk|l= |Zk|Ek|Pi -1Pj-1P4.4 Burnside引理 (4)Burnside引理 設(shè)G=a1,a2,ag是目標集1,n上的置換群。每個置換都寫成不相交循環(huán)的乘積。G將1,n換分成l個等價類。c1ak是在置換ak的作用下不動點的個數(shù)，也就是長度為1的循環(huán)的個數(shù)。 BurnsideBurnside引理引理l=c1(a1)+c1(a2)+c1(ag)/|G|4.4 Burnside引理 例如，G=e,(12),(34),(12)(34)

21、. c1(a1)=4,c1(a2)=2,c1(a3)=2,c1(a4)=0.l=4+2+2+0/4=2. 以本例列表分析： 1 2 3 4 c1(aj)(1)(2)(3)(4) 1 1 1 1 4 (1)(12)(3)(4) 0 0 1 1 2 (1) (2)(1)(2)(34) 1 1 0 0 2 (1) (2)(12)(34) 0 0 0 0 0 (2) |Zk| 2 2 2 2 8 Sjk kaj42 12 124.4 Burnside引理 Sjk= 對第j行求和得c1(aj),對第k列求和得|Zk| 表中元素的總和=Sjk=|Zk|=c1(aj). 一般而言，與上表相仿，有下頁表格，其

22、中 Sjk=1, k =k,0, k k.ajaj gj=1 gj=1 nk=1 nk=11, k =k,0, k k.ajaj4.4 Burnside引理 Sjk kaj 1 2 n c1(aj) a1 S11 S12 S1n c1(a1) a2 S21 S22 S2n c1(a2) ag Sg1 Sg2 Sgn c1(ag) |Zk| |Z1|Z2| |Z1| |Zk|=c1(aj). gj=1 nk=1Sjk=c1(aj), Sjk=|Zk|,設(shè)在G作用下，1,n分成l個等價類。1,n=E1+E2+El. gj=1 nk=14.4 Burnside引理 若j,I同屬一個等價類，則Ei=E

23、j,|Ei|=|Ej| 因|Ei|Zi|=|G|,故|Zi|=|Zj|. |Zi|=|Ej|Zj| |Zk|=|Zk|=|Ei|Zi|=|G|=l|G| l= |Zk|= c1(aj). iEj gj=1 nk=1 nk=1 1|G| 1|G| li=1 li=1 li=1iEj4.4 Burnside引理 例例2 一正方形分成4格，2著色，有多少種方案？圖象：看上去不同的圖形。方案：經(jīng)過轉(zhuǎn)動相同的圖象算同一方案。圖象數(shù)總是大于方案數(shù)。1 2 3 4 5 6 7 89 10 11 12 13 14 15 164.4 Burnside引理 不動：p1=(1)(2)(16) 逆時針轉(zhuǎn)90 ：p2=

24、(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16) 順時針轉(zhuǎn)90 ：p3=(1)(2)(6 5 4 3)(10 9 8 7) (11 12)(16 15 14 13) 轉(zhuǎn)180 ：p4=(1)(2)(3 5)(4 6)(7 9)(8 10) (11 12) (13 15)(14 16) (16+2+2+4)/4=6(種方案)。4.5 Plya定理 設(shè)=1,n,M=S1,S2,Sm是m種顏色的集合，對中的元素用M中的顏色著色，得到的圖象集合用M 表示，|M |=m ,每個中的元素都有m種著色可能，n個元的著色有m 種可能。即共有m 個圖象。 設(shè)G是以為目

25、標記得置換群，是某一轉(zhuǎn)動群R的表示。G是以M 為目標記得置換群，是同一轉(zhuǎn)動群R的表示。nnn4.5 Plya定理 G R,G R，G G 一個著色圖象在G的作用下變?yōu)榱硪粋€圖象，則這兩個圖象屬于同一方案。 PlyaPlya定理定理 設(shè)G=P1,P2,Pg是上的一個置換群，C(Pk)是置換Pk的循環(huán)的個數(shù)，用M中的顏色對中的元著色，著色方案數(shù)為l=m +m +m .C(P1)C(P2)C(Pg)1 |G|4.5 Plya定理 f:M,G是作用在圖象集合M 上的置換群。對于PG,P= ,k=1,2,n T: PP,P= ,i=1,2,m ,T:GG fi(k)=fi(k ),i=1,2,m ,k=

26、1,n. P稱為由P誘導(dǎo)出的M 上的置換。 G=P1,Pg,G=P1,P2,Pg T是G到G的同構(gòu)映射。C1(Pi)=mkkpfifipn_pnC(Pi)4.5 Plya定理 在Pi作用下M 中的不動圖象的個數(shù)C1(Pi)=m ，C(Pi)表示Pi的循環(huán)的個數(shù)，即同一循環(huán)中的元素都著同一種顏色的圖象在Pi的作用下保持不變。 對應(yīng)于PG,有PG,P是M (圖象集)上的一個置換。現(xiàn)在要計算的也就是圖象集在G作用下的等價類的個數(shù)。下面對前例進行分析，然后推導(dǎo)到一般。C(Pi)4.5 Plya定理P1=(1)(2)(3)(4),P1=(1)(2)(16)P2=(4321), P2=(1)(2)(3 4

27、 5 6)(7 8 9 10)(11 12)(13 14 15 16) P3=(1234), P3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13) P4=(13)(24), P4=(1)(2)(35)(46)(79)(8 10)(11)(12)(13 15)(14 16) C(P1)=4,C1(P1)=16=2C(P2)=1,C1(P2)=2=2C(P3)=1,C1(P3)=2=2C(P4)=2,C1(P4)=4=2求著色的方案數(shù)也即求圖象的等價類個數(shù)。按 Burside定理，求等價類的個數(shù)歸結(jié)為每個置 換下的不動點(不動圖象)的個數(shù)。C(P1)C(

28、P2)C(P3)C(P4)2 13 44.5 Plya定理 證 對的n個目標用m種顏色著色的圖象集為M |M |=|M| =m G的每一個元Pi是上的一個置換，也對應(yīng)了M 上的一個置換Pi,這樣 G G,T:PiPi 在Pi的作用下不動圖象的個數(shù)C1(Pi)等于Pi的同一循環(huán)中的目標都著相同色的選擇的個數(shù)。即C1(Pi)=m 。因而在G的作用下，M (圖象)的等價類的個數(shù)。 l=C1(P1)+C1(Pg)=m +m +m . |nC(Pi)C(P1)C(P2)C(Pg)1 |G|1 |G|4.6 舉例 例例1 等邊三角形的3個頂點用紅，蘭，綠3著色，有多少種方案？ 解解 在3維空間考慮，3頂點

29、的置換群S3. (3) : 2個； (1) (2) : 3個； (1) : 1個； l = (23 +33 +3 )/6=10 131 11 2 34.6 舉例 例例2 甲烷CH4的4個鍵任意用H,Cl,CH3, C2H5 連接，有多少種方案？ 解解 CH4的結(jié)構(gòu)是一個正4面體，C原子居于正4面體的中心。正4面體的轉(zhuǎn)動群按轉(zhuǎn)動軸分類：頂點-對面的中心： (1)(3) 8個；棱中-棱中： (2) 3個；不動：(1) 1個； 6條棱,每條棱看作一有向邊，正向重合與反向重合共62=12個位置，故轉(zhuǎn)動群的群元有12個。l=114 +4 /12=44+64/3=36。2 44.6 舉例 例例3 3個輸入

30、端一個輸出端的布爾電路有多少種實質(zhì)上不同的結(jié)構(gòu)？ 解解 3個變量的布爾函數(shù)形式上有2 =256個,但有的只是輸入端的順序不同.輸入端的變換群是S3。輸入端的電平取值共有000111計8種。 輸出 f：S3H S3 H Pjhj= i=07 P1=(1)(2)(3),h1= (1) (1) 1個;(3) (1) (3) 2個;(1) (2) (1) (2) 3個; 結(jié)構(gòu)總數(shù)為2 +22 +32 /6=80a1 a2 a3a1 a2 a3 (i) (i)(i) (i) (i) pj pj pj000 001 010 011 100 101 110 111000 001 010 011 100 10

31、1 110 1113 8 1 2 2 1 1 4 24.6 舉例 例例4 正6面體的6個面分別用紅，藍兩種顏色著色，有多少方案？ 正6面體的轉(zhuǎn)動群用面的置換表示： 面心-面心90 (1) (4) 6個 180 (1) (2) 3個 頂點-頂點 120 (3) 8個 棱中-棱中 180 (2) 6個不動 (1) 1個122 +32 +82 +2 /24=10。 。 。 。2 2 2 2 3 63 4 2 64.6 舉例 例例5 用2種顏色給正6面體的8個頂點著色，有多少方案？ 解解 用頂點的置換表示： 面心-面心90 (4) 6個 180 (2) 3個 頂點-頂點 120 (1) (3) 8個

32、棱中-棱中 180 (2) 6個不動 (1) 1個172 +62 +2 /24=34+3+32/3=23。 。 。 。 2 42 2 4 84 2 84.6 舉例 例例6 在正6面體的每個面上任意做一條對角線，有多少方案？ 解解 在每個面上做一條對角線的方式有2種，可參考面的2著色問題。但面心-面心的轉(zhuǎn)動軸轉(zhuǎn)90 時，無不動圖象。除此之外，都可比照面的2著色。所求方案數(shù)： 不動 (1) 1個 2 面心-面心 90 (1) (4) 6個 無不動圖象 0 180 (1) (2) 3個 32 頂點-頂點 120 (3) 8個 82 棱中-棱中 180 (2) 6個 62 2 +0+ 32 +82 +

33、62 /24=8+6+4+6/3=8。 。 622 2 2 36 4 2 36 4 2 34.6 舉例 例例7 骰子的6個面分別有1,6點，有多少種不同的方案？ 解解 1) 6!個圖象的目標集,只有單位元有6!個不動點(圖象)其他23個群元不動點。由Burnside引理有C1(e)/24=6!/24=30個方案。C1(p1)=C1(p2)=C1(p23)=0 2) 2點,3點,6點各有兩種取向， 1點,4點,5點各有一種取向，故應(yīng)有302=240種方案。 4.6 舉例 為了解決正多面體及一些對稱對面體的計算問題介紹下面的定理。 定義定義 凸多面體與一個頂點相關(guān)的面角之和與360 的差稱為該頂點

34、的欠角。 定理定理 凸多面體各頂點欠角的和為720 (用歐拉定理證)。 。4.6 舉例 用正5邊形搭成的正多面體: (5-2)180/5=108 ,360 -3108 =36。 720 /36 =20(個頂點) 一個頂點3條棱，重復(fù)度為2：203/2=30條棱 一個頂點相關(guān)3個面,重復(fù)度為5：203/5=12個面 用正3角形搭成的面最多的正多面體: 360 -560 =60 。 720 /60 =12(個頂點) 一個頂點關(guān)聯(lián)5條棱,重復(fù)度為2：125/2=30條棱。一個頂點關(guān)聯(lián)5個面,重復(fù)度為3：125/3=20個面。 。 。 。 。 。 。 。 。4.6 舉例 足球： 欠角=360 (108

35、 +2120 )=12 720 /12 =60(個頂點) 603/2=90(條棱) 60/5=12(個5邊形) 602/6=20(個6邊形) (正20面體砍去12個頂點)。 。 。 。4.7 母函數(shù)型式的Plya定理 l=m 目標集1,n m種顏色：b1,b2,bm m 用(b1+b2+bm) (b1+b2+bm) (b1+b2+bm) 代替。 P(b1,b2,bm)以b1,b2,bm為復(fù)元的n次對稱多項式。 令Sk=(b1+b2+bm) m S1 S2 Sn P(b1,b2,bm)=Sj kCk(pi)=n1 |G|g C(Pi)i=1 C(Pi)C1(Pi)C2(Pi)2 2 2n n n

36、C(Pi)k k kC(Pi)C1(Pi)C2(Pi)Cn(Pi)Cj(Pi)1 |G|g n i=1 j=1 4.7 母函數(shù)型式的Plya定理 例例1 有3種不同顏色的珠子，串成4顆珠子的項鏈，有哪些方案？ 解解 正4邊形的運動群 繞心轉(zhuǎn) 90 (4) 2個 180 (2) 1個 繞軸翻轉(zhuǎn) (2) 2個 (1) (2) 2個 不動 (1) 1個。 1 2 22 44.7 母函數(shù)型式的Plya定理 P(b,g,r)=(b+g+r) +2(b +g +r ) +3(b +g +r ) +2(b+g+r) (b +g +r )/8 =b +g +r +b g+b r+bg +br +g r+gr +2b g +2b r +2g r +2b gr+2bg r+2bgr 例例2 4顆紅色珠子嵌在正6面體的4個面中心點上，有多少方案？ 解解 相當于對頂點2著色。無珠設(shè)b