1、組合數(shù)學(xué)(Combinatorics),哈爾濱工業(yè)大學(xué)(威海)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 孟凡超 Email: Tele主要內(nèi)容,概述 鴿巢原理 排列與組合 生成排列和組合 二項(xiàng)式系數(shù) 容斥原理及應(yīng)用 遞推關(guān)系和生成函數(shù) 特殊計(jì)數(shù)序列 Polya計(jì)數(shù)法,Polya計(jì)數(shù)法,正四面體著色問題：用紅、藍(lán)兩種顏色給一個(gè)正四面體的4個(gè)頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。,Polya計(jì)數(shù)法,正方形著色問題：用紅、藍(lán)兩種顏色給一個(gè)正方形的4個(gè)頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。,Polya計(jì)數(shù)法,群的基本知識(shí) 群：給定集合G和G上的二元運(yùn)算“”，如果 (1)”運(yùn)算在G上是封閉

2、的，即對(duì)于任意a,bX，都有abG; (2)”運(yùn)算滿足結(jié)合律，即對(duì)于任意a,b,cG，都有a(bc)=(ab)c。 (3)存在eG，對(duì)于任意aG，滿足ea=ae，e稱為G的單位元；,Polya計(jì)數(shù)法,(4)對(duì)于任意aG，存在a-1G，滿足aa-1=a-1a=e，a-1稱為a的逆元。 則稱代數(shù)結(jié)構(gòu)(G, )為群。,群的階：設(shè)(G, )為群，對(duì)于G的元素a，若存在m0，m是滿足am=e的最小正整數(shù)，則稱a是m階元。若這樣的m不存在，則稱a是無限階的，如果G是有限集合，則|G|是群的階。 子群：設(shè)(G,)是群，H是G的非空子集，若對(duì)于任意a,bH，abH，則稱(H,)是(G,)的子群。,Polya計(jì)

3、數(shù)法,群的生成元：在群(G,)中，若存在aG，任何G中的元素b均可以表示成a的方冪，則稱G為循環(huán)群，a稱為該群的生成元。 例：G=1,-1在乘法運(yùn)算下是一個(gè)群。,Polya計(jì)數(shù)法,置換群與對(duì)稱群： 置換：設(shè)X是一個(gè)有限集。不失一般性，取X為包含前n個(gè)正整數(shù)的集合X=1,2,n。X的每個(gè)置換i1,i2,in可視為X到其自身定義的一個(gè)一對(duì)一的函數(shù)f:XX， 其中， f(1)=i1, f(2)=i2, , f(n)=in。 根據(jù)鴿巢原理，f:XX為滿射。置換可視為一個(gè)函數(shù)?？梢杂萌缦?n陣列來表示置換。,Polya計(jì)數(shù)法,例：1,2,3的3!=6個(gè)置換為:,集合X=1,2,n的置換個(gè)數(shù)為n!。將X的

4、所有n!個(gè)置換構(gòu)成的集合記為Sn。,Polya計(jì)數(shù)法,合成運(yùn)算：設(shè)f和g為1,2,n上的兩個(gè)置換,f與g的合成運(yùn)算可以定義為：,其中,Polya計(jì)數(shù)法,例：,求 gf 和 fg.,Polya計(jì)數(shù)法,合成運(yùn)算結(jié)合律：(fg)h=f(gh)。 合成運(yùn)算通常情況下不滿足交換律。 自身合成運(yùn)算：f1=f，f2=ff，f3=fff，,fk= ff f (k個(gè)f)。 恒等置換：就是各整數(shù)對(duì)應(yīng)到它自身的置換：(k)=k，對(duì)所有k=1,2,n。它等價(jià)于,恒等置換性質(zhì)： f=f=f，對(duì)Sn中的所有置換f均成立。,Polya計(jì)數(shù)法,逆置換： 由于Sn中的每個(gè)置換是一對(duì)一的函數(shù)，所以存在逆函數(shù)f-1Sn，滿足：如果

5、f(s)=k，那么f-1(k)=s。通過交換2n矩陣的第一行與第二行，并重新排列列使得第一行的整數(shù)以自然順序1,2,n出現(xiàn)，便得到了2n矩陣f-1。 例如：,性質(zhì)1： 恒等置換的逆是它自身：-1=。 性質(zhì)2：任意置換與它的逆滿足：ff-1=f-1f=。,Polya計(jì)數(shù)法,置換群：如果Sn中的置換的非空子集G滿足如下三條性質(zhì)，則它定義為X的一個(gè)置換的群，簡稱置換群： 1)(合成運(yùn)算的封閉性)：對(duì)G中所有的置換f與g，fg也屬于G。 2)(單位元)：Sn中的恒等置換屬于G。 3)(逆元的封閉性)：對(duì)G中的每一個(gè)置換f，它的逆f-1也屬于G。 n階對(duì)稱置換群：X=1,2,.,n的所有置換的集合Sn是

