组合数学第四版卢开澄标准答案-第四章.doc

习 题 四4.1. 若群G的元素a均可表示为某一元素x的幂，即a = xm，则称这个群为循环群。若群的元素交换律成立，即a , b G满足 ab = ba则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。证.设循环群(G, )的生成元是x0G 。于是，对任何元素a , b G，$m，nN，使得a= x0m , b= x0n ,从而 ab = x0m x0n= x0m +n (指数律)= x0n +m (数的加法交换律) = x0n x0m (指数律) = ba 故 运算满足交换律；即(G, )是交换群。4.2. 若x是群G的一个元素，存在一个最小的正整数m，使xm=e，则称m为x的阶，试证： C=e,x,x2, ,xm-1是G的一个子群。证.(1)非空性C ：因为$eG；(2)包含性CG：因为x G，根据群G的封闭性，可知x2, ,xm-1, (xm=)eG，故CG；(3)封闭性a , b C a b C： a , b C，$k，lN (0 km，0 lm)，使a = xk , b = xl，从而a b = xk xl = x(k+l) mod mC (因为0 (k+l) mod m m)；(4)有逆元a C a -1C： a C，$k N (0 km)，使a = xk , 从而a -1 = xm-kC (因为0 m-k m) 。综合(1) (2) (3) (4)，可知(C, )是(G, )的一个子群。4.3. 若G是阶为n的有限群，则G的所有元素的阶都不超过n。证.对任一元素xG，设其阶为m，并令C=e,x,x2, ,xm-1，则由习题4.2.可知(C, )是(G, )的一个子群，故具有包含性CG。因此有m = |C| | G | = n 所以群G的所有元素的阶都不超过n。4.4. 若G是阶为n的循环群，求群G的母元素的数目，即G的元素可以表示成a的幂： a,a2, ,an的元素a的数目。证.设(G, )是循环群，a是其一个母元素(生成元)，a的阶为n(也是G的阶)，则G =a,a2, ,an(=e) 。(1).我们来证：对任何自然数r N (0 rn，(r,n) = 1)，元素arG都是G的一个母元素(生成元)。为此，只需证ar的阶为n即可。首先，设ar的阶为k，因此有ark = (ar)k = e，由于a的阶为n，故根据引理*可得n | rk 。已知0 rn，(r,n) = 1，因此只能有n | k，所以n k。其次，(ar)n = arn (指数律)= anr (数的加法交换律)=(an)r (指数律)= er= e 。因而，由k是元素ar的阶，具有最小性，所以k n。综合这两方面，可得k = n。(2).根据(1)的结论，可得，群G的母元素的数目为j(n) (欧拉函数，小于n且与n互素的数的个数)。注.引理*.设(G,)是群。xG，若x的阶为k，从而xk =e 。则 mN, xme k | m 。证.先证)：若xme，则必有k | m 。否则k m ，于是，由带余除法，可设 m=kq+r (0 r k)，故可得 r=m-kq，从而 xrxm-kq xm+(-kq) xm (xk)-q (指数律) e e-q (xme, xk =e) e e e故与x的阶为k，具有最小性，矛盾。次证): 若k | m，则m = kq。于是 xm xkq (xk)q (指数律) eq (xk =e ) =e 。4.5. 试证循环群G的子群仍是循环群。证.设(H, )是循环群(G, )=的一个子群，则H中的元素都可表示成a的一些正方幂。设am是H中指数最小的正方幂，我们来证(H, )=。为此只要证明H中任一元素都可表示成am的正方幂即可。任取H中一个元素ak，根据带余除法，可知有非负整数q及r，使k=qm+r 且 0rm于是由(H, )构成群，可知(am)qH，从而(am)-qH，于是ar=ak (am)-qH由m的选择(最小性)必须有r=0，所以ak=(am)q，这说明(H, )=，因而(H, )循环群。4.6. 若H是G的子群，x和y是G的元素，试证xHyH或为空，或xH = yH。证.对任何x,yG，若xH yH=，则问题已证。否则若xH yH，则必至少有一元素x0xH yH，从而x0 xH yH x0 xH x0 yH x0=xh1 x0 =yh2 (这里h1, h2H) xh1 = yh2 x = y h2h1-1 y = x h1h21 (*) 下面我们来证：xH = yH。为此，要分证： (1)xH yH ； (2)yH xH ；我们只证(1) ；(2)同理可证 ；对任何元素a， a xH a =xh (这里hH) a = y h2h1-1h (由(*)：x = y h2h1-1 ) a =y h (由H的封闭性 ： h= h2h1-1hH) a yH所以 xH yH； 所以，由包含关系的反对称性，我们得到 xH = yH 。4.7. 若H是G的子群，|H|=k，试证： |xH|=k其中xG。证.建立自然映射 f : HxH，使得 对任何hH， f(h)=xh。于是 (1)后者唯一：由运算的结果唯一性可得；(2)满射：对任何 bxH，有a = hH，使得b = xh。于是，有 f(a)= f(h)= xh = b ； (3)单射： f(h1)= f(h2) xh1 = xh2 h1 = h2 (群的消去律 )。 所以，f是从H到的双射，因此 |xH|=|H|=k 。4.8.有限群G的阶为n，H是G的子群，则H的阶必除尽G的阶。证.这即是著名的拉格郎日(Lagrange法国著名数学家、力学家1736-1814)定理。设G的子群。于是令，这里，并且我们定义R是G上的二元关系，即，。从而R是G上的等价关系，其等价块的形式为aH，设其代表元为，则是所有的等价块，构成对G的一个划分(参见习题4.6.)。即根据习题4.7.可得。因此，所以r必能整除n，即H的阶必除尽G的阶。4.10. 若x和y在群G作用下属于同一等价类，则x所属的等价类Ex，y所属的等价类Ey有|Ex| = |Ey| 。证.设底基X=1,2,n。对任一个元素aX，Ea =bX | $pG , (a)p=b。 因为已知x和y在群G作用下属于同一等价类，因此，存在zX，使得x, yEz，于是$p1, p2G , 使得 (z)p1=x, (z)p2=y 。我们来证：Ex = Ey 。为此，要分证： (1) Ex Ey ； (2) Ey Ex ；我们只证(1) ；(2)同理可证 ；对任何元素aX， a Ex a = (x)p (这里pG) a = (z)p1p (由 (z)p1=x ) a = (y)p2-1p1p (由(z)p2=y , 得 (y)p2-1=z (群G有逆元) a = (y) p (由群G的封闭性 ： p= p2-1p1pG) a Ey所以 Ex Ey。所以，由包含关系的反对称性，我们得到 Ex = Ey。所以得证 |Ex| = |Ey| 。4.11. 有一个33的正方形棋盘，若用红、蓝色对这9个格进行染色，要求两个格着红色，其余染蓝色，问有多少种着色方案？123456789解. 一个33的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:不动0： P1=(1)(2)(3)(4)(5)(6)(7)(8)(9)逆时针旋转90: P2=(5)(1793)(2486)顺时针旋转90: P3=(5)(1397)(26 84)旋转180: P4=(5)(19)(28)(37)(46)转动群格式置换循环节不动 0(1)91个9个中心 90(1)1(4)22个3个中心 180 (1)1(2)41个5个第4.11题 表将2个格着以r色，7个格着以b色，相当于用b，r二种颜色对33的正方形棋盘进行染色。于是根据母函数形式的Plya定理，方案枚举：P(b,r)=(b+r)9+2(b+r)(b4+r4)2+(b+r)(b2+r2)4其中b7r2的系数即为所求染色方案数： =36+4/4=10(种) 。4.12. 试用贝恩塞特引理解决n个人围一圆桌坐下的方案问题。解.(参见ppt第四章6. 例4.6.7.)目标集： n个坐位；图象集：n!个着色方案(排坐)。转动群的2n个置换(参见第7题(第二版)，即第4.17题(第三版)，只有幺元有n!个不动点(图象)，其他2n-1个置换没有不动点(因为没有两个坐位坐同一人)，即c1(e)= c1(P1)= n!，c1(P2)= c1(P3)= c1(P2n)=0。故由Burnside引理有 l=c1(e)/2n =n!/ 2n =(n-1)!/2个方案。4.13. 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案？旋转使之重合作为相同处理。o1243zyx5x6zy解. 见第4.13题 图，使之重合的刚体运动群，它含有关于正六角形中心轴旋转60，120，180的置换，绕过2个对角的轴翻转180o的置换，以及绕过2个对凹的轴翻转180o的置换：不动0：(1)(2)(3)(4)(5)(6) 旋转 60：(1 2 3 4 5 6)，(6 5 4 3 2 1)旋转 120：(1 3 5)(2 4 6)，(5 3 1)(6 4 2)旋转180：(1 4)(2 5)(3 6)翻转(角-角) 180：(1)(2 6)(3 5)(4)，(2)(1 3)(4 6)(5)，(3)(1 5)(2 4)(6)翻转(凹-凹) 180：(1 4)(2 3)(5 6)，(1 2)(3 6)(4 5)，(1 6)(2 5)(3 4)。转动群格式置换循环节所求方案数不动 0(1)61个6个56旋转 60(6)12个1个 251旋转 120(3)22个2个 252旋转 180(2)31个3个 53翻转(角-角) 180(1)2(2)23个4个354翻转(凹-凹) 180(2)33个3个353第4.13题 表于是根据Plya定理，可得不同的染色方案数为： l=18060 =1505(种) 。4.25. 若G和G是两个群 G G(g,g)|g G , g G , (g1,g1) (g2,g2)(g1g2,g1g2),G G的单位元素是(e,e)。试证G G成群。证. 1封闭性：(g1,g1) , (g2,g2) G G ( g1 , g2 G) (g1 , g2 G)( g1 g2 G) (g1 g2 G) (群G和G的封闭性)(g1g2,g1g2) G G(g1,g1) (g2,g2) G G因而封闭性成立。2结合律：(g1,g1) , (g2,g2) , (g3,g3) G G(g1,g1)(g2,g2)(g3,g3)=(g1g2,g1g2)(g3,g3)=(g1g2)g3,(g1g2)g3)=(g1(g2g3),g1(g2g3) (群G和G的结合律)=(g1,g1)(g2g3,g2g3)=(g1,g1)(g2,g2)(g3,g3)因而结合律成立。3有幺元：(e,e) G G，这里e是群 G的幺元，e是群G的幺元。(g , g) G G，(e,e)(g , g) = (eg , eg) = (g , g) (eg=g，eg=g) = (ge , ge) (g=ge，g=ge) = (g , g)(e,e) 因而(e,e)是幺元。4有逆元：(g , g) G G ( g G) (g G)( g-1 G) (g-1 G) (群G和G有逆元)(g-1, g-1) G G 使得 (g , g)(g-1, g-1) = (gg-1 , gg-1) = (e,e) (gg-1= e，gg-1= e) = (g-1g , g-1g) (g-1g = e，g-1g= e) = (g-1, g-1)(g , g)因而有逆元。所以G G构成群。4.26. 若G是关于X=x1, x2, xn的置换群，G是关于X =x1, x2, xm的置换群，对于G G的每一对元素 (g,g)(v)证G G是关于XX的置换群。证.将题中G G中的置换的前置定义换为如下等价的后置定义：(v)(g,g)。因而G G=(g,g)|g G , g G 。于是，我们可定义G G上的二元“乘法”运算如下： (g1,g1) (g2,g2)(g1g2,g1g2)。由于置换群G和G也是群，故根据习题4.25.，可知G G是群。又由于G G是XX上置换的集合，所以G G是关于XX的置换群。o1a243dec65第4.27题图1bgf4.27. 一个项链由7颗珠子装饰而成的，其中两颗珠子是红的，3颗是蓝的，其余两颗是绿的，问有多少种装饰方案？试列举之？解. 见第4.27题 图，使之重合的刚体运动群，令a=，它含有关于圆环中心轴旋转=a，=2a，=3a，以及绕过一个顶点及其对弧中点的轴翻转180o的置换：不动0：(1)(2)(3)(4)(5)(6)(7) 旋转a：(1 2 3 4 5 6 7)，(7 6 5 4 3 2 1)旋转2a：(1 3 5 7 2 4 6)，(7 5 3 1 6 4 2)旋转3a：(1 4 7 3 6 2 5) ，(7 4 1 5 2 6 3)翻转(点-弧) 180：(1)(2 7)(3 6)(4 5)，(2)(1 3)(4 7)(5 6)，(3)(1 5)(2 4)(6 7)，(4)(1 7)(2 6)(3 5)，(5)(1 2)(3 7)(4 6)，(6)(1 2)(3 7)(4 6)，(7)(1 6)(2 5)(3 4)。转动群格式置换循环节不动 0(1)71个7个旋转 a(7)12个1个旋转 2a(7)12个1个旋转 3a(7)12个1个翻转(点-弧) 180(1)1(2)37个4个第4.27题 表将2颗r色,2颗g色,3颗b色的珠子装饰在圆环的7个等分点上的问题，相当于用b，g， r三种颜色对正七边型进行染色。于是根据母函数形式的Plya定理，染色方案枚举：P(b,g,r)=(b+g+r)7+6(b7+g7+r7)1+7(b+g+r)1(b2+g2+r2)3其中b3g2r2的系数即为所求项链串珠方案数： =18(种)。所求18种项链串珠方案枚举如下：第4.27题图24.28.一个正八面体,用红、蓝两色对6个顶点进行着色；用黄、绿两种颜色对8个面进行染色，试求其中4个顶点为红, 两个顶点为蓝, 黄和绿的面各四面的方案数。注. 正八面体可以看作是正方体的对偶,每一面用中心代表一个顶点,相交于一个顶点的3个面对应过3个中心的三角形,由此构成的6个顶点, 8个面的几何图形。解.(参见第二版第17题)本题相当于把正八面体的6个顶点、8个面合并起来作为目标集；6个顶点、8个面,共14个元素的置换群。转动群格式置换循环节不动 0(1)6-(1)81个14个面心-面 90(1)2(4)1-(4)26个5个面心-面心 180 (1)2(2)2-(2)43个8个顶点-顶点 120 (3)2-(1)2 (3)28个116个棱中-棱中 180 (2)3-(2)46个7个1A23456(1)(2)(3)(4)(5)(6)(7)(8)B1E2346(2)(3)(4)(6)(7)(8)F1D23456(1)(2)(3)(4)(5)(6)(7)(8)C第4.28题 图第17题 图于是根据母函数形式的Plya定理，染色方案枚举：P(r,b,y,g)=(r+b)6(y+g)8+6(r+b)2(r4+b4)1(y4+g4)2+3(r+b)2(r2+b2)2(y2+g2)4+8(r3+b3)2(y+g)2(y3+g3)2+6(r2+b2)3(y2+g2)4其中r4b2y4g4的系数即为所求项链串珠方案数： =51(种)。详细的点-面混合的置换群为:不动 0:(1)(2)(3)(4)(5)(6)-(1)(2)(3)(4)(5)(6)(7)(8)绕外接正方体面心-面心轴旋转 90: (1)(2345)(6)-(1234)(5678)(2)(1563)(4)-(1485)(2376)(3)(1264)(5)-(1562)(3487) -90: (1)(5432)(6)-(4321)(8765)(2)(3651)(4)-(5841)(6732)(3)(4621)(5)-(2651)(7843)180: (1)(24)(35)(6)-(13)(24)(57)(68)(2)(16)(35)(4)-(18)(45)(27)(36)(3)(16)(24)(5)-(16)(25)(38)(47)绕外接正方体棱中-棱中轴旋转180 : (16)(25)(34)-(17)(26)(35)(48)(16)(23)(45)-(15)(28)(37)(46)(24)(15)(36)-(17)(28)(34)(56) (24)(13)(56)-(12)(35)(46)(78)(35)(12)(46)-(14)(28)(35)(67)(35)(14)(26)-(17)(23)(46)(58)绕外接正方体顶-顶轴旋转 120:(123)(456)-(1)(245)(386)(7)(134)(265)-(2)(163)(457)(8)(145)(236)-(3)(168)(274)(5)(152)(346)-(4)(138)(275)(6) -120:(321)(654)-(1)(542)(683)(7)(431)(562)-(2)(631)(754)(8)(541)(632)-(3)(861)(472)(5)(251)(643)-(4)(831)(572)(6) 。【第 9 页 共 9 页】