组合数学第四版答案前八章

范文一：组合数学第四版答案前八章

第二章作业答案

7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明用100分别除这52个整数，得到的余数必为0, 1,?, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则能被100整除。若a,ba和b被100除余数之和是100，则能被100整除。 a，b

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间(不过，每天都是整数个小时)，都存在连续的若干天，在此期间她恰好学习了13小时。

a证明设从第一天到第i天她共学习了小时。因为她每天至少学习1小时，所以i

和都是严格单调递增序列。因为总的学习时间a,a,？,aa，13,a，13,？,a，1312371237

不超过60小时，所以，。, a,60a，13,73a,a,？,a37371237

是1和73之间的74个整数，由鸽巢原理知道，它们中存在相a，13,a，13,？,a，131237

a，13a,a，13a,a,13a同的整数，有和使得，，从第j，1天到第i天她恰好jijiji

学习了13小时。

14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果,

4，(12,1)，1,45解由加强形式的鸽巢原理知道，如果从袋子中取出个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。

17. 证明:在一群个人中，存在两个人，他们在这群人中有相同数目的熟人(假设没n,1

有人与他/她自己是熟人)。

证明因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到的整数。若n,1有两个人的熟人的数目分别是0和，则有人谁都不认识，有人认识所有的人，这是不n,1

可能的。因此，这n个人的熟人的数目是个整数之一，必有两个人有相同数目的熟人。 n,1

第三章作业答案

6. 有多少使下列性质同时成立的大于5400的整数,

(a) 各位数字互异。

(b) 数字2和7不出现。

解因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。

7，P(7,7)? 考虑8位整数。最高位不能为0，因此8位整数有个。

7，P(7,6)? 考虑7位整数。最高位不能为0，因此8位整数有个。

? 考虑6位整数。最高位不能为0，因此8位整数有个。 7，P(7,5)

? 考虑5位整数。最高位不能为0，因此8位整数有个。 7，P(7,4)

? 考虑4位整数。若千位数字大于5，有个。若千位数字等于5，则百位数字3，P(7,3)

必须大于等于4，有个。 4，P(6,2)

根据加法原理，符合条件的整数的个数为

7，P(7,7)，7，P(7,6)，7，P(7,5)，7，P(7,4)，3，P(7,3)，4，P(6,2),948308. 15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方式,如果B只拒绝坐在A的右侧，又有多少种围坐方式,

解 15人围坐一个圆桌，有种围坐方式。若B固定坐在A的左侧，则可将看作一14!BA个整体，有13!种围坐方式。若B固定坐在A的右侧，则可将看作一个整体，有13!种AB

围坐方式。因此，B不挨着A坐的围坐方式有14!,2，13!,12，13!种，B不坐在A的右侧的围坐方式有14!,13!,13，13!种。

11. 从15个球员的集合中选人组成11个球员的足球队，其中5人只能踢后卫，8人只能踢边卫，2人既能踢后卫又能踢边卫。假设足球队有7个人踢边卫4个人踢后卫，确定足球队可能的组队方法数。

解设甲和乙既能踢后卫又能踢边卫。

85,,,,若甲和乙均不入选，组队方法数为。 ,,,,,,,,74,,,,

858585,,,,,,,,,,,,若甲和乙均入选，组队方法数为++。 ,,,,,,,,,,,,,,,,,,,,,,,,726354,,,,,,,,,,,,

8585,,,,,,,,若甲入选且乙不入选，组队方法数为+。 ,,,,,,,,,,,,,,,,7364,,,,,,,,

8585,,,,,,,,若乙入选且甲不入选，组队方法数也为+。 ,,,,,,,,,,,,,,,,7364,,,,,,,,

因此，组队方法数总共为

,,858585858585,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,++++=1120 ,,,,,,,,,,,,,,,,2，，,,,,,,,,,,,,,,,,,,,,,,,,,,736474726354,,,,,,,,,,,,,,,,,,,,,,,,,,21. 一位秘书在距离家以东9个街区、以北7个街区的一座大楼里工作。每天他都要步行16个街区去上班。

(a) 对他来说可能有多少不同的路线,

(b) 如果在他家以东4个街区、以北3个街区开始向东方向的街区在水下(而他又不会游泳)，则有多少条不同的路线,

(a) 用E表示向东步行1个街区，用N表示向北步行1个街区。因为该秘书需要向东解

步行9个街区，向北步行7个街区，总共步行16个街区，因此他的上班路线是多重集

16!的排列。这样的排列的个数为,11440。 {9,E,7,N}9!7!

(b) 若他从水下的街区走过，则他先要走到离家以东4个街区、以北3个街区的地方，再向东走一个街区，最后走到工作的大楼。他从家走到离家以东4个街区、以北3个街区的地方

7!,的路线的数目是多重集的排列数，即35。他从离家以东5个街区、{4,E,3,N}4!3!

以北3个街区的地方走到工作的大楼的路线的数目是多重集的排列数，即{4,E,4,N}8!,70。所以，如果他从水下的街区走过，则他可能有的路线数是。因35，70,24504!4!

此，如果他不从水下的街区走过，则他可能有的路线数是。 11440,2450,899026. 确定多重集S,{3,a,4,b,5,c}的10-排列的个数。

10!,1260解 S的有1个a ，4个b， 5个c的10-排列的个数为。 1!4!5!

10!,2520S的有3个a ，2个b， 5个c的10-排列的个数为。 3!2!5!

10!,4200S的有3个a ，4个b ，3个c的10-排列的个数为。 3!4!3!

10!,2520S的有2个a， 3个b， 5个c的10-排列的个数为。 3!2!5!

10!,3150S的有2个a， 4个b， 4个c的10-排列的个数为。 2!4!4!

10!,4200S的有3个a 3个b 4个c的10-排列的个数为。 3!4!3!

S的10-排列的个数为。 1260，2，2520，2，4200，3150,17850

x，x，x，x,30x,,5x,2x,0x,831. 方程有多少满足，，，的整数解, 12343124解进行变量代换:

y,x，5y,x,2y,xy,x,8，，， 33112244

则方程变为

y，y，y，y,25 1234原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为

25，4,12828,,,,,,28，27，26 ,,,,,,,,,,3276,,,,,,252533!,,,,,,

第五章作业答案 8. 用二项式定理证明

nn,,nkn,k,, 2,(,1)3,,,k,,0k,

证明由二项式定理知道

nn,,,nnkk,, ，,(xy)xy,,,k,,,0k

令，y,,1得 x,3

nnnn,,,,,,nnnkkknk,,,, ,，,,,,,2(3(1))3(1)(1)3,,,,,,kk,,,,,0,0kk18. 求和

nnnn,,,,,,,,1111n,,,,,,,, 1？(1),，,，，,,,,,,,,,2132431nn，,,,,,,,,

n，1nn，1n,,,,,,,,11解法1 对任意非负整数,,,,,,,,n和k，，即，(k，1),(n，1),,,,,,,,,k，1kk，1kn，1k，1,,,,,,,,

因此，

nnnn,,,,,,,,1111n ,,,,,,,, 1？(1),，,，，,,,,,,,,,1232341nn，,,,,,,,,

kknnn，1nnn，，11,,,,,,,,(1)(1)1k,1,,,,,, ,,,,(1),,,,,,,,,kkk，knn，，，1111,,,,,,k,0k,0k,1

n，1n，1n，1n，1,,,,11111kk,,,,,,(,1),,(,1)，,0，, ,,,,,,kkn，1n，1n，1n，1n，1,,,,k,1k,0

解法2 由二项式定理知道

nn,,nkk,, ,,,(1x)(1)x,,,k,,,0k

两边分别求积分得

n，1n，11(1,1)(1,0)1n(1,x)dx,,，, ,0n，1n，1n，1

knnnn1,,,,(1),kk,,,, (1)xdx,,,,,,,,,0kkk1，,,,,,0,0kk

所以

nnnn,,,,,,,,11111n,,,,,,,, 1,，,，，(,1),？,,,,,,,,123n234n，1n，1,,,,,,,,20. 求整数a，b和c，使得对所有的m

mmm,,,,,,3 ,,,,,,,，，mabc,,,,,,321,,,,,,

33331，2，3，？，n求级数的和。

11111,,,,,,,,,,3解令，，因为，所以。 ,,,,,,,,,,m,11,，，c,1abc,,0,,,,,,,,,,32132,,,,,,,,,,

2222,,,,,,,,3令，，因为，所以。 ,,,,,,,,m,22,，，b,8,2c,6abc,0,,,,,,,,3213,,,,,,,,

333,,,,,,3令，,,,,,,，所以。 3,，，m,3a,27,3b,3c,6abc,,,,,,321,,,,,,

nnnnmmm,,,,,,33333,,,,,, 123？66，，，，,,，，nm,,,,,,,,,,321,,,,,,,0,0,0,0mmmm

n，1n，1n，1n，2n，1,,,,,,,,,, ,,,,,,,,,, ,6，6，,6，,,,,,,,,,,43242,,,,,,,,,,

226(2)(1)(1)(1)(1)n，n，nn,n，nnn， ,，,4!24

