組合數(shù)學(xué)(27)

1、1第八章第八章 Polya計數(shù)法計數(shù)法14.3 Polya計數(shù)公式計數(shù)公式(一一) 本節(jié)課通過研究置換中的本節(jié)課通過研究置換中的循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu), 使得不使得不等價是著色問題計算變是簡單。等價是著色問題計算變是簡單。 設(shè)設(shè) f 是集合是集合X = 1,2,3,n的一個置換的一個置換, Df是是頂點(diǎn)集合為頂點(diǎn)集合為X并且弧集合為并且弧集合為Af = ( i, f(i) | i X 的有向圖。將有向圖的有向圖。將有向圖Df用圖論中的標(biāo)準(zhǔn)表示方用圖論中的標(biāo)準(zhǔn)表示方法記法記: Df = (X , Af ) 即用頂點(diǎn)集和邊集的序偶即用頂點(diǎn)集和邊集的序偶2表示。該有向圖的邊集是由弧構(gòu)成表示。該有向圖的邊集

2、是由弧構(gòu)成, 有向弧的起有向弧的起 點(diǎn)是點(diǎn)是i, 終點(diǎn)是通過置換得到的終點(diǎn)是通過置換得到的 f(i)，例如：，例如：7231458687654321: f置換是該有向圖如右圖所示該有向圖如右圖所示:我們能得到幾個小的循我們能得到幾個小的循環(huán)環(huán): 16351;2872; 44;167243853 以以3,5,6,7,8為起點(diǎn)的循環(huán)已經(jīng)包含在上述三個為起點(diǎn)的循環(huán)已經(jīng)包含在上述三個 循環(huán)中循環(huán)中; 我們將這種小循環(huán)定義成我們將這種小循環(huán)定義成循環(huán)循環(huán)。每個循環(huán)用中括號加一有序數(shù)組表示：每個循環(huán)用中括號加一有序數(shù)組表示： 循循 環(huán)環(huán)表表 達(dá)達(dá) 式式(有向圈有向圈)163511 6 3 528722 8

3、 7 244;4 保持一個循環(huán)不變。在這個循環(huán)外的元素保持一個循環(huán)不變。在這個循環(huán)外的元素都作恒等置換，表示成下列置換：都作恒等置換，表示成下列置換：4 以上這種保持一個循環(huán)不變。這個循環(huán)以上這種保持一個循環(huán)不變。這個循環(huán)外余下的元素都作恒等置換，稱這樣的置換為外余下的元素都作恒等置換，稱這樣的置換為循環(huán)置換循環(huán)置換或者或者循環(huán)環(huán)循環(huán)環(huán)。如果循環(huán)置換中的元素。如果循環(huán)置換中的元素87654321876543214726543818765432178287314526876543215361 5是是k個，我們就稱為個，我們就稱為k-循環(huán)，如循環(huán)，如1 6 3 5是是4-循環(huán)循環(huán) 置換置換 f 的

4、劃分的劃分Df = 1 6 3 5,2 8 7 2,4那么，置換那么，置換 f 就可以按劃分成循環(huán)環(huán)關(guān)于合成運(yùn)就可以按劃分成循環(huán)環(huán)關(guān)于合成運(yùn)算的因式分解。算的因式分解。 這是因?yàn)橹脫Q中的每個元素僅僅屬于因式這是因?yàn)橹脫Q中的每個元素僅僅屬于因式分解的某個循環(huán)因子。分解的某個循環(huán)因子。4287216357231458687654321f6設(shè)設(shè) f 是集合是集合X的任意置換，按上例推廣為：的任意置換，按上例推廣為： f =i1, i2, ., ip 。j1, j2, ., jq 。 。l1, l2, ., lr 其中集合其中集合X的各個元素只出現(xiàn)在某一個循環(huán)中。的各個元素只出現(xiàn)在某一個循環(huán)中。我們將

