组合数学第四版标准答案第四章.doc

习 题 四

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£ k<m，0£ l<m)，使a = xk , b = xl，从而
a × b = xk × xl = x(k+l) mod mÎC (因为0 £ (k+l) mod m < m) ；
(4)有逆元"a ÎCÞ a -1ÎC：" a ÎC，$k ÎN (0£ k<m)，使a = xk , 从而
a -1 = xm-kÎC (因为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, ×)的一个子群，故具有包含性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 (0< r<n，(r,n) = 1)，元素arÎG都是G的一个母元素(生成元)。
为此，只需证ar的阶为n即可。
首先，设ar的阶为k，因此有ar×k = (ar)k = e，由于a的阶为n，故根据引理*可得n | r×k 。已知0< r<n，(r,n) = 1，因此只能有n | k，所以n £ k。
其次，
(ar)n = ar×n (指数律)
= an×r (数的加法交换律)
=(an)r (指数律)
= er
= e 。
因而，由k是元素ar的阶，具有最小性，所以k £ n。
综合这两方面，可得k = n。
(2).根据(1)的结论，可得，群G的母元素的数目为j(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£r<m
于是由(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
所以 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的子群。
于是令，这里，并且我们定义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}。对任一个元素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. 有一个3´3的正方形棋盘，若用红、蓝色对这9个格进行染色，要求两个格着红色，其余染蓝色，问有多少种着色方案？
1
2
3
4
5
6
7
8
9

[解]. 一个3´3的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:
不动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)9
1个
9个
中心 ±90°
(1)1(4)2
2个
3个
中心 180°
(1)1(2)4
1个
5个
第4.11题 表

将2个格着以r色，7个格着以b色，相当于用b，r二种颜色对3´3的正方形棋盘进行染色。
于是根据母函数形式的Pólya定理，方案枚举：
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种颜色进行染色，试问有多少种不同的方案？旋转使之重合作为相同处理。
o
1

2
4
3
z
y
x¢
5
x
6
z¢
y¢
[解]. 见第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)6
1个
6个
56
旋转 ±60°
(6)1
2个
1个
2·51
旋转 ±120°
(3)2
2个
2个
2·52
旋转 180°
(2)3
1个
3个
53
翻转(角-角) 180°
(1)2(2)2
3个
4个
3·54
翻转(凹-凹) 180°
(2)3
3个
3个
3·53
第4.13题 表

于是根据Pólya定理，可得不同的染色方案数为：
l=
=
=×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¢)
Þ( g1 g2 Î G)Ù (g¢1 g¢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)
= (e,e¢) (gg-1= e，g¢g¢-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¢ ={x¢1, x¢2,¼, x¢m}的置换群，对于G ´G¢的每一对元素
(g,g¢)(v)≜
证G ´G¢是关于XÈX¢的置换群。
[证].将题中G ´G¢中的置换的前置定义换为如下等价的后置定义：
(v)(g,g¢)≜。
因而G ´G¢={(g,g¢)|gÎ G , g¢Î G¢ }。
于是，我们可定义G ´G¢上的二元“乘法”运算如下：
(g1,g¢1) (g2,g¢2)≜(g1g2,g¢1g¢2)。
由于置换群G和G¢也是群，故根据习题4.25.，可知G ´G¢是群。又由于G ´G¢是XÈX¢上置换的集合，所以G ´G¢是关于XÈX¢的置换群。

o
1
a
2
4
3
d
e
c

6
5
第4.27题图1
b
g
f
4.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)7
1个
7个
旋转 ±a
(7)1
2个
1个
旋转 ±2a
(7)1
2个
1个
旋转 ±3a
(7)1
2个
1个
翻转(点-弧) 180°
(1)1(2)3
7个
4个
第4.27题 表

将2颗r色,2颗g色,3颗b色的珠子装饰在圆环的7个等分点上的问题，相当于用b，g， r三种颜色对正七边型进行染色。
于是根据母函数形式的Pólya定理，染色方案枚举：
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题图2

4.28.一个正八面体,用红、蓝两色对6个顶点进行着色；用黄、绿两种颜色对8个面进行染色，试求其中4个顶点为红, 两个顶点为蓝, 黄和绿的面各四面的方案数。
注. 正八面体可以看作是正方体的对偶,每一面用中心代表一个顶点,相交于一个顶点的3个面对应过3个中心的三角形,由此构成的6个顶点, 8个面的几何图形。
[解].(参见第二版第17题)本题相当于把正八面体的6个顶点、8个面合并起来作为目标集；6个顶点、8个面,共14个元素的置换群。

转动群
格式
置换
循环节
不动 0°
(1)6-(1)8
1个
14个
面心-面 ±90°
(1)2(4)1-(4)2
6个
5个
面心-面心 180°
(1)2(2)2-(2)4
3个
8个
顶点-顶点 ±120°
(3)2-(1)2 (3)2
8个
1
1
6个
棱中-棱中 180°
(2)3-(2)4
6个
7个
1
A
2
3
4
5
6
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
B
1
E
2
3
4

6

(2)
(3)
(4)

(6)
(7)
(8)
F
1
D
2
3
4
5
6
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
C
第4.28题 图
第17题 图

于是根据母函数形式的Pólya定理，染色方案枚举：
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 页】