25( 应用组合学论证方法，证明二项式系数的Vandermonde卷积:

mm对所有的正整数，和n， 12

nmmmm，,,,,,,1212,,,,,, ,,,,,,,,knkn,,,,,,,,k0

作为特殊情形，推导恒等式(5-11)。

|A|,m|B|,m|S|,m，m证明设，，，，则。 S,A,BA,B,,1212我们可以从集合A中取出k个元素，再从集合B中取出个元素，把它们合起来构成Sn,k

m,,1的有n个元素的子集。因为A的有k个元素的子集有个，因为B的有个元素的,,n,k,,k,,

nmmmm，m,,,,,,,,12122,,,,,,子集有个，所以S的有n个元素的子集个数为。 ,,,,,,,,,,,,nknk,n,k,,,,,,,,,0k

933237. 在的展开式中的系数是什么, (x,x，2x,2x)xxxx12341234

解由多项式定理知道

n,,nnnnn3124,,，，，,(xxxx)xxxx ,12341234,,nnnn1234,,n，n，n，n,n1234

x2x令x为,x，为，x为,2x，n为9，得到 332424

9,,nnnnnnn93124324,,(x,x，2x,2x),x(,1)x2x(,2)x ,12341234,,nnnn1234,,n，n，n，n,91234

332因此，的系数是 xxxx1234

9,,9!，(,8)32 ,,，(,1)，2，(,2),,,40320,,33123!，3!，1!，2!,,

1/31042. 用牛顿二项式定理近似计算。

1/31/31/3解 10,(8，2),2(1，0.25)

,,11,,,,111121112511133,,,,,,，，，,，，，，，，，，，22(1) ,,kk,,,,3433216333664kk44,,,,k0k4,,

111211125111/310,2，(1，，,，，，，，，，，),2.1547 3433216333664

第六章作业答案

3. 求出从1到10000既不是完全平方数也不是完全立方数的整数个数。

AA解设S是从1到10000的整数的集合，是从1到10000的完全平方数的集合，是从21

2100,10000|A|,1001到10000的完全立方数的集合。因为，所以。因为13321,9261,10000,10648,22|A|,21，所以。因为一个整数既是完全平方数也是2

664,4096,10000,15625,5完全立方数的充分必要条件是它是完全六次方数，，所以

|A,A|,4。从1到10000既不是完全平方数也不是完全立方数的整数个数 12

|A,A|,|S|,(|A|，|A|)，|A,A|,10000,(100，21)，4,9883 121212

6. 面包店出售巧克力的、肉桂的和素的炸面包圈，并在一特定时刻有6个巧克力、6个肉桂和3个素炸面包圈。如果一个盒子装12个面包圈，那么可能有多少种不同的盒装面包圈组合,

解用a，b，c分别表示巧克力的、肉桂的和素的炸面包圈。本题要求的是多重集

*的12-组合的个数。设S为的所有12-T,{6,a,6,b,3,c}T,{,,a,,,b,,,c}

12，3,114,,,,*T组合的集合，则。设A为的所有至少有7个a的12-组合,,,,|S|,,,911,,,,1212,,,,

**TT的集合，A为的所有至少有7个b的12-组合的集合，为的所有至少有4个c的A23

*T12-组合的集合。每个的5-组合再加上7个a就得到一个至少有7个a的12-组合，所以**TT的至少有7个a的12-组合的个数等于的5-组合的个数，

5，3,175，3,17,,,,,,,,。同样可得到，,,,,,,,,|A|,,,21|A|,,,2112,,,,,,,,5555,,,,,,,,

8，3,110,,,,*T。的至少有7个a和7个b的12-组合的个数,,,,|A|,,,453,,,,88,,,,

**TT，的至少有7个a和4个c的12-组合的个数，的至|A,A|,0|A,A|,31213

*T少有7个b和4个c的12-组合的个数，的至少有7个a、7个b和4个|A,A|,323

c的12-组合的个数。因此，T的12-组合的个数 |A,A,A|,0123

|A,A,A|123

,|S|,(|A|，|A|，|A|)，|A,A|，|A,A|，|A,A|,|A,A,A|123121323123,91,(21，21，45)，0，3，3,0,10

9. 确定方程

x，x，x，x,20 1234

满足

4,x,81,x,60,x,72,x,6，，， 3124

的整数解的个数。

解引入新变量

y,6,xy,7,xy,8,xy,6,x11223344

则方程

x，x，x，x,20 1234

满足

4,x,81,x,6， 0,x,7，， 2,x,6 3124的整数解的个数等于方程

y，y，y，y,71234

满足

，，， 0,y,50,y,70,y,40,y,41234的整数解的个数。设S是方程的所有非负整数解的集合，则y，y，y，y,71234

7，4,110,,,,A。设为方程的所有满足的,,,,y，y，y，y,7y,6|S|,,,120112341,,,,77,,,,

A非负整数解的集合，为方程的所有满足的非负整数解的y，y，y，y,7y,8212342集合，为方程的所有满足的非负整数解的集合，为方Ay，y，y，y,7y,5A1234334

程的所有满足的非负整数解的集合，则，，y，y，y，y,7y,5|A|,4|A|,01234241

2，4,15,,,,。若，则。因此，方程 ,,,,i,jA,A,,|A|,|A|,,,10ij34,,,,23,,,,

y，y，y，y,71234

满足

，，， 0,y,50,y,70,y,40,y,41234的整数解的个数

|A,A,A,A|,|S|,|A|,|A|,|A|,|A|,120,4,0,10,10,961234123424. 把六个非攻击型车放到具有如下所述禁止位置的6行6列棋盘上的方法数是多少,

(c)

× ×

部分，包含5个位置，右下角的部解禁放位置可分成两个“独立”部分，左上角的FF12分，包含3个位置。用表示把k个非攻击型车都放在禁止位置的方法数。。若在rr,8F11k

部分的禁止位置放两个非攻击型车，则有种方法;若在部分的禁止位置放F3，2，1,62两个非攻击型车，则有1种方法;若在部分和部分的禁止位置各放一个非攻击型车，FF12

则有种方法。因此，。若在部分的禁止位置放两个非攻击r,6，1，15,22F5，3,1521

型车，在部分的禁止位置放一个非攻击型车，则有种方法;若在部分的禁FF6，3,1822止位置放两个非攻击型车，在部分的禁止位置放一个非攻击型车，则有种方法;F1，5,51

若在部分的禁止位置放三个非攻击型车，则有1种方法。因此，。Fr,18，5，1,2413若在部分的禁止位置放三个非攻击型车，在部分的禁止位置放一个非攻击型车，则有FF12

种方法;若在部分和部分的禁止位置各放两个非攻击型车，则有种FF1，3,36，1,612

方法。因此，。若在部分的禁止位置放三个非攻击型车，在部分的禁r,3，6,9FF412止位置放两个非攻击型车，则有1种方法，。把六个非攻击型车放到具有上述禁止位r,15

置的6行6列棋盘上的方法数是

6!,r，5!，r，4!,r，3!，r，2!,r，1!12345

,720,8，120，22，24,24，6，9，2,1,161

iiiiii26. 计算{1,2,3,4,5,6}的排列的个数，其中 123456

i,5,6i,5,6i,1i,1,2,3i,1; ; ; 以及。 56312

解所要求的排列个数等于把六个非攻击型车放到具有如下所述禁止位置的6行6列棋盘上的方法数。

× × ×

× ×

部分，包含5个位置，右下角的部分，禁放位置可分成两个“独立”部分，左上角的FF12包含4个位置。用表示把k个非攻击型车都放在禁止位置的方法数。。若在部rr,9F11k

分的禁止位置放两个非攻击型车，则有4种方法;若在部分的禁止位置放两个非攻击型F2

车，则有2种方法;若在部分和部分的禁止位置各放一个非攻击型车，则有FF5，4,2012

种方法。因此，。若在部分的禁止位置放两个非攻击型车，在部r,4，2，20,26FF212分的禁止位置放一个非攻击型车，则有种方法;若在部分的禁止位置放两个F4，4,162非攻击型车，在部分的禁止位置放一个非攻击型车，则有种方法。因此，F2，5,101

。若在部分和部分的禁止位置各放两个非攻击型车，则有r,18，5，1,24FF312

种方法。因此，。。把六个非攻击型车放到具有上述禁止位置的6r,8r,04，2,845

行6列棋盘上的方法数是

6!,r，5!，r，4!,r，3!，r，2!,r，1!12345

,720,9，120，26，24,26，6，8，2,0，1,124

27. 8个女孩围坐在旋转木马上。她们可以有多少种方法改变座位，使得每个女孩前面的女孩都与原先的不同,

A解令{1,2,3,4,5,6,7,8}7!i(i，1)S为的全部个循环排列的集合，为出现模式的循环i排列的集合()，为出现模式的循环排列的集合。若且是Ai,？,i1,i,7811,k,71k8

{1,2,3,4,5,6,7,8}集合中的不同整数，则。。因此， |A,？,A|,(7,k)!|A|,1:iii1ki,1

8888888,,,,,,,,,,,,,, ,,,,,,,,,,,,,,|A,？,A|,7!,6!，5!,4!，3!,2!，1!,0!，1,162518,,,,,,,,,,,,,,1234567,,,,,,,,,,,,,,她们可以有1625种方法改变座位。

第七章作业答案

f,f,？,f,？1. 设表示斐波那契序列。通过用小的n值为下列每一个表达式赋值，猜测01n

一般公式，然后用数学归纳法和斐波那契递归证明之。

n(c) f,f，f,？，(,1)f012n

222 (d)f，f，？，f01n

nkf解 (c) 对于小的n值，列出和的值如下。 (,1)fn,k

,0k

n 0 1 2 3 4 5 6 7 8

f 0 1 1 2 3 5 8 13 21 n

nk 0 0 1 4 12 (,1)f,1,2,4,9,k

,0k

n,0若n0,k猜测: ,,(1)f,,kn(,1)f,1若n,1n,1,k,0

f,0当时，，结论成立。 n,00

f,f,,1,,f,1当时，，结论成立。 n,1010

nkn设且，则 (,1)f,(,1)f,1n,1,kn,1

k,0

n，1nkkn，1nn，1 (,1)f,(,1)f，(,1)f,(,1)f,1，(,1)f,,kkn，1n,1n，1

k,0k,0

n，1n，1 ,(,1)(f,f),1,(,1)f,1n，1n,1n

n2f(d) 对于小的n值，列出和的值如下。 fn,k

k,0

n 0 1 2 3 4 5 6 7 8 f 0 1 1 2 3 5 8 13 21 n

n2 0 1 2 6 15 40 104 273 714 f,k

k,0

222猜测: f，f，？，f,ff01nnn，1

2当时，，结论成立。 f,0,ffn,0001

222设，则 f，f，？，f,ff01nnn，1

22222 f，f，？，f，f,ff，f,f(f，f),ff01nn，1nn，1n，1n，1nn，1n，1n，2

h,014. 求解初始值，，和的递推关系h,1h,1h,20132

，()。 h,5h,6h,4h，8hn,4nn,1n,2n,3n,4

432解特征方程为x,5x，6x，4x,8,0。

432因为，所以是该方程的一个根。 ,1(,1),5，(,1)，6，(,1)，4，(,1),8,0

43243322x,5x，6x，4x,8,x，x,6x,6x，12x，12x,8x,8

3232 ,x(x，1),6x(x，1)，12x(x，1),8(x，1),(x,6x，12x,8)(x，1)

3 ,(x,2)(x，1)

因此，一般解为

2nnnn h,c2，cn2，cn2，c(,1)1234n

c，c,0() n,014

2c，2c，2c,c,1() n,11234

4c，8c，16c，c,1() n,21234

8c，24c，72c,c,2() n,31234

8871解该方程组得到 c, c, c,, c,, 134227722427

因此，

2nnnn8781h,，2，n，2,n，2,，(,1) n2772242718. 求解非齐次递推关系

n () h,4h，3，2n,1,1nn

h,1 0

解对应齐次递推关系的特征方程为，它的特征根为4。设该非齐次递推关系的特x,4,0

nnn,1np,2p，3p,,3解为，则，因而，因此。 p2p2,4p2，3，2

nn该非齐次递推关系的一般解为。 h,c4,3，2n

n，1n令，得，解得。因此，。 h,4,3，2n,0c,3,1c,4n26. 求解非齐次递推关系

n () h,4h，4n,1,1nn

h,3 0

，它的特征根为4。设该非齐次递推关系解法一对应齐次递推关系的特征方程为x,4,0

nnn,1n的特解为，则，解得。该非齐次递推关系的一p,1pn4pn4,4，p(n,1)，4，4

nnn般解为。令，得。因此，。 h,c4，4nh,(n，3)，4n,0c,3nn

,n解法二该序列的生成函数。 g(x),hx,n

n0,

,,,nnn1， (1,4x)g(x),(1,4x)hx,hx,4hx,,,nnn

n0nn00,,,

,,,nnn ,h，hx,4hx,h，(h,4h)x,,,0nn10nn1,,

nn11n1,,,

,,,1nnnnnn ,h，4x,3，4x,2，4x,2， ,,,01,4xn1n1n0,,,

12，211,4xg(x),,， 21,4x1,4x(1,4x),,,nnnnnn ,24x，(n，1)4x,(n，3)4x,,,

n0n0n0,,,

n因此，。 h,(n，3)，4n

h30. 确定苹果、桔子、香蕉和梨的袋装水果的袋数的生成函数，其中各袋要有偶数个苹n

h果，最多两个桔子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出的公式。 n

解生成函数

,,2n23n g(x),(x)(1，x，x)(x)(1，x),,

n0n0,,

2,(1，x，x)(1，x)1n ,,,(n，1)x,232(1,x)(1,x)(1,x)n0,

h,n，1因此，。 n

n,,32. 令是由,,定义的序列()。确定该序列的生成函数。 h,h,h,？,h,？n,0h,012nn,,2,,

,1nx,解 ,1,xn0,

,1n1, 两边求导数得到 nx,,2(1,x)n0,

,2n2,两边再求导数得到 n(n,1)x,,3(1,x)n0,

22,xn(n,1)xn两边乘得到 x,,322(1,x)n0,

因此，该序列的生成函数

2,,,n,,n(n,1)xnnn,, g(x),hx,x,x,,,,n,,322(1,x),,n0nn00,,,

n,,32. 令是由定义的序列()。确定该序列的指数生成函数。 ,,h,h,h,？,h,？n,0h,012nn,,2,,

解该序列的指数生成函数

nnn,,,nn,,,,xxx(e),,,, g(x)h,,,,,,n,,,,22n!n!n!,,,,n0n0n2,,,

nnn22n2x，,,,,!11nxxxxxxe ,,,,,,,,,2!(2)!!2(2)!2!2!2n,nn,nnn,2n,2n,0n,041. 确定所有的数字至少是4的n位数的个数，其中4和6每个都出现偶数次，5和7每个

至少出现1次，但对于数字8和9则没有限制。

解设为满足条件的n位数的个数，序列的指数生成函数是 hh,h,h,？n012

24232xxxxx(e)222 g(x),(1，，，？)(x，，，？)(1，x，，？)2!4!2!3!2!

x,x22x,2x2xx2x()(2)(21)e，ee，，ee,e，ex22x(1),e,e, 44

6x5x4x3x2xx234321e,e，e,e，e,e，, 4

nnnnnnnnnnn,,,,,,16x15x34x3x32x1x1 ,,，,，,，,,,,,,4n!2n!4n!n!4n!2n!4000000n,n,n,n,n,n,

nnnnnn,6253443322x,，，，,，，，, ,,4n!n1,

0n,0若,,nnnnn 因此，h,6,2，5，3，4,4，3，3，2,2,nn,1若,4,

第八章作业答案

1. 设在圆上选择个(等间隔的)点。证明将这些点成对连接起来所得到的n条线段不相2n

C交的方法数等于第n个Catalan数。 n

证明设为将圆上的个点成对连接起来得到n条不相交线段的方法数。我们证明序h2nn

列与Catalan数序列满足同样的递推关系和初始条件。 h,h,h,？C,C,C,？012012

设圆上的个点顺时针依次排列为，若连接线段，则其左边a,a,a,？,aaa2n0122n,10k和右边的点不能相互连接，那样会与相交。左边的点的数目和它右边的点的aaaa0k0k

数目都应当是偶数，即k是奇数。若左边的点的数目是2i，则右边的点的数aaaa0k0k目就是2(n,1,i)。随着k从1变到，i从0变到。因此，序列h,h,h,？2n,1n,1012满足递推关系

h,hh，hh，？，hhn0n,11n,2n,10

2n,2,,1g,C令，则,,。由定理7.6.1知道序列满足递推关系 g,g,g,？g,nn,1123n,,n,1n,,

g,gg，gg，？，ggn1n,12n,2n,11因此，

C,g,gg，gg，？，gg,CC，CC，？，CC nn，11n2n,1n10n,11n,2n,10又有，序列与Catalan数序列满足同样的递推关系h,1,Ch,h,h,？C,C,C,？00012012和初始条件。

8. 求前n个正整数的五次幂的和。

5555解计算序列的差分表如下。 0,1,2,？,n,？

0 1 32 243 1024 3125 ?

1 31 211 781 2101 ?

30 180 570 1320 ?

150 390 750 ?

240 360 ?

120 ?

其差分表的第0条对角线为

0，1，30，150，240，120，0，0，?

因此

n111111，，，，，，nnnnnn,,,,,,,,,,,,5,,,,,,,,,,,, 0130150240120,，，，，，k,,,,,,,,,,,,,123456,,,,,,,,,,,,,0k

12. 证明第二类Stirling数满足关系

(a) ， S(n,1),1(n,1)

n,1(b) ， (n,2)S(n,2),2,1

n,,(c) ， (n,1),,S(n,n,1),,,2,,

nn,,,,(d) ，(n,2) ,,,,S(n,n,2),，3,,,,34,,,,

证明 (a) 设，因为将个物体放入1个盒子中，只有一种方法，所以S(n,1),1。 n,1

n2,2(b) 设，A是n-元集，则A的非空真子集的个数为。任取A的非空真子集B，n,2

将B中元素放入一个盒子，而将其他元素放入另一个盒子，就得到一种将A中元素放入两个非空盒子的方法。显然，B和它的补集对应同一种方法，即每种方法都对应AA,B

nn,1的两个子集。因此，。 S(n,2),(2,2)/2,2,1

n,,(c) 设。若，则,,。下面考虑的情况。将n个物体放入n,1n,1S(n,n,1),0,n,2n,1,,2,,

个非空盒子中，必然有一个盒子中有两个物体，而其余盒子中只有一个物体。设A是n-元集，任取A的2-组合B，将B中元素放入一个盒子，将其余元素各放进一个盒子，就得到将n个物体放入个非空盒子中的方法。因此，可在A的2-组合和将n个物体放n,1

n,,入个非空盒子中的方法之间建立一一对应。所以，,,。 n,1S(n,n,1),,,2,,

nn,,,,,,,,(d) 设。若，。下面考虑的情况。将n个物n,2n,2S(n,n,2),0,，3n,3,,,,34,,,,

体放入个非空盒子中，有两种可能。一种情况是，有一个盒子中放入3个物体，其n,2

n,,余盒子中各放入一个物体，这种情况发生的次数是。另一种情况是，有两个盒子中各,,,,3,,

放入2个物体，其余盒子中各放入一个物体。从这n个物体中任取出四个，设它们是

n,,a,b,c,db,c,d,,，a可与之一在一个盒子中。因此，这种情况发生的次数是。所以，3,,4,,

nn,,,,。 ,,,,S(n,n,2),，3,,,,34,,,,

13. 令X是p-元集并令Y是k-元集。证明，把X映射到Y上的函数的个数等于 f:X,Y

# k!S(p,k),S(p,k)

Y,{b,b,？,b}b,b,？,bf(x),b证明设。将看作k个不同盒子，若，则把12k12ki

bX中元素x放入盒子，这在X映射到Y上的函数和将X中元素放入k个不同非空i

盒子的方法之间建立了一一对应。因此，把X映射到Y上的函数的个数等f:X,Y

#于。 k!S(p,k),S(p,k)

范文二：离散数学第四版答案

浅谈高中数学新教材中课本例题的教学

无锡市辅仁高级中学王文俊文章提要：搞好课本例题的多种形式教学，能使学生的数学思维能力得到进一步提高。本文从以下几个方面进行说明。首先，课本例题是解题规范参照的最佳样本；其次，课本例题是将设问引申的最理想起点；第三、课本例题是一题多解的最佳展示台；第四、课本例题是变式教学的最丰富源泉。

关键词：课本例题规范引申一题多解变式

《普通高中数学课程标准》指出：教师不仅是新课程的实施者,而且也是课程的研究、建设和资源开发的重要力量。《普通高中课程标准实验教科书—数学》，即通常所说的教材，具有完备的知识体系，又具有权威性，是教师进行数学教学的主要依据，也是学生学习数学基础知识的重要依据。而课本例题更是经过编者反复论证精心设计的，具有典型的范例作用，蕴含着基本的解题思想和方法，具有很高的教学价值。

新教材中例题的选择更是力求与生活实际接近，许多情景甚至完全可以通过实际活动来表现。在高中数学教学中，搞好例题教学，特别是搞好课本例题的多种形式教学，不仅能加深基础知识的理解和掌握，更重要的是在开发学生智力、培养和提高学生能力等方面，能发挥其独特的功效。

但是对课本例题的教学，很多老师有时会照本宣科，或认为课本例题太过一般，不值得花费时间讲解，一带而过，而改用自己在其他参考书上找来的例题。事实上，这正是教师对课程、教材研究不深入的表现。只要教师认真钻研教材，深刻理解例题的用意，充分挖掘例题的价值，结合学生的实际情况和教学的实际需要，进行适当的引申和拓展，就可以满足不同层次教学的要求。下面就新教材中课本例题的教学，谈一下笔者几点简单的想法。

一、课本例题是解题规范参照的最佳样本

解题是深化知识、发展智力、提高数学能力的重要手段。规范的解题能够养成良好的学习习惯，提高思维水平。语言（包括数学语言）叙述是表达解题程式的过程，是数学解题的重要环节。因此，语言叙述必须规范。规范的语言叙述应步骤清楚、正确、完整、详略得当，言必有据。数学本身有一套规范的语言系统，切不可随意杜撰数学符号和数学术语，让人不知所云。在高中数学的学习中，有些题目的解答过程是有严格的规范和要求的，比如函数单调性的证明，立体几何证明等等。

例1、求证：函数在区间上是单调增函数．（苏教版高中数学《必修1》第35页例2）例2、已知、分别是平面的垂线和斜线，、分别是垂足和斜足，，

．求证：．（苏教版高中数学《必修2》第36页例2）（解答过程略）

通过例1，教师应要求学生掌握解题的基本步骤是：①设所证区间内任意两个变量（通常情况下）②作差 ③变形（通常化成几个因式的乘积或商的形式）④判断差的正负⑤给出结论。教师可以通过让学生对照课本上该例题的解题过程来“回扣”函数单调性的定义，并强调凡是证明函数的单调性，必须严格按照这个解题规范来解答。通过这个例题，可以让学生明白，用定义解题，回扣课本，才是体现数学基础知识掌握好坏的一个重要方面。

在立体几何解题过程中，证明过程的书写规范是体现学生立体几何学习水平的一个重要方面。而公理定理成立的条件，相关角和距离的说明等等，也一直是许多学生不能既简洁又准确书写到位的环节。例2就是一道立体几何证明题，只是立几部分课本例题中的一例。它的书写结构是最清晰的“联立大括号+推出符号”形式，而且证明过程中顺序合理，层次清楚，条件和结论书写都很规范，是学生以后证明立几问题时参照的最佳范本。

课本例题已经为学生的解题规范作了最好的示范，而重视解题的规范化将对学生的数学学习带来积极的影响。新课程中加入《算法》的内容，学习流程图，也从一个方面说明了新课程强调数学解题要步骤清晰，规范到位。

二、课本例题是将设问引申的最理想起点

课本例题的最大特点是针对性强，基础性强，但大多数课本例题是一题一问，给学生的思维空间较小。尽管和老教材相比，新教材在部分例题解答后面安排了“思考”这个环节，对例题进行了一些挖掘，但大多数例题仍缺乏纵向和横向的引申。为了培养思维的深刻性和广阔性，激发学生的学习积极性，结合教学的实际情况，适当地对课本例题的设问进行引申是非常必要的。

例1、如图，在长方体ABCD-A1B1C1D1

中，P为棱BB1的中点，画出由A1、C1、P三

点所确定的平面与长方体表面的交线．（苏

教版高中数学《必修2》第23页例2）

例2、求下列函数的最小值：（1）；（2）

．（苏教版高中数学《必修1》第36页例4）

在解决了书中提出的设问后，针对例1，可以再提问学生：平面A1PC1与平面ABCD有没有公共点？事实上，部分空间想象能力较弱的学生会因为一时的表面现象而给出“平面A1PC1与平面ABCD无公共点”的错误答案，经同学和老师指正后，回忆起了“平面是无限延展的”这一性质，明确了平面A1PC1与平面ABCD应该也有一条交线。教师这时可适时提问：“如何作出这条交线？”一下子激发起学生强烈的探究欲望。通过和原题的比较，学生就会类似地利用所学的公理去寻找两个平面的公共点，从而得到答案。这样的设问引申可以极大地调动广大学生课堂思考的积极性，再次巩固了前面所学的公理并能更好的运用，也为后续的学习打下一个良好的注脚。

针对例2，可以再提问学生：如何更改（1）中函数（保持解析式不变），可以使得该函数既有最小值，又有最大值？又如何进行更改可以使得该函数的最小值保持不变？学生通过思考后能说出若干不同的答案，并明确：保持解析式不变，虽然改变了函数的定义域，但最值、值域仍然可能相同。这样的引申能使学生更好的把握函数定义域与值域的关系，以及函数定义域对值域的影响，又能与书中第33页习题13和第94页习题19形成前后呼应。

以上两题的解决过程并不困难，大多数学生很快就能得出答案。但若在教学过程中就题讲题，不再引申，就会丧失拓展学生创新思维的大好时机，很难激发学生的学习兴趣，造成教师、学生争相

“扔掉” ，

课本而投身到大量写板书抄笔记的运动中去，这是完全和新课程的理念背道而驰的。

三、课本例题是一题多解的最佳展示台

课本例题大部分是一题一解，目标明确，且解法的基础性强，符合大多数学生的认知要求。但这样做不利于发散性思维的培养，不利于求异思维和创新能力的培养，同样也不利于知识的融会贯通和综合解题能力的提高。一题多解的思想具有对所学知识加以融会贯通的作用，不仅体现了解题能力的强弱，更重要的是其具有开放式思维特点，是一种培养创新能力的重要思维方法。因此，一题多解应当成为教师和学生掌握数学知识和探索数学思维规律的重要手段。

例、如图，三个相同的正方形相接，求证：．（苏教版高中数学《必修4》第103

页例3）

证法1（三角函数法）：由

又，所以．

，利用

．，可得，证法2（解析几何法）：如图，由，到角公式可求得直线OA到直线OB的角的正切等于1，所以

证法3（平面几何法）：

如图，设每个小正方形边长为1，易得

EA=EF= ，AF= ，故△EAF是等腰直

角三角形，可得∠EAF=

，所以．

证法4（相似三角形法）：

如图，设每个小正方形边长为1，易得

，故△EAF∽△ECA，所以

．

以上是针对本题的4种解法，分别是利用了三角、解几、平几（沟股定理）、相似三角形的相关知识。相信对于此题，很多老师在教学中都会介绍除书本解法外的其他解法。这样做，使学生既加深了对各部分知识的理解，又找到了各部分知识之间的联系，积累了研究问题的经验，提高了解决问题的能力。

在教学中，教师应积极地引导学生从各种途径，用多种方法思考问题，培养学生积极探索的能力与意识。这样，即可暴露学生解题的思维过程，增加教学透明度，又能拓宽学生的解题思路，发展学生的思维能力，使学生熟练掌握知识的内在联系。

四、课本例题是变式教学的最丰富源泉

变式教学，就是引导学生在解答某些数学题之后，进行观察、联想、判断、猜想，对数学题的内容、形式、条件和结论作进一步的探索，从不同的侧面深入思考数学题的各种变化，并对这些“变式题”进行解答，从而培养学生灵活、深刻、广阔、发散的数学思维能力。在数学教学中,若将课本例题充分挖掘，注重对课本例题进行变式教学,不但可以抓好基础知识点,还可以激发学生的探求欲望,提高创新能力；不仅能让教师对教材的研究更加深入，对教学目标和要求的把握更加准确，同时也让学生的数学思维能力得到进一步提高，并逐渐体会到数学学习的乐趣。

例、长为（是正常数）的线段AB的两端点A、B分别在互相垂直的两条直线上滑动，求线段AB中点M的轨迹．（苏教版高中数学《选修2—1》第57页例1）

变题1：长为（是正常数）的线段AB的两端点A、B分别在互相垂直的两条直线上滑动，延长AB到点M，且使AB=BM，求点M的轨迹．

变题2：长为（是正常数）的线段AB的两端点A、B分别在互相垂直的两条直线上滑动，点M在直线AB上且

（），求点M的轨迹．

变题3：长为（是正常数）的线段AB的两端点A、B分别在互相垂直的两条直线上滑动，点C在直线AB上，若MC⊥AB且（其中为非零常数），求点M的轨迹．

上面这个例题只是最基本的求轨迹问题（转移法），但在三个变题中先是将转移点的位置进行了变化，轨迹由圆变化为椭圆，接着转移点的数量一般化，化简出轨迹方程后需经过分类讨论来说明所表示的曲线类型，最后一个变题则更进一步要求学生综合运用求轨迹的知识，合理化简轨迹方程，并通过分类讨论描述轨迹。在题目条件背景相同的情况下，以这个例题为基础变化出了三个层次渐进的变题，由

易到难，由浅入深，使学生进一步巩固了轨迹问题的求解，并且也让学生注意到了分类讨论的解题思想在求轨迹问题中的应用。

新教材中可以这样进行变式教学的例题还有很多，还有许多看似平淡但却很精彩的题目，忽视对这些题目的研究和运用，是很可惜的。所以，进行变式教学，请记住：课本例题就在你的手边。纵观近几年高考数学试卷，源于课本的题型占了很大的比重，大多是将课本题型进行变式提高，灵活应用，这与高考命题中的“源于课本，高于课本”的原则是一致的。所以，只有讲好，学好，用好课本，发挥课本例题的最大作用，才能在高考中取得好成绩。

课本例题一般都具有典型性、示范性和关联性，它们或是渗透着某些数学方法，或是体现了某种数学思想，或提供某种重要结论。教师应该让学生充分认识例题本身所蕴含的教育价值，学会怎样进行数学思维，怎样运用数学知识进行思考、解题，如何表述自己的解题过程等等。教师只有充分地利用教材，发挥课本例题的潜能，才能达到优化学生的认知结构，开阔学生的眼界，活跃学生的思维，提高学生解题能力的目的。

参考文献

1 教育部. 《普通高中数学课程标准（实验）》北京：人民教育出版社，2003 2 单墫. 普通高中课程标准实验教科书(必修). 南京:江苏教育出版社,2005 3 刘占溪.挖掘习题资源培养思维品质. 中学数学教学参考，2006，8

4 陈凌，宗平芬. 再议“一题多解”及其教学策略. 中学数学教学参考，2006，10

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

习题四

m4.1. 若群G的元素a均可表示为某一元素x的幂，即a= x，则称这个群为循环群。若群的

元素交换律成立，即a , b ,G满足

a,b = b,a

则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。 m[证].设循环群(G, ,)的生成元是x,G 。于是，对任何元素a , b ,G，，m，n,N，使得a= x , 00nb= x ,从而 0m n a,b = x, x00 m +n = x(指数律)0n +m = x(数的加法交换律) 0n m = x, x (指数律) 00

= b,a

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

m4.2. 若x是群G的一个元素，存在一个最小的正整数m，使x=e，则称m为x的阶，试证: 2m-1 C={e,x,x, ？,x}

是G的一个子群。

[证].(1)非空性C ,,:因为，e,G; 2m-1m(2)包含性C,G:因为x ,G，根据群G的封闭性，可知x, ？,x, (x=)e,G，故C,G; kl(3)封闭性,a , b ,C, a , b ,C:, a , b ,C，，k，l,N (0, k< m)="" ;="" -1k(4)有逆元,a="" ,c,="" a="" ,c:,="" a="" ,c，，k="" ,n="" (0,="">< m)="" 。="">

综合(1) (2) (3) (4)，可知(C, ,)是(G, ,)的一个子群。

4.3. 若G是阶为n的有限群，则G的所有元素的阶都不超过n。 2m-1[证].对任一元素x,G，设其阶为m，并令C={e,x,x, ？,x}，则由习题4.2.可知(C, ,)是(G, ,)的一个子群，故具有包含性C,G。因此有

m = |C| , | G | = n

所以群G的所有元素的阶都不超过n。

4.4. 若G是阶为n的循环群，求群G的母元素的数目，即G的元素可以表示成a的幂: 2n a,a, ？,a

的元素a的数目。

[证].设(G, ,)是循环群，a是其一个母元素(生成元)，a的阶为n(也是G的阶)，则 2nG ={a,a, ？,a(=e) }。 r(1).我们来证:对任何自然数r ,N (0<><>

其次， rn r,n (a)= a(指数律)n,r = a(数的加法交换律)nr =(a)(指数律) r = e = e 。r因而，由k是元素a的阶，具有最小性，所以k , n。

to find solutions. Especially valuable is, these two missions took the city in Beijing, the considerable work in blue, from yinglaisongwang, provide services to invite businessmen and for major projects, micromanaging, hands-on, real offices full service, full service role. Hotel in Pingliang, Pingliang building and printingBrush factory service quality and service levels have also been further enhanced. Second, creatively work towards funding projects onto a new stage. The Beijing liaison office LAN from simple secure funding, and the shift to a more directly involved in the project, from the small projects to large projects to introduce change, strengthening project work. Liaison Office in Beijing, always put the report convergence and implementation, as reported to national construction projects, I work a top priority, take the initiative to strengthen contacts with national ministries and provincial authorities on contact and, from top to bottom convergence projects in advance, timely feedback on the city and the County (district). Liaison Office in Beijing this year, and cooperate with, or directly with item 8 of the interface implemented on the national, provincial, for State investment of nearly 20 million Yuan. The blue Office closely around the city's four pillar industries, large projects and more mature projects, brand focus and direction of the project as an investment. Grasp the

综合这两方面，可得k = n。

(2).根据(1)的结论，可得，群G的母元素的数目为,(n) (欧拉函数，小于n且与n互素

的数的个数)。

k m注.引理*.设(G,,)是群。,x,G，若x的阶为k，从而x=e 。则 ,m,N, x,e , k | m 。 [证].先证,): m 若x,e，则必有k | m 。

否则k ? m ，于是，由带余除法，可设 m=kq+r (0, r, k)，故可得 r=m-kq，从而 rm-kq x,x m+(-kq) ,x mk-q ,x , (x) (指数律) -qmk ,e , e (x,e, x=e)

,e , e

故与x的阶为k，具有最小性，矛盾。

次证,):