6、一個(gè)置換群，稱它為n階對(duì)稱群。,Polya計(jì)數(shù)法,例： 設(shè)n是一個(gè)正整數(shù)，n表示1,2,n的置換，它定義為,則當(dāng)i=1,2,n-1時(shí)，有n(i)=i+1且n(n)=1。,n按照順時(shí)針方向?qū)⒏髡麛?shù)傳到隨后的整數(shù)?？蓪視為圓的360/n度的旋轉(zhuǎn)，置換2n為圓的2(360/n)度的旋轉(zhuǎn)， kn為圓的k(360/n)度的旋轉(zhuǎn)。從而,Polya計(jì)數(shù)法,例如：當(dāng)n=4時(shí)，有,Polya計(jì)數(shù)法,Polya計(jì)數(shù)法,性質(zhì)：設(shè)0kn-1， rn，如果k=r mod n，則kn=rn。,Polya計(jì)數(shù)法,例如：當(dāng)n=4,5,6,7,時(shí)，有,Polya計(jì)數(shù)法,性質(zhì)：Cn=0n= , n, 2n, n-1n是一個(gè)置換

7、群。,證明：置換群的三個(gè)條件：合成運(yùn)算的封閉性、單位元和逆元運(yùn)算的封閉性。 (1)設(shè)in和jn(0i,jn-1)是Cn中的任意兩個(gè)置換， injn=i+jn， 如果0i+jn-1，則i+jnCn； 如果ni+j， 則一定存在k(0kn-1)，滿足 k=(i+j) mod n，所以，i+jn=knCn。,Polya計(jì)數(shù)法,(2) 0n= Cn。 (3) 對(duì)于任意knCn，(kn)-1= n-kn。,對(duì)稱：設(shè)是一個(gè)幾何圖形， 到它自身的一個(gè)(幾何)運(yùn)動(dòng)稱為的一個(gè)對(duì)稱。例如， 可以是正方形、四面體、立方體等。每個(gè)對(duì)稱可以看作是頂點(diǎn)、邊以及三維情形下的面上的一個(gè)置換。 頂點(diǎn)對(duì)稱群、邊對(duì)稱群、面對(duì)稱群：

8、的對(duì)稱就是它頂點(diǎn)上的置換群GC、邊上的置換群GE以及三維情形下的面上的置換群GF。,Polya計(jì)數(shù)法,例(正方形)：頂點(diǎn)1,2,3,4，邊a, b, c, d。,存在2種類型，8個(gè)的對(duì)稱。 (1)平面對(duì)稱：圍繞正方形中心0、90、180 、270 角的4個(gè)旋轉(zhuǎn)。 (2)反射：對(duì)角點(diǎn)連線(2個(gè))、對(duì)邊中點(diǎn)連線(2個(gè))。,Polya計(jì)數(shù)法,正方形的角點(diǎn)對(duì)稱群：,Polya計(jì)數(shù)法,正n角形對(duì)稱群： n個(gè)旋轉(zhuǎn)0n=,n, 2n, n-1n。 n個(gè)反射：1,2,n。如果n為偶數(shù)，則有n/2個(gè)關(guān)于對(duì)角點(diǎn)的反射和n/2個(gè)關(guān)于對(duì)邊中點(diǎn)連線的反射。如果n為奇數(shù)，則有n個(gè)關(guān)于角點(diǎn)與其對(duì)邊中點(diǎn)的連線的反射。 所以，