5、上式稱為置換我們將上式稱為置換f 的的循環(huán)因子分解循環(huán)因子分解，除循，除循環(huán)出現(xiàn)的次序外，環(huán)出現(xiàn)的次序外， f 的循環(huán)因子分解的唯一的。的循環(huán)因子分解的唯一的。例：正方形角點(diǎn)標(biāo)以例：正方形角點(diǎn)標(biāo)以1、2、3、4，在平面旋，在平面旋轉(zhuǎn)和空間翻轉(zhuǎn)可以得到轉(zhuǎn)和空間翻轉(zhuǎn)可以得到8個置換。個置換。71432 其中：其中：,432134241404cG;32144321;21434321;14324321;4321432134241404;12344321;34124321;41234321;2341432143218 對每個置換我們可以用下表描述因式分解對每個置換我們可以用下表描述因式分解置置 換換循環(huán)

6、的因式分解循環(huán)的因式分解1 。2 。3 。41 2 3 41 3 。2 41 4 3 21 。2 4 。31 3 。2 。41 2 。3 41 4 。2 32134241404349 由上表看出對與恒等置換由上表看出對與恒等置換的循環(huán)因子分解中，的循環(huán)因子分解中， 所有的的循環(huán)因子都是所有的的循環(huán)因子都是1-循環(huán)，這與恒等置循環(huán)，這與恒等置換保持所有元素不變這個事實(shí)相吻合。換保持所有元素不變這個事實(shí)相吻合。例：求例：求(10階二面體群階二面體群) 正五邊形的頂點(diǎn)對稱群中正五邊形的頂點(diǎn)對稱群中各置換的循環(huán)因子分解。各置換的循環(huán)因子分解。解：如右圖所示，置換是解：如右圖所示，置換是由平面由平面5個

7、個(360/5)的旋轉(zhuǎn)和沿的旋轉(zhuǎn)和沿51432510中垂線翻轉(zhuǎn)構(gòu)成。中垂線翻轉(zhuǎn)構(gòu)成。5123454321;34512543211234554321;4512354321;2345154321;4321554321;3215454321;2154354321;1543254321;5432154321543214535251505；和11對每個置換用下表描述循環(huán)因式分解對每個置換用下表描述循環(huán)因式分解置置 換換循環(huán)的因式分解循環(huán)的因式分解1 。2 。3 。4 。51 2 3 4 51 3 5 2 41 4 2 5 31 5 4 3 21 。2 5 。3 41 3 。2 。4 51 5 。3 。2

8、 41 2 。3 5 。41 4 。2 3 。505152535451234512注意：沿中垂線翻轉(zhuǎn)時，有一個頂點(diǎn)位置沒有改注意：沿中垂線翻轉(zhuǎn)時，有一個頂點(diǎn)位置沒有改 變，所以變，所以5個翻轉(zhuǎn)置換的循環(huán)因子中，總有個翻轉(zhuǎn)置換的循環(huán)因子中，總有一個一個1-循環(huán)出現(xiàn)。循環(huán)出現(xiàn)。 下面我們再討論循環(huán)因子在著色問題中應(yīng)用：下面我們再討論循環(huán)因子在著色問題中應(yīng)用：例：設(shè)例：設(shè) f 是集合是集合X = 1,2,3,n的一個置換的一個置換:283567194987654321f這個置換的循環(huán)因式分解為：這個置換的循環(huán)因式分解為：13 f =1 4 7 3 。2 9 。5 6 。8 假設(shè)我們能使用的顏色是紅色

9、、白色和藍(lán)色，假設(shè)我們能使用的顏色是紅色、白色和藍(lán)色，C是所有這樣的著色構(gòu)成的集合。問置換是所有這樣的著色構(gòu)成的集合。問置換 f 保保持持C中著色不變的中著色不變的 |C( f )| 是多少？是多少？解：設(shè)解：設(shè)c是保持置換是保持置換 f 下不變的著色下不變的著色: f * c = c ;先先考慮考慮4-循環(huán)循環(huán)1 4 7 3，該循環(huán)將，該循環(huán)將1的顏色變到的顏色變到4的顏色，的顏色，4的顏色變到的顏色變到7的顏色，的顏色，由于由于f 使使得得 c 不變，只能是它們有相同的著色不變，只能是它們有相同的著色 ;同理同理14 2-循環(huán)循環(huán)2 9和和5 6中兩點(diǎn)各分別著同一顏色，中兩點(diǎn)各分別著同一顏