若k | m，则m = kq。于是 m kq x, x kq ,(x) (指数律) qk ,e (x=e )

=e 。

4.5. 试证循环群G的子群仍是循环群。

[证].设(H, ,)是循环群(G, ,)=的一个子群，则H中的元素都可表示成a的一些正方幂。设mma是H中指数最小的正方幂，我们来证(H, ,)=。为此只要证明H中任一元素都可表示m成a的正方幂即可。

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

k=qm+r 且 0,r

4.6. 若H是G的子群，x和y是G的元素，试证xH,yH或为空，或xH = yH。 [证].对任何x,y,G，若xH , yH=,，则问题已证。

否则若xH , yH,,，则必至少有一元素x,xH , yH，从而 0

x, xH , yH 0

, x, xH , x, yH 00

, x=x,h , x =y,h (这里h, h,H) 010212

, x,h = y,h 12-1–1 , x = y ,h,h , y = x ,h,h (*) 2112

下面我们来证:xH = yH。为此，要分证:

(1)xH , yH ;

(2)yH , xH ;

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

对任何元素a，

a, xH

, a =x,h, (这里h,,H) -1-1 , a = y ,h,h,h, (由(*):x = y ,h,h ) 2121-1 , a =y ,h,, (由H的封闭性 : h,,= h,h,h,,H) 21

, 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(h)= f(h) 12

, x,h = x,h 12

, h = h (群的消去律 )。 12

所以，f是从H到的双射，因此 |xH|=|H|=k 。

4.8.有限群G的阶为n，H是G的子群，则H的阶必除尽G的阶。 [证].这即是著名的拉格郎日(Lagrange法国著名数学家、力学家1736-1814)定理。

设G的子群。 H,{e,h,h,？,h}r,112

a,G于是令，这里，并且我们定义R是G上aH,{a,e,a,a,h,a,h,？,a,h}12r,1

R,G，G的二元关系，即

,，。 x,y,GxRy::,(，b,G)(x,aH,y,aH)

从而R是G上的等价关系，其等价块的形式为aH，设其代表元为，则a,a,？,a12k

是所有的等价块，构成对G的一个划分(参见习题4.6.)。即 aH,aH,？,aH12k

，，， G,aH，aH，？，aH12k

aH,aH,？,aH,H,r根据习题4.7.可得。 12k

G,kH,kr,n因此，所以r必能整除n，即H的阶必除尽G的阶。

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

|E| = |E| 。 xy

[证].设底基X={1,2,？,n}。对任一个元素a,X，E={b,X | ，p,G , (a)p=b}。 a

因为已知x和y在群G作用下属于同一等价类，因此，存在z,X，使得x, y,E，于是z，p, p,G , 使得 (z)p=x, (z)p=y 。 1212

我们来证:E= E 。为此，要分证: x y

(1) E , E ; xy

(2) E , E; yx

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

对任何元素a,X，

a, E x

, a = (x)p, (这里p,,G)

, a = (z)pp, (由 (z)p=x ) 11-1-1 , a = (y)ppp, (由(z)p=y , 得 (y)p=z (群G有逆元)) 2122-1, a = (y) p,, (由群G的封闭性 : p,,= ppp,,G) 21

, a, E y

所以 E , E。 xy

所以，由包含关系的反对称性，我们得到 E= E。 x y

