组合数学答案

循环群也是群，所以群的定义不用再证，只需证明对于任意a,bG,G是循环群，有a*bb*a成立，因为循环群中的元素可写成a=xm形式所以等式左边xm×xnxmn,等式右边xn xm＝xmn，a*bb*a，即所有的循环群都是ABEL群。 4.2

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

的阶，试证：

C=｛e,x,x2, …,xm-1｝ 证：

x是G的元素，G满足封闭性所以，xk是G中的元素 C∈G

再证C是群：

1、xi , xj∈C , xi·xj= xi+j 若i+j<=m-1,则xi+j∈C

若i+j>m,那么xi+j=xm+k=xm·xk=xk∈C 所以C满足封闭性。 2、存在单位元e.

3、显然满足结合性。 4、存在逆元， 设xa·xb=e=xm xb=xm-a

xa∈C, (xa)-1= xb=xm-a

4.3设G是阶为n 的有限群，则G的所有元素的阶都不超过n.

证明：设G是阶为n 的有限群，a是G中的任意元素，a的阶素为k， 则此题要证kn

首先考察下列n+1个元素

a,a,a,a,....a234n1

由群的运算的封闭性可知，这n+1个元素都属于G,，而G中仅有n 个元素，所以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为

aiiaiij（1jn）

jaaa

jj由群的性质3可知，a是单位元，即a=e，又由元素的阶数的定义可知，当a为k阶元素时a=e，且k是满足上诉等式的最小正整数，由此可证kjn

k4.4 若G是阶为n的循环群，求群G的母元素的数目，即G的元素可表示a的幂：

a,a2……..an

解：设n=p1a1…….pkak，共n个素数的乘积，所以群G中每个元素都以用这k个素数来表示，而这些素数，根据欧拉定理，一共有 Φ(n)=n(1-1/p1)………(1-1/pk)

所以群G中母元素的数目为n(1-1/p1)………(1-1/pk)个. 4.5

证明循环群的子群也是循环群

证明：设H是G=的子群，若H=,显然H是循环群，否则取H中最小的正方幂元am，下面证明am是H的生成元,易见amH，只要证明H中的任何元素都可以表成am的整数次方，由除法可知存在q和r,使得l=qm+r,其中0rm-1,因此有ar=alqm，因为am是H中最小的正方幂元，必有r=0,这就证明出

al=amq{am}证明完毕。

4.6 若H是G的子群，x和y是G的元素，试证xHyH或为空，或xHyH 4.7 若H是G的子群,|H|=k,试证：

|xH|=k 其中xG.

证明：∵H是G的子群，xG ∴|xH|≤k

如果|xH|.4.8 有限群G的阶为n，H是G的子群，则H的阶必除尽G的阶。 答案：已知|G|=n, |H|<=|G|

设G={a0,a1,a2.......an1}，

H={b0,b1,b2......bn1}

因为H是G的子群，所以在H中的一个(bm)r一定在G中对应一个am使得

(bm)ram，

所以有brmam，则rm一定是m的倍数，所以则H的阶必除尽G的阶。

4．9 G是有限群，x是G的元素，则x的阶必除尽G的阶。

解：证： 设|G|=g,则x,x2,x3,,xg1中必有相同元。设xkxl, 1klg1，则xlke，1lkg。

对于给定的x，存在最小的正整数r，使得xre。于是H{x,x2,x3,,xr}是G 的子群，

若HG，则aH，显然，HHa，HHa2r。 若HHaG， 则

2rg,r|g，否则bHHa，Hb(HHa)。 于是HHaHbG，r(k1)g，r|g。证毕。

4.10 若x和y在群G作用下属于同一等价类，则x所属的等价类Ex，y所属的等价类Ey有

|Ex| = |Ey|

解：因为x和y在群G作用下属于同一等价类，所以x和y在群G作用下存在置换P1使x和y互相转变，即

Ex = Ey={x,y}

所以|Ex| = |Ey|。

4．11 有一个3х3的正方形棋盘,若用红,蓝色对这9个格进行染色,要求两个格着红色,其余染蓝色,问有多少种着色方案?

