組合數(shù)學(xué)第四章習(xí)題解答

1、習(xí) 題,4.1 若群G的元素a均可表示為某一元素x的冪，即a=xm,則稱這個群為循環(huán)群，若群的元素交換率成立，即a,b?G滿足a?b=b?a,則稱這個群為阿貝爾群，試證明所有的循環(huán)群為阿貝爾群,證明：設(shè)G是一循環(huán)群，對任意的a,b?G,按定義a=xm,b=xn,a?b=xm?xn=xn?xm=b?a,因此，循環(huán)群都是阿貝爾群。,4.2 若x是群G的一個元素，存在一最小的正整數(shù)m，使xm=e，則稱m為x的階，試證：

2、 C={e,x,x2,…,xm-1}是G的一個子群,證明：顯然C中元素都是G中元素，只需證C滿中群的四個性質(zhì)即可(1)封閉性,對任意的xm,xn?C,由結(jié)合性，設(shè)m+n=r(mod m-1)xm?xn=xr,(2)結(jié)合律顯然(3)單位元顯然(4)逆元素為原群逆元素,4.3 設(shè)G是階為n的有限群，則G的所有元素的階都不超過n,單位元e顯然，對非單位元a，顯然,4.4 若G是階為n的循環(huán)群，求群G的母元素的

3、數(shù)目，即G的元素可表示成a的冪：a,a2,…,an的元素a的數(shù)目。,若a是母元素，則an=e,若ak(1<0<n)也是G的母元素，當(dāng)且僅當(dāng)ak的階為n,,即當(dāng)且僅當(dāng)k與n互素，與n互素的元素個數(shù)為?(n),,證明：如果k與n互素，則ak的階為n,顯然ak的階不能大于n,現(xiàn)證明ak的階不能小于n即可,,如果ak的階為m<n,則akm=e,則km=hn,n=km/h,這與n與k互素矛盾，,因此ak的階等于n,,證明：如果

4、ak的階為n, 則k與n互素，,證明：akn=e,且不存在m<n,使akm=e,則k與n互素,,設(shè)k與n不互素，存在h>1,k=hb,n=hc,kn=(hb)(hc),則(hb)c=kc=bn因此akc=abn=e,c<n矛盾,4.5 試證循環(huán)群的子群也是循環(huán)群。,顯然。,4.6 若H是G的子群，x和y是G的元素，試證：xH∩yH或為空，或xH=yH。,設(shè)a,b∈H,xa=yb,xH≠yH存在m∈H,xm屬于

5、xH但不屬于yH,x=yba-1,xm=yba-1m,由H是G的子群，因此ba-1m∈H, yba-1m∈yH,也就是xm∈yH，矛盾,4.7 若H是G的子群，|H|=k,試證：|xH|=k, 其中x∈G。,只需證：對任意a,b∈H,a≠b,有a≠b即可,設(shè)a,b∈H,a≠b,有xa=xb則左乘x的逆得a=b矛盾,4.8 有限群G的階為n,H是G的子群，則H的階必除盡G的階。,用4.6的結(jié)論,4.9 有限群G的階為n,x是G的元