9、正n角形對(duì)稱群(2n階二面體群)：,Polya計(jì)數(shù)法,例(10階二面體群)：,1,2,3,4,5,Polya計(jì)數(shù)法,著色：X=1,2,n的一種著色是對(duì)X的每一個(gè)元素指定一種顏色。令c表示X的一種著色，c(i)表示i(i=1,2,n)的顏色。令C表示X的所有著色的集合。令,是G中的一個(gè)置換，那么f*c是使ik具有顏色c(k)的著色，即，(f*c)(ik)=c(k)，或(f*c)(k)=c(f-1(k)。 f將k變到ik，所以，k的顏色，即c(k)移到f(k)=ik并且變成ik的顏色。,Polya計(jì)數(shù)法,性質(zhì)： (gf)*c=g*(f*c)。,證明：方程左邊是將k的顏色變到(gf)(k)的著色，右

10、邊是將k的顏色變到f(k)，然后再將f(k)的顏色變到g(f(k)的著色。因?yàn)橛珊铣蛇\(yùn)算的定義有(gf)(k)=g(f(k)，所以， (gf)*c=g*(f*c)。,Polya計(jì)數(shù)法,正方形著色問題：用紅、藍(lán)兩種顏色給一個(gè)正方形的4個(gè)頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。,正方形的角點(diǎn)對(duì)稱群：,下列著色表示為：(R,B,B,R)。,4將著色 (R,B,B,R)變?yōu)?R,R,B,B)。,4,Polya計(jì)數(shù)法,這4種著色是等價(jià)的,Polya計(jì)數(shù)法,這2種著色是等價(jià)的,Polya計(jì)數(shù)法,Polya計(jì)數(shù)法,Polya計(jì)數(shù)法,這4種著色是等價(jià)的,Polya計(jì)數(shù)法,這4種著色是等價(jià)的,Polya計(jì)數(shù)法

11、,著色等價(jià)關(guān)系： 令G是作用在集合X=1,2,n上的一個(gè)置換群，C為X的一個(gè)著色集合，使得對(duì)于G中的任意元f和C中任意元c，X的著色f*c仍屬于C。 設(shè)c1與c2是C中的兩種顏色，如果存在G中的一個(gè)置換f，使得f*c1=c2，則稱c1等價(jià)于c2，記為c1c2。反之，如果在G中不存在置換使得它們相等，則稱這兩種顏色不等價(jià)。,Polya計(jì)數(shù)法,著色等價(jià)關(guān)系滿足： 自反性：對(duì)于任意c，cc。 對(duì)稱性：如果c1c2，則c2c1。 傳遞性：如果c1c2， c2c3，則c1c3。,Polya計(jì)數(shù)法,Burnside定理 穩(wěn)定核,4保持了原著色。,著色保持不變的置換集： G(c)=f:fG,f*c=c。 置

12、換作用下不變著色集： C(f)=c:cC,f*c=c。 穩(wěn)定核：使著色c保持不變的所有置換的集合G(c)稱為c的穩(wěn)定核。,保持了原著色。,Polya計(jì)數(shù)法,定理：對(duì)于每一種著色c，c的穩(wěn)定核G(c)是一個(gè)置換群，而且對(duì)G中任意置換f與g，g*c=f*c當(dāng)且僅當(dāng)f-1g屬于G(c)。,例如，著色(R,B,B,R)的穩(wěn)定核G(c)=04=,4。根據(jù)定理，G(c)是一個(gè)置換群。因?yàn)?4=4=， 44=4。(合成運(yùn)算封閉性)。 G(c)。(單位元)。 -14= -14。(逆元封閉性)。,Polya計(jì)數(shù)法,證明：置換群的三個(gè)條件：合成運(yùn)算的封閉性、單位元和逆元運(yùn)算的封閉性。 (1)設(shè)f,gG(c)，則(

13、gf)(c)=g(f(c)=g(c)=c，所以fgG(c)，即在合成運(yùn)算下，G(c)具有封閉性。 (2)單位元使所有著色不變。 (3)設(shè)fG(c)，如果f使c不變，那么f-1也使c不變，即G(c)對(duì)逆元具有封閉性。 所以，G(c)也是一個(gè)置換群。,Polya計(jì)數(shù)法,()如果f*c=g*c，則 (f-1g)*c=f-1*(g*c)=f-1*(f*c)=(f-1f)*c=*c=c。 所以f-1g使c不變，因此，f-1gG(c)。 ()如果f-1gG(c)，則(f-1g)*c=c，所以 (f(f-1g)*c=(ff-1)g)*c=g*c=f*c,Polya計(jì)數(shù)法,推論：設(shè)c為C中的一種著色，那么與c

14、等價(jià)的著色數(shù)|f*c:fG|等于G中的置換個(gè)除以c的穩(wěn)定核中的置換個(gè)數(shù)，即,例如，與(R,B,B,R)等價(jià)的著色：(R,B,B,R)、(R,R,B,B)、(B,R,R,B)、(B,B,R,R)，即等價(jià)數(shù)目為4。,Polya計(jì)數(shù)法,有8個(gè)置換，對(duì)每個(gè)置換，都存一個(gè)與之作用結(jié)果相同的置換,Polya計(jì)數(shù)法,證明：設(shè)f是G中的一個(gè)置換，則滿足g*c=f*c的置換g實(shí)際上就是集合fh:hG(c)中的那些置換。(根據(jù)前述定理) 而集合fh:hG(c)中置換的數(shù)量等于|G(c)|。這是因?yàn)槿绻鹒h=fh，則h=h。于是fh:hG(c)的大小等于|G(c)|的大小。 從而對(duì)于每個(gè)置換f，恰好存在|G(c)|

