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

【第1页共9页】习题四4.1.若群G的元素a均可表示为某一元素x的幂，即a=xm，则称这个群为循环群。若群的元素交换律成立，即a,bG满足ab=ba则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。[证].设循环群(G,)的生成元是x0G。于是，对任何元素a,bG，m，nN，使得a=x0m,b=x0n,从而ab=x0mx0n=x0m+n(指数律)=x0n+m(数的加法交换律)=x0nx0m(指数律)=ba故运算满足交换律；即(G,)是交换群。4.2.若x是群G的一个元素，存在一个最小的正整数m，使xm=e，则称m为x的阶，试证：C={e,x,x2,,xm-1}是G的一个子群。[证].(1)非空性C：因为eG；(2)包含性CG：因为xG，根据群G的封闭性，可知x2,,xm-1,(xm=)eG，故CG；(3)封闭性a,bCabC：a,bC，k，lN(0km，0lm)，使a=xk,b=xl，从而ab=xkxl=x(k+l)modmC(因为0(k+l)modmm)；(4)有逆元aCa-1C：aC，kN(0km)，使a=xk,从而a-1=xm-kC(因为0m-km)。综合(1)(2)(3)(4)，可知(C,)是(G,)的一个子群。4.3.若G是阶为n的有限群，则G的所有元素的阶都不超过n。[证].对任一元素xG，设其阶为m，并令C={e,x,x2,,xm-1}，则由习题4.2.可知(C,)是(G,)的一个子群，故具有包含性CG。因此有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(0rn，(r,n)=1)，元素arG都是G的一个母元素(生成元)。为此，只需证ar的阶为n即可。首先，设ar的阶为k，因此有ark=(ar)k=e，由于a的阶为n，故根据引理*可得n|rk。已知0rn，(r,n)=1，因此只能有n|k，所以nk。其次，(ar)n=arn(指数律)=anr(数的加法交换律)=(an)r(指数律)=er=e。因而，由k是元素ar的阶，具有最小性，所以kn。【第2页共9页】综合这两方面，可得k=n。(2).根据(1)的结论，可得，群G的母元素的数目为(n)(欧拉函数，小于n且与n互素的数的个数)。注.引理*.设(G,)是群。xG，若x的阶为k，从而xk=e。则mN,xm＝ek|m。[证].先证)：若xm＝e，则必有k|m。否则k∤m，于是，由带余除法，可设m=kq+r(0rk)，故可得r=m-kq，从而xr＝xm-kq＝xm+(-kq)＝xm(xk)-q(指数律)＝ee-q(xm＝e,xk=e)＝ee＝e故与x的阶为k，具有最小性，矛盾。次证):若k|m，则m=kq。于是xm＝xkq＝(xk)q(指数律)＝eq(xk=e)=e。4.5.试证循环群G的子群仍是循环群。[证].设(H,)是循环群(G,)=a的一个子群，则H中的元素都可表示成a的一些正方幂。设am是H中指数最小的正方幂，我们来证(H,)=am。为此只要证明H中任一元素都可表示成am的正方幂即可。任取H中一个元素ak，根据带余除法，可知有非负整数q及r，使k=qm+r且0rm于是由(H,)构成群，可知(am)qH，从而(am)-qH，于是ar=ak(am)-qH由m的选择(最小性)必须有r=0，所以ak=(am)q，这说明(H,)=am，因而(H,)循环群。4.6.若H是G的子群，x和y是G的元素，试证xHyH或为空，或xH=yH。[证].对任何x,yG，若xHyH=，则问题已证。否则若xHyH，则必至少有一元素x0xHyH，从而x0xHyHx0xHx0yHx0=xh1x0=yh2(这里h1,h2H)xh1=yh2x=yh2h1-1y=xh1h2–1(*)下面我们来证：xH=yH。为此，要分证：(1)xHyH；(2)yHxH；我们只证(1)；(2)同理可证；对任何元素a，axHa=xh(这里hH)a=yh2h1-1h(由(*)：x=yh2h1-1)a=yh(由H的封闭性：h=h2h1-1hH)ayH【第3页共9页】所以xHyH；所以，由包含关系的反对称性，我们得到xH=yH。4.7.若H是G的子群，|H|=k，试证：|xH|=k其中xG。[证].建立自然映射f:HxH，使得对任何hH，f(h)=xh。于是(1)后者唯一：由运算的结果唯一性可得；(2)满射：对任何bxH，有a=hH，使得b=xh。于是，有f(a)=f(h)=xh=b；(3)单射：f(h1)=f(h2)xh1=xh2h1=h2(群的消去律)。所以，f是从H到的双射，因此|xH|=|H|=k。4.8.有限群G的阶为n，H是G的子群，则H的阶必除尽G的阶。[证].这即是著名的拉格郎日(Lagrange法国著名数学家、力学家1736-1814)定理。设G的子群},,,,{121rhhheH。于是令},,,,{121rhahahaaeaaH，这里Ga，并且我们定义R是G上的二元关系，即GGRGyx,，))((::aHyaHxGbxRy。从而R是G上的等价关系，其等价块的形式为aH，设其代表元为kaaa,,,21，则HaHaHak,,,21是所有的等价块，构成对G的一个划分(参见习题4.6.)。即HaHaHaGk21根据习题4.7.可得rHHaHaHak21。因此nkrHkG，所以r必能整除n，即H的阶必除尽G的阶。4.10.若x和y在群G作用下属于同一等价类，则x所属的等价类Ex，y所属的等价类Ey有|Ex|=|Ey|。[证].设底基X={1,2,,n}。对任一个元素aX，Ea={bX|pG,(a)p=b}。因为已知x和y在群G作用下属于同一等价类，因此，存在zX，使得x,yEz，于是p1,p2G,使得(z)p1=x,(z)p2=y。我们来证：Ex=Ey。为此，要分证：(1)ExEy；(2)EyEx；我们只证(1)；(2)同理可证；对任何元素aX，aExa=(x)p(这里pG)a=(z)p1p(由(z)p1=x)a=(y)p2-1p1p(由(z)p2=y,得(y)p2-1=z(群G有逆元))a=(y)p(由群G的封闭性：p=p2-1p1pG)aEy所以ExEy。所以，由包含关系的反对称性，我们得到Ex=Ey。【第4页共9页】所以得证|Ex|=|Ey|。4.11.有一个33的正方形棋盘，若用红、蓝色对这9个格进行染色，要求两个格着红色，其余染蓝色，问有多少种着色方案？[解].一个33的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:不动0：P1=(1)(2)(3)(4)(5)(6)(7)(8)(9)逆时针旋转90:P2=(5)(1793)(2486)顺时针旋转90:P3=(5)(1397)(2684)旋转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二种颜色对33的正方形棋盘进行染色。于是根据母函数形式的Pólya定理，方案枚举：P(b,r)=41[(b+r)9+2(b+r)(b4+r4)2+(b+r)(b2+r2)4]其中b7r2的系数即为所求染色方案数：]140229[41=]!3!1!4!7!2!9[41=[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种颜色进行染色，试问有多少种不同的方案？旋转使之重合作为相同处理。[解].见第4.13题图，使之重合的刚体运动群，它含有关于正六角形中心轴旋转±60，±120，180的置换，绕过2个对角的轴翻转180o的置换，以及绕过2个对凹的轴翻转180o的置换：不动0：(1)(2)(3)(4)(5)(6)旋转±60：(123456)，(654321)旋转±120：(135)(246)，(531)(642)旋转180：(14)(25)(36)翻转(角-角)180：(1)(26)(35)(4)，(2)(13)(46)(5)，(3)(15)(24)(6)123456789o1243zyx5x6zy【第5页共9页】翻转(凹-凹)180：(14)(23)(56)，(12)(36)(45)，(16)(25)(34)。转动群格式置换循环节所求方案数不动0(1)61个6个56旋转±60(6)12个1个2·51旋转±120(3)22个2个2·52旋转180(2)31个3个53翻转(角-角)180(1)2(2)23个4个3·54翻转(凹-凹)180(2)33个3个3·53第4.13题表于是根据Pólya定理，可得不同的染色方案数为：l=]5353552525[121343216=)3751875125501015625(121=12118060=1505(种)。4.25.若G和G是两个群GG≜{(g,g)|gG,gG},(g1,g1)(g2,g2)≜(g1g2,g1g2),GG的单位元素是(e,e)。试证GG成群。[证].1封闭性：(g1,g1),(g2,g2)GG(g1,g2G)(g1,g2G)(g1g2G)(g1g2G)(群G和G的封闭性)(g1g2,g1g2)GG(g1,g1)(g2,g2)GG因而封闭性成立。2结合律：(g1,g1),(g2,g2),(g3,g3)GG((g1,g1)(g2,g2))(g3,g3)=(g1g2,g1g2)(g3,g3)=((g1g2)g3,(g1g2)g3)=(g1(g2g3),g1(g2g3))(群G和G的结合律)=(g1,g1)(g2g3,g2g3)=(g1,g1)((g2,g2)(g3,g3))因而结合律成立。3有幺元：(e,e)GG，这里e是群G的幺元，e是群G的幺元。(g,g)GG，(e,e)(g,g)=(eg,eg)=(g,g)(eg=g，eg=g)=(ge,ge)(g=ge，g=ge)=(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,gg-1)【第