6、素，則x的階必除盡G的階。,用4.2和4.8的結(jié)論,4.10 若x和y在群G作用下屬于同一等價類，則x所屬的等價類Ex，y所屬的等價類Ey有|Ex|=|Ey|。,顯然,4.11 有一個3×3的正方形棋盤，若用紅藍色對這9個格進行染色，要求兩個格著紅色，其余染藍色，問有多少種著色方案。,(1+x)9中x2項的系數(shù)是c(9,2)=36,4(1+x)3(1+x2)3中x2項的系數(shù)是4[c(3,2)c(3,0)+c(3,0)c(

7、3,1)]=24,2(1+x) (1+x4)2中x2項的系數(shù)是0,(1+x) (1+x2)4中x2項的系數(shù)是c(4,1)=4,P(x)中x5項的系數(shù)是(36+24+4)/8=8,4.12 試用貝恩塞特引理解n個人圍一圓桌坐下的方案問題。,只考慮圍中以旋轉(zhuǎn)變化。,旋轉(zhuǎn)0度(1)(2)…(n!),旋轉(zhuǎn)360/n度(12…n!),旋轉(zhuǎn)[360/n]×2度(135…n!2),旋轉(zhuǎn)[360/n]×(n-1)度(n!(n!-1

8、)…21),………………………………,共有n!種方案。,4.13 對正六角形的六個頂點用5種顏色進行染色，試問有多少種不同的方案，旋轉(zhuǎn)使之重合的算一種方案。,G (1)(2)(3)(4)(5)(6),(123456)(135)(246),(14)(25)(36),(153)(264),(165432),(1)(4)(26)(35), (2)(5)(13)(46),(3)(6)(15)(24),,(61)(25)(34), (12

9、)(36)(54), (23)(14)(56),,4.14 一個正方體的六個面用g,r,b,y四種顏色涂染，求其中兩個面用色g,兩個面用色y，其余一面用b，一面用r的方案數(shù)。,解：使正六面體重合的剛體運動群如下：,以上下的中心為軸線左旋90度，右旋90度：,不動置換(1)(2)(3)(4)(5)(6),(1)(2345)(6),(1)(5432)(6),正六面體有3對對面，這種置換有6個,以上下的中心為軸線左旋180度，,(1)(24

10、)(35)(6),,正六面體有3對對面，這種置換有3個,以對角線位置的平行棱的中以線為軸線旋轉(zhuǎn)180度，,(16)(25(34),這種形式的置換有6種,以對角線±120度位置,(345)(152),(643)(251),這種形式的置換有8個,求g2y2br的系數(shù),C(6,2)C(4,2)C(2,1)+3C(2,1)C(2,1)/24=8,4.15 對一個正六面體的8個頂點用y和r兩種顏色染色，使其中有5個頂點用色y，其余

11、三個頂點用色r，求其方案數(shù)。,4.16 用b,r,g這三種顏色的5顆珠子鑲成的圓環(huán)，共有幾種不同的方案？,構(gòu)造群G共有如下幾種置換,旋轉(zhuǎn),翻轉(zhuǎn),4.17 一個圓圈上有n個珠子，用n種顏色對這n個珠子著色，要求顏色數(shù)目不少于n的方案數(shù)是多少？,項鏈排列：n!/2n,4.18 若已給兩個r色的球，兩個b色的球，用它裝在正六面體的頂點，試問有多少不同的方案？,正六面體頂點的置換群見4.7例2 ，本題相當(dāng)于用2個r,兩個b,4個g色的

12、球裝在正六面體的8個頂點上。 其中r2b2g4 的系數(shù)為 [C(8,2)C(6,2)+9C(4,2)C(2,1)]/24=22,4.19 試說明S5群的不同格式及其個數(shù)，,9.解：5的拆分共有：00005,00014,00023, 00113,00122,01112,11111共七種，根據(jù)講義4.4節(jié)定理1可得S5中： (1)5共軛類有5!/5!=1個置換； (1)1(4)1共軛類有5!/4

13、=30個置換； (2)1(3)1共軛類有5!/(2·3)=20個置換； (1)2(3)1共軛類有5!/(2!3)=20個置換； (1)1(2)2共軛類有5!/(2!2 )=15個置換； (1)3(2)1共軛類有5!/(3!2)=10個置換； (5)1共軛類有5!/5=24個置換； ∴共有不同格式7種，如上所示。,4.20 圖4.5用兩種顏色著色的問題，若考慮互換顏色使

14、之一致的方案屬于同一類，問有多少種不同的方案,(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 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)(

15、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)(4 10)(57)(68)(11 12)(1

16、3)(14)(15)(16)(16+2+2+4+0+2+2+4)/8=4(種方案),4.21 在正四面體的每個面上都引一條高，有多少種方案？,解：除了繞頂點-對面的中心軸旋轉(zhuǎn)均不會產(chǎn)生不變的圖象外, 繞其他軸的旋轉(zhuǎn)相當(dāng)于正4面體的面3著色。參照講義4.6例3可得不同的方案數(shù)為M=[34+3·32]/12=9,解：除了繞面心—面心軸旋轉(zhuǎn)任何度數(shù)均不會產(chǎn)生不變的圖象外，繞其他軸的旋轉(zhuǎn)都相當(dāng)于正六面體的面4著色。

17、參照講義4.6例4可得不同的方案數(shù)為M=[4 +0·6·4 +0·3·4 +8·4 +6·4 ]/24=192,4.22一幅正方形的肖像與一個立方體的面一樣大，6幅相同的肖像貼在立方體的6個面上，有多少種貼法？,4.23 凸多面體中與一個頂點相關(guān)的各角之和與2?的差稱為該頂點的欠角，證明凸多面體各頂點欠角之和為4?,證：設(shè)V,S,E分別為頂點集，面集，邊(棱)集。由歐拉

18、定理 |V|+|S|－|E|=2. 設(shè)aij為與頂點vi，面Sj為相關(guān)的面角，ej為Sj的的邊數(shù)，給定Sj則∑aij=(ej－2)π 欠角和為∑(2π－∑aij)=∑2π－∑ ∑aij =2|V|π－∑ ∑aij=2|V|π－∑(ej－2)π =2|V|π－∑ejπ+2|S|π=2|V|π+2|S|π－2|E|π=4π,4.24 足球由正五邊形與正六邊形相嵌而成(a)一個

19、足球由多少正五邊形與正六邊形組成(b)把一個足球所有的正六邊形都著以黑色，正五邊形則著以其它各色，每個正五邊形著色各不相同，有多少種方案？,4.25 若G和G?是兩個群,G×G’的單位元素是(e,e’),試證G×G’是群,(1)封閉性顯然,(2)結(jié)合律顯然,(3)逆元素顯然,(4)單位元顯然,4.27 一個項鏈由7顆珠子裝飾成的，其中兩顆珠子是紅的，3顆是藍的，其余兩顆是綠的，問有多少種裝飾方案，試列舉之。

20、,,,,,,,,,1,2,3,4,5,6,7,G (1)(2)(3)(4)(5)(6)(7),(1234567),(1357246),(1473625),(1526374),(1642753),(1765432),(1)(27)(36)(45),(2)(13)(47)(56)(3)(24)(15)(67),(4)(17)(26)(35)共7個,[C(7,2)C(5,3)+7C(3,1)C(2,1)]/14=18,,,,,,,,

21、,1,2,3,4,5,6,7,,,,,,,,,1,2,3,4,5,6,7,,,,,,,,,1,2,3,4,5,6,7,,,,,,,,,1,2,3,4,5,6,7,例4.16 骰子的6個面分別有1,2,3,4,5,6個點，問有多少種不同的方案？,解法1,用Burnside引理,問題相當(dāng)于對正六面體的6個面，用6種顏色對之染色，要求各面的顏色都不一樣，求不同的方案數(shù)？,6個面用6種顏色涂染，各面顏色都不一樣，共有6!種方案。,設(shè)這6!

22、個方案為S1,S2,…,S720,,形成這720個元素的24個置換，設(shè)這24個置換為p0,p1,…,p23,其中p0為不動置換。,則c1(p0)=6!,27,因為6個面的顏色各不同，則除p0外，其它置換中不可能出現(xiàn)不動元素，,則c1(p1)=c1(p2)=…=c1(p23)=0，,解法2,用Polya定理與容斥原理,28,使正六面體重合的置換群為,(1)(2)(3)(4)(5)(6),(1)(2345)(6),(1)(5432)(6