1、第七章 Plya計(jì)數(shù)定理,借助于“群”計(jì)數(shù) (1)群的構(gòu)造; (2) Plya定理. Plya,匈牙利數(shù)學(xué)家,以群論為理論基礎(chǔ),結(jié)合生成函數(shù)建立起來的一個(gè)定理,它是解決組合計(jì)數(shù)問題最重要的工具之一。,7.1 關(guān)系和群,1. 群的定義及例子 (1) (2) (3) (4) 2 子群及其(|H| )判定,7.2 置換群的輪換指標(biāo),1. S上的置換, S = 1, 2, , n (1)S上的置換p: S S (2)置換的個(gè)數(shù): n! (3)置換的記法 (a) p(i) = ai, i = 1, 2, , n S = 1, 2, 3, 4,雙射,1 2 2 4 3 1 4 3,1 1 2 2 3 4

2、4 3,p = (1243),p = (1)(2)(43),p:,p:,(b) (c) p = ()(.)(.)(.) S = 1, 2, 3, S3 = (1)(2)(3), (12)(3), (13)(2), (1)(23), (123), (132),(4)置換的運(yùn)算,2. 置換群 (1) Def 若干S = 1, 2, ,n上的置換組成的集合，在映射“”下構(gòu)成的群稱為S上的置換群。 (2) Theorem 群 H S3 , ,例1,G = (1)(2)(3)(4)(5), (15)(24)(3),1,2,3,4,5,例2,1,2,3,G = S3 = (1)(2)(3), (12)(3

3、), (13)(2), (1)(23), (123), (132),例3,1,2,3,4,G = (1)(2)(3)(4), (1234), (13)(24), (1432), (14)(23), (13)(2)(4), (12)(34), (1)(24)(3),例4,1,2,3,4,5,G = (1)(2)(3)(4)(5), (12345), (13524), (14253), (15432), (15)(24)(3), (14)(23)(5), (13)(2)(45), (12)(35)(4), (1)(25)(34),例5,1,2,3,4,G = (1)(2)(3)(4), (1)(2

4、34), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), (4)(132), (12)(34), (13)(24), (14)(23),例6 一個(gè)物體“所有”的剛體運(yùn)動(dòng)，在復(fù)合映射下必作成群！,7.3 Burnside引理,Burnside引理 為證明Plya定理做準(zhǔn)備。,7.4 圓（環(huán)）排列,一、兩類圓排列,二、r元集的n-可重圓排列,三、多重集的圓排列,7.5 Plya定理,Plya定理: 設(shè)G是n個(gè)對(duì)象上的置換群，用m種顏色涂染這n個(gè)對(duì)象，則不同的染色方案數(shù)為 其中, c(g)為置換g的循環(huán) 含1循環(huán)節(jié)的個(gè)數(shù)。,例1

5、例6 例 Solution G = (1)(2)(3)(4), (1234), (13)(24), (1432) 注意 按要求構(gòu)造群,1,2,3,4,例(2000年)一個(gè)正方形被分為四個(gè)大小相同的方格。用n種不同的顏色對(duì)四個(gè)方格染色，每個(gè)方格染一種顏色。兩種染色方案稱為同一染色款式當(dāng)且僅當(dāng)圖形經(jīng)過某種旋轉(zhuǎn)或在空中翻轉(zhuǎn)使一種染色方案變成另一種染色方案。試求不同的染色款式數(shù)。,Solution G = (1)(2)(3)(4), (1234), (13)(24), (1423), (12)(34), (14)(23), (13)(2)(4), (1)(3)(24),1,2,3,4,例 用紅(r)、

6、藍(lán)(b)、綠(g)三種顏色對(duì)正三角形的頂點(diǎn)和中心涂色，求不同的涂色方案數(shù)。經(jīng)旋轉(zhuǎn)或翻轉(zhuǎn)能使之重合的方案算一種。 Solution G = (1)(2)(3)(4), (123)(4), (132)(4), (1)(4)(23), (2)(4)(13), (3)(4)912) 30,1,2,3,4,例 用8個(gè)相同的骰子垛成一個(gè)正6面體，有多少方案? Hint 看成用m種顏色對(duì)正六面體的頂點(diǎn)染色。 Key: m = ? 每個(gè)頂點(diǎn)相鄰有3個(gè)面：m = 38 = 24.,既可用于計(jì)數(shù)，又可用于對(duì)狀態(tài)的列舉。 研究的內(nèi)容：滿足某種特定條件的方案及方案數(shù)： 研究的方法：,Def(群G的輪換指數(shù)) n個(gè)對(duì)象，m種顏色: b1, b2, , bm: 其中ci(g)表示置換g的長(zhǎng)度為i的循環(huán)節(jié)數(shù)目。 Theorem 在G的輪換指數(shù)中，令,則其展開式中 前面的系數(shù)表示有1