15、個(gè)置換，這些置換作用在c上跟f作用在c上有同樣的效果。因?yàn)榭偣灿衸G|個(gè)置換，所以與c等價(jià)的著色數(shù)為：,Polya計(jì)數(shù)法,Burnside定理：設(shè)G是X的一個(gè)置換群，C是X的一個(gè)著色集并且使得對(duì)于G中的f與C中任意c，f*c屬于C，則C中不等價(jià)的著色數(shù)N(G,C)為,即，C中不等價(jià)的著色數(shù)等于使著色通過G中的置換保持不變的著色的平均數(shù)。,Polya計(jì)數(shù)法,證明：通過計(jì)數(shù)使f保持c不變(f*c=c)的對(duì)偶(f,c)的個(gè)數(shù)來證明。 這存在兩種計(jì)數(shù)方式：一種是方式是考察G中每個(gè)f，計(jì)算f保持不變的著色數(shù)，然后相加所有的量；另一種方式考察C中的每個(gè)c，計(jì)算滿足f*c=c的置換個(gè)數(shù)，然后相加所有的量。,

16、方式1的數(shù)量為：,Polya計(jì)數(shù)法,方式2：對(duì)每種著色c，滿足f*c=c的所有f的集合就是c的穩(wěn)定核G(c)。因此，每個(gè)c對(duì)整個(gè)計(jì)數(shù)的貢獻(xiàn)是|G(c)|，因此，方式2的數(shù)量為：,由前述推論，,其中，|c|表示與c等價(jià)的著色集。,Polya計(jì)數(shù)法,C所包含的等價(jià)著色集的數(shù)量為N(G,C)。可以按照等價(jià)類將著色歸類。在同一等價(jià)類中，兩種著色對(duì)求和貢獻(xiàn)了同樣的量，因此，每個(gè)等價(jià)類的總貢獻(xiàn)是|G|。,Polya計(jì)數(shù)法,方式1與方式2的計(jì)數(shù)數(shù)量相等，所以,即,Polya計(jì)數(shù)法,例：用紅、藍(lán)兩種顏色給一個(gè)正方形的4個(gè)頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。,正方形的角點(diǎn)對(duì)稱群：,Polya計(jì)數(shù)法,正方形

17、的角點(diǎn)的著色集為C=(c1,c2,c3,c4)|ciR,B,1i 4 ，因此，|C|=16。 單位元使所有著色保持不變，即，C()=C 旋轉(zhuǎn)4和34各自保持2種著色，即所有頂點(diǎn)為紅色和所有頂點(diǎn)為藍(lán)色的著色不變，因此C(4)=(R,R,R,R),(B,B,B,B) C(34)=(R,R,R,R),(B,B,B,B) 旋轉(zhuǎn)24保持4種著色，即所有頂點(diǎn)為相同顏色以及紅和藍(lán)間隔出現(xiàn)的著色不變，因此C(24)=(R,R,R,R),(B,B,B,B), (R,B,R,B),(B,R,B,R),Polya計(jì)數(shù)法,為了使在反射1作用下著色保持不變，頂點(diǎn)1和3可以選擇任何顏色，頂點(diǎn)2和4必須具有相同顏色。所以，