解: 对于一个3×3的正方形棋盘,要求两个格着红色,其余染蓝色,如下图所示.

置换群: 格式: (1),1个.(1)(2),4个.(1) (4),2个.(1)(2),1个

9 3324

p(x)=1/8×[(1+x)9+4(1+x)(1+x2)3+2(1+x)(1+x4)2+(1+x)(1+x2)4]

x2的系数为 1/8×[C(9,2)+4(C(3,2)+C(3,1))+C(4,1)]

=(36+24+4)/8=8

其中划横线为红色,其它为蓝色.共8种着色方案.

4.12：试用Burnside引理解决n个人围一圆桌坐下的方案问题。 解：

2341N1N-1NN-1……23……56……图一C1…45……图二 C2456321NN-1图N CN……………………………………

23……N-1N-2N1图N! C N!

如图： N个人围成一个圆桌的所有排列如上图所示。一共N!个。

……………6…………………………

……………………旋转360/i，i={n,n-1,n-2,……1}； 得到n种置换

当且仅当i=1的置换（即顺时针旋转360/1度：P1=(c1)(c2)……(cn!);） 时有1阶循环存在（因为只要圆桌转动，所有圆排列中元素的绝对位置都发生了变化，所以不可能有1阶循环存在）。

不同的等价类个数就是不同的圆排列个数，根据Burnside引理，

所以一共有(n-1)!种排列。

4.13 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案，旋转使之重合作为相同处理

解：首先对每个顶点进行编号，分别为1，2，3，4，5，6，根据旋转的角度不同，共可以旋转6次，得到不同的旋转方式

旋转0度： a1132

c(a1)=6 45 6旋转60度： a2123456 c(a1)=1 旋转120度：a3135246 c(a1)=2 旋转180度：a4142536 c(a1)=3 旋转240度：a51532 c(a1)=2 旋转300度：a6165432 c(a1)=1 所以G=6，根据Polya定理，m=5，

l1mc(a1)mc(a2)...mc(a6)G

1612321555555 62635 故一共2635种涂色方案

4.15 对一个正六面体的8个顶点，用y和r两种颜色染色，使其中有5个顶点用色y，其余3个顶点用色r，求其方案数。

解： 相当于4.7节中例2中求b5r3的系数，为[C(8,5)+8C(2,1)]/24=3

4.15 对一个正六面体的8个顶点，用y和r两种颜色染色，其中五个顶点用色

y，

其余三个顶点用色r，求方案数？

158C1 解：C82=3 244.16：用b，r，g这3种颜色的5颗珠子镶成的圆环，共有几种不同的方案。 解: 正5边形的运动群 绕心转 ±72。 (5)1 2个 ±144。 (5)1 2个 翻转 180。 (1)(2)2 5个 不动 (1)5 1个 不同方案数为m=(35+4·31+5·33)/10=39

4.16 用b，r，g，这三种颜色的5颗珠子镶成的圆环，共有几种不同的方案？

1 5 2 4 3

解：G：(1)(2)(3)(4)(5),(1 2 3 4 5),(1 3 5 2 4),(1 4 2 5 3),(1 5 4 3 2) ,(1)(2 5)(3 4)

, (2)(1 3)(4 5), (3)(2 4)(1 5), (4)(3 5)(1 2),(5)(1 4)(2 3).

|G|=10.

应用polya定理，不同的方案数为：

15(34*315*33)=39 104─17 一个圆圈上有n个珠子,用n种颜色对这n个珠子着色,要求颜色数目不少于n的方案数是多少?

解: 使重合的运动包括绕中心旋转和绕水平对称轴翻转生2n个置换群.n个球用n种颜色着色共有n!种不同方案.因此,所求方案数为n!/2n.

4.18 若以给两个r色球，量个b色的球，用它装在正六面体的顶点，试问有多少种不同的方案。 解：单位元素（1）（2）（3）（4）（5）（6）（7）（8），格式为（1）8. 绕中轴旋转90。的置换非别为（1234）（5678），（4321）（8765） 格式为（4）2，同格式的共轭类有6个。

绕中轴旋转180。的置换非别为（13）（24）（57）（68），格式为（2）4，同类置换有3个。

