組合數(shù)學(xué)幻燈片64

1、24-24-2 26.46.4PolyaPolya定理定理BurnsideBurnside引理可用來(lái)解決諸如上節(jié)例引理可用來(lái)解決諸如上節(jié)例5 5這類(lèi)問(wèn)題，這類(lèi)問(wèn)題，即用即用m m種色對(duì)無(wú)標(biāo)號(hào)物體著色的計(jì)數(shù)問(wèn)題。然而當(dāng)種色對(duì)無(wú)標(biāo)號(hào)物體著色的計(jì)數(shù)問(wèn)題。然而當(dāng)m m較大較大時(shí)，計(jì)算量將大增，如對(duì)上節(jié)例時(shí)，計(jì)算量將大增，如對(duì)上節(jié)例5 5，若用，若用5 5種顏色著色，種顏色著色，則對(duì)應(yīng)的圖像將有則對(duì)應(yīng)的圖像將有5 53 3=125=125個(gè)，即個(gè)，即M M將有將有125125個(gè)元素。顯然個(gè)元素。顯然計(jì)算量很大。本節(jié)將介紹的計(jì)算量很大。本節(jié)將介紹的PlyaPlya計(jì)數(shù)定理，將計(jì)數(shù)定理，將大大減大大減少計(jì)算

2、量。少計(jì)算量。 24-24-3 3PlyaPlya定理可用著色模型來(lái)描述。定理可用著色模型來(lái)描述。設(shè)有設(shè)有n n個(gè)著色對(duì)象，用個(gè)著色對(duì)象，用m m種色對(duì)這種色對(duì)這n n個(gè)對(duì)象的一種著個(gè)對(duì)象的一種著色稱(chēng)為一種色稱(chēng)為一種著色方案著色方案。例如上節(jié)例。例如上節(jié)例5 5中若小三角形編號(hào)中若小三角形編號(hào)為為1 1、2 2、3(3(如圖如圖(a)(a)所示所示),),則則1 1、2 2、3 3為著色對(duì)象。為著色對(duì)象。1 1著著黑色，黑色，2 2與與3 3著白色著白色( (如圖如圖(b)(b)所示所示) )為一種著色方案。為一種著色方案。BurnBurnsideside引理所使用的群是作用在著色對(duì)象上的，對(duì)

3、象引理所使用的群是作用在著色對(duì)象上的，對(duì)象集比方案集小得多，且與顏色數(shù)無(wú)關(guān)。集比方案集小得多，且與顏色數(shù)無(wú)關(guān)。 24-24-4 4設(shè)設(shè)G是著色對(duì)象上的置換群。是著色對(duì)象上的置換群。若一種著色方案能由若一種著色方案能由另一著色方案通過(guò)另一著色方案通過(guò)G G中置換而中置換而導(dǎo)出，則稱(chēng)兩著色方案在導(dǎo)出，則稱(chēng)兩著色方案在本質(zhì)上是相同的本質(zhì)上是相同的。例如，圖中例如，圖中(b)(b)與與(c)(c)兩個(gè)著色方案在本質(zhì)上是相兩個(gè)著色方案在本質(zhì)上是相同的。這是因?yàn)橥摹＿@是因?yàn)?c)(c)圖所示的著色方案圖所示的著色方案“2 2著黑，著黑，3 3與與1 1著著白色白色” ” 是是(b)(b)圖所示的著色方案

4、圖所示的著色方案“1 1著黑，著黑，2 2與與3 3著白色著白色”通過(guò)置換通過(guò)置換(123)(123)而得，該置換將而得，該置換將“1”1” 變?yōu)樽優(yōu)椤?”2”，對(duì)應(yīng)，對(duì)應(yīng)的將的將“1 1著黑著黑”變?yōu)樽優(yōu)椤? 2著黑著黑”。實(shí)際上，若考慮著色模。實(shí)際上，若考慮著色模型，則型，則BurnsideBurnside引理中述及的同一等價(jià)類(lèi)中所有元素引理中述及的同一等價(jià)類(lèi)中所有元素( (著色方案著色方案) )在本質(zhì)上是相同的，而處于不同等價(jià)類(lèi)中兩在本質(zhì)上是相同的，而處于不同等價(jià)類(lèi)中兩個(gè)著色方案在本質(zhì)上是不同的，因而不同個(gè)著色方案在本質(zhì)上是不同的，因而不同的等價(jià)類(lèi)個(gè)數(shù)的等價(jià)類(lèi)個(gè)數(shù)即為本質(zhì)上不同的著色方案

