組合數(shù)學(xué)置換群與Pólya定理

1、ACM暑期集訓(xùn) 組合數(shù)學(xué)（5） 置換群與Pólya定理1 群的基本概念2 置換群POJ 2369 Permutations 求置換P的秩k（order）：Pk=IPOJ 1026 Cipher 求置換P的k次冪Pk。題目大意：首先輸入長度為n的數(shù)字串構(gòu)成置換P。然后求字符序列Src進(jìn)行k次置換后的字符序列。POJ 1721 CARDS 已知置換P的k次冪Pk，求P（是k次方根嗎）2 置換的奇偶性POJ 3128 Leonardo's Notebook 已知置換P，求一個置換M，使P=M2劉汝佳的分析：考慮某個置換的平方。對于其中長度為奇數(shù)的輪換，平方以后這個輪換仍然為一個輪換

2、只是元素順序換了。一個長度為偶數(shù)的輪換，平方以后就變?yōu)閮蓚€大小相等的輪換了。因此，對于給定的置換，當(dāng)中所有長度為奇數(shù)的輪換，可以直接當(dāng)做是它原先平方產(chǎn)生的。而長度為偶數(shù)的輪換，必須一一配對，當(dāng)做原先拆出來的。滿足這個條件，就是平方。3 Pólya波利亞定理應(yīng)用Polya定理的解題思路：（1）認(rèn)定對象集合X（2）找出置換群G（3）分析每個置換的輪換指數(shù) （4）代入Polya定理例1：正六面體6個面用紅、藍(lán)著色，有多少種方案？旋轉(zhuǎn)重合算同一種方案。解：使正六面體重合的剛體運動有5類：繞對面中心連線旋轉(zhuǎn)正負(fù)90度(共3*2種)；旋轉(zhuǎn)180度(共3種)；繞對棱中點連線旋轉(zhuǎn)180度(共6種)；

3、繞對角線旋轉(zhuǎn)正負(fù)120度(共4*2種)；不動變換。 以1,2,3,4,5,6分別記正六面體的上,下,左,右,前,后六個面, 則G=(1)(2)(3)(4)(5)(6),(1)(2)(3546)(類似的有6個), (1)(2)(34)(56)(類似的有3個),(12)(35)(46)(類似的有6個), (253)(164) (類似的有8個)。所以例2：將等邊三角形的三個頂點用紅、藍(lán)、綠三種顏色進(jìn)行著色,問有多少種不同的著色方案? 如果 (1) 經(jīng)旋轉(zhuǎn)能重合的方案認(rèn)為是相同的？ (2) 經(jīng)旋轉(zhuǎn)和翻轉(zhuǎn)能重合的方案認(rèn)為是相同的？解 (1) 等邊三角形的三個頂點分別標(biāo)記為1,2,3. 1,2,3上的置換群為 G=e,(123),(132)其循環(huán)指標(biāo)為所求染色方案數(shù)為 (2) 只是將(1)中的置換群變成 G=e,(123),(132),(1)(23),(2)(13),(3)(12)其循環(huán)指標(biāo)為 所求染色方案數(shù)為：POJ 2409 Let it Bead 用M種顏色的寶石嵌套長度為N的項鏈，求出本質(zhì)不同的方案數(shù)。分旋轉(zhuǎn)和翻