绕斜对角线旋转180。的置换为（17）（26）（35）（48），格式为（2）4同类置换有3个。

绕斜对角线旋转120。的置换为（136）（475）（8）（2），（631）（574）（2）（8），格式为（3）2（1）2同类置换有8个。 依据Polya定理，不同方案数为

M=（28+6×22+3×24+6×24+8×24）/24=23

4.18．若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少种不同的方案？

解：由P191 例4-14知，六面体顶点的置换群中有一个(1)8，六个(4)2，九个(2)4，八个(3)2(1)2，本题相当于用2个顶点涂r色，2个顶点涂b色，4个顶点涂w色，利用母函数形式的polya定理知总的方案数为 1844P(rbw)6r(bw2442)2r9(2bw2)4r8b(w23r)b(w3

3)2其中r2b2w4的系数即为所求，系数为22，总的所求方案数为22种。

4．19 试说明S5群的不同格式及其个数。

解：5 的拆分共有：00005,00014,00023, 00113,00122,01112,11111 共七种，则可得S5群的７种不同格式如下：

(1)5共轭类有5!/5!=1 个置换；

(1)3(2)2共轭类有5!/(3!2)=10 个置换； (1)1(2)2共轭类有5!/(2!2 )=15 个置换； (1)2(3)1共轭类有5!/(2!3)=20 个置换； (1)1(4)1共轭类有5!/4=30 个置换；

(2)1(3)1共轭类有5!/(2·3)=20 个置换； (5)1共轭类有5!/5=24 个置换；

4.19 试说明S5群的不同格式及其个数。

解： 5的拆分有：00005,00014,00023, 00113,00122,01112,11111共七种，则

(5)1共轭类有5!/5=24个置换； (1)1(4)1共轭类有5!/4=30个置换；

(2)1(3)1共轭类有5!/(2·3)=20个置换； (1)2(3)1共轭类有5!/(2!3)=20个置换； (1)1(2)2共轭类有5!/(2!2 )=15个置换； (1)3(2)1共轭类有5!/(3!2)=10个置换； (1)5共轭类有5!/5!=1个置换；

所以，共有不同格式7种，其总个数为119。

4.20 如图4-5一个方格平均分成四个部分有两种颜色着色的问题，若考虑呼唤颜色使之一致的方案属于同一类，问有多少种不同的图像？

答案：

(1)不换色:

不动：p1=(1)(2)(3)(4)(5)(6)……(13)(14)(15)(16)

逆时针转90度:p2=(1)(2)(3456)(7 8 9 10)(11 12)(13 14 15 16) 顺时针转90度:p3=(1)(2)(6543)(10 9 8 7)(11 12)(16 15 14 13) 转180度：(1)(2)(3 5)(4 6)(7 9)(8 10)(11 12)(13 15)(14 16) (2)换色:

不动：p5:=(1 2)(3 7)(4 8)(5 9)(6 10)(11 12)(13 15)(14 16)

逆时针转90度:p6=(1 2)(3 8 5 10)(6 7 4 9)(11)(12)(16 15 14 13) 顺时针转90度：p7=(1 2)(10 5 8 3)(9 4 7 6)(11)(12)(13 14 15 16) 转180度:p8=(1 2)(3 9)(4 10)(5 7)(6 8)(11 12)(13)(14)(15)(16)

总方案数为（12+2+2+4+0+2+2+4）/8=4

4.20图4-5 用两种颜色着色问题，若考虑互换颜色使之一致的方案属于同一类，问有多少种不同的图象？

答：有4种 分别是

4.21 在正四面体的每个面上都任意引一条高,有多少种方案.

解：问题相当于在4个面上用3种颜色着色，求方案数。

使4个面重合的旋转群G的元素为:

(1)(2)(3)(4) , (1)(234) , (1)(432) , (2)(134) , (2)(431) , (3)(124) , (3)(421) , (4)(123) , (4)(321) , (12)(34) , (13)(24) , (14) (23) 所以不同的方案数共有

113483233281722715 1212

4.21 在正四面体的每个面上都任意引一条高，有多少种？