5、數(shù)。即為本質(zhì)上不同的著色方案數(shù)。24-24-5 5定理定理6 6.1616 設(shè)設(shè)N N是是n n個(gè)對(duì)象的集合，個(gè)對(duì)象的集合，G=G=1 1,2 2, ,k k是是N N上上的置換群，用的置換群，用m m種顏色對(duì)種顏色對(duì)n n個(gè)對(duì)象著色，則本質(zhì)上不同的個(gè)對(duì)象著色，則本質(zhì)上不同的著色方案數(shù)為著色方案數(shù)為mmm|G|1t)c()c()c(k21 其中其中c(c(i i) )為置換為置換i i中所含的不相交的循環(huán)的個(gè)數(shù)。中所含的不相交的循環(huán)的個(gè)數(shù)。24-24-6 6著色方案的集合。因一個(gè)方案含著色方案的集合。因一個(gè)方案含n n個(gè)對(duì)象，而每個(gè)對(duì)象均可著個(gè)對(duì)象，而每個(gè)對(duì)象均可著m m種種色，故色，故S S

6、=m=mn n。不妨設(shè)。不妨設(shè)S=S=x x1 1,x,x2 2, , , 并設(shè)并設(shè)x xi i=(x=(xi1i1,x,xi2i2, ,x,xinin) )，其中，其中x xijijBB，表示在著色方案，表示在著色方案x xi i中，對(duì)中，對(duì)象象1 1著著x xi1i1色，對(duì)象色，對(duì)象2 2著著x xi2i2色，色，對(duì)象，對(duì)象n n著著x xinin色，色，i=1,2,i=1,2,m,mn n。對(duì)任意的對(duì)任意的j jG,G,j j是是N N上的一個(gè)置換，上的一個(gè)置換，j j將將N N中的元中的元k k變變?yōu)闉閖 jk k，同時(shí)對(duì)應(yīng)地將每個(gè)，同時(shí)對(duì)應(yīng)地將每個(gè)x xi i中的中的x xikik變

7、為變?yōu)閤 xijkijk，從而將，從而將x xi i變?yōu)樽優(yōu)镾 S中的中的某個(gè)元某個(gè)元y y，這表明，這表明j j誘導(dǎo)誘導(dǎo)出出了一個(gè)了一個(gè)S S上上的置換的置換j j，此，此j j將將x xi i變?yōu)樽優(yōu)閥 y，即，即y=y=j j(x(xi i) )。記記G G* *= =1 1,2 2, ,k k。證明：證明： 設(shè)設(shè)N=N=1,2,1,2,n,n為為n n個(gè)對(duì)象的集合，個(gè)對(duì)象的集合，B B為顏色的集合，為顏色的集合，S S為為nmx24-24-7 7證明證明(續(xù)續(xù)1)由由G G是群，易知是群，易知G G* *也是群且為也是群且為S S上的一個(gè)置換群。顯然有上的一個(gè)置換群。顯然有| |G G

8、* *|=|=G G=k=k同時(shí)，同時(shí)，j j(x(xi i) )是由是由x xi i經(jīng)經(jīng)G G中置換中置換j j導(dǎo)出的，故導(dǎo)出的，故x xi i與與j j(x(xi i) )是本質(zhì)是本質(zhì)上相同的著色方案。而上相同的著色方案。而j j(x(xi i) )j jGG* *,j=1,2,j=1,2,k,k正是正是S S由由G G* *導(dǎo)出的含導(dǎo)出的含x xi i的等價(jià)的等價(jià)類(lèi)，所以類(lèi)，所以S S中本質(zhì)上不同的著色方案中本質(zhì)上不同的著色方案?jìng)€(gè)數(shù)即為個(gè)數(shù)即為S S中由中由G G* *導(dǎo)出的不同的等價(jià)類(lèi)個(gè)數(shù)。導(dǎo)出的不同的等價(jià)類(lèi)個(gè)數(shù)。設(shè)設(shè)(x(xi i) )為置換為置換j j中中1-1-循環(huán)，即在置換循環(huán)

