组合数学第四章习题解答

1、习 题,4.1 若群G的元素a均可表示为某一元素x的幂，即a=xm,则称这个群为循环群，若群的元素交换率成立，即a,bGab=ba,则称这个群为阿贝尔群，试证明所有的循环群为阿贝尔群,证明：设G是一循环群，对任意的a,bG, 按定义a=xm,b=xn,ab=xmxn=xnxm=ba, 因此，循环群都是阿贝尔群。,4.2 若x是群G的一个元素，存在一最小的正整数m，使xm=e，则称m为x的阶，试证： C=e,x,x2,xm-1 是G的一个子群,证明：显然C中元素都是G中元素，只需证C满中群的四个性质即可 (1)封闭性,对任意的xm,xnC, 由结合性，设m+n=r(mod m-1) xmxn=x

2、r, (2)结合律显然 (3)单位元显然 (4)逆元素为原群逆元素,4.3 设G是阶为n的有限群，则G的所有元素的阶都不超过n,单位元e显然，对非单位元a，显然,4.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,则akm=e,则km=hn,n=km/h,这与n与k互素矛盾，,因此ak的阶等于n,

3、证明：如果ak的阶为n, 则k与n互素，,证明：akn=e,且不存在m1,k=hb,n=hc, kn=(hb)(hc),则(hb)c=kc=bn 因此akc=abn=e,cn矛盾,4.5 试证循环群的子群也是循环群。,显然。,4.6 若H是G的子群，x和y是G的元素，试证：xHyH或为空，或xH=yH。,设a,bH,xa=yb,xHyH 存在mH,xm属于xH但不属于yH,x=yba-1,xm=yba-1m,由H是G的子群，因此ba-1mH, yba-1myH,也就是xmyH，矛盾,4.7 若H是G的子群，|H|=k,试证： |xH|=k, 其中xG。,只需证：对任意a,bH,ab,有ab即可

4、,设a,bH,ab,有xa=xb则左乘x的逆得a=b矛盾,4.8 有限群G的阶为n,H是G的子群，则H的阶必除尽G的阶。,用4.6的结论,4.9 有限群G的阶为n,x是G的元素，则x的阶必除尽G的阶。,用4.2和4.8的结论,4.10 若x和y在群G作用下属于同一等价类，则x所属的等价类Ex，y所属的等价类Ey有|Ex|=|Ey|。,显然,4.11 有一个33的正方形棋盘，若用红蓝色对这9个格进行染色，要求两个格着红色，其余染蓝色，问有多少种着色方案。,(1+x)9中x2项的系数是c(9,2)=36,4(1+x)3(1+x2)3中x2项的系数是 4c(3,2)c(3,0)+c(3,0)c(3,

5、1)=24,2(1+x) (1+x4)2中x2项的系数是0,(1+x) (1+x2)4中x2项的系数是c(4,1)=4,P(x)中x5项的系数是(36+24+4)/8=8,4.12 试用贝恩塞特引理解n个人围一圆桌坐下的方案问题。,只考虑围中以旋转变化。,旋转0度(1)(2)(n!),旋转360/n度(12n!),旋转360/n2度(135n!2),旋转360/n(n-1)度(n!(n!-1)21),共有n!种方案。,4.13 对正六角形的六个顶点用5种颜色进行染色，试问有多少种不同的方案，旋转使之重合的算一种方案。,G (1)(2)(3)(4)(5)(6),(123456) (135)(24

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

7、中心为轴线左旋180度，,(1)(24)(35)(6),正六面体有3对对面，这种置换有3个,以对角线位置的平行棱的中以线为轴线旋转180度，,(16)(25(34),这种形式的置换有6种,以对角线120度位置,(345)(152),(643)(251),这种形式的置换有8个,求g2y2br的系数,C(6,2)C(4,2)C(2,1)+3C(2,1)C(2,1)/24 =8,4.15 对一个正六面体的8个顶点用y和r两种颜色染色，使其中有5个顶点用色y，其余三个顶点用色r，求其方案数。,4.16 用b,r,g这三种颜色的5颗珠子镶成的圆环，共有几种不同的方案？,构造群G共有如下几种置换,旋转,翻

8、转,4.17 一个圆圈上有n个珠子，用n种颜色对这n个珠子着色，要求颜色数目不少于n的方案数是多少？,项链排列：n!/2n,4.18 若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少不同的方案？,正六面体顶点的置换群见4.7例2 ，本题相当于用2个r,两个b,4个g色的球装在正六面体的8个顶点上。 其中r2b2g4 的系数为 C(8,2)C(6,2)+9C(4,2)C(2,1)/24=22,4.19 试说明S5群的不同格式及其个数，,9.解：5的拆分共有：00005,00014,00023, 00113,00122,01112,11111共七种，根据讲义4.4节定理1可得S

9、5中： (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种，如上所示。,4.20 图4.5用两种颜色着色的问题，若考虑互换颜色使之一致的方案属于同一类，问有多少种不同的方案,(1)不换色 不动：p1=(1)(2)(3)(4)(5)(6)(7)(8)(9)(13)(14)(15)(1

10、6) 逆时针转90 :p2=(1)(2)(3456)(789 10)(11 12)(13 14 15 16) 顺时针转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) (2)换色 不动：p5=(12)(37)(48)(59)(6 10)(11 12)(13 14)(15 16) 逆时针转90 :p6=(12)(385 10)(6749)(11)(12)(16 15 14 13) 顺时针转90 :p7=(12)(10 583)(9476)(1

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

12、4 +84 +64 /24=192,4.22一幅正方形的肖像与一个立方体的面一样大，6幅相同的肖像贴在立方体的6个面上，有多少种贴法？,4.23 凸多面体中与一个顶点相关的各角之和与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|=4,4.24 足球由正五边形与正六边形相嵌而成

13、(a)一个足球由多少正五边形与正六边形组成 (b)把一个足球所有的正六边形都着以黑色，正五边形则着以其它各色，每个正五边形着色各不相同，有多少种方案？,4.25 若G和G是两个群,GG的单位元素是(e,e),试证GG是群,(1)封闭性显然,(2)结合律显然,(3)逆元素显然,(4)单位元显然,4.27 一个项链由7颗珠子装饰成的，其中两颗珠子是红的，3颗是蓝的，其余两颗是绿的，问有多少种装饰方案，试列举之。,1,2,3,4,5,6,7,G (1)(2)(3)(4)(5)(6)(7),(1234567),(1357246), (1473625),(1526374), (1642753),(176

14、5432),(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,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引理,问题相当于对正六面体的6个面，用6种颜色对之 染色，要求各面的颜色都不一样，求不同的方案数？,6个面用6种颜色涂染，各面颜色都不一样，共有 6!种方案。,设这6!个方案为S1,S2,S720,形成这720个元素的24个置换，设这24个置换为 p0,p1,p23,其中p0为不动置换。,则c1(p0)=6!,27,因为6个面的颜色各不同，则除p0外，其它置换 中不可能出现不动元素，,则c1(p1)=