题解： 除了绕顶点-对面的中心轴旋转均不会产生不变的图象外,绕其他轴的旋转相当于正4面体的面3着色。参照讲义4.6例3可得不同的方案数为M=[34+0·8·32+3·32]/12=9

4.22 一幅正方形的肖像与一个立方体的面一样大，6幅相同的肖像贴在立方体的6个面上，有多少种贴法？

题解： 除了绕面心—面心轴旋转任何度数均不会产生不变的图象外，绕其他轴的旋转都相当于正六面体的面4着色。不同的方案数为M=[46+0·6·43+0·3·44+8·42+6·43]/24=192 4.22 一幅正方形的小巷与一个立方体的面一样大。6幅相同的肖像贴在立方体的6个面上，有多少种贴法？ 解：除了绕面心以面心轴旋转任何读书均不会产生不变的图像外，绕其他轴的旋转都相当于正六面体的面4着色。可得不同的方案数为M=460*6*430*3*448*426*43/24192

4.23 凸多面体中与一个顶点相关的各面角之和与2的差称为该顶点的欠角。

证明凸多面体各顶点欠角之和为4。

证：设V，S，E分别为顶点集，面集，边集。由欧拉定理 V+S-E=2。 设aij为与顶点vi面sj相关的面角，ej为sj的边数，给定sj则

vjvaij(ej2)

ijijvjv(2a)2a)

sjsvjvvjvsjsvjvsjs=2V-aij

=2V-(ej2)=2V-ej+2S

sjssjs=2V+2S-2E =4

所以欠角和为4。

4.24 足球由正五边形和正六边形相嵌而成。

(a) 一个足球由多少块正五边形与正六边形组成？

(b) 把一个足球所有的正六边形都着以黑色，正五边形则着以其它各色，每个五边形的着色都不同，有多少种方案？ 解： （a）足球是多面体，满足欧拉公式F－E＋V＝2，其中F,E,V分别

表示面,棱,顶点的个数。设足球表面正五边形和正六边形的面各有x个和y个，那么，面数F＝x＋y；棱数E＝(5x+6y)/2；顶点数V＝(5x+6y)/3。

由欧拉公式，x＋y－(5x+6y)/2＋(5x+6y)/3＝2，解得x＝12。

由于每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接；每一个五边形的五条边都与其它的五个六边形的五条边连接。所以，五边形的个数x=3y/5。之前求得x=12，所以y=20。

(b) 一个顶点通过一个转动可与任一顶点重合，重合的方式只有1种，

故转动群的阶为60。因为5边形着色均不同，所以除不变置换的任意旋转都不会产生不变图象，12个5边形着不同颜色共12!种方案。所以共有12!/60=7983360种方案。

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'成群。

证明：要证GG是群，即证GG满足群的四个性质：

（1）封闭性：若a,bGG,设a(gx,gx) 其中gxG,gxG，b(gy,gy) 其中gyG,gyG，

abgxgygxgy 由于G,G是群，所以

gabGG，故满足封闭性。 gxg,GxgGyy，由定义知

（2）结合律：对于任意的a,b,cGG，a(gx,gx),b(gy,gy),c(gz,gz)，由于G,G是群，本身满足结合律，所以GG满足结合律。 （3）存在单位元素，题中已给出。

（4）存在逆元：对GG的任意元素a, a(gx,gx)，其中gxG,gxG，存在b，b(gx1,gx1)，显然bGG，ab(e,e)，所以存在逆元。 综上所述：GG是群。

4.25 若G和G'是两个群