18、在1的作用下保持著色不變的方法：對(duì)頂點(diǎn)1選擇一種顏色(2種選擇)，對(duì)頂點(diǎn)3選擇一種顏色(2種選擇)，對(duì)頂點(diǎn)2和4選擇一種顏色(2種選擇)。所以，在1的作用下保持著色不變的著色數(shù)是222=8。即,Polya計(jì)數(shù)法,C(1)=(R,R,R,R),(R,R,B,R),(B,R,R,R),(B,R,B,R), (R,B,R,B),(R,B,B,B),(B,B,R,B),(B,B,B,B) 類似地，在2的作用下保持著色不變的著色數(shù)是222=8。即 C(2)=(R,R,R,B),(R,R,R,B),(R,B,R,R),(R,B,R,B) (B,R,B,B),(B,R,B,B),(B,B,B,R),(B,B

19、,B,B),Polya計(jì)數(shù)法,為了使在反射3作用下著色保持不變，頂點(diǎn)1和2必須具有相同顏色，頂點(diǎn)3和4必須具有相同顏色。所以，在3的作用下保持著色不變的方法：對(duì)頂點(diǎn)1和2選擇一種顏色(2種選擇)，對(duì)頂點(diǎn)3和4選擇一種顏色(2種選擇)。所以，在3的作用下保持著色不變的著色數(shù)是22=4。即 C(3)=(R,R,R,R),(R,R,B,B),(B,B,R,R),(B,B,B,B 類似地，在4的作用下保持著色不變的著色數(shù)是22=4。即 C(4)=(R,B,B,R),(R,R,R,R),(B,R,R,B),(B,B,B,B),Polya計(jì)數(shù)法,根據(jù)Burnside定理，總的著色方法數(shù)為：,Polya計(jì)數(shù)

20、法,例：用紅、藍(lán)兩種顏色給一個(gè)正五角形的頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。,正五角形的角點(diǎn)對(duì)稱群：,1,2,3,4,5,正五角形的角點(diǎn)的著色集： C=(c1,c2,c3,c4,c5)|ciR,B,1i5，因此，|C|=32。,Polya計(jì)數(shù)法,單位元使所有著色保持不變，即，C()=C，|C()|=32。 其它四類旋轉(zhuǎn)5, 25, 35, 45各自僅保持兩種著色，即，所有頂點(diǎn)為紅色的著色和所有頂點(diǎn)為藍(lán)色的著色不變，因此，|C(i5)|=2，i=1,2,3,4。 為了在反射1的作用下使著色保持不變，頂點(diǎn)2和5必須具有相同顏色，頂點(diǎn)3和4必須具有相同顏色。因此，在1的作用下保持著色不變可以通

21、過如下方法獲得：對(duì)頂點(diǎn)1選擇一種顏色(2種選擇)、對(duì)頂點(diǎn)2和5選擇一種顏色(2種選擇)、對(duì)頂點(diǎn)3和4選擇一種顏色(2種選擇)。因此，在1的作用下保持著色不變的著色數(shù)為|C(1)|=222=8。,Polya計(jì)數(shù)法,根據(jù)Burnside定理，總的著色方法數(shù)為：,類似地，其它四類反射i(i=2,3,4,5)的著色數(shù)為|C(i)|=8。,Polya計(jì)數(shù)法,例：用紅、藍(lán)與綠三種顏色給一個(gè)正方形的4個(gè)頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)？如果用p種顏色給一個(gè)正方形的頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。 例：用紅、藍(lán)與綠三種顏色給一個(gè)正五角形的頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)？如果用p種顏