10、色， 1-循環(huán)循環(huán)8沒有限制，可以著三種顏色的任沒有限制，可以著三種顏色的任意一種色，意一種色，我們對四個循環(huán)因子的每一個都能我們對四個循環(huán)因子的每一個都能提供三種顏色，如同對四個格子可重復(fù)填提供三種顏色，如同對四個格子可重復(fù)填3個個號碼，共計有：號碼，共計有：34 = 81種著色。種著色。 將本題擴(kuò)展到多個循環(huán)因子和將本題擴(kuò)展到多個循環(huán)因子和k種顏色的種顏色的一般情況中去，將置換一般情況中去，將置換 f 的循環(huán)因子分解中的循環(huán)因子分解中的循環(huán)因子數(shù)量記為：的循環(huán)因子數(shù)量記為： # (f ) ；15定理定理14.3.1設(shè)設(shè) f 是集合是集合X 的一個置換的一個置換, 假如用假如用k種顏種顏 色

11、對色對X 的元素著色，令的元素著色，令C是是X 的所有著色的的所有著色的集合，則集合，則 f 保持保持C中中著色不變著色不變的著色數(shù)為：的著色數(shù)為： |C( f )| = k#( f )例：用例：用紅色、白色和藍(lán)色對紅色、白色和藍(lán)色對正方形角點(diǎn)進(jìn)行著正方形角點(diǎn)進(jìn)行著色，問有多少色，問有多少不等價不等價的著色方案數(shù)？的著色方案數(shù)？解：正方形角點(diǎn)的置換共解：正方形角點(diǎn)的置換共8種，與循環(huán)因子關(guān)系種，與循環(huán)因子關(guān)系如下：如下：16置置 換換 f循環(huán)因子分解循環(huán)因子分解#( f )|C( f )|1 。2 。3 。4 434=811 2 3 4 131=31 3 。2 4 232=91 4 3 2 1

12、31=31 。2 4 。3 333=271 3 。2 。4 333=271 2 。3 4 232=91 4 。2 3 232=9041424341234由由Burnside定理得定理得C中不等價的著色數(shù)量中不等價的著色數(shù)量N(G,C)：21899272739381)(1),(GffCGCGN17 利用利用Burnside定理和定理定理和定理14.3.1給出的公式給出的公式)(#)()(1),(fGfkfCfCGCGN和 為我們提供了計算集合為我們提供了計算集合(在集合在集合X的一個置換群的一個置換群G的作用下的作用下)C中中不等價著色數(shù)不等價著色數(shù)的方法，其中的方法，其中, C是用給定顏色集對

13、是用給定顏色集對X的所有著色的集合。該方的所有著色的集合。該方法需要對各個置換求出循環(huán)因子分解；我們還法需要對各個置換求出循環(huán)因子分解；我們還可以引入置換個數(shù)的生成函數(shù)來解決此類問題?？梢砸胫脫Q個數(shù)的生成函數(shù)來解決此類問題。18置換數(shù)的生成函數(shù)置換數(shù)的生成函數(shù) 令令 f 是含有是含有n個元素的集合個元素的集合X的一個置換。的一個置換。假設(shè)假設(shè) f 的循環(huán)因子分解中有個的循環(huán)因子分解中有個e1個個1-循環(huán)循環(huán), e2個個2-循環(huán)循環(huán), en個個n-循環(huán)。因?yàn)檠h(huán)。因?yàn)閄的每一個元素的每一個元素僅僅出現(xiàn)在置換僅僅出現(xiàn)在置換 f 的某個循環(huán)因子中，所以，的某個循環(huán)因子中，所以，非負(fù)整數(shù)非負(fù)整數(shù)e1

14、, e2 , e3 ,. en滿足滿足: 1e1+2e2+3e3+. +nen = n我們將我們將n元組元組(e1, e2 , e3 ,. en)稱為置換稱為置換 f 的的型型。19記為：記為：type( f ) = (e1, e2 , e3 ,. en), 注意，我們注意，我們 定義過置換定義過置換 f 的循環(huán)因子數(shù)量記為：的循環(huán)因子數(shù)量記為：# f 那么：那么：# (f ) = e1+e2+e3+. +en 對每個對每個f 都都有自有自己的型；己的型；因?yàn)橐驗(yàn)?f 的型僅僅取決于的型僅僅取決于k-循環(huán)中的循環(huán)中的階數(shù)階數(shù)k，不關(guān)心每個元素在哪個循環(huán)中，所以，不關(guān)心每個元素在哪個循環(huán)中，所以

