组合数学作业答案解析

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

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

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

a1,a2,,a37和a113,a213,,a3713都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a3760，a371373。a1,a2,,a37,

a113,a213,,a3713是1和73之间的74个整数，由鸽巢原理知道，它们中存在相

同的整数，有ai和aj13使得aiaj13，aiaj13，从第j1天到第i天她恰好学习了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。

① 考虑8位整数。最高位不能为0，因此8位整数有7P(7,7)个。 ② 考虑7位整数。最高位不能为0，因此8位整数有7P(7,6)个。 ③ 考虑6位整数。最高位不能为0，因此8位整数有7P(7,5)个。 ④ 考虑5位整数。最高位不能为0，因此8位整数有7P(7,4)个。

⑤ 考虑4位整数。若千位数字大于5，有3P(7,3)个。若千位数字等于5，则百位数字必须大于等于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)94830

8. 15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A的右侧，又有多少种围坐方式？

解 15人围坐一个圆桌，有14!种围坐方式。若B固定坐在A的左侧，则可将BA看作一个整体，有13!种围坐方式。若B固定坐在A的右侧，则可将AB看作一个整体，有13!种围坐方式。因此，B不挨着A坐的围坐方式有14!213!1213!种，B不坐在A的右侧的围坐方式有14!13!1313!种。

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

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

若甲和乙均不入选，组队方法数为74。

若甲和乙均入选，组队方法数为72+6858585853+54。 85854。 若甲入选且乙不入选，组队方法数为73+68585若乙入选且甲不入选，组队方法数也为73+64。

因此，组队方法数总共为

858585858585++++2364747263547=1120

21. 一位秘书在距离家以东9个街区、以北7个街区的一座大楼里工作。每天他都要步行

16个街区去上班。

(a) 对他来说可能有多少不同的路线？ (b) 如果在他家以东4个街区、以北3个街区开始向东方向的街区在水下（而他又不会游泳），则有多少条不同的路线？

解 (a) 用E表示向东步行1个街区，用N表示向北步行1个街区。因为该秘书需要向东步行9个街区，向北步行7个街区，总共步行16个街区，因此他的上班路线是多重集

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

16!11440。 9!7!(b) 若他从水下的街区走过，则他先要走到离家以东4个街区、以北3个街区的地方，再

向东走一个街区，最后走到工作的大楼。他从家走到离家以东4个街区、以北3个街区的地方的路线的数目是多重集{4E,3N}的排列数，即

7!35。他从离家以东5个街区、4!3!以北3个街区的地方走到工作的大楼的路线的数目是多重集{4E,4N}的排列数，即

8!70。所以，如果他从水下的街区走过，则他可能有的路线数是35702450。因4!4!此，如果他不从水下的街区走过，则他可能有的路线数是11440245090。 26. 确定多重集S{3a,4b,5c}的10-排列的个数。 解 S的有1个a ，4个b， 5个c的10-排列的个数为

10!1260。

1!4!5!S的有3个a ，2个b， 5个c的10-排列的个数为

10!2520。

3!2!5!10!4200。

3!4!3!10!2520。

3!2!5!10!3150。

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

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

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

S的有3个a 3个b 4个c的10-排列的个数为

10!4200。

3!4!3!S的10-排列的个数为12602252024200315017850。

31. 方程x1x2x3x430有多少满足x12，x20，x35，x48的整数解？ 解 进行变量代换：

y1x12，y2x2，y3x35，y4x48

则方程变为

y1y2y3y425

原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为

254128282827263276 252533!第五章作业答案

8. 用二项式定理证明

2证明 由二项式定理知道

nknnk(1)k3

k0n(xy)令x3，y1得

nnnkkkxy k0nnnnkkknnk2(3(1))3(1)(1)3 kkk0k0nnn18. 求和

1n1n1nn1n 1(1)213243n1nn1n1n11n解法1 对任意非负整数n和k，即(k1)(n1)，，k1kk1kn1k1因此，

11n1n1nn1n (1)123n234n1

