組合數(shù)學(xué)第四章Pólya定理習(xí)題.ppt

1、2021/3/27,組合數(shù)學(xué),第四章習(xí)題,1.試證(4-2-2)對應(yīng)關(guān)系是同構(gòu)。解 2.試證對于有限群G的任一元素a , 存在一整數(shù)r , 使得a =e. 而且r必能整除g，g是群G的階。解 3.試證下列函數(shù)對于運算fg=f(g(x)是一個群。f1(x)=x, f2(x)=, f3(x)=1-x, f4(x)=, f5(x)=, f6(x)=. 解,1 x,1 1x,x1 x,x x1,r,2021/3/27,組合數(shù)學(xué),4.一正立方體的六個面用g,r,b,y四種顏色涂染，求其中兩個面用色g,兩個面用色y,其余一面用b,一面用r的方案數(shù)。 解 5.對一正六面體的八個頂點，用y和r兩種顏色染色，使

2、其中有5個頂點用色y,其余3個頂點用色r,求其方案數(shù)。 解 6.由b、r、g三種顏色的5顆珠子鑲成的圓環(huán)，共有幾種不同的方案?解,2021/3/27,組合數(shù)學(xué),7.一個圓圈上有n個珠，用n種顏色對這n個珠子著色，要求顏色數(shù)目不少于n的方案數(shù)。解 8.若已給兩個r色的球，兩個b色的球，用它裝在正六面體的頂點，試問有多少不同的方案?解 9.試說明S5群的不同格式及其個數(shù)。解 10.圖4-1-1用兩種顏色著色的問題，若考慮互換顏色使之一致的方案屬同一類，問有多少不同的圖象？解,2021/3/27,組合數(shù)學(xué),11.在正四面體的每個面上都任意引一條高，有多少方案？解 12.一幅正方形的肖像與一個立方體的

3、面一樣大，6副相同的肖像貼在立方體的6個面上有多少種貼法？解 13.凸多面體中與一個頂點相關(guān)的各面角之和與2的差稱為該頂點的欠角，證明凸多面體各頂點欠角之和為4.解 14.足球由正5邊形與正6邊形相嵌而成。 (a)一個足球由多少塊正5邊形與正6邊形組成？(b)把一個足球所有的正6邊形都著以黑色，正5邊形則著以其它各色，每個5邊形的著色都不同，有多少種方案？解,2021/3/27,組合數(shù)學(xué),15.(a)本質(zhì)上有多少種確實是2個輸入端的布爾電路？寫出其布爾表達式。 (b)本質(zhì)上有多少種確實是3個輸入端的布爾電路？解 16.用8個相同的骰子垛成一個正6面體，有多少方案？解 17.正六面體的6個面和8

4、個頂點分別用紅、藍兩種顏色的珠子嵌入。試問有多少種不同的方案數(shù)?(旋轉(zhuǎn)使之一致的方案看作是相同的).解,2021/3/27,組合數(shù)學(xué),習(xí)題解答,1.證：設(shè)G=a1,a2,an,指定G中任一元ai, 任意ajG，Pi：aj ajai ，則Pi是G上的一個置換，即以G為目標(biāo)集。Pi=( )， G的右正則表示f：ai( )=Pi。f是單射：aiaj，則PiPj f(aiaj) = ( ) =( )( )=f(ai)f(aj) 證畢。題,a1 a2 an a1ai a2ai anai,ai aai,a1 a2 an a1(aiaj) a2(aiaj) an(aiaj),a1 a2 an a1ai a2

5、ai anai,a1 a2 an (a1ai)aj (a2ai)aj (anai)aj,2021/3/27,組合數(shù)學(xué),2.證：設(shè)|G|=g,則a,a ,a ,a ,a 中必有相同元。a = a , 1klg+1 a =e. 1l-kg 對于給定的a，存在最小的正整數(shù)r,a =e .于是 H=a ,a ,a (=e)是G的子群，若HG,則存在a1不屬于H, 顯然，HHa1=,|H+Ha1|=2r若H+Ha1=G,則2r=g,r|g否則存在a2不屬于H+Ha1, Ha2(H+Ha1)=于是H+Ha1+Ha2+Hak=G,r(k+1)=g,r|g. 證畢。題,2 3 g g+1,k l,l-k,r

6、2 r,.,.,.,.,. . . .,2021/3/27,組合數(shù)學(xué),3.證：(a)封閉性：f1fi=f1(fi(x)=fi(x); f2f3=f2(f3(x)=f2(1-x)=1/(1-x)=f4(x); 同理一一列舉可得任意fi都屬于G; (b)結(jié)合律成立：運算相當(dāng)于把前面的計算結(jié)果帶入到后面的函數(shù)中，對于該數(shù)學(xué)運算，運算的先后順序與結(jié)果無關(guān)。結(jié)合律成立。 (c)存在單位元：e=f1; (d)存在逆元素： f1=e; f2f2=e; f3f3=e; f4f5=f5f4=e; f6f6=e;滿足群的條件，得證。題,2021/3/27,組合數(shù)學(xué),4.解：正6面體的轉(zhuǎn)動群用面的置換表示： 面心-

7、面心90 (1) (4) 6個 180 (1) (2) 3個 頂點-頂點 120 (3) 8個 棱中-棱中 180 (2) 6個不動 (1) 1個 P=(g+r+b+y) +6(g+r+b+y) (g +r +b +y ) +6(g + r + b + y ) +3(g+r+b+y) (g +r +b +y ) +8(g +r +b +y ) /24 其中g(shù) y br的系數(shù)為C(6,2)C(4,2)C(2,1)+3C(2,1)C(2,1)/24=8 題,。 。 。 。,2 2 2 2 3 6,6 2 4 4 4 4 2 2 2 2 3 2 2 2 2 2 2 3 3 3 3 2 2 2,202

8、1/3/27,組合數(shù)學(xué),5.解：相當(dāng)于4.7節(jié)中例2中求b r 的系數(shù)，為C(8,5)+8C(2,1)/24=3題 6.解：正5邊形的運動群 題 繞心轉(zhuǎn) 72 (5) 2個 144 (5) 2個 翻轉(zhuǎn) 180 (1)(2) 5個 不動 (1) 1個 不同方案數(shù)為m=(3 +43 +53 )/10=39 7.解：使重合的運動包括繞中心旋轉(zhuǎn)和繞水平對稱軸翻轉(zhuǎn)共產(chǎn)生2n個置換群。,5 3,。 。 。,1 1 2 5,5 1 3,2021/3/27,組合數(shù)學(xué),(續(xù)前)n個球用n種顏色著色共有n!種不同方案。因此，所求方案數(shù)為n!/2n. 題 8.解：正六面體頂點的置換群見4.7例2 ，本題相當(dāng)于用2個

9、r,兩個g,4個b色的球裝在正六面體的8個頂點上。 P=(r+g+b) +6(r +g +b ) +9(r +g +b ) +8(r+g+b) (r +g +b ) /24 其中r g b 的系數(shù)為 C(8,2)C(6,2)+9C(4,2)C(2,1)/24=22 題,8 4 4 4 2 2 2 2 4 2 3 3 3 2,2 2 4,2021/3/27,組合數(shù)學(xué),9.解：5的拆分共有：00005,00014,00023, 00113,00122,01112,11111共七種，根據(jù)講義4.4節(jié)定理1可得S5中： (1) 共軛類有5!/5!=1個置換； (1) (2) 共軛類有5!/(3!2)=

10、10個置換； (1) (2) 共軛類有5!/(2!2 )=15個置換； (1) (3) 共軛類有5!/(2!3)=20個置換； (1) (4) 共軛類有5!/4=30個置換； (2) (3) 共軛類有5!/(23)=20個置換； (5) 共軛類有5!/5=24個置換； 共有不同格式7種，如上所示。題,5,3 1,1 2,2,2 1,1 1,1 1,1,2021/3/27,組合數(shù)學(xué),10.解：類似講義4.4例2求： (1)不換色 不動：p1=(1)(2)(3)(4)(5)(6)(7)(8)(9)(13)(14)(15)(16) 逆時針轉(zhuǎn)90 :p2=(1)(2)(3456)(789 10)(11

11、 12)(13 14 15 16) 順時針轉(zhuǎn)90 :p3=(1)(2)(6543)(10 987)(11 12)(16 15 14 13) 轉(zhuǎn)180 :p4=(1)(2)(35)(46)(79)(8 10)(11 12)(13 15)(14 16) (2)換色 不動：p5=(12)(37)(48)(59)(6 10)(11 12)(13 14)(15 16) 逆時針轉(zhuǎn)90 :p6=(12)(385 10)(6749)(11)(12)(16 15 14 13) 順時針轉(zhuǎn)90 :p7=(12)(10 583)(9476)(11)(12)(13 14 15 16) 轉(zhuǎn)180 :p8=(12)(39)

12、(4 10)(57)(68)(11 12)(13)(14)(15)(16) (16+2+2+4+0+2+2+4)/8=4(種方案) 題,。,。,。,。,。,。,2021/3/27,組合數(shù)學(xué),11.解：除了繞頂點-對面的中心軸旋轉(zhuǎn)均不會產(chǎn)生不變的圖象外, 繞其他軸的旋轉(zhuǎn)相當(dāng)于正4面體的面3著色。參照講義4.6例3可得不同的方案數(shù)為 M=3 +083 +33 /12=9題 12.解：除了繞面心面心軸旋轉(zhuǎn)任何度數(shù)均不會產(chǎn)生不變的圖象外，繞其他軸的旋轉(zhuǎn)都相當(dāng)于正六面體的面4著色。參照講義4.6例4可得不同的方案數(shù)為 M=4 +064 +034 +84 +64 /24=192 題,4 2 2,6 3 4

13、 2 3,2021/3/27,組合數(shù)學(xué),13.證：設(shè)V,S,E分別為頂點集，面集，邊(棱)集。由歐拉定理 |V|+|S|E|=2. 設(shè)aij為與頂點vi，面Sj為相關(guān)的面角，ej為Sj的的邊數(shù)，給定Sj則aij=(ej2) 欠角和為(2aij)=2 aij =2|V| aij=2|V|(ej2) =2|V|ej+2|S|=2|V|+2|S|2|E|=4 題,SjS,SjS,SjS,vjV,SjS,vjV,SjS,vjV,vjV,vjV,2021/3/27,組合數(shù)學(xué),14.解：5邊形面心與體心連一直線從另一5邊形面心穿出。該直線為對稱軸。 欠角=360 (108 +2120 )=12 720 /

14、12 =60(個頂點) 603/2=90(條棱) 60/5=12(個5邊形) 602/6=20(個6邊形) 一個頂點通過一個轉(zhuǎn)動可與任一頂點重合，重合的方式只有1種，故轉(zhuǎn)動群的階為60。因為5邊形著色均不同，所以除不變置換的任意旋轉(zhuǎn)都不會產(chǎn)生不變圖象，12個5邊形著不同顏色共12!種方案。所以共有12!/60=7983360種方案。 題,。 。 。 。,2021/3/27,組合數(shù)學(xué),15.解：S2: (1)題 (1) (2) l=2 +2 /2=12 其中包括0個輸入端的2個，1個輸入端的2個，故確實是2個輸入端的布爾電路是8個。 S3: (1) 1個；(1) (3) 2個；(1) (2) 3

15、個 l=2 +22 +32 /6=80，8012=68， 確實是3輸入端的布爾電路本質(zhì)上有68個。,8 4 6,8 2 2 4 2,00 01 10 11 00 01 10 11,00 01 10 11 00 10 01 11,4 3,4 2 1,2021/3/27,組合數(shù)學(xué),16.解：相當(dāng)于正六面體每個角上放一個骰子。骰子按講義4.6中關(guān)于正立方體的不同旋轉(zhuǎn)均不會產(chǎn)生重合現(xiàn)象，共24種方案。因此本題相當(dāng)于正六面體的頂點24著色。但繞頂點-頂點的對稱軸旋轉(zhuǎn)不會產(chǎn)生重合的圖象。 參照習(xí)題11可得不同的方案數(shù)為 M=24 +624 +324 +0824 +624 /24 =8011008題,6 3 4