《組合數(shù)學(xué)》課件PPT

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 解決的問(wèn)題：解決的問(wèn)題：循環(huán)排列計(jì)數(shù)循環(huán)排列計(jì)數(shù)項(xiàng)鏈計(jì)數(shù)項(xiàng)鏈計(jì)數(shù)圖著色圖著色如：立方體的頂點(diǎn)與面的著色如：立方體的頂點(diǎn)與面的著色化學(xué)分子的同分異構(gòu)計(jì)數(shù)化學(xué)分子的同分異構(gòu)計(jì)數(shù)這些問(wèn)題的共性：這些問(wèn)題的共性：經(jīng)過(guò)旋轉(zhuǎn)或翻轉(zhuǎn)后與原圖形等價(jià)經(jīng)過(guò)旋轉(zhuǎn)或翻轉(zhuǎn)后與原圖形等價(jià)第七章 Plya 定理3 4 5 67 8 9 10 1 2 13 14 15 16 11 12 數(shù)學(xué)問(wèn)題數(shù)學(xué)問(wèn)題求解一般步驟：求解一般步驟：?jiǎn)栴}抽象問(wèn)題抽象 數(shù)學(xué)表示數(shù)學(xué)表示 建立模型建立模型 求解求解 驗(yàn)證普適性驗(yàn)證普適性群群：給定一個(gè)集合G=a,b,c,和集合G上的二元運(yùn)算，并滿足:(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-1。則稱集合G在運(yùn)算之下是一個(gè)群，簡(jiǎn)稱G是群。(Z,+)(Z,*)(R,+)一般ab簡(jiǎn)寫(xiě)為ab。置換置換：n個(gè)元素1,2,n之間的一個(gè)置換 表示1被1到n中的某個(gè)數(shù)a1取代，2被1到n中的某個(gè)數(shù)a2取代，直到n被1到n中的某個(gè)數(shù)an取代，且a1,a2,an互不相同。轉(zhuǎn)0 轉(zhuǎn)90 轉(zhuǎn)180 轉(zhuǎn)270置換置換的連接運(yùn)算的連接運(yùn)算：置換群置換群：置換群的元素是置換，運(yùn)算是置換的連接?？梢则?yàn)證置換群滿足群的四個(gè)條件（封閉性，結(jié)合律，單位元，逆元）。本題中置換群G=轉(zhuǎn)0、轉(zhuǎn)90、轉(zhuǎn)180、轉(zhuǎn)270可以記作：G=1,2,3,4 關(guān)于群元素個(gè)數(shù)的重要公式Ek(等價(jià)類等價(jià)類)Zk(K不動(dòng)置換類不動(dòng)置換類)Zk(K不動(dòng)置換類不動(dòng)置換類)：設(shè)G是元素1n的置換群。若k是1n中某個(gè)元素，G中使k保持不變的置換的全體，記以Zk，叫做G中使K保持不動(dòng)的置換類，簡(jiǎn)稱K不動(dòng)置換類。如本例中：G是涂色方案116的置換群。對(duì)于方案1，四個(gè)置換都使方案1保持不變，所以Z1=1,2,3,4；對(duì)于方案3，只有置換1使其不變，所以Z3=1；對(duì)于方案11，置換1和3使方案其保持不變，所以Z11=1,3。Ek(等價(jià)類等價(jià)類)：設(shè)G是元素1n的置換群。若k是1n中某個(gè)元素，k在G作用下的軌跡，記作Ek。即k在G的作用下所能變化成的所有元素的集合。如本例中：方案1在四個(gè)置換作用下都是方案1，所以E1=1；方案3，在1下是3，在2下變成6，在3下變成5，在4下變成4，所以E3=3,4,5,6；方案11，在1、3下是11，在2、4下變成12，所以E11=11,12。E1Z1=14=4=GE3Z3=41=4=GE11Z11=22=4=G元素j Sij置換i1216D(i)1 234S1,1S2,1S3,1S4,1S1,2S2,2S3,2S4,2S1,16S2,16S3,16S4,16D(1)D(2)D(3)D(4)ZjZ1Z2Z16D(j)表示在置換j下不變的元素的個(gè)數(shù) 不妨設(shè)N=1，n中共有L個(gè)等價(jià)類，N=E1+E2+EL，則當(dāng)j和k屬于同一等價(jià)類時(shí)，有Zj=Zk。所以 這里的L就是我們要求的互異的組合狀態(tài)的個(gè)數(shù)。于是我們得出：利用這個(gè)式子（Burnside引理）我們可以得到本題的解 L=(16+2+4+2)/4=6如本例中：但是，我們發(fā)現(xiàn)要計(jì)算D(j)的值不是很容易，如果采用搜索的方法，總的時(shí)間規(guī)模為O(nsp)。(n表示元素個(gè)數(shù)，s表示置換個(gè)數(shù)，p表示格子數(shù)，這里n的規(guī)模是很大的)下一步就是要找到一種簡(jiǎn)便的D(j)的計(jì)算方法。先介紹一個(gè)循環(huán)的概念循環(huán)循環(huán)：記稱為n階循環(huán)。每個(gè)置換都可以寫(xiě)若干互不相交的循環(huán)的乘積，兩個(gè)循環(huán)(a1a2an)和(b1b2bn)互不相交是指aibj,i,j=1,2,n。例如：這樣的表示是唯一的。置換的循環(huán)節(jié)數(shù)是上述表示中循環(huán)的個(gè)數(shù)。例如(13)(25)(4)的循環(huán)節(jié)數(shù)為3 2 1 3 4構(gòu)造置換群G=g1,g2,g3,g4,G4，令gi的循環(huán)節(jié)數(shù)為c(gi)(i=1,2,3,4)在G的作用下，其中 g1表示轉(zhuǎn)0,即g1=(1)(2)(3)(4)c(g1)=4 g2表示轉(zhuǎn)90,即g2=(4 3 2 1)c(g2)=1g3表示轉(zhuǎn)180,即g3=(1 3)(2 4)c(g3)=2g4表示轉(zhuǎn)270,即g4=(1 2 3 4)c(g4)=1我們可以發(fā)現(xiàn)，gi的同一個(gè)循環(huán)節(jié)中的對(duì)象涂以相同的顏色所得的圖像數(shù)mc(gi)好對(duì)應(yīng)中置換i作用下不變的圖象數(shù)，即2c(g1)=24=16=D(1)2c(g2)=21=2=D(2)2c(g3)=22=4 =D(3)2c(g4)=21=2=D(4)設(shè)G是p個(gè)對(duì)象的一個(gè)置換群，用m種顏色涂染p個(gè)對(duì)象，則不同染色方案為：其中G=g1,gs c(gi)為置換gi的循環(huán)節(jié)數(shù)(i=1s)這就是所謂的Plya定理。我們發(fā)現(xiàn)利用Plya定理的時(shí)間復(fù)雜度為O(sp)(這里s表示置換個(gè)數(shù)，p表示格子數(shù))，與前面得到的Burnside引理相比之下，又有了很大的改進(jìn)，其優(yōu)越性就十分明顯了。Plya定理充分挖掘了研究對(duì)象的內(nèi)在聯(lián)系，總結(jié)了規(guī)律，省去了許多不必要的盲目搜索，把解決這類問(wèn)題的時(shí)間規(guī)模降到了一個(gè)非常低的水平。Plya定理三步1 確定置換群 2 計(jì)算循環(huán)節(jié)個(gè)數(shù)3 代入公式 即利用Plya定理得到最后結(jié)果例例7.4.3 正6面體的6個(gè)面分別用紅，藍(lán)兩種顏色著色，有多少方案？設(shè)6個(gè)面分別是1，2，3，4，5，6，則S=1,2,3,4,5,6,找到S上的置換群G。（前3后5）如圖7.4.1所示，除了不動(dòng)置換外，有3種類型的旋轉(zhuǎn)：2614（a)(b)(c)（1）如圖（a）所示，經(jīng)過(guò)1和6兩個(gè)面中心所在直線的對(duì)稱軸的逆時(shí)針旋轉(zhuǎn)90，180和270。逆時(shí)針旋轉(zhuǎn)90的置換為(1)(2345)(6)，考慮位置的不同，同類的置換有3個(gè)。逆時(shí)針旋轉(zhuǎn)180的置換為(1)(24)(35)(6)，考慮位置的不同，同類的置換有3個(gè)。逆時(shí)針旋轉(zhuǎn)270的置換為(1)(5432)(6)，考慮位置的不同，同類的置換有3個(gè)。6142（2）如圖（b）所示，繞對(duì)面棱的中點(diǎn)所在直線的對(duì)稱軸逆時(shí)針旋轉(zhuǎn)180，對(duì)應(yīng)的置換為(16)(25)(34)，根據(jù)位置的不同，同類的置換有6個(gè)；2164（3）如圖（c）所示，繞對(duì)角線為對(duì)稱軸的逆時(shí)針旋轉(zhuǎn)120和240。逆時(shí)針旋轉(zhuǎn)120的置換為(346)(152)，考慮位置的不同，同類的置換有4個(gè)。逆時(shí)針旋轉(zhuǎn)240的置換為(643)(251)，考慮位置的不同，同類的置換有4個(gè)。2461因此|G|=24，根據(jù)Plya定理，不同的涂色方案數(shù)為，致謝祝大家在期末考試中取得好成績(jī)！