组合数学第四章习题解答PPT课件

1、1习习 题题4.1 若群若群G的元素的元素a均可表示为某一元素均可表示为某一元素x的幂，即的幂，即a=xm,则称这个群为循环群，若群的元素交换率成则称这个群为循环群，若群的元素交换率成立，即立，即a,b G满足满足a b=b a,则称这个群为阿贝尔群，则称这个群为阿贝尔群，试证明所有的循环群为阿贝尔群试证明所有的循环群为阿贝尔群证明：设证明：设G是一循环群，对任意的是一循环群，对任意的a,b G,按定义按定义a=xm,b=xn,a b=xm xn=xn xm=b a,因此，循环群都是阿贝尔群。因此，循环群都是阿贝尔群。24.2 若若x是群是群G的一个元素，存在一最小的正整数的一个元素，存在一最

2、小的正整数m，使使xm=e，则称，则称m为为x的阶，试证：的阶，试证： C=e,x,x2,xm-1是是G的一个子群的一个子群证明：显然证明：显然C中元素都是中元素都是G中元素，只需证中元素，只需证C满中满中群的四个性质即可群的四个性质即可(1)封闭性封闭性,对任意的对任意的xm,xn C,由结合性，设由结合性，设m+n=r(mod m-1)xm xn=xr,(2)结合律显然结合律显然(3)单位元显然单位元显然(4)逆元素为原群逆元素逆元素为原群逆元素34.3 设设G是阶为是阶为n的有限群，则的有限群，则G的所有元素的阶都不的所有元素的阶都不超过超过n单位元单位元e显然，对非单位元显然，对非单位

3、元a，显然，显然44.4 若若G是阶为是阶为n的循环群，求群的循环群，求群G的母元素的数目，的母元素的数目，即即G的元素可表示成的元素可表示成a的幂：的幂：a,a2,an的元素的元素a的数目。的数目。若若a是母元素，则是母元素，则an=e若若ak(10n)也是也是G的母元素，当且仅当的母元素，当且仅当ak的阶为的阶为n,即当且仅当即当且仅当k与与n互素，与互素，与n互素的元素个数为互素的元素个数为 (n),证明：如果证明：如果k与与n互素，则互素，则ak的阶为的阶为n,显然显然ak的阶不能大于的阶不能大于n,现证明现证明ak的阶不能小于的阶不能小于n即可即可,如果如果ak的阶为的阶为mn,则则

4、akm=e,则则km=hn,n=km/h,这与这与n与与k互素矛盾，互素矛盾，因此因此ak的阶等于的阶等于n,5证明：如果证明：如果ak的阶为的阶为n, 则则k与与n互素，互素，证明：证明：akn=e,且不存在且不存在m1,k=hb,n=hc,kn=(hb)(hc),则则(hb)c=kc=bn因此因此akc=abn=e,cn矛盾矛盾64.5 试证循环群的子群也是循环群。试证循环群的子群也是循环群。显然。显然。4.6 若若H是是G的子群，的子群，x和和y是是G的元素，试证：的元素，试证：xHyH或为空，或或为空，或xH=yH。设设a,bH,xa=yb,xHyH存在存在mH,xm属于属于xH但不属

5、于但不属于yHx=yba-1,xm=yba-1m,由由H是是G的子群，因此的子群，因此ba-1mH, yba-1myH也就是也就是xmyH，矛盾，矛盾74.7 若若H是是G的子群，的子群，|H|=k,试证：试证：|xH|=k, 其中其中xG。只需证：对任意只需证：对任意a,bH,ab,b,有有abb即即可可设设a,bH,ab,b,有有x xa=xb b则左乘则左乘x x的逆得的逆得a=ba=b矛盾矛盾84.8 有限群有限群G的阶为的阶为n,H是是G的子群，则的子群，则H的阶必除的阶必除尽尽G的阶。的阶。用用4.6的结论的结论94.9 有限群有限群G的阶为的阶为n,x是是G的元素，则的元素，则x