9、，即在置換j j下著色方案下著色方案x xi i不變，不變，即即j j(x(xi i)=x)=xi i。而。而j j(x(xi i)=x)=xi i等價(jià)于等價(jià)于j j的每個(gè)循環(huán)中的含于同一的每個(gè)循環(huán)中的含于同一循環(huán)中的所有對(duì)象著同色的一種著色，這又可視為以循環(huán)循環(huán)中的所有對(duì)象著同色的一種著色，這又可視為以循環(huán)24-24-8 8證明證明(續(xù)續(xù)2)為為“點(diǎn)點(diǎn)”，對(duì)，對(duì)j j的的c(c(j j) )個(gè)個(gè)“點(diǎn)點(diǎn)”( (循環(huán)循環(huán)) )的一種著色，從而的一種著色，從而j j中的中的1-1-循環(huán)個(gè)數(shù)循環(huán)個(gè)數(shù)( (設(shè)為設(shè)為c c1 1(j j)等于用等于用m m種色對(duì)種色對(duì)j j的的c(c(j j) )個(gè)循環(huán)

10、的著個(gè)循環(huán)的著色數(shù)，即色數(shù)，即 )c(jm )c(j1jm)(c 由定理由定理6.156.15得得。)(c)(c)(c |G|1tk12111* mmm|G|1)c()c()c(k21 24-24-9 9注注用用PlyaPlya定理解題，首先應(yīng)建立作用在定理解題，首先應(yīng)建立作用在n n個(gè)對(duì)象上的個(gè)對(duì)象上的置換群。在建立置換群的過(guò)程中，若對(duì)允許的諸如旋轉(zhuǎn)、置換群。在建立置換群的過(guò)程中，若對(duì)允許的諸如旋轉(zhuǎn)、翻轉(zhuǎn)等等變換找完，則相應(yīng)的置換構(gòu)成的集合翻轉(zhuǎn)等等變換找完，則相應(yīng)的置換構(gòu)成的集合G G一定對(duì)一定對(duì)置換的乘法置換的乘法封閉，故能構(gòu)成有限群封閉，故能構(gòu)成有限群S Sn n(n(n次對(duì)稱(chēng)群次對(duì)稱(chēng)群

11、) )的子的子群。群。24-24-1010例例1 1 一個(gè)正方形被均分為四個(gè)小方格，如圖一個(gè)正方形被均分為四個(gè)小方格，如圖(a)(a)所示。所示。用三種色對(duì)其四個(gè)小方格用三種色對(duì)其四個(gè)小方格著色，求其不同的著色方案數(shù)。著色，求其不同的著色方案數(shù)。經(jīng)旋轉(zhuǎn)或翻轉(zhuǎn)能使之重合的方案算一種。經(jīng)旋轉(zhuǎn)或翻轉(zhuǎn)能使之重合的方案算一種。24-24-1111解：解：將正方形中的一些點(diǎn)及區(qū)域賦以相應(yīng)的記號(hào)將正方形中的一些點(diǎn)及區(qū)域賦以相應(yīng)的記號(hào), ,如圖如圖(b)(b)所示所示, ,使正方形重合的運(yùn)動(dòng)及使正方形重合的運(yùn)動(dòng)及對(duì)應(yīng)的集合對(duì)應(yīng)的集合1,2,3,41,2,3,4上的置換有：上的置換有：1)1) 不動(dòng)，對(duì)應(yīng)的置換

12、不動(dòng)，對(duì)應(yīng)的置換1 1=(1)(2)(3)(4)=(1)(2)(3)(4)，格式為，格式為(1)(1)4 4，有有c(c(1 1)=4)=4。2)2) 繞中心繞中心0 0逆時(shí)針轉(zhuǎn)逆時(shí)針轉(zhuǎn)9090，180180，270270，記相應(yīng)的置，記相應(yīng)的置換為換為2 2,3 3,4 4，即，即2 2=(1432),=(1432),3 3=(13)(24),=(13)(24),4 4=(1234)=(1234)格式分別為格式分別為(4)(4)1 1,(2),(2)2 2,(4),(4)1 1，有，有c(c(2 2)=1,c()=1,c(3 3)=2,c()=2,c(4 4)=1)=1。24-24-1212

13、3)3)繞軸繞軸ACAC、DBDB、EGEG、FHFH翻轉(zhuǎn)，相應(yīng)的置換依次記為翻轉(zhuǎn)，相應(yīng)的置換依次記為5 5,6 6,7 7,8 8，即，即5 5=(2)(4)(13),=(2)(4)(13),6 6=(1)(3)(24),=(1)(3)(24),7 7=(12)(34),=(12)(34),8 8=(14)(23)=(14)(23)。5 5，6 6的格式為的格式為(1)(1)2 2(2)(2)1 1，有，有c(c(5 5)=c()=c(6 6)=3;)=3;7,87,8的格式為的格式為(2)(2)2 2，有，有c(c(7 7)=c()=c(8 8)=2)=2。由由(1)(1)、(2)(2)、