to find solutions. Especially valuable is, these two missions took the city in Beijing, the considerable work in blue, from yin【第 3 页共 9 页】 glaisongwang, provide services to invite businessmen and for major projects, micromanaging, hands-on, real offices full service, full service role. Hotel in Pingliang, Pingliang building and printingBrush factory service quality and service levels have also been further enhanced. Second, creatively work towards funding projects onto a new stage. The Beijing liaison office LAN from simple secure funding, and the shift to a more directly involved in the project, from the small projects to large projects to introduce change, strengthening project work. Liaison Office in Beijing, always put the report convergence and implementation, as reported to national construction projects, I work a top priority, take the initiative to strengthen contacts with national ministries and provincial authorities on contact and, from top to bottom convergence projects in advance, timely feedback on the city and the County (district). Liaison Office in Beijing this year, and cooperate with, or directly with item 8 of the interface implemented on the national, provincial, for State investment of nearly 20 million Yuan. The blue Office closely around the city's four pillar industries, large projects and more mature projects, brand focus and direction of the project as an investment. Grasp the

所以得证 |E| = |E| 。 xy

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

其余染蓝色，问有多少种着色方案,

[解]. 一个3，3的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:

不动0:: P=(1)(2)(3)(4)(5)(6)(7)(8)(9) 1 3 12

逆时针旋转90:: P=(5)(1793)(2486) 24 5 6 顺时针旋转90:: P=(5)(1397)(26 84) 3

7 8 9 旋转180:: P=(5)(19)(28)(37)(46) 4

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

第4.11题表

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

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

19442224P(b,r)=[(b+r)+2(b+r)(b+r)+(b+r)(b+r)] 472其中br的系数即为所求染色方案数:

94,,,,1,,,, [，2,0，],,,,214,,,,

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个置换没有不动点(因为没有两个坐位坐同一人)，即

c(e)= c(P)= n!，c(P)= c(P)=…= c(P)=0。 111121312n

故由Burnside引理有

l=[c(e)]/2n =n!/ 2n =(n-1)!/2 1

个方案。

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

合作为相同处理。

[解]. 见第4.13题图，使之重合的刚体运动群，它含有关于正六角形中心轴旋转?60:，?120:，oo180:的置换，绕过2个对角的轴翻转180的置换，以及绕过2个对凹的轴翻转180的置换:

不动0::(1)(2)(3)(4)(5)(6) 1y z 旋转 ?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) 26 旋转180::(1 4)(2 5)(3 6)

x, 翻转(角-角) 180::(1)(2 6)(3 5)(4)，(2)(1 3)(4 x o 6)(5)，(3)(1 5)(2 4)(6)

5 3

翻转(凹-凹) 180::(1 4)(2 3)(5 6)，(1 2)(3 6)(4 5)，(1 6)(2 5)(3 4)。

转动群格式置换循环节所求方案数 66(1) 5 不动 0: 1个 6个 11(6) 2?5 旋转 ?60: 2个 1个 22(3) 2?5 旋转 ?120: 2个 2个 33(2) 5 旋转 180: 1个 3个 224(1)(2) 3?5 翻转(角-角) 180: 3个 4个 33(2) 3?5 翻转(凹-凹) 180: 3个 3个

第4.13题表

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

1612343 l=[5，2,5，2,5，5，3,5，3,5] 12

1=(15625，10，50，125，1875，375) 12

1=,18060 12

=1505(种) 。

4.25. 若G和G,是两个群

G ，G,?{(g,g,)|g, G , g,, G, },

(g,g,) (g,g,)?(gg,g,g,), 11221212

G ，G,的单位元素是(e,e,)。试证G ，G,成群。 [证]. 1:封闭性:,(g,g,) , (g,g,) , G ，G, 1122

,( g , g , G), (g, , g, , G,) 1212

,( gg , G), (g, g, , G,) (群G和G,的封闭性) 1 212

,(gg,g,g,) , G ，G, 1212

,(g,g,) (g,g,) , G ，G, 1122

因而封闭性成立。

2:结合律:,(g,g,) , (g,g,) , (g,g,), G ，G, 112233

((g,g,)(g,g,))(g,g,) 112233

=(gg,g,g,)(g,g,) 121233

=((gg)g,(g,g,)g,) 123123

=(g(gg),g,(g,g,)) (群G和G,的结合律) 123123

=(g,g,)(gg,g,g,) 112323

=(g,g,)((g,g,)(g,g,)) 112233

因而结合律成立。

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,) -1-1,( g, G), (g,, G,) (群G和G,有逆元) -1-1,(g, g,) , G ，G, -1-1-1-1 使得 (g , g,)(g, g,) = (gg , g,g,)

to find solutions. Especially valuable is, these two missions took the city in Beijing, the considerable work in blue, from yin【第 5 页共 9 页】 glaisongwang, provide services to invite businessmen and for major projects, micromanaging, hands-on, real offices full service, full service role. Hotel in Pingliang, Pingliang building and printingBrush factory service quality and service levels have also been further enhanced. Second, creatively work towards funding projects onto a new stage. The Beijing liaison office LAN from simple secure funding, and the shift to a more directly involved in the project, from the small projects to large projects to introduce change, strengthening project work. Liaison Office in Beijing, always put the report convergence and implementation, as reported to national construction projects, I work a top priority, take the initiative to strengthen contacts with national ministries and provincial authorities on contact and, from top to bottom convergence projects in advance, timely feedback on the city and the County (district). Liaison Office in Beijing this year, and cooperate with, or directly with item 8 of the interface implemented on the national, provincial, for State investment of nearly 20 million Yuan. The blue Office closely around the city's four pillar industries, large projects and more mature projects, brand focus and direction of the project as an investment. Grasp the

-1-1 = (e,e,) (gg= e，g,g,= e,) -1-1-1-1 = (gg , g,g,) (gg = e，g,g,= e,) -1-1 = (g, g,)(g , g,)

因而有逆元。

所以G ，G,构成群。

4.26. 若G是关于X={x, x,？, x}的置换群，G,是关于X, ={x,, x,,？, x,}的置换群，对于G 12n12m

，G,的每一对元素

g(v),v,X, (g,g,)(v)? ,,,g(v),v,X,

证G ，G,是关于X,X,的置换群。

[证].将题中G ，G,中的置换的前置定义换为如下等价的后置定义:

(v)g,v,X,(v)(g,g,)?。 ,,,(v)g,v,X,

因而G ，G,={(g,g,)|g, G , g,, G, }。

于是，我们可定义G ，G,上的二元“乘法”运算如下:

(g,g,) (g,g,)?(gg,g,g,)。 11221212

由于置换群G和G,也是群，故根据习题4.25.，可知G ，G,是群。又由于G ，G,是X,X,上置换的集合，所以G ，G,是关于X,X,的置换群。

4.27. 一个项链由7颗珠子装饰而成的，其中两颗珠子是红的，3颗是蓝的，其余两颗是绿

的，问有多少种装饰方案,试列举之,

,1 3ed [解]. 见第4.27题图，使之重合的刚体运动群，令,=，5172

1,fc,,360它含有关于圆环中心轴旋转=?,， 7

6 3 o23 ,,,,360,,360=?2,，=?3,，以及绕过一个顶点及其77g b o对弧中点的轴翻转180的置换: 4 5 a 不动0::(1)(2)(3)(4)(5)(6)(7)

旋转?,:(1 2 3 4 5 6 7)，(7 6 5 4 3 2 1) 第4.27题图1

旋转?2,:(1 3 5 7 2 4 6)，(7 5 3 1 6 4 2)

旋转?3,:(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)。

转动群格式置换循环节 7(1) 不动 0: 1个 7个 1(7) 旋转 ?, 2个 1个 1(7) 旋转 ?2, 2个 1个 1(7) 旋转 ?3, 2个 1个 13(1)(2) 翻转(点-弧) 180: 7个 4个

第4.27题表

将2颗r色,2颗g色,3颗b色的珠子装饰在圆环的7个等分点上的问题，相当于用b，g， r三种颜色对正七边型进行染色。

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

17777112223P(b,g,r)=[(b+g+r)+6(b+g+r)+7(b+g+r)(b+g+r)] 14322其中bgr的系数即为所求项链串珠方案数:

73,,,,1 ,,,,[，6,0，7,1,],,,,32211114,,,,

17!3!= [，7]143!2!2!1!1!1!

1=[210，42] 14

1= ,25214

=18(种)。

所求18种项链串珠方案枚举如下:

to find solutions. Especially valuable is, these two missions took the city in Beijing, the considerable work in blue, from yin【第 7 页共 9 页】 glaisongwang, provide services to invite businessmen and for major projects, micromanaging, hands-on, real offices full service, full service role. Hotel in Pingliang, Pingliang building and printingBrush factory service quality and service levels have also been further enhanced. Second, creatively work towards funding projects onto a new stage. The Beijing liaison office LAN from simple secure funding, and the shift to a more directly involved in the project, from the small projects to large projects to introduce change, strengthening project work. Liaison Office in Beijing, always put the report convergence and implementation, as reported to national construction projects, I work a top priority, take the initiative to strengthen contacts with national ministries and provincial authorities on contact and, from top to bottom convergence projects in advance, timely feedback on the city and the County (district). Liaison Office in Beijing this year, and cooperate with, or directly with item 8 of the interface implemented on the national, provincial, for State investment of nearly 20 million Yuan. The blue Office closely around the city's four pillar industries, large projects and more mature projects, brand focus and direction of the project as an investment. Grasp the

第4.27题图2

4.28.一个正八面体,用红、蓝两色对6个顶点进行着色;用黄、绿两种颜色对8个面进行染

色，试求其中4个顶点为红, 两个顶点为蓝, 黄和绿的面各四面的方案数。注. 正八面体可以看作是正方体的对偶,每一面用中心代表一个顶点,相交于一个顶点的3个面对应过3个

中心的三角形,由此构成的6个顶点, 8个面的几何图形。

[解].(参见第二版第17题)本题相当于把正八面体的6个顶点、8个面合并起来作为目标集;6个顶点、8个面,共14个元素的置换群。

转动群格式置换循环节 68(1)-(1) 不动 0: 1个 14个 212(1)(4)-(4) 面心-面 ?90: 6个 5个 224 (1)(2)-(2) 面心-面心 180: 3个 8个 222 (3)-(1) (3) 顶点-顶点 ?120: 8个 6个 1 34 (2)-(2) 棱中-棱中 180: 6个 7个 1

第17题图

A E

1 1 1

D (3) (3) 5 (3) 5 (4) (4) (4) (7) (7) (7) (2) (2) (2) 2 4 2 4 (8) 2 4 (8) (8) (1) (1) 3 3 (6) 3 (6) (6) C (5) (5)

6 6 6

F B 第4.28题图

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

16824414422222224 P(r,b,y,g)=[(r+b)(y+g)+6(r+b)(r+b)(y+g)+3(r+b)(r+b)(y+g)243322332223224+8(r+b)(y+g)(y+g)+6(r+b)(y+g)] 4244其中rbyg的系数即为所求项链串珠方案数:

68222222434,,,,,,,,,,,,,,,,,,,,,,1,,,,,,,,,,,,,,,,,,,,,,[，6,,1,，3,(，),，8,0，6,] ,,,,,,,,,,,,,,,,,,,,,,2421012021224,,,,,,,,,,,,,,,,,,,,,,to find solutions. Especially valuable is, these two missions took the city in Beijing, the considerable work in blue, from yinglaisongwang, provide services to invite businessmen and for major projects, micromanaging, hands-on, real offices full service, full service role. Hotel in Pingliang, Pingliang building and printingBrush factory service quality and service levels have also been further enhanced. Second, creatively work towards funding projects onto a new stage. The Beijing liaison office LAN from simple secure funding, and the shift to a more directly involved in the project, from the small projects to large projects to introduce change, strengthening project work. Liaison Office in Beijing, always put the report convergence and implementation, as reported to national construction projects, I work a top priority, take the initiative to strengthen contacts with national ministries and provincial authorities on contact and, from top to bottom convergence projects in advance, timely feedback on the city and the County (district). Liaison Office in Beijing this year, and cooperate with, or directly with item 8 of the interface implemented on the national, provincial, for State investment of nearly 20 million Yuan. The blue Office closely around the city's four pillar industries, large projects and more mature projects, brand focus and direction of the project as an investment. Grasp the

1= [15，70，6，2，3，(2，1)，6，6，3，6]24

1= [1050，12，54，108]24

1= ,122424

=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)

)(28)(34)(56) (24)(15)(36)-(17

(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) 。

to find solutions. Especially valuable is, these two missions took the city in Beijing, the considerable work in blue, from yin【第 9 页共 9 页】 glaisongwang, provide services to invite businessmen and for major projects, micromanaging, hands-on, real offices full service, full service role. Hotel in Pingliang, Pingliang building and printingBrush factory service quality and service levels have also been further enhanced. Second, creatively work towards funding projects onto a new stage. The Beijing liaison office LAN from simple secure funding, and the shift to a more directly involved in the project, from the small projects to large projects to introduce change, strengthening project work. Liaison Office in Beijing, always put the report convergence and implementation, as reported to national construction projects, I work a top priority, take the initiative to strengthen contacts with national ministries and provincial authorities on contact and, from top to bottom convergence projects in advance, timely feedback on the city and the County (district). Liaison Office in Beijing this year, and cooperate with, or directly with item 8 of the interface implemented on the national, provincial, for State investment of nearly 20 million Yuan. The blue Office closely around the city's four pillar industries, large projects and more mature projects, brand focus and direction of the project as an investment. Grasp the

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

第1章排列与组合

1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：[解] (a) a -b =5

将上式分解，得到?a -b =+5

(a ) a -b =5; (b ) a -b ≤5.

?a -b =-5

a = b–5，a=1，2，?，45时，b ＝6，7，?，50。满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，?，50时，b ＝0，1，2，?，45。满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) a -b ≤5

(6+10) ?5+11?(45-4) =16?5+11?41=531个点。

1.2 5个女生，7个男生进行排列，

