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

习 题 四

4.1. 若群G的元素a均可表示为某一元素x的幂，即a = xm，则称这个群为循环群。若群的元素交换律成立，即a , b G满足 ab = ba

则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。

[证].设循环群(G, )的生成元是x0?G 。于是，对任何元素a , b G，m，n?N，使得a= x0m , b= x0n ,从而 ab = x0m x0n

= x0m +n (指数律)

= x0n +m (数的加法交换律)

= x0n x0m (指数律) = ba

故 运算满足交换律；即(G, )是交换群。

4.2. 若x是群G的一个元素，存在一个最小的正整数m，使xm=e，则称m为x的阶，试证：

2m-1

C={e,x,x, ,x} 是G的一个子群。 [证].(1)非空性C ：因为e?G；

(2)包含性CG：因为x ?G，根据群G的封闭性，可知x2, ,xm-1, (xm=)e?G，故CG；

(3)封闭性a , b C a b C： a , b C，k，l?N (0 k

使a = x , b = x，从而

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 k

a -1 = xm-kC (因为0 m-k < m) 。

综合(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, )的一个子群，故具有包含性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< r

为此，只需证ar的阶为n即可。

首先，设ar的阶为k，因此有ark = (ar)k = e，由于a的阶为n，故根据引理*可得n | rk 。已知0< r

(ar)n = arn (指数律)

= anr (数的加法交换律) =(an)r (指数律)

= er = e 。

因而，由k是元素ar的阶，具有最小性，所以k n。

综合这两方面，可得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, )=的一个子群，则H中的元素都可表示成a的一些正方幂。设am是H中指数最小的正方幂，我们来证(H, )=。为此只要证明H中任一元素都可表示成am的正方幂即可。

任取H中一个元素ak，根据带余除法，可知有非负整数q及r，使

k=qm+r 且 0r

于是由(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,y?G，若xH ? yH=?，则问题已证。

否则若xH ? yH??，则必至少有一元素x0?xH ? yH，从而

x0? xH ? yH

? x0? xH ? x0? yH

? x0=xh1 ? x0 =yh2 (这里h1, h2?H) ? xh1 = yh2

? x = y h2h1-1 ? y = x h1h2–1 (*)

下面我们来证：xH = yH。为此，要分证： (1)xH ? yH ； (2)yH ? xH ；

我们只证(1) ；(2)同理可证 ；

对任何元素a， a? xH

? a =xh? (这里h??H)

? a = y h2h1-1h? (由(*)：x = y h2h1-1 )

? a =y h?? (由H的封闭性 ： h??= h2h1-1h??H) ? a? yH 所以 xH ? yH；

所以，由包含关系的反对称性，我们得到 xH = yH 。

4.7. 若H是G的子群，|H|=k，试证： |xH|=k 其中xG。

[证].建立自然映射 f : H?xH，使得 对任何h?H， f(h)=xh。于是 (1)后者唯一：由运算的结果唯一性可得；

(2)满射：对任何 b?xH，有a = h?H，使得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的子群H?{e,h1,h2,?,hr?1}。

于是令aH?{a?e?a,a?h1,a?h2,?,a?hr?1}，这里a?G，并且我们定义R是G上的二元关系，即R?G?G

x,y?G，xRy::?(?b?G)(x?aH?y?aH)。

从而R是G上的等价关系，其等价块的形式为aH，设其代表元为a1,a2,?,ak，则

a1H,a2H,?,akH是所有的等价块，构成对G的一个划分(参见习题4.6.)。即

?a2H?????akH G?a1H?根据习题4.7.可得a1H?a2H???akH?H?r。

因此G?kH?kr?n，所以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。 所以得证 |Ex| = |Ey| 。

4.11. 有一个33的正方形棋盘，若用红、蓝色对这9个格进行染色，要求两个格着红色，

其余染蓝色，问有多少种着色方案？ [解]. 一个33的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:

不动0?： P1=(1)(2)(3)(4)(5)(6)(7)(8)(9) 1 2 3 逆时针旋转90?: P2=(5)(1793)(2486)

4 5 6

顺时针旋转90?: P3=(5)(1397)(26 84)

7 8 9 旋转180?: P4=(5)(19)(28)(37)(46)

转动群 格式 置换 循环节 (1)9 不动 0? 1个 9个 12(1)(4) 2个 中心 ±90? 3个 14中心 180? (1)(2) 1个 5个 第4.11题 表

将2个格着以r色，7个格着以b色，相当于用b，r二种颜色对33的正方形棋盘进行染色。

于是根据母函数形式的Pólya定理，方案枚举：

P(b,r)=

其中b7r2的系数即为所求染色方案数： [?????2?0?????]

1[(b+r)9+2(b+r)(b4+r4)2+(b+r)(b2+r2)4] 4?4?1?9?4?2??1?19!4!?] =[42!7!1!3!=[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?的置换，绕1 y z o

过2个对角的轴翻转180的置换，以及绕过2个对凹的轴翻转180o的置换： 6 2 不动0?：(1)(2)(3)(4)(5)(6)

xx o 3 z

5 4 y旋转 ±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? 旋转 ±60? 旋转 ±120? 旋转 180? 翻转(角-角) 180? 翻转(凹-凹) 180? 格式 置换 (1)6 1个 1(6) 2个 (3)2 2个 (2)3 1个 (1)2(2)2 3个 3(2) 3个 第4.13题 表 循环节 6个 1个 2个 3个 4个 3个 所求方案数 56 2·51 2·52 53 3·54 3·53

于是根据Pólya定理，可得不同的染色方案数为： l=

16[5?2?51?2?52?53?3?54?3?53] 121=(15625?10?50?125?1875?375) 121=18060 12=1505(种) 。

是两个群 G

?{(g,g

)|g

G , g

G

},

4.25. 若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,g1g G G 2)

(g1,g1) (g2,g2) G G

因而封闭性成立。

2结合律：(g1,g1) , (g2,g2) , (g3,gG 3) 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

本文来源：https://www.bwwdw.com/article/740t.html