G*G'

 {

(g,g' | gG,g'G'},

'''

(g,g(g11'2',g)2(gg,gg). G*G'的单位元是(e,e)1212，

G*G'是群。 证明：

封闭性：设(g,g)，(g,g) G*G'，

1122'' G*G' {'(g,g | gG,g'G'},

''''对于(g,g)，gG,gG,同理(g,g)，gG,gG

'111122'22G和G'是两个群，则g1g2G,g'1gG

'2'(g,g)(g,g)1122'''(gg,gg)，封闭性成立。

1212'''结合性：若(g,g)，(g,g)，(g,g) G*G'

1122'33（(g,g)(g,g)）(g,g)=(g1122'''331g,gg21'12''2)(g,g)=(g33''23'1gg,ggg)

23123'''23123'''(g,g)((g,g)(g,g))=(g,g)(g1122'''331g,gg3)=(g1gg,ggg)

'(ggg,ggg)=(ggg,ggg)

123123123123''''''即（(g,g)(g,g)）(g,g)=(g,g)((g,g)(g,g))

1122'''''33112233结合律成立。

单位元：G*G'的单位元是(e,e) 逆元素：设，(g,g)，(g,g) G*G'

1122'''若(g,g)(g,g)=(e,e) 则(g,g)是(g,g)的逆元素。

'''''11222211(g,g)(g,g)1122''(gg,gg121''2)=(e,e)

' G*G'

 {(g,g | gG,g'G'},

'g,g,eG

12G是群，g'111g2eg211g11，同理g2'g'11

(g,g)的逆元素为(g,g)，逆元素存在。

1'1综上，G*G'是群。

4.26若G是关于X=｛x1,x2,,xn｝的置换群，G’是关于X’=｛x’1,x’2,,x’m｝的置换群，对于G×G’的每一对元素 证 G×G’是关于X∪X’的置换群。 证：

1、 封闭性 G×G’是群

（g,g’）(v1) ∈G×G’ （g,g’）(v2) ∈G×G’ （g,g’）(v1) ·（g,g’）(v2) =g(v1) ·g’(v2)

若 v1、v2 ∈X，或v1、v2 ∈X’ 显然成立。 或v1∈X，v2 ∈X’

因为G是置换群，那么，g(v1)=xk∈G G’是置换群，那么，g’(v2)=xl∈G’

对应于xk这一置换，可在X’中找到一个相应的置换与之对应 若g(v1) ∈X g’(v2) ∈X’ 那么 n,m若相等，显然成立。 若 m≠n,假设 n>m g(v1)是G中一个置换 g’(v2)是G’中一个置换

对于 g(v1)来说，乘以一个g’(v2),由于g’(v2)一个循环中元素个数最多不会超过g(v1)

相当于，对于g’(v2),可在G中找到对应的。 所以，g(v1) ·g(v2) ∈G

此时，若 m>n, g(v1),g’(v2) ∈X’ 2、单位元 e =(1)(2)(3)(4)(m) m>n e =(1)(2)(3)(4)(n) m4.27 一个项链由7颗珠子装饰成的，其中两颗珠子是红色的，3颗是蓝色的，其余两颗是绿色的，问有多少种装饰方案？ 解：

7 1 2 6 3

G: 1.单位元 (1)(2)(3)(4)(5)(6)(7) 格式为(1)7，

2.顺时针转动一个格 ( 1 2 3 4 5 6 7) 格式为 (7)1，顺时针转动两个格，三个格……六个格，所得的置换的格式都为(7)1，所以同格式的共轭类共有6个 3. 1 不动，其余对折，得到置换(1)(2 7)(3 6)(4 5) 格式为(1)1(2)3，同理，其余六个珠子分别不动，又能得到六个置换，且所得的置换的格式都为(1)1(2)3，所以同格式的共轭类共有7个 |G|=14.

5对应于g0= (1)(2)(3)(4)(5)(6)(7)，用两红三蓝两绿镶嵌可有(72)*(3)=210种方案，

在g0的作用下变为自身，

对应于( 1 2 3 4 5 6 7)等6个(7)1格式的方案数为0， 对应于(1)1(2)3格式的方案数为3！，故 N=

1(2107*3!)=18种 14

4.28 一个正八面体，用红蓝两色对6个顶点进行着色；用黄绿两种颜色对八个

面进行染色，试求其中4个顶点为红色，两个顶点为蓝色，黄和绿的面各四面的方案数。

141222C261C1 解：C62C36C43*3*C451 244.28 一个正八面体，用红蓝两色对6个顶点进行着色；用黄绿两种颜色对八个

面进行染色，试求其中4个顶点为红色，两个顶点为蓝色，黄和绿的面各四面的方案数。 解：

46234133+261651 2424122