(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？

[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）! ×5!=8!×5! ＝40320×120=4838400

(b) 先将男生排列有7! 种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有C 8种选择。将女生插入，有5! 种方案。故按乘法原理，有：

7! ×C 8×5!=33868800(种) 方案。

(7+1)! = 8!

由于A ，B 可交换，如图

**A***B** 或 **B***A**

故按乘法原理，有：

2×C 5×3! ×8!=4838400（种）

1.3 m个男生，n 个女生，排成一行，其中m ，n 都是正整数，若

(a) 男生不相邻(m?n+1)； (b) n个女生形成一个整体； (c) 男生A 和女生B 排在一起；分别讨论有多少种方案.

[解] (a) 先将n 个女生排列，有n! 种方法，共有n+1个空隙，选出m 个空隙，共有C n +1种

方法，再插入男生，有m! 种方法，按乘法原理，有：

n! ×C n +1×m! ＝n! ×

(n +1)! n ! (n +1)!

m!=×种方案。

m ! (n +1-m )! (n +1-m )!

(b) n个女生形成一个整体，看作一个人，与m 个男生做重排列，然后，n 个女生内部

再作排列，按乘法原理，有(m+1)!×n! 种方案。

(c) 男生A 和女生B 排在一起，看作一人，和其余n-1+m-1=n+m-2个人一起，作排列，共有(n+m-2+1)=(n+m-1)!种方法，A ，B 两人内部交换，故有2×(n+m-1)!种方案。 1.4 26个英文字母进行排列，要求x 和y 之间有5个字母的排列数.

[解] 选入26－2＝24个字母中选取5个字母，有C 24种方法，5个字母内部排列，有

5! 种方案，再将X*****Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X 与Y 可交换，故按乘法原理，有：

24! ?24? 5

2×C 24×5! ×20!=2××5! ×20!=40×24! ≈ 40×2π?24× ?

5! ?19! e ??

又因为：ln40+0.5(lgπ+lg48)+24(lg24–lge)

≈1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481) =25.39325777

所以，结果为e ?1025＝2.473191664×1025

1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字. [解] 3000~8000中各位不同的奇数，分类讨论：

首位3，1×8×7×4（末位不能取3）首位4，1×8×7×5（末位全取）首位5，1×8×7×4 首位6，1×8×7×5 首位7，1×8×7×4 从而，由加法原理，得：

8×7×（4＋5＋4＋5＋4）=56×22＝1232个。 1.6 计算

1?1! +2?2! +3?3! + +n ?n !

! +2?2! +3?3! + +n ?n ! =(n +1)! -1 (参见p14) (n ! -1=[解] 1?1

1.7 试证

被2n 除尽.

∑k ?k ! )

k =1

n -1

(n +1)(n +2) (2n )

(2n )! (2n )! ! (2n -1)! ! 2n ?n ! ?(2n -1)! !

==2n (2n -1)! ! [证] (n +1)(n +2) (2n ) ==

n ! n ! n !

故能被2整除。

1.8 求1040和2030的公因数. [解]因为1040=240·540，2030=(22·5) 30=260·530, 所以它们的公因数为形如2m ·5n 的数，其中0?m ?40，0?n ?30，故它们的公因数的数目为(40+1)(30+1)=1271。 1.9 试证n 2的正除数的数目是奇数.

[证]当n=1时，因数为10；当n=2时，因数为20，21，22；当n=3时，因数为30，31，32；

设n =p 11p 22 p n n ，(p 1, p 2, , p n , 均为质数) ，则n =p 11p 22 p n n 的正除数可表示为

k n k 2

p 1k 1p 2 p n ，其中k 1, k 2, , k n , 均为整数，且

0≤k 1≤2l 1,0≤k 2≤2l 2, ,0≤k n ≤2l n , ，所以n 2的正除数的个数为(2l 1+1)(2l 2+1) (2l n +1) ，结果是奇数的乘积为奇数。

1.10 证明任一正整数n 可惟一地表示成如下形式：

n =∑a i i ! ,(0≤a i ≤i , i ≥1)

i ≥1

[证]. (1)可表示性：

令M={(a m-1, a m-2, ?, a 2, a 1):0≤a i ≤i ，i=1,2,?,m-1}，显然|M |=m!；

N={0,1,2,?,m!-1}，显然|N |=m!，其中m 是大于n 的任意整数。定义函数f : M→N

f (a m-1, a m-2, ?, a 2, a 1)=a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11! (*)

显然，0= 0(m-1)!+0(m-1)!+?+0?2!+0?1! ≤ a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11!

≤ (m-1)(m-1)!+(m-2)(m-1)!+?+2?2!+1?1!= m!-1 （见P 14）即0≤ f(a m-1, a m-2, ?, a 2, a 1) ≤m!-1

由于f 是用普通乘法和普通加法所定义的，故从而f 无歧义。从而有一确定的数K （0≤K ≤m!-1），使K =f (a m-1, a m-2, ?, a 2, a 1)

为证N 中的任一数均可表示成上边(*)的形式，只要证明f 是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f 是单射函数即可。

否则，设存在某数K 0∈N , 有(a m-1, a m-2, ?, a 2, a 1) ≠(b m-1, b m-2, ?, b 2, b 1) 均属于M ，使

K 0=f (a m-1, a m-2, ?, a 2, a 1) 且K 0=f (b m-1, b m-2, ?, b 2, b 1)

由于不相等, 故必有某个j(≤m-1) ，使a j ≠b j 。不妨设这个j 是第一个不使相等的，即ai=bi(i =m -1, j +1) ，aj ≠bj 且aj

a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11!= bm-1(m-1)!+b m-2(m-1)!+?+b 22!+b 11! 就可有(b j -a j )j!+(b j-1-a j-1)(j-1)!+?+(b 2-a 2)2!+(b 2-a 1)1!=0 但是

(b j -a j )j!+(b j-1-a j-1)(j-1)!+?+(b 2-a 2)2!+(b 2-a 1)1! ≥(b j -a j )j!-[|b j-1-a j-1|?(j-1)!+?+|b 2-a 2|?2!+|b 2-a 1|?1!] ≥j!-[(j-1)?(j-1)!+?+2?2!+1?1!]=j!-(j!-1)=1 矛盾，这说明f 是单射函数。

由于|M |=|N |=m!有限，故f 是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由n ∈N ，都有(a m-1, a m-2, ?, a 2, a 1) ∈M ，使得

n=a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11! 这就证明了任何n 可表示成以上形式。 (2)唯一性：用证明单射的方法，就可以证明表示法的唯一性(表示方法见P 14), 留给读者。 1.11 证明nC (n -1, r ) =(r +1) C (n , r +1) ，并给予组合解释. [证]. (参见 P 28 (1-8-4))

nC (n -1, r ) =n

(n -1)! n !

=(r +1) =(r +1) C (n , r +1)

r ! (n -r -1)! (r +1)! (n -r -1)!

组合意义：（等式右边）由n 个元素中取出r+1个元素组合（有C (n,r+1)种），再从每个组合中取出1个（有r+1种），全部结果为C (n,r+1)(r+1)。（等式左边）由此所得的全部结果相当于从n 个元素中直接取1个元素（有n 种），但有重复，其重复数等于剩下的n-1个元素中取r 个元素的组合C (n-1,r)，故n C (n-1,r)= (r+1)C (n,r+1)。 1.12 试证等式：

∑kC (n , k ) =n 2

k =1

n -1

[证]. 证法一：根据二项式定理，(参见 P 29 (1-8-5))

(1+x ) n =1+C (n,1)x +C (n,2)x 2+?+ xn

两边对x 求导，有n(1+x ) n-1=C (n,1)+2C (n,2)x +?+ nx n-1

令x =1，即得∑kC (n , k ) =n 2n -1。

k =1n

证法二：组合意义：设有n 个不同的小球，并有A 、B 两个合子，A 合中恰好放入一个球，B 合中可放入任意多个球。有两种放球方法：

(1)（等式左边）先从n 个球中选取k 个，再从这k 个球中任选一个放入A 合，剩下的k-1个球全部放入B 合中，方案数共为∑kC (n , k ) ；

k =1n

(2)（等式右边）先从n 个球中任选一个放入A 合，剩下的n-1个球每个都有两种可能，要么放入B 合，要么不放，方案数共为n2n-1；

显然，两种放球方法等效，两种放球方案数相等，即∑kC (n , k ) =n 2n -1。

k =1n

1.13 有n 个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数. [解] 设这n 个不同的数为m 1<>

若假定第一组取k 1个数，第二组取k 2个数，并且令m=k1+k2(m≥2) ，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n 个数中任选m 个数(有C(n,m)种选法) ，再从这m 个数中从大到小取k 1个数作为第一组数(有k 1=1,2,?,m-1共m-1种取法) ，将其余k 2个数作为第二组数，即可。故总方案数为

m =2

。 ∑(m -1) C (n , m ) =(n -2) 2n -1+1（参见第3题等式）

1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少

种方案？

[解] 第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种, ??。

即方案数为1?3?2?2?1?1=12。

1.15 试求从1到1 000 000的整数中，0出现的次数. [解] (参见P 8) 从1到1 000 000的整数中，0出现的次数相当于10-99，100-999，1000-9999, 10000-99999, 100000-999999, 以及1 000 000中的0的个数。 10-99中的零的个数为： 9

100-999中的零的个数为： 2?9+9?9+9?9=18+81+81=180

十位、个

位为零，故对百位的每一种取法，有两个零

十位为零

个位为零

1000-9999中的零的个数为：3?9+2?C 3?9?9+C 3?9?9?9 有三位为零

有两位为零

有一位为零

=27+486+2 187 =2 700

10000-99999中的零的个数为：

321

4?9+3?C 4?9?9+2?C 4?9?9?9+C 4?9?9?9?9

有四位零

有三位零

有二位零

有一位零

=36+972+8 748+26 244 =36 000

100000-99999中的零的个数为：

4321

5?9+4?C 5?9?9+3?C 5?9?9?9+2?C 5?9?9?9?9+C 5?9?9?9?9?9 有五位零

有四位零

有三位零

有二位零

有一位零

=45+1 620+21 870+131 220+295 245=450 000 1，000，000中的0的个数为： 6 故1到1，000，000的整数中0的个数为：9+180+2 700+36 000+450 000+6=488 895。 1.16 n个完全一样的球放到r 个有标志的盒（n ?r ）中，无一空盒，试问有多少种方案？ [解]

1.17 n和r 都是正整数，而且r ?n ，试证下列等式：

-1

(a ) P r n =nP r n -1

(b ) P r n =(n -r +1) P r n -1n

P r n -1, r

(d ) P r n +1=P r n +rP r n -1(c ) P r n =

n -1r (e ) P r n +1=r ! +r (P r n -1+P r -1+ +P r -1)

[解] (a) 方法一

n !

P ==n (n -1) (n -r +1) =n (n -1) [n -1-(r -1) +1]

(n -r )!

(n -1)! -1

=n =nP r n -1

[(n -1) -(r -1) +1]!

n r

方法二（组合意义）

等式左边：从n 个元素种取r 个元素做排列有P r n 种，就是等式左边；

等式右边：先从n 个元素中拿出一个元素排在首位，有n 种方法，然后再从剩下的n-1

-1n -1

个元素中取r-1个元素做后面r-1位的排列, 有P r n -1种方法, 按乘法原理, 共有n P r -1种方法。

(b) 方法一

P r n =

n !

=n (n -1) (n -r +2)(n -r +1)

(n -r )!

=(n -r +1) ?n (n -1) [n -(r -1) +1] =(n -r +1)

n !

=(n -r +1) P r n -1

[n -(r -1)]!

方法二（组合意义法）

等式左边：从n 个元素中取r 个元素做r 位排列，有P r n 种方案。

等式右边：先从n 个元素中取r-1个元素做r-1位排列，有P r n 再从剩下的n-r+1-1种方法；个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有(n -r +1) P r n -1

P r n =

n !

=n (n -1) (n -r +2)(n -r +1)

(n -r )! n =(n -1) (n -r +2)(n -r +2)(n -r +1)(n -r ) n -r n n (n -1)! n =(n -1) (n -r +1)[(n -1) -r +1]==P r n -1n -r n -r [(n -1) -r ]!n -r

方法二：（组合意义法）

等式左边：从n 个元素中取r 个元素做r 位排列，其方案数为P r n ；

等式右边：从n 个元素中先取出一个元素放在第一位，有n 种方法，再从剩下的n-1个元素种取出r 个元素放在第2位，?，第r 位，第r+1位，有P r n -1种方法，这样就多了一位，故应除去第r+1位的选取方法，共有n-r 种选法，故总方案为

(d) 方法一

P r n -1。 n -r

P r n +1=

(n +1)!

=(n +1) n (n -r +2) =[(n -r +1) +r ]n (n -r +2)

(n +1-r )!

=n (n -r +2)(n -r +1) +r ?n [n -(r -1) +1] =

n ! r ?n !

+=P r n +rP r n -1

(n -r )! (n -r +1)!

方法二：（组合意义）

等式左边：从n+1个不同的元素中取r 个元素进行r 位排列。其方案为P r n +1；等式右边：(a) 不取某特定元素b ，则r 个元素需从剩下的n 个元素中取，然后做r 位

排列，共有P r n 种方案。

(b) 取定某特定元素b ，则其余r-1个元素需从剩下的n 个元素中取，先做r-1位排列，共有P r n -1种方法，再将特定元素b 插入这r-1个元素形成的r 个空隙中，有r 种方法，故按乘法原理，共有r P r n 种方案。

(e) 方法一（根据(d)可得）

P r n +1=P r n +rP r n -1

-1n

=P r n -1+rP r n -1+rP r -1

-2n -1n =P r n -2+rP r n -1+rP r -1+rP r -1-2n -1n =P r n -2+rP r n -1+rP r -1+rP r -1

1n -1n =P r r +rP r r -1+rP r r -+1+ +rP r -1+rP r -11n -1n =r ! +r (P r r -1+P r r -+1+ +P r -1+P r -1) n -1r +1r =r ! +r (P r n -1+P r -1+ +P r -1+P r -1

方法二：组合意义（同样根据d ）

等式左边：从n+1个不同元素取r 个元素做r 位排列，其方案数为：P r n +1 等式右边：设b 1, b 2, b 3, , b n +1-r 是n-r+1个特定元素。

(a) 不取特定元素b 1, b 2, b 3, , b n +1-r ，剩下的r 个元素做全排列，有P r r =r!种方案。 (b)(1)：取特定元素b 1，但不取特定元素b 2, b 3, , b n +1-r ，于是先在剩下的r 个元素中取r-1个元素做排列，有P r r -1种方法，然后将b 1插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r P r r -1种方案。

(2)：取特定元素b 1，但不取特定元素b 3, , b n +1-r ，于是先在剩下的r+1个元素中取r-1

个元素做排列，有P r r -+1种方法，然后，将b 1插入这r-1个元素的r 个空隙，共有r 种方法，1故按乘法原理，有r P r r -+1种方案。

(n-r)：取特定元素b 1，但不取特定元素b n +1-r ，于是先在剩下的n-1个元素中取r-1个

-1元素做排列，有P r n -1种方法，然后，将b 1插入这r-1个元素的r 个空隙，共有r 种方法，故-1按乘法原理，有r P r n -1种方案。

(n-r+1）：取特定元素b 1，先在剩下的n 个元素中取r-1个元素做排列，有P r n -1种方法，然后，将b 1插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r P r n -1种方案。

最后，按加法原理，共有：

n -1n r ! +r (P r n -1+P r -1+ +P r -1)

1.18 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？

[解] 先将5个球进行全排列，有5! 种方法，再将三个空格插入5个球的6个空隙中，有

C 36

种方法，然后将这些元素的排列一对一的放入8个盒子中，即完成了每盒最多一球，空盒不相邻的放球要求，总方案有：C 3?5! =2400（种）

1.19 n+m位由m 个0，n 个1组成符号串，其中n ?m+1，试问不存在两个1相邻的符号串的数目。

[解]：先将m 个0排成一排，再将n 个1插入m 个0的m+1个空隙（因为n ?m+1,这可实现）, 就得到了无相邻的n+m位0-1符号串，其方案数为

?m +1?

??。 n ??

1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产

生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位. 试问有多少种方案？ [解] 甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2，至多为4。

?10??4??15??10??10??4??15??10??10??4??15??10? 2?? 2?? 3?? 0??+ 3?? 1?? 2?? 1??+ 4?? 0?? 1?? 2??=768600 ????????????????????????

1.21 一个盒子里有7个无区别的白球，5个无区别的黑球. 每次从中随机取走一个球，已知前面取走6个，其中3个是白的. 试问取第6个球是白球的概率. [解] 已知前面取走6个球，有3个白球，则有3个黑球。

故总的取球方案是 ???7?6?5?5?4?3；

?6?

?3?

?5?

第六个球是白球的方案是 2???7?6?5?5?4?3

?5? 2???7?6?5?5?4?31??==0. 5 因此取出第6个球是白球的概率P =

2?6?

??7?6?5?5?4?3 3???

1.22 求下图中从0到P 的路径数：

(a) 路径必须过A 点； (b) 路径必须过道路AB ；

(d) 道路AB 封锁（但A ，B 两点开放）.

[解] O(0,0), A(3,2), B(4,2), P(8,5), C(6,3)

(a) 路分为两段：先从O 到A ，再从A 到P ，则有：

?3+2??8-3+5-2??5??8? ? 2?? 5-2?= 2?? 3??=560????????

(b)路分为三段：先从O 到A ，再从A 到B ；再从A 到B ；然后从B 到P ；

?3+2??8-4+5-2??5??7? ? 2???1? 5-2?= 2?? 3??=350????????

?3+2??6-3+3-2??8-6+5-3??5??4??4?

?? 2??? 3-2?? 5-3?= 2?? 1?? 2??=240????????????

(d) (采用排除法)

从O 到P 的满足不过AB 的路＝从O 到P 的路－从O 到P 经过AB 的路，因此：

?8+5??3+2??8-4+5-2??13? ?- ??1? ?= ?-350=1287-350=937 525-2???????5?

1.23 另s={1,2,3…,n+1},n?2

T ={(x , y , z ) |x , y , z ∈s , x

[证]

?n +1??n +1?

T =∑k 2=+2 +2? ?

23k =1????

T =∑∑∑1=∑(z -1)=∑k 2

z =1y =1x =1

z =1

k =1

n +1z -1z -1n +1n

而(k +1)=k 3+3k 2+3k +1，故k =

(k +1)3-k 3-3k -1 3

[]

n n

1?n 3?1?3?33

k =(k +1) -k -3k -n =n +1-1-n n +1-n ()()∑∑∑∑?3??3?2??k =1k =1k =1?k =1?

11(n +1) 1113

=n (n +1) +(n +1) 3-n (n +1) -(n +1) (n +1)-n (n +1)-

323233

n +1?n +1???11?1?22

= ?+(n +1) (n +1) -n -?= ?+(n +1)(n +2n +1-3n -1)

3??2?3?3?2?=

?n +1?1?n +1?(n +1) n (n -1) ?n +1??n +1?2

= +(n +1)(n -n ) =+2?= ? ??+2 ?222333?2?1????????

1.24 A={(a , b)|a , b∈Z, 0?a ?9,0?b ?5}

(a) 求x-y 平面上以A 作顶点的长方形的数目. (b) 求x-y 平面上以A 作顶点的正方形数目. [解] (a) 先选定横作标，再选定纵坐标，其方案数为：

?10??6?10?96?5 2?? 2??=2?2=675????

(b) 求x －y 平面上以A 作顶点的正方形数目。

按边长分类：

边长为1的正方形：9×5＝45

边长为2的正方形：(9-1)×(5-1)=32 边长为3的正方形：(9-2)×(5-2)=21 边长为4的正方形：(9-3)×(5-3)=12 边长为5的正方形：(9-4)×(5-1)=5

故总的以x －y 平面上A 点作顶点的正方形的数目，按加法原理可得数目为115.

1.25 平面上有15个点P 1, P2, … , P15，其中P 1, P2, P3, P4, P5共线，此外不存在3点共线的.

(a) 求至少过15个点中两点的直线的数目. (b) 求由15个点中3点组成的三角形的数目. [解] (a) (采用排除法)

至少过15个点中两点的直线数目＝在15个点中任选2个点将有一条直线－从P 1～P 5

中选2点构成直线＋P 1～P 5所在的直线l

?15??5?= 2??- 2??+1????=96

(b) (采用排除法)

由15个点中3点组成的三角形的数目＝任在15个点中取3点构成三角形的数目－在5个点P 1～P 5中取3点构成的“三角形”的数目

?15??5?= 3??- 3??????=445

1.26 S={1, 2, … , 1000}，a ，b ∈S ，使ab ≡0 mod 5，求数偶{a, b}的数目.

[解] 因为 ab ≡0m od 5

所以 ab ＝5k （k 是整数）

1?a ?1000, 1?b ?1000

1?ab ?1000000

1?5k ?1000000

1?k ?200000

所以满足 ab ≡0m od 5且1?a,b ?1000的{a,b}的数目为200000

1.27 6位男宾，5位女宾围一圆桌而坐

(a) 女宾不相邻有多少种方案？

(b) 所有女宾在一起有多少种方案？

[解] (a) 先将6位男宾作圆排列有Q 6=5! =120

再将5位女宾插入6个空格，每格一人，共有6×5×4×3×2×1＝720

按乘法原理：有120×720＝86400

(b) 5位女宾在一起，可看作一人，与6位男宾一起，先做圆排列，有Q 7=6!=720 然后5位女宾内部作线排列，有5! ＝120。

所以，总方案为：720×120＝86400

(c)先将6个男宾做圆排列，共有Q 6=120种方法。

再将女宾A 随便插入6个空格中的一个，有6种方法。

然后将剩下的4个女宾插入5个空格中，但每个空格不限人数，故相当于将4个有区别676

?4+5-1?的球放入5个不同的盒子中的放球方案(可重组合) ，共有 4??=5×6×7×8＝1680。??

所以，按乘法原理，有120×6×1680＝1209600种方案。

1.28 k和n 都是正整数，kn 位来宾围着k 张圆桌而坐，试求其方案数.

[解] 先将k ×n 个来宾分成k 堆，每堆n 个人，有

?kn ??(kn )! ?(kn )! n , n , , n (k 堆) ??= n ! ?n ! ? ?n ! ?=(n ! ) k ????

再将每堆n 个人做圆排列，有

故按乘法原理，有 n Q n k [(n -1)! ]＝(n-1)!,共有种方法。

(kn )! (kn )! k [](n -1)! =(n ! ) k n k

1.29 从n 个对象中取r 个作圆排列，求其方案数目. 已知1?r ?n.

[解] 每一个r 个人围成的圈（圆排列）a 1, a 2, , a r -1, a r

?a 1, a 2, , a r -1, a r ??a 2, a 3, a r , a 1?(线排列) ? ???a r , a 1, a r -2, a r -1

即每一个r 圈相当于r 个r 排列。故不同的方案数为N =11n ! P (n , r ) =r r (n -r )!

若不计顺逆方向，则为N =

1.30 试证下列等式 11n ! 。 P (n , r ) =?2r 2r (n -r )!

?n ?n ?n -1?(a ) ?= ?,1≤r ≤n r r -1??r ??

?n ?n -r +1?n ?(b ) ?= ?,1≤r ≤n r ?r ??r -1?

?n ?n ?n -1?(c ) ?= ?,0≤r ≤n ?r ?n -r ?r ?

[证] (a) 方法一

?n ?n ! n (n -1)! n ?n -1?==?= ? ? ?r ?r !(n -r )! r (r -1)! ?[(n -1) -(r -1)]!r ?r -1?

方法二：组合意义法：

一方面，从n 个元素中取出r 个元素，然后再做排列，故按乘法原理，其数目为

?n ? r ???r ! ??

另一方面：先从n 个元素中取出1个元素，排在第一位，再从剩下的n-1个元素中取出r-1个元素，并将这r-1个元素排在第2～r 位，故按乘法原理，其方案数为

?n -1?n r -1???(r -1)! ??

?n ??n -1? ? ??r ! =n ??(r -1)! 这两方面的组合意义相同，故有 ? ??r ??r -1?

因此，有： ??=

(b) 方法一 ?n ??r ?n ?n -1? ?? r -1r ??

?n ?n (n -1) (n -r +2)(n -r +1) ?=r ! ?r ? (n -r +1)?n (n -1) (n -r +2) =n -r +1??n ?= ?r (r -1)! r ?r -1?

方法二：组合意义

一方面：从n 个元素中取出r 个元素来，然后，在做排列，故按乘法原理，其方案数为

?n ? r ???r ! ??

另一方面：先从n 个元素中先取出r-1个元素，将其排排列再第1～r-1位，再从剩下的n-r+1个元素中取出1个元素排在第r 位。故按乘法原理，其方案数为：

?n ? r -1???(r -1)! ?(n -r +1) ??；

这两方面的组合意义相同，故有

?n ??n ? ? ?r ! r -1???(r -1)! ?(n -r +1) r ????＝?

所以，有：

?n ?n -r +1?n ? ? r ??= ?r ???r -1?

?n ?n (n -1) (n -r +1)(n -r )(n -r -1) 1 ?=r !(n -r )(n -r -1) 1?r ?

n (n -1) (n -r +1)(n -r )(n -r -1) 1 =?n -r r !(n -r -1) 1

=n (n -1)! n ?n -1??= ?n -r r !(n -1-r )! n -r ?r ?

方法二：组合意义

一方面，从n 个元素中取出n-r 个元素，然后再做排列，按乘法原理，其方案数为：

?n ??n ? ? (n -r )! = n -r ? r ??(n -r )! ????

另一方面，选从n 个元素中取出1个元素排再第一位，再从剩下的n-1个元素中选取n-r+1个元素，排在第2～n-r 位。故按乘法原理，其方案数为

?n -1??n -1?n ? n -r -1???(n -r -1)! =n ? r ???(n -r -1)! ????

这两方面的组合意义相同，可得：

?n ??n -1? ? (n -r )! =n ? r ? r ???(n -r -1)! ????

?n ?n ?n -1? ?= r ?n -r r ??????

1.31 试证任意r 个相邻数的连乘：

被r ！除尽.

[证] (n +1)(n +2) (n +r ) =(n +1)(n +2) (n +r ) ?n +r ?(n +r )! ?r ! = ?r ! ?r ! n ! ?r ?

?n +r ??由于 r ?是从n+r个元素中选取r 个元素的组合数，故当然是整数，因此，??

?n +r ??(n+1)(n+2)?(n+r)可以整除r! ，其商为组合数 r ?。 ??

1.32 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y 必须夹在两个x 之间，问这样的排列数等于多少？

[解] 由于y 必须乘在两个x 之间，故两个y 只能夹在仅有的三个x 之间，形成图象xyxyx ，形成6个空档。其余的6个元素a,b,c,d,e,y, 只能放在这6个空格处，这相当于将6个不同的小球放入6个不同的盒子中，允许空盒，且盒内还要排列的方案数。故：

?6+6-1?11! ?6! =6! ?=332640 6-1?5! 6! ??

1.33 已知r, n, k 都是正整数，r ?nk ，将r 个无区别的球放在n 个有标志的盒子里，每盒至少k 个球，试问有多少种方案？

[解] 先将nk 个球放入n 个有标志的盒中，每盒k 个球，其方案为1。

再将剩下的r-nk 个球放入这n 个盒中，每盒球数不限，其方案数为

?n +(r -nk ) -1??r -n (k -1) -1? ?? r -nk ?= n -1?????

故总的方案为

?r -n (k -1) -1??r -n (k -1) -1???1? n ?= n -1?????

1.34 在r, s, t, u, v, w, x, y, z的排列中求y 居x 和z 中间的排列数.

[解] 由于y 必须居于x 和z 之间，故形成图象xyz ，形成4个空格。其余r,s,t,u,v,w 这6个元素，只能放在这4个空格处，这相当于将6个不同的小球放入4个不同的盒子中，允许空盒，且盒内还要进行排列的方案数。故有：

?6+4-1?9! ?6! ? =6! =60480 4-1?3! 6! ??

将9个字母进行全排列，有9! 中排列，而x,y,z 这3个字母形成的3! 个排列只看作一种排列xyz ，故有：

9! =60480 3!

1.35 凸十边形的任意三条对角线不共点. 试求这凸十边形的对角线交于多少个点？

[解] 从一个顶点可引出7条线和第一条（从右到左）交

的有1?7，和第二条交的有2?6条, 故和一个顶点引出的7条

线相交的点为： 1?7+2?6+3?5+4?4+5?3+6?2+7?1=84

故和从10点引出的对角线交的点有个84?10=840，但每

个点重复了四次（因为每个点在两条线上，而每条线有两个

端点）。故凸10 边形（这样的）对角线交于

4=故也可为C 10840=210个点, 410?9?8?7=210 4?3?2?1

1.36 试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整数.

[证] “必要性”。若整数n 是另一个整数的平方，则n 一定可写成如下形式：

2αe 2α12α2n =P P P 12e （参见P7例4）

其中P1,P2, ?,Pe 是e 个不同的素数。由于第9题可得，除尽n 的正整数数目为 (2α1+1)(2α2+1)?(2αe+1)为奇数。

“充分性”。若除尽正整数n 的正整数的数目为奇数。则n 一定是某个正整数的平方，否则，n 不是平方数，则n 一定是可分解成如下形式：

β1βe n =P P 2β2 P 1e

其中P1,P2, ?,Pe 是e 个不同的素数，且β1, β2, ?, βe 中至少有一个奇数（否则n 为平方数）。于是(2β1+1)(2β2+1)?(2βe+1)必为偶数，与充分性假设矛盾。

1.37 给出

?n ??r ??n -1??r +1??n -2??r +2??n -m ??r +m ??n +r +1?+++ +??? ??? ??? ???= ? ?m ??0??m -1??1??m -2??2??0??m ??m ?

的组合意义.

[证] 组合意义一：

从(n+r+1)个元素{1,2,?,n+r+1}中取出(n +r +1-m ) 个元素i 1<><>

?n +r +1??n +r +1?

????

r+1,r+2,?,r+1+m。

当i r+1取(r+1+k)时(k=0,1,2,?,m) ，前边r 个数i 1,i 2, ?,i r 可在{1,2,?,r+1+(k-1)}这(r+k)

?r +k ??r +k ?个数里取，故有 r ??= k ??种取法；后边[(n+r+1-m)-(r+1)]=n-m个数i r+2, ?,i n+r+1-m可

????

?n -k ??n -k ?在{r+1+k+1, ?,n+r+1}这[(n+r+1)-(r+1+k)]=n-k个数中取，故有 n -m ??= m -k ??。根据乘

????

?n -k ??r +k ??n -k ??r +k ?法原理，当i r+1=r+1+k时，这样的组合数为 m -k ???1? k ??= m -k ?? k ??。根据加法????????

原理，对k=0,1,2,?,m 作和，就有

?n ??r ??n -1??r +1??n -2??r +2??n -m ??r +m ??n +r +1? ? ? ? ? ? ? +++ + m ? 0? m -1? 1? m -2? 2? 0?? m ??= m ????????????????????。

注：参见《 Combinatorial Problems and Exercise》 by L.Lovasz 0143.7 L896c

P 18-42 (i) P 96 P 172

(i)The number of those(n+r+1-m)-tuples of{1,2,?,n+r+1}Whose st (r +1) element is r+k+1is ?r +k ??n -k ? k ?? m -k ??. Summing for k=0,1,2,?,m,we ????

get the result. 组合意义二：（格路方法）

等式左端：从点A(-r-1,0)到点

C(-1,k)(k=0,1,2,?,m) 直接经过点D(0,k)再到

点B(n-m,m)的路径数(参见本题图1) ；

等式右端：从点A(-r-1,0)到点B(n-m,m)

的路径数。 ?r ??r +1??r +2??n ??n +1?1.38 给出 ?+ ?+ ?+ + ?= ?的组合意义. r r r r r +1??????????

[证]. 组合意义一：

等式右端是从n+r+1个元素a 1, a 2, , a n +1中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P 25等式3的组合意义) ：

(1) r+1个元素的组合中含有a 1

的，相当于从n 个元素a 2, a 3, , a n +1

?n ?中取r 个组合，其组合数为（即A ）。 r ????

(2)r+1个元素的组合中不含有

a 1，但又含有元素a 2的。即一个(r-1)-第16题图1

组合。依a 1来分，不外乎含a 1和不含a 1；不含a 1的又依a 2分，不外乎含a 2和不含a 2。不含a 1而含a 2的组合，相当于从n-1个元素a 2, a 3, , a n +1中取r 个元素的组合，然后加上a

?n -1?而成，其组合数为 r ??即A 1 A 2。 ??()

(3)r+1个元素的组合中不含a 1和a 2，但含有元素a 3的。即不含a 1, a 2的依a 3来分，不外乎含a 3和不含a 3。不含a 1, a 2而含a 3的组合，相当于从n-2个元素a 4, , a n +1中取出r 个元素的组合，然后再加上a 3而成，其组合数为 ?n -2???即A 1 A 2 A 3。 r ??()

取出的r+1个组合元素中不含a 1, a 2, a 3, , a n -r -1，但含有元素a n -r 的。即不含a 1, a 2, a 3, , a n -r -1的，又依a n -r 来分，不外乎含有a n -r 和不含有a n -r 。不含a 1, a 2, , a n -r -1而含a n -r 的组合，相当于从n-(n-r-1)=r+1个元素a n -r , a n -r -1, , a n +1中取出r 个元素的组合

?r +1?而加上a n -r 而成，其组合数为 r ??(即A 1 A 2 A n -r -1 A n -r ) 。 ??

?r +1??r ?(4)由a n -r +1, a n -r +2, , a n +1组成的(r+1)-组合的组合数为 r +1??= r ?? ????

(即A 1 A 2 A n -r ) 。而且

A 1 (A 1 A 2) (A 1 A 2 A 3) (A 1 A 2 A n -r -1 A n -r )

(A 1 A 2 A n -r -1 A n -r ) =X(即全集)

组合意义二：

等式右端：从n+1个不同元素a 1,a 2, ?,a n ,a n+1, 中任选r+1个元素的组合方案数；等式左端：从n+1个不同元素a 1,a 2, ?,a n ,a n+1, 中选取r+1个元素，一定选元素a r+k+1(k=0,1,2,?,n-r) ，但是不选元素a r+k+2, ?,a n ,a n+1的组合方案数。

1.39 证明

?m ??m ??m ??m -1??m ??m -n ?n ?m ? ???+ ???+ + ???=2 ? 0n 1n -1n 0?????????????n ?

?m ??m -r ??m ??n ?[证]. 借助P 28等式4，可知： r ?? n -r ??= n ?? r ?? (n≥r) (r=0,1,2,?,n)

????????

?m ??m ??m ??m -1??m ??m -n ??m ??n ??m ??n ??m ??n ?? ? ? ? ? ? ? ? ? ? ++ +=++ +从而有 0? n ? 1? n -1? n ? 0? n ? 0? n ? 1? n ?? n ?? ????????????????????????

?m ???n ??n ??n ??n ?m ?? ? ? ? = ++ +=2 n ?? 0? 1? n ?? n ??(用了P 29等式5)

????????????

组合意义一：

等式右端可看作从m 个元素中取出n 个元素进行组合。然后对这取出的n 个元素进行

?m ?n 染色（红，白）的所有方案，它为 n ??2；

?m ?等式左端可看作先从m 个元素中取出k 个元素（个数为，全部染以红色。再从剩 k ??）

?m -k ?下的(m-k)个元素中取出(n-k)个元素（个数为，全部染以白色。根据乘法原理，从 n -k ??）

?m ??m -k ?m 个元素中取出n 个元素，k 个染上红色，(n-k)个染上白色的方案数为 k ?? n -k ??，

????

k=0,1,2,?,n ；

而从m 个元素中取出n 个元素染以红白两色的方案可分解成有0个，1个，?，n 个染以红色的总和。故根据加法原理，17题成立。

组合意义二：

等式右端：将从m 个不同的小球中任意选出的n 个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数；

等式左端：先从m 个球中任选k 个球放入第一个合子里(k=0,1,2,?,n) ，再从剩下的m-k 个球中任选n-k 个球放入第二个合子里，然后对k 从0到n 求和，就得到了所有可能的放球方案数。

1.40 从n 个人中选r 个围成一个圆圈，问有多少种不同的方案？

?a 1, a 2, , a r -1, a r ??a 2, a 3, a r , a 1[解]. 每一个r 个人围成的圈（圆排列）a 1, a 2, , a r -1, a r ?(线排列) ? ???a r , a 1, a r -2, a r -1

即每一个r 圈相当于r 个r 排列。故不同的方案数为N =11n ! P (n , r ) =r r (n -r )!

若不计顺逆方向，则为N =11n ! 。 P (n , r ) =?2r 2r (n -r )!

1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法.

[解]. （略）

1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.

(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法.

[解]. （略）

1.43 对于给定的正整数n ，证明，当

?n -1n +1或，若n 是奇数??22k =?时，C(n,k)的最大值.

?n ，若n 是偶数??2

[证] 取C (n,k)与C (n,k-1)进行比较。C (n,k)/C (n,k-1)=(n-k+1)/k。

当k 1，即C (n,k)>C (n,k-1)；

当k >n/2时，(n-k+1)/k<1，即c>

因此，得到当k=n/2或最接近n/2时，C (n,k)取得最大值。

1.44 (a) 用组合方法证明(2n )! (3n )! 和都是整数. n n n 22?3

(n 2)! (b) 证明是整数. (n !) n +1

[证] (a)考虑2n 个不同的球放入n 个不同的合子里，每合两个的方案数。这个方案数应该是整数。

对2n 个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n 个合子内部的排列共重复计算了2n 次，故总的重复因子是2n 。因此，把2n 个不

(2n )! (2n )! 同的球放入n 个不同的合子里，每合两个的方案数是n 。所以，n 是整数。 22

同理，考虑3n 个不同的球放入n 个不同的合子里，每合3个的方案数。这个方案数应该是整数。

对3n 个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=2?3。n 个合子内部的排列共重复计算了2n ?3n 次，故总的重复因子是2n ?3n 。因此，

(3n )! (3n )! 把3n 个不同的球放入n 个不同的合子里，每合3个的方案数是n n 。所以，n n 是整2?32?3

数。

(b)考虑n 2个不同的球放入n 个相同的合子里，每合n 个的方案数。这个方案数应该是整数。

对n 2个球进行排列的方案数为(n2)! 。而把n 个球放入同一个合子里不计顺序，重复因子是n! 。n 个合子内部的排列共重复计算了(n!)n 次，故重复因子是(n!)n 。另外，由于n 个合子相同，放入不同的合子是没有区别的，其重复因子是n! 。故此，总的重复因子是(n!)n+1。

(n 2)! (n 2)! 因此，把n 个不同的球放入n 个相同的合子里，每合n 个的方案数是。n +1(n ! ) n +1(n ! ) 2

是整数。

1.45 (a) 在2n 个球中，有n 个相同. 求从这2n 个球中选取n 个的方案数.

(b) 在3n+1个球中，有n 个相同. 求从这3n+1个球中选取n 个的方案数.

[解] (a)相当于从n 个不同的小球中取出m 个小球(0≤m ≤n), 再从n 个相同的小球中取出n-m 个小球，m=0,1,2,?,n 的方案数。

根据加法原理，这个方案数应该是：C (n,0)+ C(n,1)+?+ C(n,n)=2n 。

同理，考虑3n 个不同的球放入n 个不同的合子里，每合3个的方案数。这个方案数应该是整数。

(b)相当于从2n+1个不同的小球中取出m 个小球(0≤m ≤n), 再从n 个相同的小球中取出

n-m 个小球，m=0,1,2,?,n 的方案数。

根据加法原理，这个方案数应该是：C (2n+1,0)+ C(2n+1,1)+?+ C(2n+1,n)。

1.46 证明在由字母表{0, 1, 2}生成的长度为n 的字符串中

(a) 0出现偶数次的字符串有3n +1个； 2

?n ?n ?n ?n -2?n ?n -q 3n +1?n ?=, 其中q =2?? (b) ?2+ ?2+ + ?22?2??0??2??q ?

[证] (a)方法一：采用（串值）数学归纳法

31+1［基始］当n=1时，0出现偶数次，长度为1的字符串有=2个（即1和2两个2

长度为1的字符串）。所证结论成立；

［归纳假设］当n=m(1≤m ≤k) 时，假设所证结论成立。即，0出现偶数次，长度为m 的3m +1字符串有个； 2

［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：

(1)给0出现偶数次，长度为k 的字符串后面再增加一位不是0的数（只能是1或2），3k +1因此，按乘法原理，由归纳假设，此种字符串有?2=3k +1个； 2

(2)给0出现奇数次，长度为k 的字符串后面再增加一位是0的数，因此，按乘法原理，?k 3k +1?3k -1由归纳假设，此种字符串有 3-2???1=2个；

所以，按加法原理，0出现偶数次，长度为k+1的字符串共有

3k -13k +1+1(3+1)+= 个。所证结论成立；归纳完毕。 22k 方法二：采用指数型母函数方法

设：a n —0出现偶数次，长度为n 的字符串的个数，则{an }的指数型母函数

x n

A (x ) =∑a n ?n ! n =0∞

x 2x 4x 6x x 2x 3

=(1++++ )(1++++ ) 2! 4! 6! 1! 2! 3!

e x +e -x

2x =?e 2 3x x e +e =2

13x (3x ) 2(3x ) 3x x 2x 3

=[(1++++ ) +(1++++ )]21! 2! 3! 1! 2! 3!

1(3+1) x (32+1) x 2(33+1) x 3

=[(1+1) ++++ ]21! 2! 3!

3n +1所以，a n =（规定a 0=1）。 2

(b)利用组合意义法来证

3n +1考虑0出现偶数次，长度为n 的字符串的个数。根据上面(a)，已证其个数为； 2

?n ?另一方面，相当于先从n 个位置中选取2m (0≤2m ≤n ) 个（有 2m ??种选择）放置上数

?n ?n -2m 0, 再在剩下的n-2m 个位置上放置数1或2（有2n-2m 种放法），按乘法原理，是 2m ??2??

?n ?个，m=0,1,2,?,q (q =2??) 的方案数。 ?2?

?n ?n ?n ?n -2?n ?n -q ? ? 按加法原理，此方案数为 2+2+ + 0? 2? q ??2。因此，我们有 ??????

?n ?n ?n ?n -2?n ?n -q 3n +1 0??2+ 2??2+ + q ??2=2。 ??????

1.47 5台教学机器m 个学生使用. 使用第1台和第2台的人数相等，有多少种分配方案？

[解] 先从m 个学生中选取k 个使用第1台机器，再从剩下的m-k 个学生中选取k 个使用第2台机器，其余m-2k 个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C (m,k)

?m ?C (m -k , k ) ?3(m -2k ) 。这里k=0,1,2,?,q (q =??) ，于是，按加法原理，共有 ?2?

∑C (m , k ) C (m -k , k ) ?3

k =0q (m -2k ) 种使用方案。 1.48 在由n 个0及n 个1构成的字符串中，在任意前

k 个字符中，0的个数不少于1的个数的字符串有多

少？

[解] 转化为格路问题（弱领先条件—参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对角线。它可看作是从(0,1)到(n,n+1)

的强领先条件（只能从对角线上方走，但不可以碰到

对角线）的格路问题。更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一步必到(0,1)格点) 。故这样的字符串有

?n -0+(n +1) -1??n -1+(n +1) -0? ?- ?=C (2n , n ) -C (2n , n -1) n n -1????

1.49 在1到n 的自然数中选取不同且互不相邻的k 个数，有多少种选取方案？

[解] 设：g (n,k)为从1~n中选取不同且互不相邻的k 个数的方案数。

于是，按这k 个数中有无数n 而分为两种情况：(1)若选n ，则必不能选n-1，故此种方

案数为g (n-2,k-1)；(2)若不选n ，则可以选n-1，故此种方案数为g (n-1,k)；所以，按加法原理，总的方案数g (n,k)=g (n-2,k-1)+g (n-1,k)。

且只有当n ≥2k-1时，g (n,k)>0；否则g (n,k)=0。因此，可给定初始值：

g (2k-1,k)=1，g (2k-2,k)=0。

1.50 (a) 在由5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？

(b) 在m 个0，n 个1组成的字符串中，出现01或10的总次数为k 的字符串，有多少个？

[解] (a)先将5个0排成一列：00000，一个1若插在两个0中间，就形成一个“010”，则同时出现“01”和“10”，计数为2；若插在两端，则仅出现一个01”或“10”，计数为1。

现在要出现01”或“10”的总次数为4，可有两种办法：

(1)先把两个1插入五个0所形成的四个空档内，再将剩下的两个1放在已插入的1的前面，比如：011100100。按乘法原理，有C (4,2)?C (2+2-1,2)= C(4,2)?C (3,2)种方案；

(2)先把一个1插入五个0所形成的四个空档内，然后取两个1分别插入两端，剩下的一个1放在已插入的1的前面，比如：100011001。按乘法原理，有C (4,1)?3种方案；

最后，按加法原理，总的方案数为C (4,2)?C (3,2)+C (4,1)?3=30。

k -1个1插入m 个0所形成的m-1个空档内，2

k +1k +1然后取一个1插入头或尾，最后将剩下的n -个1放在已插入的个1的前面，形22

成出现k 个01或10的格局。按乘法原理，总的方案数为 (b)若k 为奇数，则只有一种办法：先把

2?C (m -1, k -1k +1k +1k +1k -1k +1) C (n -+-1, n -) =2?C (m -1, ) C (n -1, n -) ； 222222

k k 个1插入m 个0所形成的m-1个空档内，再将剩下n -的个1放在已插入22若k 为偶数，则现在可有两种办法： (1)先把

的k 个1的前面，形成出现k 个01或10的格局。按乘法原理，有 2

k k k k k k C (m -1, ) C (n -+-1, n -) =C (m -1, ) C (n -1, n -) 种方案； 222222

k -2个1插入m 个0所形成的m-1个空档内，然后取两个1分别插入两端，2

k +2k +2再将剩下的n -个1放在已插入的个1的前面，形成出现k 个01或10的格局。22

按乘法原理，有 (2)先把

C (m -1, k -2k +2k +2k +2k -2k +2) C (n -+-1, n -) =C (m -1, ) C (n -1, n -) 222222种方案；

最后，按加法原理，总的方案数为

k k k -2k +2C (m -1, ) C (n -1, n -) +C (m -1, ) C (n -1, n -) 。 2222

1.51 从N={1, 2, … , 20}中选出3个数，使得没有两个数相邻，有多少种方案？

[解] 方法一（采用排除法）

在20个数中选取3个数都不相邻的方案数；

从1～20这20个数中选取3个数，总数为 ?20?? ??3?

然后在其中去掉有3个数相邻的方案数，也要去掉有两个数相邻的方案数。这样，就是在20个数中选取3个数都不相邻的方案数。

设选取的3个数a 1，a 2，a 3。

如果这三个数相邻，若a 1?a 2?a 3，则1?a 1?18。故此种方案有18个。

如果有两个数相邻，不妨设是a 1a 2，且a 1?a 2，则1?a 1?19，但是，当a 1＝1或19时，a 2＝2或20，a 3只有3和18不能选，故a 3有3个数不能选，17种选择方案；当a 1≠1或19时，a 3有4个数不能选。故a 3有16种选择，因此，此种方案数为：

2×17＋17×16

故此，从1～20这20个数种选取3个互不相邻的数的方案数为：

?20? 3??-18-(2?17+17?16) =816 ??

方法二（采用一一对应技术）

设：A:从1～20这20个数中选取三个数a 1，a 2，a 3，使得无两数相邻的方案集。 B ：从1～18这18个数中选取三个数b 1，b 2，b 3，使得三数可相邻的方案集。

这里，a 1

设：b 1

建立双射函数h ：A →B ，使得：

h(a 1, a 2, a 3)=(b 1, b 2, b 3)

?b 1=a 1??b 2=a 2-1

?b =a -23?3

其有逆函数h :B→A, -1

h -1（b 1，b 2，b 3）＝（a 1，a 2，a 3）

?a 1=b 1??a 2=b 2+1

?a =b +23?3

故此，根据一一对应技术，有A =B = 3??=816 ??

1.52 从N={1, 2, … , n}中选出k 个数，使之没有两数相邻，求不同方案数.

[解] （采用一一对应技术）

设：A ：从1～n 这n 个数中选取k 个数a 1，a 2，?，?18?a k ，使之无二数相邻的方案集。 B ：从1～n-k+1这n-k+1个数中选取k 个数b 1，b 2，?，

这里：①

②b k ，二数可相邻的方案集。 a 1

建立双射函数：h ：A →B

h(a 1, a 2, ?, a k )=(b 1, b 2, ?, b k )

?b 1=a 1?b =a -1?22??

??b k =a k -(k -1)

其逆函数为：h :B→A

?b 1=a 1?b =a -1?22??

??a k =b k +(k -1) -1

故此，根据一一对应技术，有：

?n -k +1??A =B = k ???

1.53 把n 个无区别的球放进有标志1, 2, … , n的n 个盒子中，每个盒子可放多于一个球，求有多少种方案？

[解] （采用一一对应技术）

设：A ：将n 个无区别的球放进n 个有区别的盒子中，每盒球数不限的方案集。

B ：n 个“*”，n-1个隔档“1”构成的线性图案集。

于是一种放球方案与一种图案一一对应，根据一一对应技术，有

A =B =(2n -1)! ?2n -1??= ?n -1n ! (n -1)! ??

1.54 m个1，n 个0进行排列，求1不相邻的排列数. 设n>m.

[解] n个0有n+1个空隙（内外都计），选取m 个空隙（可以选取，因为m<>

?n +1? m ???? m 个1 ，每空插入一个1，使得后两个1相邻。故其方案数为：

1.55 偶数位的对称数，即从左向右读法与从右向左的读法相同，如3223. 试证这样的数可被11整除.

[证] 此种偶数位得对称数《形式语言》称为迴文。

设任一个这样得数m 有2n 位，故有：

m =a 1?102n -1+a 2?102n -2+ +a n ?10n +a n ?10n -1+ +a 2?10+a 1

=a 1(102n -1+1) +a 2(102n -2+10) + +a n (10n +10n -1)

=a 1(102n -1+1) +a 2?10?(102n -3+1) + +a n ?10n -1?(10+1)

由于10+1=(10+1)(10k k -1 -10k -2+ +(-1)k -1) （当k 是奇数时），故10k +1可被11整除。

1.56 n个男人与n 个女人沿一圆桌坐下，问两个女人之间坐一个男人的方案数. 又m 个女人n 个男人，且m<>

[解] ○1先将n 个女人进行圆排列，共有Q n =(n-1)! 种方法，再将n 个男人插入n 个女人形成得n 个空位中，则有n! 种方法。故按乘法原理，此种方案数为(n-1)!×n! 个。

n 2先将n 个男人进行圆排列，共有Q n =(n-1)! 种方法，再将m 个女人插入n 个男人形○n

成得n 个空位中。则有P (n , m )=n ! n ! (n -1)! ? 。按乘法原理，此种排法有(n -m )! (n -m )!

1.57 n个人分别沿着两圆桌坐下，一张r 个人，另一张n-r 个人，试问有多少种不同的方案？

?n ? r ??r Q ??r [解] 先从n 个人中选取r 个人，有种选法，然后将r 个人排成一圆桌，有=(r-1)!种

方法，再将其余(n-r)个人排成一圆桌n -r Q n -r =(n-r-1)!种方法，故共有

n ! n ! ?n ?(r -1)! (n -r -1)! = ?(r-1)!(n-r-1)!= ×× r ?r ! (n -r )! r (n -r ) ??

1.58 一圆周上n 个点标以1, 2, …, n. 每一点与其他n-1个点连以直线，试问这些直线交于圆内有多少点？

[解] 每4个点形成矩形，其对角线有一个交点，故圆内交点有：

C (n , 4) =

n (n -1)(n -2)(n -3) 1=n (n -1)(n -2)(n -3) 4?3?2?124

范文五：[考试]组合数学第四版卢开澄标准答案-第四章

习题四

m4.1. 若群G的元素a均可表示为某一元素x的幂，即a= x，则称这个群为循环群。若群的

元素交换律成立，即a , b G满足

a b = b a

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

[证].设循环群(G, )的生成元是x,G 。于是，对任何元素a , b G，,m，n,N，使得0mna= x , b= x ,从而 00 m n a b = x x00 m +n = x(指数律)0n +m = x(数的加法交换律) 0n m = x x (指数律) 00

= b a

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

m4.2. 若x是群G的一个元素，存在一个最小的正整数m，使x=e，则称m为x的阶，试证: 2m-1 C={e,x,x, ,x}

是G的一个子群。

[证].(1)非空性C :因为,e,G; 2m-1m(2)包含性C G:因为x ,G，根据群G的封闭性，可知x, ,x, (x=)e,G，故C

(3)封闭性,a , b C a b C:, a , b C，,k，l,N (0 k< m)="" ;="" -1k(4)有逆元,a="" c="" a="" c:,="" a="" c，,k="" ,n="" (0="">< m)="" 。="">

综合(1) (2) (3) (4)，可知(C, )是(G, )的一个子群。

4.3. 若G是阶为n的有限群，则G的所有元素的阶都不超过n。 2m-1[证].对任一元素x,G，设其阶为m，并令C={e,x,x, ,x}，则由习题4.2.可知(C, )是(G,

)的一个子群，故具有包含性C G。因此有

m = |C| , | G | = n

所以群G的所有元素的阶都不超过n。

4.4. 若G是阶为n的循环群，求群G的母元素的数目，即G的元素可以表示成a的幂: 2n a,a, ,a

的元素a的数目。

[证].设(G, )是循环群，a是其一个母元素(生成元)，a的阶为n(也是G的阶)，则 2nG ={a,a, ,a(=e) }。 r(1).我们来证:对任何自然数r ,N (0<>

k 。已知0<>

其次， rn r n (a)= a(指数律)n r = a(数的加法交换律)

nr =(a)(指数律) r = e = e 。r因而，由k是元素a的阶，具有最小性，所以k n。

综合这两方面，可得k = n。

(2).根据(1)的结论，可得，群G的母元素的数目为 (n) (欧拉函数，小于n且与n互素

的数的个数)。

k m注.引理*.设(G, )是群。,x,G，若x的阶为k，从而x=e 。则 ,m,N, x,e , k | m 。 [证].先证,): m 若x,e，则必有k | m 。

否则k ? m ，于是，由带余除法，可设 m=kq+r (0, r, k)，故可得 r=m-kq，从而 rm-kq x,x m+(-kq) ,x mk-q ,x (x) (指数律) -qmk ,e e (x,e, x=e)

,e e

故与x的阶为k，具有最小性，矛盾。

次证,):

若k | m，则m = kq。于是 m kq x, x kq ,(x) (指数律) qk ,e (x=e )

=e 。

4.5. 试证循环群G的子群仍是循环群。 [证].设(H, )是循环群(G, )=的一个子群，则H中的元素都可表示成a的一些正方幂。mm设a是H中指数最小的正方幂，我们来证(H, )=。为此只要证明H中任一元素都可m表示成a的正方幂即可。

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

k=qm+r 且 0 r

4.6. 若H是G的子群，x和y是G的元素，试证xH yH或为空，或xH = yH。

[证].对任何x,y,G，若xH , yH=,，则问题已证。

否则若xH , yH,,，则必至少有一元素x,xH , yH，从而 0

x, xH , yH 0

, x, xH , x, yH 00

, x=x h , x =y h (这里h, h,H) 010212

, x h = y h 12-1–1 , x = y h h , y = x h h (*) 2112

下面我们来证:xH = yH。为此，要分证:

(1)xH , yH ;

(2)yH , xH ;

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

对任何元素a，

a, xH

, a =x h, (这里h,,H) -1-1 , a = y h h h, (由(*):x = y h h ) 2121-1 , a =y h,, (由H的封闭性 : h,,= h h h,,H)21

, 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(h)= f(h) 12

, x h = x h 12

, h = h (群的消去律 )。 12

所以，f是从H到的双射，因此 |xH|=|H|=k 。

4.8.有限群G的阶为n，H是G的子群，则H的阶必除尽G的阶。

[证].这即是著名的拉格郎日(Lagrange法国著名数学家、力学家1736-1814)定理。

设G的子群H,{e,h,h,？,h}。 r,112

a,G于是令，这里，并且我们定义R是G上aH,{a,e,a,a,h,a,h,？,a,h}12r,1

R,G，G的二元关系，即

,，。 x,y,GxRy::,(，b,G)(x,aH,y,aH)

从而R是G上的等价关系，其等价块的形式为aH，设其代表元为，则a,a,？,a12k

是所有的等价块，构成对G的一个划分(参见习题4.6.)。即aH,aH,？,aH12k

，，，G,aH，aH，？，aH 12k

aH,aH,？,aH,H,r根据习题4.7.可得。 12k

G,kH,kr,n因此，所以r必能整除n，即H的阶必除尽G的阶。

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

|E| = |E| 。 xy

[证].设底基X={1,2, ,n}。对任一个元素a,X，E={b,X | ,p,G , (a)p=b}。a

因为已知x和y在群G作用下属于同一等价类，因此，存在z,X，使得x, y,E，于是z

,p, p,G , 使得 (z)p=x, (z)p=y 。 1212

我们来证:E= E 。为此，要分证: x y

(1) E , E ; xy

(2) E , E; yx

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

对任何元素a,X，

a, E x

, a = (x)p, (这里p,,G)

, a = (z)pp, (由 (z)p=x ) 11-1-1 , a = (y)ppp, (由(z)p=y , 得 (y)p=z (群G有逆元))2122

-1, a = (y) p,, (由群G的封闭性 : p,,= ppp,,G) 21

, a, E y

所以 E , E。 xy

所以，由包含关系的反对称性，我们得到 E= E。 x y

所以得证 |E| = |E| 。 xy

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

其余染蓝色，问有多少种着色方案,

[解]. 一个3 3的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:

不动0:: P=(1)(2)(3)(4)(5)(6)(7)(8)(9)2 1 13

逆时针旋转90:: P=(5)(1793)(2486) 24 5 6 顺时针旋转90:: P=(5)(1397)(26 84) 3

7 8 9 旋转180:: P=(5)(19)(28)(37)(46) 4

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

第4.11题表

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

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

19442224[(b+r)+2(b+r)(b+r)+(b+r)(b+r)] P(b,r)=472其中br的系数即为所求染色方案数:

94,,,,1,,,, [，2,0，],,,,214,,,,

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个置换没有不动点(因为没有两个坐位坐同一人)，即

c(e)= c(P)= n!，c(P)= c(P)=…= c(P)=0。 111121312n

故由Burnside引理有

l=[c(e)]/2n =n!/ 2n =(n-1)!/2 1

个方案。

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

合作为相同处理。

[解]. 见第4.13题图，使之重合的刚体运动群，它含有1y z 关于正六角形中心轴旋转?60:，?120:，180:的置换，绕o过2个对角的轴翻转180的置换，以及绕过2个对凹的26 o轴翻转180的置换: xx

5 3

yz4

不动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)。

第4.13题表

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

1612343 l=[5，2,5，2,5，5，3,5，3,5] 12

1(15625，10，50，125，1875，375)= 12

1= 18060 12

=1505(种) 。

4.25. 若G和G 是两个群

G G ?{(g,g )|g G , g G },

(g,g ) (g,g )?(gg,g g ), 11221212

G G 的单位元素是(e,e )。试证G G 成群。

[证]. 1 封闭性:,(g,g ) , (g,g ) G G 1122

( g , g G) (g , g G ) 1212

( gg G) (g g G ) (群G和G 的封闭性)1 212

(gg,g g ) G G 1212

(g,g ) (g,g ) G G 1122

因而封闭性成立。

2 结合律:,(g,g ) , (g,g ) , (g,g ) G G 112233

((g,g )(g,g ))(g,g ) 112233

=(gg,g g )(g,g ) 121233

=((gg)g,(g g )g ) 123123

=(g(gg),g (g g )) (群G和G 的结合律) 123123

=(g,g )(gg,g g ) 112323

=(g,g )((g,g )(g,g )) 112233

因而结合律成立。

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 ) -1-1 ( g G) (g G ) (群G和G 有逆元) -1-1 (g, g ) G G -1-1-1-1 使得 (g , g )(g, g ) = (gg , g g ) -1-1 = (e,e ) (gg= e，g g = e ) -1-1-1-1 = (gg , g g ) (gg = e，g g = e ) -1-1 = (g, g )(g , g )