6、的阶必除的阶必除尽尽G的阶。的阶。用用4.2和和4.8的结论的结论104.10 若若x和和y在群在群G作用下属于同一等价类，则作用下属于同一等价类，则x所所属的等价类属的等价类Ex，y所属的等价类所属的等价类Ey有有|Ex|=|Ey|。显然显然114.11 有一个有一个33的正方形棋盘，若用红蓝色对这的正方形棋盘，若用红蓝色对这9个格进行染色，要求两个格着红色，其余染蓝色，个格进行染色，要求两个格着红色，其余染蓝色，问有多少种着色方案。问有多少种着色方案。123456789)1)(1 ()1)(1 (2 )1 ()1 (4)1(81)(42243239xxxxxxxxP(1+x)9中中x2项的

7、系数是项的系数是c(9,2)=364(1+x)3(1+x2)3中中x2项的系数是项的系数是4c(3,2)c(3,0)+c(3,0)c(3,1)=242(1+x) (1+x4)2中中x2项的系数是项的系数是0(1+x) (1+x2)4中中x2项的系数是项的系数是c(4,1)=4P(x)中中x5项的系数是项的系数是(36+24+4)/8=8124.12 试用贝恩塞特引理解试用贝恩塞特引理解n个人围一圆桌坐下的个人围一圆桌坐下的方案问题。方案问题。只考虑围中以旋转变化。只考虑围中以旋转变化。旋转旋转0度度(1)(2)(n!)旋转旋转360/n度度(12n!)旋转旋转360/n2度度(135n!2)旋

8、转旋转360/n(n-1)度度(n!(n!-1)21)(.)()(112111gacacacnl共有共有n!种方案。种方案。)!1( !1nnn134.13 对正六角形的六个顶点用对正六角形的六个顶点用5种颜色进行染色，种颜色进行染色，试问有多少种不同的方案，旋转使之重合的算一试问有多少种不同的方案，旋转使之重合的算一种方案。种方案。1 12 23 34 45 56 6G (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)(

9、24),(61)(25)(34), (12)(36)(54), (23)(14)(56),5352545251214326N1505144.14 一个正方体的六个面用一个正方体的六个面用g,r,b,y四种颜色涂染，四种颜色涂染，求其中两个面用色求其中两个面用色g,两个面用色两个面用色y，其余一面用，其余一面用b，一面用一面用r的方案数。的方案数。 解：使正六面体重合的刚体运动群如下：解：使正六面体重合的刚体运动群如下： 以上下的中心为轴线左旋以上下的中心为轴线左旋90度，右旋度，右旋90度：度： 不动置换不动置换(1)(2)(3)(4)(5)(6) (1)(2345)(6),(1)(5432)

10、(6) 正六面体有正六面体有3对对面，这种置换有对对面，这种置换有6个个 以上下的中心为轴线左旋以上下的中心为轴线左旋180度，度， (1)(24)(35)(6), 正六面体有正六面体有3对对面，这种置换有对对面，这种置换有3个个15 以对角线位置的平行棱的中以线为轴线旋转以对角线位置的平行棱的中以线为轴线旋转180度，度， (16)(25(34) 这种形式的置换有这种形式的置换有6种种 以对角线以对角线120120度度位置位置 (345)(152) (643)(251) 这种形式的置换有这种形式的置换有8个个)( 8)( 6)()(3)()(6)(241)(23333322222222224

11、44426ybrgybrgybrgybrgybrgybrgybrgGP16求求g2y2br的系数的系数)( 8)( 6)()(3)()(6)(241)(2333332222222222444426ybrgybrgybrgybrgybrgybrgybrgGPC(6,2)C(4,2)C(2,1)+3C(2,1)C(2,1)/24=8174.15 对一个正六面体的对一个正六面体的8个顶点用个顶点用y和和r两种颜色两种颜色染色，使其中有染色，使其中有5个顶点用色个顶点用色y，其余三个顶点用，其余三个顶点用色色r，求其方案数。，求其方案数。184.16 用用b,r,g这三种颜色的这三种颜色的5颗珠子镶成

12、的圆环，颗珠子镶成的圆环，共有几种不同的方案？共有几种不同的方案？构造群构造群G共有如下几种置换共有如下几种置换1 12 23 34 45 5 5432112345135241543214253旋转旋转翻转翻转 34251 45132 15243 35124 23145.1)()()(21gacacacmmmGl353431013539194.17 一个圆圈上有一个圆圈上有n个珠子，用个珠子，用n种颜色对这种颜色对这n个个珠子着色，要求颜色数目不少于珠子着色，要求颜色数目不少于n的方案数是多少？的方案数是多少？项链排列：项链排列：n!/2n204.18 若已给两个若已给两个r色的球，两个色的球

13、，两个b色的球，用它装色的球，用它装在正六面体的顶点，试问有多少不同的方案？在正六面体的顶点，试问有多少不同的方案？正六面体顶点的置换群见正六面体顶点的置换群见4.7例例2 ，本题相当于用，本题相当于用2个个r,两个两个b,4个个g色的球装在正六面体的色的球装在正六面体的8个顶点上。个顶点上。 其中其中r2b2g4 的系数为的系数为 C(8,2)C(6,2)+9C(4,2)C(2,1)/24=22214.19 试说明试说明S5群的不同格式及其个数，群的不同格式及其个数， 9.解：解：5的拆分共有：的拆分共有：00005,00014,00023, 00113,00122,01112,11111共

14、七种，根据讲义共七种，根据讲义4.4节定理节定理1可得可得S5中：中： (1)5共轭类有共轭类有5!/5!=1个置换；个置换； (1)1(4)1共轭类有共轭类有5!/4=30个置换；个置换； (2)1(3)1共轭类有共轭类有5!/(23)=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种，如上所示。种，如上所示。224.2

15、0 图图4.5用两种颜色着色的问题，若考虑互换颜用两种颜色着色的问题，若考虑互换颜色使之一致的方案属于同一类，问有多少种不同色使之一致的方案属于同一类，问有多少种不同的方案的方案(1)(1)不换色不换色不动：不动：p1=(1)(2)(3)(4)(5)(6)(7)(8)(9)(13)(14)(15)(16)p1=(1)(2)(3)(4)(5)(6)(7)(8)(9)(13)(14)(15)(16)逆时针转逆时针转90 :p2=(1)(2)(3456)(789 10)(11 12)(13 14 15 16)90 :p2=(1)(2)(3456)(789 10)(11 12)(13 14 15 16

16、)顺时针转顺时针转90 :p3=(1)(2)(6543)(10 987)(11 12)(16 15 14 13)90 :p3=(1)(2)(6543)(10 987)(11 12)(16 15 14 13)转转180 :p4=(1)(2)(35)(46)(79)(8 10)(11 12)(13 15)(14 16)180 :p4=(1)(2)(35)(46)(79)(8 10)(11 12)(13 15)(14 16)(2)(2)换色换色不动：不动：p5=(12)(37)(48)(59)(6 10)(11 12)(13 14)(15 16)p5=(12)(37)(48)(59)(6 10)(1

17、1 12)(13 14)(15 16)逆时针转逆时针转90 :p6=(12)(385 10)(6749)(11)(12)(16 15 14 13)90 :p6=(12)(385 10)(6749)(11)(12)(16 15 14 13)顺时针转顺时针转90 :p7=(12)(10 583)(9476)(11)(12)(13 14 15 16)90 :p7=(12)(10 583)(9476)(11)(12)(13 14 15 16)转转180 :p8=(12)(39)(4 10)(57)(68)(11 12)(13)(14)(15)(16)180 :p8=(12)(39)(4 10)(57)

18、(68)(11 12)(13)(14)(15)(16)(16+2+2+4+0+2+2+4)/8=4(16+2+2+4+0+2+2+4)/8=4(种方案种方案) )234.21 在正四面体的每个面上都引一条高，有多少在正四面体的每个面上都引一条高，有多少种方案？种方案？解：除了绕顶点解：除了绕顶点- -对面的中心轴旋转均不会对面的中心轴旋转均不会产生不变的图象外产生不变的图象外, , 绕其他轴的旋转相当于正绕其他轴的旋转相当于正4 4面体的面面体的面3 3着色。参照讲义着色。参照讲义4.64.6例例3 3可得不同的可得不同的方案数为方案数为M=3M=34 4+33+332 2/12=9/12=9

19、24解：除了绕面心解：除了绕面心面心轴旋转任何度数面心轴旋转任何度数均不会产生不变的图象外，绕其他轴的旋转均不会产生不变的图象外，绕其他轴的旋转都相当于正六面体的面都相当于正六面体的面4 4着色。着色。参照讲义参照讲义4.64.6例例4 4可得不同的方案数为可得不同的方案数为M=4 +064 +034 +84 +64 /24=192M=4 +064 +034 +84 +64 /24=1924.22一幅正方形的肖像与一个立方体的面一样大，一幅正方形的肖像与一个立方体的面一样大，6幅相同的肖像贴在立方体的幅相同的肖像贴在立方体的6个面上，有多少种个面上，有多少种贴法？贴法？254.23 凸多面体中

20、与一个顶点相关的各角之和与凸多面体中与一个顶点相关的各角之和与2 的差称为该顶点的欠角，证明凸多面体各顶点欠的差称为该顶点的欠角，证明凸多面体各顶点欠角之和为角之和为4 证：设证：设V,S,E分别为顶点集，面集，边分别为顶点集，面集，边(棱棱)集。集。由欧拉定理由欧拉定理 |V|+|S|E|=2. 设设aij为与顶点为与顶点vi，面面Sj为相关的面角，为相关的面角，ej为为Sj的的边数，的的边数，给定给定Sj则则aij=(ej2) 欠角和为欠角和为(2aij)=2 aij =2|V| aij=2|V|(ej2) =2|V|ej+2|S|=2|V|+2|S|2|E|=4264.24 足球由正五边

21、形与正六边形相嵌而成足球由正五边形与正六边形相嵌而成(a)一个足球由多少正五边形与正六边形组成一个足球由多少正五边形与正六边形组成(b)把一个足球所有的正六边形都着以黑色，正五把一个足球所有的正六边形都着以黑色，正五边形则着以其它各色，每个正五边形着色各不相边形则着以其它各色，每个正五边形着色各不相同，有多少种方案？同，有多少种方案？274.25 若若G和和G 是两个群是两个群),() ,)(,(,) ,(21212211ggggggggGgGgggGGGG的单位元素是的单位元素是(e,e),试证试证GG是群是群(1)封闭性显然封闭性显然(2)结合律显然结合律显然(3)逆元素显然逆元素显然(4

22、)单位元显然单位元显然28 4.27 一个项链由一个项链由7颗珠子装饰成的，其中两颗珠颗珠子装饰成的，其中两颗珠子是红的，子是红的，3颗是蓝的，其余两颗是绿的，问有多少颗是蓝的，其余两颗是绿的，问有多少种装饰方案，试列举之。种装饰方案，试列举之。1 12 23 34 45 56 67 7G (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个个)(7)(6

23、)(141)(32227777rgbrgbrgbrgbGP29)(7)(6)(141)(32227777rgbrgbrgbrgbGP的系数是232gbrC(7,2)C(5,3)+7C(3,1)C(2,1)/14=181 12 23 34 45 56 67 71 12 23 34 45 56 67 7301234567123456731 例例4.16 骰子的骰子的6个面分别有个面分别有1,2,3,4,5,6个点，问有个点，问有多少种不同的方案？多少种不同的方案？ 解法解法1,用用Burnside引理引理 问题相当于对正六面体的问题相当于对正六面体的6 6个面，用个面，用6 6种颜色对之种颜色对之

24、染色，要求各面的颜色都不一样，求不同的方案数？染色，要求各面的颜色都不一样，求不同的方案数？ 6 6个面用个面用6 6种颜色涂染，各面颜色都不一样，共有种颜色涂染，各面颜色都不一样，共有6!6!种方案。种方案。 设这设这6!6!个方案为个方案为S S1 1,S,S2 2,S,S720720, , 形成这形成这720720个元素的个元素的2424个置换，设这个置换，设这2424个置换为个置换为p p0 0,p,p1 1,p,p2323, ,其中其中p p0 0为不动置换。为不动置换。则则c c1 1(p(p0 0)=6!)=6!272732 因为因为6 6个面的颜色各不同，则除个面的颜色各不同，则除p p0 0外，其它置换外，其它置换中不可能出现不动元