组合数学第四章习题解答.pptVIP

习题014.1若群G的元素a均可表示为某一元素x的幂，即a=xm,则称这个群为循环群，若群的元素交换率成立，即a,b?G满足a?b=b?a,则称这个群为阿贝尔群，试证明所有的循环群为阿贝尔群02证明：设G是一循环群，对任意的a,b?G,按定义a=xm,b=xn,a?b=xm?xn=xn?xm=b?a,因此，循环群都是阿贝尔群。034.2若x是群G的一个元素，存在一最小的正整数m，使xm=e，则称m为x的阶，试证：C={e,x,x2,…,xm-1}是G的一个子群证明：显然C中元素都是G中元素，只需证C满中群的四个性质即可封闭性,对任意的xm,xn?C,由结合性，设m+n=r(modm-1)xm?xn=xr,结合律显然单位元显然逆元素为原群逆元素4.3设G是阶为n的有限群，则G的所有元素的阶都不超过n单位元e显然，对非单位元a，显然4.4若G是阶为n的循环群，求群G的母元素的数目，即G的元素可表示成a的幂：a,a2,…,an的元素a的数目。若a是母元素，则an=e因此ak的阶等于n,即当且仅当k与n互素，与n互素的元素个数为?(n),若ak(10n)也是G的母元素，当且仅当ak的阶为n,显然ak的阶不能大于n,现证明ak的阶不能小于n即可,如果ak的阶为mn,则akm=e,则km=hn,n=km/h,这与n与k互素矛盾，证明：如果k与n互素，则ak的阶为n,证明：如果ak的阶为n,则k与n互素，证明：akn=e,且不存在mn,使akm=e,则k与n互素,设k与n不互素，存在h1,k=hb,n=hc,kn=(hb)(hc),则(hb)c=kc=bn因此akc=abn=e,cn矛盾4.5试证循环群的子群也是循环群。显然。4.6若H是G的子群，x和y是G的元素，试证：xH∩yH或为空，或xH=yH。设a,b∈H,xa=yb,xH≠yH存在m∈H,xm属于xH但不属于yHx=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即可01设a,b∈H,a≠b,有xa=xb则左乘x的逆得a=b矛盾024.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有一个3×3的正方形棋盘，若用红蓝色对这9个格进行染色，要求两个格着红色，其余染蓝色，问有多少种着色方案。123456789(1+x)9中x2项的系数是c(9,2)=364(1+x)3(1+x2)3中x2项的系数是4[c(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=84.12试用贝恩塞特引理解n个人围一圆桌坐下的方案问题。只考虑围中以旋转变化。01旋转0度(1)(2)…(n!)02旋转360/n度(12…n!)03旋转[360/n]×2度(135…n!2)04旋转[360/n]×(n-1)度(n!(n!-1)…21)05………………06共有n!种方案。074.13对正六角形的六个顶点用5种颜色进行染色，试问有多少种不同的方案，旋转使之重合的算一种方案。123456G(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)(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个