因而有逆元。

所以G G 构成群。

4.26. 若G是关于X={x, x, , x}的置换群，G 是关于X ={x , x , , x }的12n12m

置换群，对于G G 的每一对元素

g(v),v,X, (g,g )(v)? ,,,g(v),v,X,

证G G 是关于X X 的置换群。 [证].将题中G G 中的置换的前置定义换为如下等价的后置定义:

(v)g,v,X,(v)(g,g )?。 ,,,(v)g,v,X,

因而G G ={(g,g )|g G , g G }。

上的二元“乘法”运算如下: 于是，我们可定义G G

(g,g ) (g,g )?(gg,g g )。 11221212

由于置换群G和G 也是群，故根据习题4.25.，可知G G 是群。又由于G G

是X X 上置换的集合，所以G G 是关于X X 的置换群。

4.27. 一个项链由7颗珠子装饰而成的，其中两颗珠子是红的，3颗是蓝的，其余两颗是绿

的，问有多少种装饰方案,试列举之, ,1e 3d [解]. 见第4.27题图，使之重合的刚体运动群，令 =，5172

12,,cf ,,360,,360它含有关于圆环中心轴旋转=? ，=?2 77

6 3 o 3,,,360 ，=?3 ，以及绕过一个顶点及其对弧中点的轴7g b o翻转180的置换: 4 5 a 不动0::(1)(2)(3)(4)(5)(6)(7)