15、，不同的置換可以得到不同的置換可以得到相同相同的型。但置換的型的型。但置換的型僅僅能描述置換的循環(huán)因子分解中各個長度僅僅能描述置換的循環(huán)因子分解中各個長度因子的因子的個數(shù)個數(shù)，不能清楚每個循環(huán)的具體結(jié)構(gòu)。，不能清楚每個循環(huán)的具體結(jié)構(gòu)。20例如：對于集合例如：對于集合X=1,2,3,n，定義，定義X上的一個上的一個 置換：置換： f =1 4 7 3 。2 9 。5 6 。8f 的型為的型為(1,2,0,1) 還有：還有：e1=1; e2 =2; e3 =0; e4= 1；并有關(guān)系：并有關(guān)系：1e1+2e2+3e3+4e4 = 1+22+30+41= 9 成立成立 這個數(shù)正好是集合這個數(shù)正好是集

16、合X的基數(shù)。的基數(shù)。 我們引入我們引入n個未知量：個未知量：z1, z2, z3, ., zn。其中，其中，每個每個zk對應(yīng)一個對應(yīng)一個k-循環(huán)循環(huán)(k =1,2,3,.n)。21對于具有型為：對于具有型為： type( f ) = (e1, e2 , e3 ,. en) 的的 每個置換每個置換 f ，定義置換，定義置換 f 的單項(xiàng)式為：的單項(xiàng)式為：neneeezzzzfmon.)(321321 注意：置換注意：置換 f 單項(xiàng)式的次數(shù)單項(xiàng)式的次數(shù)(冪冪)為為f 的的循環(huán)因循環(huán)因子中循環(huán)個數(shù)的和子中循環(huán)個數(shù)的和: # (f ) = e1+e2+. +en 。 各置換的型決定了各置換的單項(xiàng)式，根據(jù)

17、定各置換的型決定了各置換的單項(xiàng)式，根據(jù)定理理14.3.1還能求出各置換作用還能求出各置換作用k個顏色集合個顏色集合C中著中著色不變的著色數(shù)：色不變的著色數(shù)： |C( f )| = k#( f )22 下面引入置換按照它的下面引入置換按照它的型型得到的生成函數(shù)：得到的生成函數(shù)： 設(shè)設(shè)G為為X上的一個置換群，對上的一個置換群，對G中的每一個置中的每一個置 換換 f 的單項(xiàng)式求和，稱該和式為的單項(xiàng)式求和，稱該和式為G中的置換中的置換f 按照型的生成函數(shù)按照型的生成函數(shù)。GfeneeeGfnzzzzfmon.)(321321 如果合并和式中的同類項(xiàng)，單項(xiàng)式如果合并和式中的同類項(xiàng)，單項(xiàng)式 的系數(shù)等于型為

18、的系數(shù)等于型為(e1, e2 , . en)的的G中的置換個數(shù)，中的置換個數(shù)，取定取定zk的顏色數(shù)量就得到不變的著色數(shù)的顏色數(shù)量就得到不變的著色數(shù)|C( f )| 。neneezzz.212123 定義：置換群定義：置換群G中的置換中的置換 f 按照型的生成函數(shù)按照型的生成函數(shù) 除以除以G中的置換個數(shù)中的置換個數(shù)|G|，稱為，稱為置換群置換群G的的循循環(huán)指數(shù)環(huán)指數(shù)。記為：。記為：PG (z1, z2 , z3 ,. zn) ;GfeneeenGnzzzzGzzzzP.1),.,(321321321 循環(huán)指數(shù)描述了循環(huán)指數(shù)描述了G中每個置換的循環(huán)因子結(jié)構(gòu)。中每個置換的循環(huán)因子結(jié)構(gòu)。例：求正方形頂

19、點(diǎn)關(guān)于平面旋轉(zhuǎn)、翻轉(zhuǎn)構(gòu)成的例：求正方形頂點(diǎn)關(guān)于平面旋轉(zhuǎn)、翻轉(zhuǎn)構(gòu)成的8階二面體群階二面體群D4的循環(huán)指數(shù)。的循環(huán)指數(shù)。解：列表描述置換、循環(huán)因子、型和置換單項(xiàng)式解：列表描述置換、循環(huán)因子、型和置換單項(xiàng)式24 8階二面體群階二面體群循環(huán)指數(shù)循環(huán)指數(shù):f循環(huán)因子分解循環(huán)因子分解型型單項(xiàng)式單項(xiàng)式1 。2 。3 。4 (4, 0, 0, 0)1 2 3 4 (0, 0, 0, 1)1 3 。2 4 (0, 2, 0, 0)1 4 3 2 (0, 0, 0, 1)1 。2 4 。3 (2, 1, 0, 0)1 3 。2 。4 (2, 1, 0, 0)1 2 。3 4 (0, 2, 0, 0)1 4 。2

20、3 (0, 2, 0, 0)0434241421434104030241zzzzz1414030201zzzzz2204032201zzzzz122104031221zzzzzz1414030201zzzzz122104031221zzzzzz2204032201zzzzz2204032201zzzzz)232(81),(122122144143214zzzzzzzzzPD25如果我們知道集合如果我們知道集合X的置換群的置換群G的循環(huán)指數(shù)的循環(huán)指數(shù), 那么那么 就能用指定的顏色集合，在就能用指定的顏色集合，在X的所有著色的所有著色集中求出集中求出不等價不等價的著色數(shù)量；的著色數(shù)量；定理定理14

21、.3.2 設(shè)設(shè)X是是n個元素的集合，假設(shè)用個元素的集合，假設(shè)用k種現(xiàn)種現(xiàn)有的顏色對有的顏色對X的元素著色。令的元素著色。令C是是X的所有的所有kn種種著色的集合，著色的集合，G是是X的一個置換群。則不等價的一個置換群。則不等價的著色數(shù)是用的著色數(shù)是用 zi=k (i=1,2,.n)代入代入G的循環(huán)的循環(huán)數(shù)中而得到的數(shù)，即：數(shù)中而得到的數(shù)，即：26 |N( G, C )| = PG(k, k,. ,k) 證明：由證明：由P358 Burnside定理定理(定理定理14.2.3)和和P365 定理定理14.3.1； G的循環(huán)指數(shù)是的循環(huán)指數(shù)是G中置換中置換 f 的單項(xiàng)式求和的平均值，即：的單項(xiàng)式求

22、和的平均值，即：GfeneeenGnzzzzGzzzP.1),.,(32132121 由定理由定理14.3.1可知，可知，置換置換 f 保持保持C 中著色不變中著色不變的著色數(shù)是：的著色數(shù)是：nneeeeeefkkkkk.2121.#27其中其中(e1, e2 , e3 ,. en)是置換是置換 f 的型。再由定理的型。再由定理 14.2.3可得不等價的著色數(shù)是：可得不等價的著色數(shù)是：),.,(.1),(21kkkPkkkGCGNGGfeeen例：例：求對正方形頂點(diǎn)進(jìn)行求對正方形頂點(diǎn)進(jìn)行k種著色后，種著色后，正方形頂正方形頂點(diǎn)的點(diǎn)的8階二面體群階二面體群D4的不等價著色數(shù)是多少？的不等價著色數(shù)

23、是多少？解：我們已經(jīng)有：解：我們已經(jīng)有：)232(81),(122122144143214zzzzzzzzzPD28由定理由定理14.3.2，不等價著色數(shù)是：不等價著色數(shù)是：)232(81)232(81),(2342244kkkkkkkkkkkkkPD如果顏色數(shù)量是如果顏色數(shù)量是3種，則種，則不等價著色數(shù)是：不等價著色數(shù)是：21)6275481(81)3233323(81)3 , 3 , 3 , 3(2344DP29例例:令令X=1,2,.,6表示立方體的表示立方體的6個面?zhèn)€面, 1表頂面；表頂面； 3表底面；表底面； 2表迎面；表迎面；4表背面；表背面； 5和和6表左、表左、 右側(cè)面。右側(cè)面