14、(3)(3)得置換群得置換群G=G=1 1,2 2, ,，8 8。又。又顏色數(shù)顏色數(shù)m=3,m=3,由由PlyaPlya定理得：著色方案數(shù)為定理得：著色方案數(shù)為218168)33333333(81m|G|1t22332481i)c(i 24-24-1313例例2 2 用紅用紅(r)(r)、藍(lán)、藍(lán)(b)(b)、綠、綠(g)(g)三種色對(duì)正三角形的頂點(diǎn)三種色對(duì)正三角形的頂點(diǎn)及其中心著色，如下圖及其中心著色，如下圖。求不同的著色方案數(shù)。經(jīng)旋轉(zhuǎn)。求不同的著色方案數(shù)。經(jīng)旋轉(zhuǎn)或翻轉(zhuǎn)能使之重合的方案算一種。或翻轉(zhuǎn)能使之重合的方案算一種。 24-24-1414解解： 1)1) 不動(dòng)，對(duì)應(yīng)的置換為不動(dòng)，對(duì)應(yīng)的置

15、換為(1)(2)(3)(4)(1)(2)(3)(4)，格式為，格式為(1)(1)4 4；2)2) 繞中心繞中心4 4旋轉(zhuǎn)旋轉(zhuǎn)120120，對(duì)應(yīng)的兩個(gè)置換為，對(duì)應(yīng)的兩個(gè)置換為(123)(4)(123)(4)，(132)(4)(132)(4)，格式均為，格式均為(1)(1)1 1(3)(3)1 1；3)3) 繞中線繞中線1414、2424、3434翻轉(zhuǎn)，對(duì)應(yīng)的置換有三個(gè)，為翻轉(zhuǎn)，對(duì)應(yīng)的置換有三個(gè)，為(1)(4)(23)(1)(4)(23)，(2)(4)(13)(2)(4)(13)，(3)(4)(12)(3)(4)(12)，格式均為格式均為(1)(1)2 2(2)(2)1 1；將圖中的將圖中的“”標(biāo)

16、號(hào)如右圖所示。標(biāo)號(hào)如右圖所示。使正三角形重合的運(yùn)動(dòng)及對(duì)應(yīng)的使正三角形重合的運(yùn)動(dòng)及對(duì)應(yīng)的1 1，2 2，3 3，4 4上的置換有：上的置換有： 24-24-1515解解(續(xù)續(xù))共共6 6個(gè)置換，構(gòu)成一個(gè)個(gè)置換，構(gòu)成一個(gè)6 6階置換群，由階置換群，由PlyaPlya定理得著色定理得著色方案數(shù)為方案數(shù)為t= (3t= (34 4+2+23 32 2+3+33 33 3)/6)/6180/6180/63030其中中心著紅色的著色方案見(jiàn)下圖。其中中心著紅色的著色方案見(jiàn)下圖。24-24-1616例例3 3 在一個(gè)正四面體的若干頂點(diǎn)上嵌上三種顏色的珠子，在一個(gè)正四面體的若干頂點(diǎn)上嵌上三種顏色的珠子，同色珠子

17、均相同，可得多少同色珠子均相同，可得多少種不同樣式的四面體。經(jīng)適種不同樣式的四面體。經(jīng)適當(dāng)轉(zhuǎn)動(dòng)能使之重合的樣式算一種。當(dāng)轉(zhuǎn)動(dòng)能使之重合的樣式算一種。 24-24-1717解：解：1)1) 不動(dòng)，對(duì)應(yīng)的置換為不動(dòng)，對(duì)應(yīng)的置換為(1)(2)(3)(4)(1)(2)(3)(4)，格式為，格式為(1)4(1)4。問(wèn)題相當(dāng)于對(duì)一個(gè)正問(wèn)題相當(dāng)于對(duì)一個(gè)正四面體的四個(gè)頂點(diǎn)用四種四面體的四個(gè)頂點(diǎn)用四種顏色著染，求其本質(zhì)上不顏色著染，求其本質(zhì)上不同的著色方案數(shù)，如圖同的著色方案數(shù)，如圖610610所示，使正四面體重合的所示，使正四面體重合的剛體運(yùn)動(dòng)及相應(yīng)的頂點(diǎn)集剛體運(yùn)動(dòng)及相應(yīng)的頂點(diǎn)集1,2,3,41,2,3,4上