旋转? :(1 2 3 4 5 6 7)，(7 6 5 4 3 2 1)第4.27题图1

旋转?2 :(1 3 5 7 2 4 6)，(7 5 3 1 6 4 2)

旋转?3 :(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)。

转动群格式置换循环节 7(1) 不动 0: 1个 7个 1(7) 旋转 ? 2个 1个 1(7) 旋转 ?2 2个 1个

1 (7)旋转 ?3 2个 1个 13(1)(2) 翻转(点-弧) 180: 7个 4个

第4.27题表

将2颗r色,2颗g色,3颗b色的珠子装饰在圆环的7个等分点上的问题，相当于用b，g， r三种颜色对正七边型进行染色。

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

17777112223P(b,g,r)=[(b+g+r)+6(b+g+r)+7(b+g+r)(b+g+r)] 14322其中bgr的系数即为所求项链串珠方案数:

73,,,,1 ,,,,[，6,0，7,1,],,,,32211114,,,,

17!3!= [，7]143!2!2!1!1!1!

1=[210，42] 14

1=,252 14

=18(种)。

所求18种项链串珠方案枚举如下:

第4.27题图2

4.28.一个正八面体,用红、蓝两色对6个顶点进行着色;用黄、绿两种颜色对8个面进行染

中心的三角形,由此构成的6个顶点, 8个面的几何图形。 [解].(参见第二版第17题)本题相当于把正八面体的6个顶点、8个面合并起来作为目标集;6个顶点、8个面,共14个元素的置换群。