24、。 C=b,w表示黑、白兩種顏色。下面表示黑、白兩種顏色。下面在旋轉(zhuǎn)等價的意義下計算立方體染色的格式數(shù)。在旋轉(zhuǎn)等價的意義下計算立方體染色的格式數(shù)。 解：首先構(gòu)造立方體的解：首先構(gòu)造立方體的旋轉(zhuǎn)群旋轉(zhuǎn)群G，并把一種著色，并把一種著色看作看作X到到A的一個映射，的一個映射，14235630上、下底面不動，每次旋轉(zhuǎn)上、下底面不動，每次旋轉(zhuǎn)(右轉(zhuǎn)右轉(zhuǎn))一個面、一個面、 二個面、三個面，二個面、三個面， 可得可得X的的4個置換：個置換： f1: 132 6 4 5; f2: 132 46 5; f3: 132 5 4 6前、后面不動，每次旋轉(zhuǎn)前、后面不動，每次旋轉(zhuǎn)(逆時針逆時針)一個面、一個面、 二個二

25、個面、面、 三個面，三個面， 可得可得X的的3個置換：個置換： f4: 241 5 3 6; f5: 241 35 6; f6: 241 6 3 531 左、左、 右側(cè)面不動，右側(cè)面不動， 仿上可得三個置換：仿上可得三個置換： f7: 1 2 3 45 6; f: 1 32 456; f: 1 4 3 256 分別繞四條對角線旋轉(zhuǎn)分別繞四條對角線旋轉(zhuǎn)120、240可得可得8個置換個置換f10：1 4 56 3 2； f11：1 5 26 4 3 f12：1 5 46 2 3； f13：1 2 56 3 4 f14：1 2 63 4 5； f15：1 6 23 5 4 f16：1 6 43 5