(1)kk0k1nnn(1)kkn1k0n11n1k1n1(1)k1n1kk1

1n11n1111kn1kn1 (1)(1)0kkn1n1k1n1n1n1k0knk(1)kx k0n解法2 由二项式定理知道

(1x)两边分别求积分得

n(11)n1(10)n11(1x)dx 0n1n1n11n(1)k0(1)kxdxk1k0k01nknknnk 所以

1n1n1n1n1n1(1)3243nn1 12n120. 求整数a，b和c，使得对所有的m mmmm3a3b2c1

求级数的和123n。

解 令m1，13abc，因为0，所以c1。

33331312111132令m2，23a3b2c1，因为30，所以b82c6。

令m3，33a3b2c1，所以a273b3c6。 

nmmnm 123nm63621

m0m0m0m033333nn2222333

n1n1n1n2n166643242 

6(n2)(n1)n(n1)(n1)nn2(n1)2 4!2425． 应用组合学论证方法，证明二项式系数的Vandermonde卷积： 对所有的正整数m1，m2和n，

m1m2m1m2knkn

k0作为特殊情形，推导恒等式（5-11）。

证明 设SAB，AB，|A|m1，|B|m2，则|S|m1m2。 我们可以从集合A中取出k个元素，再从集合B中取出nk个元素，把它们合起来构成S的有n个元素的子集。因为A的有k个元素的子集有nm1个，因为B的有nk个元素的km1m2nm1m2m2子集有nknk。 nk个，所以S的有n个元素的子集个数为k033237. 在(x1x22x32x4)9的展开式中x1的系数是什么？ x2x3x4解 由多项式定理知道

(x1x2x3x4)nn1n2n3n4nnn1n2n3n4nnnnx1x2x3x4 1234令x2为x2，x3为2x3，x4为2x4，n为9，得到

(x1x22x32x4)332因此，x1的系数是 x2x3x49n1n2n3n499n1n2n2n3n3n4n4nnnnx1(1)x22x3(2)x4 123499!(8)32(1)2(2)40320 33123!3!1!2!42. 用牛顿二项式定理近似计算101/3。

解 101/3(82)1/32(10.25)1/3