转动群格式置换循环节 68(1)-(1) 不动 0: 1个 14个 212(1)(4)-(4) 面心-面 ?90: 6个 5个 224 (1)(2)-(2) 面心-面心 180: 3个 8个 222 (3)-(1) (3) 顶点-顶点 ?120: 8个 6个 1 34 (2)-(2) 1 棱中-棱中 180: 6个 7个

第17题图

A E

1 1 1

D 5 (3) (3) (3) 5 (4) (4) (4) (7) (7) (7) (2) (2) (2) 2 4 2 4 (8) 2 4 (8) (8) (1) (1) 3 3 (6) 3 (6) (6) C (5) (5)

6 6 6

F B 第4.28题图

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

16824414422222224P(r,b,y,g)=[(r+b)(y+g)+6(r+b)(r+b)(y+g)+3(r+b)(r+b)(y+g) 243322332223224+8(r+b)(y+g)(y+g)+6(r+b)(y+g)] 4244其中rbyg的系数即为所求项链串珠方案数:

68222222434,,,,,,,,,,,,,,,,,,,,,,1 ,,,,,,,,,,,,,,,,,,,,,,[，6,,1,，3,(，),，8,0，6,],,,,,,,,,,,,,,,,,,,,,,2421012021224,,,,,,,,,,,,,,,,,,,,,,

1=[15，70，6，2，3，(2，1)，6，6，3，6] 24

1= [1050，12，54，108]24

1=,1224 24

=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) 。

转载请注明出处范文大全网 » 组合数学第四版答案前八章