26、2； f17：1 4 63 2 532此外分別以六對對角平行棱線的中點(diǎn)為軸線旋轉(zhuǎn)此外分別以六對對角平行棱線的中點(diǎn)為軸線旋轉(zhuǎn) 180,共可產(chǎn)生共可產(chǎn)生6個不同置換：個不同置換： f18：1 56 32 4； f19：1 63 52 4 f20：1 24 35 6； f21：1 42 35 6 f22：2 56 41 3； f23：2 65 41 3再加單位元再加單位元(幺置換幺置換): f24：123456; 共有共有24個置換，它們的型、單項(xiàng)式如下表：個置換，它們的型、單項(xiàng)式如下表：33f循環(huán)因子分解循環(huán)因子分解型型單項(xiàng)式單項(xiàng)式 f1132 6 4 5(2, 0, 0, 1, 0, 0) f2

27、132 46 5(2, 2, 0, 0, 0, 0) f3132 5 4 6(2, 0, 0, 1, 0, 0) f4241 5 3 6(2, 0, 0, 1, 0, 0) f5241 35 6(2, 2, 0, 0, 0, 0) f6241 6 3 5(2, 0, 0, 1, 0, 0) f71 2 3 45 6(2, 0, 0, 1, 0, 0) f81 32 456(2, 2, 0, 0, 0, 0) f91 4 3 256(2, 0, 0, 1, 0, 0) f101 4 56 3 2(0, 0, 2, 0, 0, 0) f111 5 26 4 3(0, 0, 2, 0, 0, 0)

28、f121 5 46 2 3(0, 0, 2, 0, 0, 0)1421040314030221zzzzzzzz1421040314030221zzzzzzzz23040304230201zzzzzzz1421040314030221zzzzzzzz1421040314030221zzzzzzzz1421040314030221zzzzzzzz2221040304032221zzzzzzzz2221040304032221zzzzzzzz1421040314030221zzzzzzzz2221040304032221zzzzzzzz23040304230201zzzzzzz23040304230