11111121112511133) 22(1kk34332163336k4k4k0k411121112511101/32(1)2.1547

34332163336第六章作业答案

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

解 设S是从1到10000的整数的集合，A1是从1到10000的完全平方数的集合，A2是从1到10000的完全立方数的集合。因为10010000，所以|A1|100。因为

2213926110000108223，所以|A2|21。因为一个整数既是完全平方数也是

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

66|A1A2|4。从1到10000既不是完全平方数也不是完全立方数的整数个数

|A1A2||S|(|A1||A2|)|A1A2|10000(10021)49883

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

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

T{6a,6b,3c}的12-组合的个数。设S为T*{a,b,c}的所有12-组合的集合，则|S|123114设A1为T*的所有至少有7个a的12-组合91。1212的集合，A2为T*的所有至少有7个b的12-组合的集合，A3为T*的所有至少有4个c的12-组合的集合。每个T*的5-组合再加上7个a就得到一个至少有7个a的12-组合，所以T*的至少有7个a的12-组合的个数等于T*的5-组合的个数，

53175317。同样可得到|A1|21|A|2555521，

83110*|A3|8845。T的至少有7个a和7个b的12-组合的个数|A1A2|0，T*的至少有7个a和4个c的12-组合的个数|A1A3|3，T*的至

少有7个b和4个c的12-组合的个数|A2A3|3，T*的至少有7个a、7个b和4

个c的12-组合的个数|A1A2A3|0。因此，T的12-组合的个数 |A1A2A3|

|S|(|A1||A2||A3|)|A1A2||A1A3||A2A3||A1A2A3|

91(212145)033010

9. 确定方程

x1x2x3x420

满足

1x16， 0x27， 4x38， 2x46

的整数解的个数。 解 引入新变量

y16x1 y27x2 y38x3 y46x4

则方程

x1x2x3x420

满足

1x16， 0x27， 4x38， 2x46

的整数解的个数等于方程

y1y2y3y47

满足

0y15， 0y27， 0y34， 0y44

的整数解的个数。设S是方程y1y2y3y47的所有非负整数解的集合，则

74110|S|77120。设A1为方程y1y2y3y47的所有满足y16的

非负整数解的集合，A2为方程y1y2y3y47的所有满足y28的非负整数解的集合，A3为方程y1y2y3y47的所有满足y35的非负整数解的集合，A4为方程y1y2y3y47的所有满足y45的非负整数解的集合，则|A1|4，|A2|0，

2415|A3||A4|2310。若ij，则AiAj。因此，方程

y1y2y3y47

满足

0y15， 0y27， 0y34， 0y44

的整数解的个数

|A1A2A3A4||S||A1||A2||A3||A4|12040101096

24. 把六个非攻击型车放到具有如下所述禁止位置的6行6列棋盘上的方法数是多少？ (c)

× × × × × × × × 解 禁放位置可分成两个“”部分，左上角的F1部分，包含5个位置，右下角的F2部分，包含3个位置。用rk表示把k个非攻击型车都放在禁止位置的方法数。r18。若在F1部分的禁止位置放两个非攻击型车，则有3216种方法；若在F2部分的禁止位置放两个非攻击型车，则有1种方法；若在F1部分和F2部分的禁止位置各放一个非攻击型车，则有5315种方法。因此，r2611522。若在F1部分的禁止位置放两个非攻击型车，在F2部分的禁止位置放一个非攻击型车，则有6318种方法；若在F2部分的禁止位置放两个非攻击型车，在F1部分的禁止位置放一个非攻击型车，则有155种方法；若在F1部分的禁止位置放三个非攻击型车，则有1种方法。因此，r3185124。若在F1部分的禁止位置放三个非攻击型车，在F2部分的禁止位置放一个非攻击型车，则有

133种方法；若在F1部分和F2部分的禁止位置各放两个非攻击型车，则有616种

方法。因此，r4369。若在F1部分的禁止位置放三个非攻击型车，在F2部分的禁止位置放两个非攻击型车，则有1种方法，r51。把六个非攻击型车放到具有上述禁止位置的6行6列棋盘上的方法数是

6!r15!r24!r33!r42!r51!

72081202224246921161

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

i11,2,3； i21； i31； i55,6以及i65,6。

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

× × × × × × × × × 禁放位置可分成两个“”部分，左上角的F1部分，包含5个位置，右下角的F2部分，包含4个位置。用rk表示把k个非攻击型车都放在禁止位置的方法数。r19。若在F1部分的禁止位置放两个非攻击型车，则有4种方法；若在F2部分的禁止位置放两个非攻击型车，则有2种方法；若在F1部分和F2部分的禁止位置各放一个非攻击型车，则有5420种方法。因此，r2422026。若在F1部分的禁止位置放两个非攻击型车，在F2部分的禁止位置放一个非攻击型车，则有4416种方法；若在F2部分的禁止位置放两个非攻击型车，在F1部分的禁止位置放一个非攻击型车，则有2510种方法。因此，

r3185124。若在F1部分和F2部分的禁止位置各放两个非攻击型车，则有428种方法。因此，r48。r50。把六个非攻击型车放到具有上述禁止位置的6

行6列棋盘上的方法数是

6!r15!r24!r33!r42!r51!

720912026242668201124

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

解 令S为{1,2,3,4,5,6,7,8}的全部7!个循环排列的集合，Ai为出现模式i(i1)的循环排列的集合（1i7），A8为出现模式81的循环排列的集合。若1k7且i1,,ik是集合{1,2,3,4,5,6,7,8}中的不同整数，则|AiAi|(7k)!。|1ki1 Ai|1。因此，

88888888|A1A8|7!6!5!4!3!2!1!12345670!11625 她们可以有1625种方法改变座位。

第七章作业答案

1. 设f0,f1,,fn,表示斐波那契序列。通过用小的n值为下列每一个表达式赋值，猜测一般公式，然后用数学归纳法和斐波那契递归证明之。 （c）f0f1f2(1)nfn

2（d）f02f12fn

解 (c) 对于小的n值，列出fn和

k0(1)kfk的值如下。

n

n 0 1 2 3 4 5 6 7 8

fn 0 1 1 2 3 5 8 13 21

k0(1)kfk

nn0 1 0 2 1 4 4 9 12

猜测：

0k(1)fkn(1)fn11k0若n0若n1

当n0时，f00，结论成立。

当n1时，f0f11f01，结论成立。 设n1且

k0(1)kfk(1)nfn11，则

n1n

k0(1)kfkk0(1)kfk(1)n1fn1(1)nfn11(1)n1fn1

n

(1)n1(fn1fn1)1(1)n1fn1 对于小的n值，列出fn和 n

(d)

k0fk2的值如下。

n

0 1 2 3 4 5 6 7 8

fn 0 1 1 2 3 5 8 13 21

k0fk2 0

n1 2 6 15 40 104 273 714

2猜测：f02f12fnfnfn1

当n0时，f020f0f1，结论成立。

2设f02f12fnfnfn1，则

f02f12fn2fn21fnfn1fn21fn1(fnfn1)fn1fn2

14. 求解初始值h00，h11，h21和h32的递推关系（n4）。 hn5hn16hn24hn38hn4，解 特征方程为x5x6x4x80。

因为(1)45(1)36(1)24(1)80，所以1是该方程的一个根。

432x45x36x24x8x4x36x36x212x212x8x8

x3(x1)6x2(x1)12x(x1)8(x1)(x36x212x8)(x1) (x2)3(x1)

因此，一般解为

hnc12nc2n2nc3n22nc4(1)n

（n0） （n1） （n2） （n3）

c1c40

2c12c22c3c41 4c18c216c3c41 8c124c272c3c42

解该方程组得到 因此，

c18 277 c2721 c3248 c42787812hn272n72n2n24n2n27(1)n

18. 求解非齐次递推关系

hn4hn132n （n1）

h01

解 对应齐次递推关系的特征方程为x40，它的特征根为4。设该非齐次递推关系的特解为p2n，则p2n4p2n132n，因而p2p3，因此p3。 该非齐次递推关系的一般解为hnc4n32n。

令n0，得c31，解得c4。因此，hn4n132n。 26. 求解非齐次递推关系

hn4hn14n （n1）

h03

解法一 对应齐次递推关系的特征方程为x40，它的特征根为4。设该非齐次递推关系的特解为pn4n，则pn4n4p(n1)4n14n，解得p1。该非齐次递推关系的一般解为hnc4n4nn。令n0，得c3。因此，hn(n3)4n。 解法二 该序列的生成函数g(x)n0hnxn。

nn

(14x)g(x)(14x)hnxhnxn0nn0nn04hnxn1



h0hnx4hn1xh0(hn4hn1)xn

n1n1n1

h04x34x24nxn2n1n1n0nnnn1 14x

1114x2g(x)

14x14x(14x)22

24x(n1)4xn0n0nnnnn0(n3)4nxn

因此，hn(n3)4n。

30. 确定苹果、桔子、香蕉和梨的袋装水果的袋数hn的生成函数，其中各袋要有偶数个苹果，最多两个桔子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出hn的公式。 解 生成函数

g(x)(x)(1xx)(x3n)(1x)

n0n02n2因此，hnn1。

(1xx2)(1x)(1x2)(1x3)1(1x)2n0n (n1)xn32. 令h0,h1,h2,,hn,是由hn。确定该序列的生成函数。 2定义的序列（n0）

解

n0xn1 1x1(1x)2两边求导数得到

n0nxn1

两边再求导数得到

n0n(n1)xn2(1x)3

2x2两边乘得到

2因此，该序列的生成函数

n(n1)nx22x(1x)3 n0nnn(n1)nx2g(x)hnx 2x2x3(1x)n0n0n0n32. 令h0,h1,h2,,hn,是由hn。确定该序列的指数生成函2定义的序列（n0）

数。

解 该序列的指数生成函数

ng(e)nnxnxnxn(x)hn n!n02n!n22n!n0

n!xn1xn1xn2x2xnx2ex 2n0n!2n22!(n2)!n!2n2(n2)!2n0n!41. 确定所有的数字至少是4的n位数的个数，其中4和6每个都出现偶数次，5和7每个至少出现1次，但对于数字8和9则没有。

解 设hn为满足条件的n位数的个数，序列h0,h1,h2,的指数生成函数是

g(e)

x2x4x2x3x222(x)(1)(x)(1x)2

2!4!2!3!2!

(exex)2x(e2x2e2x)(e2x2ex1)e2x22x(e1)e

44e6x2e5x3e4x4e3x3e2x2ex1

4

nn16nxn15nxn34nxn3x32nxn1xn1 4n0n!2n0n!4n0n!n!4n!2n!4n0n0n0

6n25n34n43n32n2xn 4n!n1

0因此，hn6n25n34n43n32n24若n0若n1

第八章作业答案

1. 设在圆上选择2n个（等间隔的）点。证明将这些点成对连接起来所得到的n条线段不相交的方法数等于第n个Catalan数Cn。

证明 设hn为将圆上的2n个点成对连接起来得到n条不相交线段的方法数。我们证明序列h0,h1,h2,与Catalan数序列C0,C1,C2,满足同样的递推关系和初始条件。 设圆上的2n个点顺时针依次排列为a0,a1,a2,,a2n1，若连接线段a0ak，则其左边和右边的点不能相互连接，那样会与a0ak相交。a0ak左边的点的数目和它右边的点的数目都应当是偶数，即k是奇数。若a0ak左边的点的数目是2i，则a0ak右边的点的

数目就是2(n1i)。随着k从1变到2n1，i从0变到n1。因此，序列h0,h1,h2,满足递推关系

hnh0hn1h1hn2hn1h0

12n2令gnCn1，则gn。由定理7.6.1知道序列g1,g2,g3,满足递推关系 n1ngng1gn1g2gn2gn1g1

因此，

Cngn1g1gng2gn1gng1C0Cn1C1Cn2Cn1C0

又有h01C0，序列h0,h1,h2,与Catalan数序列C0,C1,C2,满足同样的递推关系和初始条件。

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

解 计算序列05,15,25,,n5,的差分表如下。

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，…

因此

n1n1n1n1n1n15k0130150240120123456 k012. 证明第二类Stirling数满足关系 (a) S(n,1)1，(n1) (b) S(n,2)2n11，(n2) (c) S(n,n1)，(n1)

nn2(d) S(n,n2)3，(n2)

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

n3n4(b) 设n2，A是n-元集，则A的非空真子集的个数为22。任取A的非空真子集B，将B中元素放入一个盒子，而将其他元素放入另一个盒子，就得到一种将A中元素放入两个非空盒子的方法。显然，B和它的补集AB对应同一种方法，即每种方法都对应A的两个子集。因此，S(n,2)(2n2)/22n11。

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

nn2n1个非空盒子中，必然有一个盒子中有两个物体，而其余盒子中只有一个物体。设A是n-元集，任取A的2-组合B，将B中元素放入一个盒子，将其余元素各放进一个盒子，就得到将n个物体放入n1个非空盒子中的方法。因此，可在A的2-组合和将n个物体放入n1个非空盒子中的方法之间建立一一对应。所以，S(n,n1)。

n2(d) 设n2。若n2，S(n,n2)03。下面考虑n3的情况。将n个物体放入n2个非空盒子中，有两种可能。一种情况是，有一个盒子中放入3个物体，其余盒子中各放入一个物体，这种情况发生的次数是。另一种情况是，有两个盒子中各放入2个物体，其余盒子中各放入一个物体。从这n个物体中任取出四个，设它们是

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

nnS(n,n2)334。

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

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

证明 设Y{b1,b2,,bk}。将b1,b2,,bk看作k个不同盒子，若f(x)bi，则把

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

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

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