18、的置換有：上的置換有：24-24-1818解解( (續(xù)續(xù)) )2)2) 以頂點(diǎn)及相對(duì)的底面三角形中心的連線以頂點(diǎn)及相對(duì)的底面三角形中心的連線( (如圖如圖610610的的AB)AB)為軸旋轉(zhuǎn)為軸旋轉(zhuǎn)120120。因有四條軸可選，對(duì)應(yīng)。因有四條軸可選，對(duì)應(yīng)8 8個(gè)個(gè)格式相同的置換，其中一個(gè)為格式相同的置換，其中一個(gè)為(1)(234),(1)(234),格式為格式為(1)(1)1 1(3)(3)1 1；3)3) 以?xún)蓷l不相交的棱的中點(diǎn)的連線以?xún)蓷l不相交的棱的中點(diǎn)的連線( (如圖如圖610610中的中的CD)CD)為軸旋轉(zhuǎn)為軸旋轉(zhuǎn)180180。因有三條軸可選，對(duì)應(yīng)。因有三條軸可選，對(duì)應(yīng)3 3個(gè)格式相

19、個(gè)格式相同的置換，其中一個(gè)為同的置換，其中一個(gè)為(14)(23),(14)(23),格式為格式為(2)(2)2 2共共1212個(gè)置換，構(gòu)成一個(gè)個(gè)置換，構(gòu)成一個(gè)1212階置換群，由階置換群，由PlyaPlya定理得不定理得不同樣式的四面體為同樣式的四面體為t t (4(44 4+8+84 42 2+3+34 42 2)/12)/12432/12432/12363624-24-1919例例4 4 1)1) 若有若有m m種顏色可用，求本質(zhì)不同的著色方案。種顏色可用，求本質(zhì)不同的著色方案。2)2) 若有若有3 3種顏色可用且涂在立方體面上的顏色最多出種顏色可用且涂在立方體面上的顏色最多出現(xiàn)兩種，求本

20、質(zhì)不同的著色方案數(shù)現(xiàn)兩種，求本質(zhì)不同的著色方案數(shù)。給一立方體的六個(gè)面著色。若一種著色圖形在空間給一立方體的六個(gè)面著色。若一種著色圖形在空間經(jīng)適當(dāng)旋轉(zhuǎn)可得另一著色圖形，則說(shuō)兩著色是本質(zhì)相同經(jīng)適當(dāng)旋轉(zhuǎn)可得另一著色圖形，則說(shuō)兩著色是本質(zhì)相同的。的。24-24-2020解：解： 1)1) 給立方體六個(gè)面標(biāo)號(hào)給立方體六個(gè)面標(biāo)號(hào), ,如右圖如右圖所示。使立方體重合的旋轉(zhuǎn)所示。使立方體重合的旋轉(zhuǎn)及相應(yīng)的面集及相應(yīng)的面集1 1，2 2，3 3，4 4，5 5，6 6上的置換有：上的置換有：a)a) 不動(dòng)，對(duì)應(yīng)的置換為不動(dòng)，對(duì)應(yīng)的置換為(1)(2)(3)(4)(5)(6)(1)(2)(3)(4)(5)(6)，格

21、式為，格式為(1)(1)6 624-24-2121解解(續(xù)續(xù)1)b)b) 以對(duì)面中心的連線以對(duì)面中心的連線為 軸 轉(zhuǎn)為 軸 轉(zhuǎn) 9 09 0 ，180180，其中關(guān)于，其中關(guān)于ABAB軸軸( (如右圖如右圖) )對(duì)應(yīng)的對(duì)應(yīng)的置換為置換為(1)(2)(3456)(1)(2)(3456)，(1)(2)(3654)(1)(2)(3654)，(1)(2)(35)(46)(1)(2)(35)(46)因有三組對(duì)面可選，故此類(lèi)置換共因有三組對(duì)面可選，故此類(lèi)置換共9 9個(gè)，其中個(gè)，其中6 6個(gè)格個(gè)格式為式為(1)(1)2 2(4)(4)1 1，3 3個(gè)格式為個(gè)格式為(1)(1)2 2(2)(2)2 2。24-24-2222解解(續(xù)續(xù)2)共共2424個(gè)置換，構(gòu)成一個(gè)個(gè)置換，構(gòu)成一個(gè)2424階群。由階群。由PlyaPlya定理得著色方定