29、201zzzzzzz34f循環(huán)因子分解循環(huán)因子分解型型單項(xiàng)式單項(xiàng)式 f131 2 56 3 4(0, 0, 2, 0, 0, 0) f141 2 63 4 5(0, 0, 2, 0, 0, 0) f151 6 23 5 4(0, 0, 2, 0, 0, 0) f161 6 43 5 2(0, 0, 2, 0, 0, 0) f171 4 63 2 5(0, 0, 2, 0, 0, 0) f181 56 32 4(0, 3, 0, 0, 0, 0) f191 63 5 2 4(0, 3, 0, 0, 0, 0) f201 24 35 6(0, 3, 0, 0, 0, 0) f211 42 35 6

30、(0, 3, 0, 0, 0, 0) f222 56 4 1 3(0, 3, 0, 0, 0, 0) f232 65 4 1 3(0, 3, 0, 0, 0, 0) f24123456(6, 0, 0, 0, 0, 0)32040304033201zzzzzzz23040304230201zzzzzzz61040304030261zzzzzzz23040304230201zzzzzzz23040304230201zzzzzzz23040304230201zzzzzzz23040304230201zzzzzzz32040304033201zzzzzzz32040304033201zzzzzzz3

31、2040304033201zzzzzzz32040304033201zzzzzzz32040304033201zzzzzzz35上述立方體的染色問題中，上述立方體的染色問題中， G的循環(huán)指數(shù)為的循環(huán)指數(shù)為:從而，六面體每面可染兩種顏色的方案數(shù)為：從而，六面體每面可染兩種顏色的方案數(shù)為： 248663),(2332421222161654321xxxxxxxxxxxxxPG102424024488686163642428262262232)2 , 2 , 2 , 2 , 2 , 2(282226GP36例例:正三角形正三角形V1V2V3，若以紅、白、藍(lán)三色涂染，若以紅、白、藍(lán)三色涂染 各頂點(diǎn)，各

32、頂點(diǎn)， 試求置換等價意義下的染色方案？試求置換等價意義下的染色方案？解解:構(gòu)造三角形的旋轉(zhuǎn)置換群構(gòu)造三角形的旋轉(zhuǎn)置換群G。分別繞形心旋。分別繞形心旋轉(zhuǎn)轉(zhuǎn)(逆旋逆旋) 0、 120、240可得三置換：可得三置換： f0: V1V2V3 ; f1: V1V2V3; f2: V3V2V1 分別繞三邊中垂線翻轉(zhuǎn)分別繞三邊中垂線翻轉(zhuǎn)180可得三個置換：可得三個置換：f3: V1V2V3; f4: V1V3V2; f5: V1V2V337故不同方案數(shù)為故不同方案數(shù)為106276276333323) 3 , 3 , 3(13GP例：對正四面體的例：對正四面體的4個頂點(diǎn)用個頂點(diǎn)用4種顏色著色，求置種顏色著色，

33、求置 換等價意義下的不同方案數(shù)。換等價意義下的不同方案數(shù)。 解：使正四面體解：使正四面體V1 V2 V3 V4重合的剛體運(yùn)動有兩重合的剛體運(yùn)動有兩類，一類是繞各面的中垂線分別旋轉(zhuǎn)類，一類是繞各面的中垂線分別旋轉(zhuǎn) 0、632),(12111331321xxxxxxxPG38120和和240；一類是繞過二對邊中點(diǎn)的連線；一類是繞過二對邊中點(diǎn)的連線 旋轉(zhuǎn)旋轉(zhuǎn)180，從而可得群，從而可得群G的各置換如下：的各置換如下：V1V2V3V4； V1V2V3V4 V1V4V3V2； V2V1 V3 V4 V2V4V3V1; V3V1 V2 V4 V3V4V2 V1; V4V1 V2 V3 V4V3 V2V1;

34、 V1 V2V3 V4 V1 V3V2 V4; V1 V4V2 V3132439 置換的型分別為置換的型分別為: (4, 0, 0, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (0, 2, 0, 0); (0, 2, 0, 0); (0, 2, 0, 0); 對應(yīng)的單項(xiàng)式和：對應(yīng)的單項(xiàng)式和：x14+(x1x3+ x1x3+ x1x3+ x1x3+ x1x3+ x1x3+ x1x3+ x1x3)+(x22+x22 +x22)= x14+8x1x3 +3x2