22、色給一個(gè)正正五角形的頂點(diǎn)著色，試問存在多少種不同的著色方法數(shù)。 例：把n個(gè)不同的對(duì)象放在一個(gè)圓上，問有多少種方法？ 例：用n種不同的顏色的珠子鑲成一個(gè)項(xiàng)鏈，問有多少種方法？,Polya計(jì)數(shù)法,利用Burnside定理計(jì)數(shù)不等價(jià)的著色數(shù)的關(guān)鍵： 確定置換群Dn； 確定著色集C； 計(jì)數(shù)Dn中每個(gè)置換的不變著色集的大小。該計(jì)數(shù)過程比較復(fù)雜，為了使該計(jì)數(shù)過程變得更加容易，我們考慮置換的循環(huán)結(jié)構(gòu)，并引入有向圈概念。,Polya計(jì)數(shù)法,置換循環(huán)結(jié)構(gòu) 設(shè)f是X=1,2,n的一個(gè)置換，Df=(X,Af)是頂點(diǎn)集為X且弧集為Af=(i,f(i):iX的有向圖。該有向圖有n個(gè)頂點(diǎn)與n個(gè)弧，各頂點(diǎn)的入度和出度等于1

23、。弧集Af可以被劃分為若干個(gè)有向圈，且每個(gè)頂點(diǎn)恰好屬于一個(gè)有向圈。,劃分有向圈,置換,有向圈,Polya計(jì)數(shù)法,有向圈,循環(huán)置換：如果某些元素以循環(huán)的方式被置換且余下元素保持不變，那么我們稱這樣的置換為循環(huán)置換或簡稱循環(huán)。如果循環(huán)中的元素個(gè)數(shù)為k，則稱它為k循環(huán)。 例如，1 6 3 5是一個(gè)4-循環(huán)，2 8 7和4分別為3和1循環(huán)。,置換,Polya計(jì)數(shù)法,循環(huán)因子分解：設(shè)f是集合X的任意置換，Df=(X,Af)是頂點(diǎn)集為X且弧集為Af=(i,f(i):iX的有向圖，i1 i2 ip，j1 j2 jq，l1 l2 lr為Df所對(duì)應(yīng)的有向圈，則f可以分解為：f= i1 i2 ip j1 j2 j

24、q l1 l2 lr。,Polya計(jì)數(shù)法,例如：,可以驗(yàn)證：,Polya計(jì)數(shù)法,例：求8階二面體群D4(正方形的頂點(diǎn)對(duì)稱群)中各置換的循環(huán)因子分解。,在一個(gè)正n角形(n為偶數(shù))的頂點(diǎn)對(duì)稱群中，對(duì)于反射，有一半有兩個(gè)1-循環(huán)和(n/2)-1)個(gè)2循環(huán)，另一半有n/2個(gè)2循環(huán),Polya計(jì)數(shù)法,例：求10階二面體群D5(正5角形的頂點(diǎn)對(duì)稱群)中各置換的循環(huán)因子分解。,Polya計(jì)數(shù)法,利用循環(huán)因子分解計(jì)算不等價(jià)著色問題 例：設(shè)X=1,2,3,4,5,6,7,8,置換：,循環(huán)因子分解：,用紅、白和藍(lán)色對(duì)X進(jìn)行著色，C是所有著色的集合，問f保持f中著色不變的|C(f)|是多少？,共有34=81種。,P

25、olya計(jì)數(shù)法,定理：設(shè)f是集合X的一個(gè)置換，假如用k種顏色對(duì)X的元素進(jìn)行著色，令C是X的所有著色的集合，則f保持C中著色不變的著色數(shù)為：|C(f)|=k#(f)，其中，#(f)為f的循環(huán)因子分解中的循環(huán)個(gè)數(shù)。 根據(jù)定理，著色的數(shù)量與顏色的數(shù)量和循環(huán)因子分解中循環(huán)的個(gè)數(shù)有關(guān)，而與每個(gè)循環(huán)的階數(shù)無關(guān)。,Polya計(jì)數(shù)法,例：用紅、白、藍(lán)對(duì)一個(gè)正方形的頂點(diǎn)進(jìn)行著色，問共有多少種不等價(jià)的著色方法？,Polya計(jì)數(shù)法,例：對(duì)一個(gè)四邊形的兩個(gè)點(diǎn)著紅色，其余點(diǎn)著藍(lán)色，問有多少種不等價(jià)的著色數(shù)？ 例：對(duì)一個(gè)正五角形的三個(gè)頂點(diǎn)著紅色，對(duì)其余頂點(diǎn)著藍(lán)色，問有多少種不等價(jià)的著色？,Polya計(jì)數(shù)法,置換的型：設(shè)X

26、=1,2,n為一個(gè)集合，f為X上的一個(gè)置換，f的循環(huán)因子分解中有e1個(gè)1-循環(huán)，e2個(gè)2-循環(huán)，en個(gè)n-循環(huán)，則e1,e2,en滿足：1e1+2e2+nen=n，我們稱n元組(e1,e2,en)是置換f的型，記為type(f)=(e1,e2,en)。 在f的循環(huán)因子分解中，循環(huán)數(shù)為：#(f)=e1+e2+en。 不同的置換可能具有相同的型。 置換的單項(xiàng)式：對(duì)于具有型為type(f)=(e1,e2,en)的每個(gè)置換f，f的單項(xiàng)式定義為：,其中，zk(k=1,2,n)對(duì)應(yīng)k階循環(huán)。,Polya計(jì)數(shù)法,置換群的生成函數(shù)：設(shè)X=1,2,n為一個(gè)集合，G為X上的一個(gè)置換群，則G關(guān)于X的生成函數(shù)是對(duì)G中的所有置換的單項(xiàng)式的和，即,置換群的循環(huán)指數(shù)：設(shè)X=1,2,n為一個(gè)集合，G為X上的一個(gè)置換群，則