组合数学 课后答案

习题二

2.1 证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明：

假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。

假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。

假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

2.2 任取11个整数，求证其中至少有两个数的差是10的整数倍。

证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3 证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 2.3证明：

有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

2.4 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？

证明：

根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。

2.5 一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？

证明：

根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

2.6 证明：在任意选取的n+2个正整数中存在两个正整数，其差或和能被2n整除。（书上例题2.1.3）

证明：对于任意一个整数，它除以2n的余数显然只有2n种情况，即：0，1，2，…，2n-2，2n-1。而现在有任意给定的n+2个整数，我们需要构造n+1个盒子，即对上面2n个余数进行分组，共n+1组： {0},{1，2n-1},{2，2n-2},{3,2n-3},…，{n-1,n+1}，{n}。

根据鸽巢原理，n+2个整数，必有两个整数除以2n落入上面n+1个盒子里中的一个，若是{0}或{n}则说明它们的和及差都能被2n整除；若是剩下n-1组，因为一组有两个余数，余数相同则它们的差能被2n整除，不同则它们的和能被2n整除。证明成立。

2.7 一个网站在9天中被访问了1800次，证明：存在连续的3天，这个网站的访问量超多600次。 证明：

设网站在9天中访问数分别为a1，a2，...，a9 其中a1+a2+...+a9 = 1800，

令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3

因为（b1+b2+b3）/3 >= 600 由推论2.2.2知，b1，b2，b3中至少有一个数大于等于600。

所以存在有连续的三天，访问量大于等于600次。

2.8 将一个矩形分成5行41列的网格，每个格子涂1种颜色，有4种颜色可以选择，证明：无论怎样涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明：首先对一列而言，因为有5行，只有4只颜色选择，根据鸽巢原理，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有

52=10种，这样一列中两个同色单元格的位置组合共有

10*4=40种情况。

而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相

同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。

2.9 将一个矩形分成(m+1)行mm121列的网格每个格子涂1

种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明：

（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。

（2）每列中两个单元格的不同位置组合有列中两个同色单元格的位置组合共有 （3）现在有m明结论成立。

m12m12种，这样一

m1m种情况 21列，根据鸽巢原理，必有两列相同。证

2.10 一名实验员在50天里每天至少做一次实验，而实验总次数不超过75。证明一定存在连续的若干天，她正好做了24次实验。

证明：令b1，b2，...，b50 分别为这50天中他每天的实验数，并做部分和

a1 = b1，a2 = b1+b2 ，。。

a50 = b1+b2+...+b50 .

由题，bi>=1(1<=i<=50)且a50<=75 所以 1<=a1考虑数列 a1，a2，...，a50，a1+24，a2+24，a50+24，它们都在1与75+24=99之间。

由鸽巢原理知，其中必有两项相等。由（*）知，a1，a2，...，a50互不相等，从而a1+24，...a50+24 也互不相等，所以一定存在1<=i24=aj-ai=(b1+b2+b3+…+bi+…+bj)-(b1+b2+…+bi)=bi1bi2...bj

所以从第i+1天到第j天这连续j-i天中，她正好做了24次实验。

2.11 证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：

将S划分为{1,3,5}，{7,9,11}……,{ 595,597,599}共100组，由鸽巢原理知任意选取101个数中必存在2个数来自同一组，即其差最多为4.

2.12 证明：从1~200中任意选取70个数，总有两个数的差是4，5或9。 证明：设这70个数为 a1,a2,…,a70, a1+4,a2+4,…,a70+4, a1+9,a2+9,…,a70+9, 取值范围209，共210个数

2.13 证明：对于任意大于等于2的正整数n，都有R(2,n)=n。 2.13证明：

要证R（2，n）= n，用红蓝两色涂色Kn的边。 当n=2时，R(2,2)=2，因为不管用红还是蓝色都是完全二边形。

假设当n=k时 成立 ，即存在R(2,k)=k（没有一条红边，只有蓝边）， 当n=k+1时，R（2，k+1）

若无红边，要想有完全k+1边形，必得有k+1个点，即R（2，k+1）=k+1。证明成立。

习题三

3.1 有10名大学生被通知参加用人单位的面试，如果5个人被安排在上午面试，5个人被安排在下午面试，则有多少种不同的安排面试的顺序？ 解：上午的5个人全排列为5！ 下午的5个人全排列为5！

5所以有C10*5!*5!10!，共14400种不同的安排方法。

3.2 某个单位内部的电话号码是4位数字，如果要求数字不能重复，那么最多可有多少个号码？如果第一位数字不能是0，那么最多能有多少个电话号码？

解：由于数字不能重复，0-9共10个数字，所以最多有10*9*8*7=5040种号码；若第一位不能是0，则最多有9*9*8*7=4536种号码。

3.3 18名排球运动员被分成A,B,C三个组，使得每组有6名运动员，那么有多少种分法？如果是分成三个组（不可区别），使得每组仍有6名运动员，那么有多少种分法？

666解：1)C18种 *C12*C6 2)

666/3! C18*C12*C63.4 教室有两排，每排8个座位。现有学生14人，其中的5个人总坐在前排，4个人总坐在后排，求有多少种方法将学生安排在座位上？

解：前排8个座位，5人固定，共C85*5!种方法；后排8个座位，4人固定，共C84*4!种方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共C75*5!种方法；则一共有

55C8*C84*C7*5!*5!*4!种安排方法。

3.5 将英文字母表中的26个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？

解：先排21个辅音字母，共有21！ 再将5个元音插入到22个空隙中，P

522故所求为21!P

522(插入法)

3.6 有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐，则有多少种不同的排坐方式？ 解：6男全排列6!；6女全排列6！；6女插入6男的前6个空或者后6个空，即女打头或男打头6!*6!*2；再除以围圈重复得(6!*6!*2)/12=6!*5! 或

男6的圆排列为5！，对每个男的排列，女要在他们之间的6个位置，进行线性排列6！（而不是5！）。

（圆排列可以通过线性排列来解决）

3.7 15个人围坐一个圆桌开会，如果先生A拒绝和先生B和C相邻，那么有多少种排坐方式？ 解：15人圆排列14！； A与B相邻有2*14!/14=2*13!； A与C相邻有2*14!/14=2*13!； A与BC同时相邻有2*13!/13=2*12!；

于是A不与B、C相邻的坐法共14!- 2*13!- 2*13!+ 2*12!（用到了容斥原理）

3.8 确定多重集M{3a,4b,5c}的11-排列数？ 解：M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列，即

11!11!11!=27720 2!4!5!3!3!5!3!4!4!当然了，容斥原理，生成函数也可以做。

3.9 求方程xx12x3x420，满足x12,x20,x35,x41的

整数解的个数。

解：令y1x120,y2x20,y3x350,y4x410 则有

y1y2y3y414，由定理3.3.3，解个数为：

14411717 14143680

3.10 书架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少种？

nr1204117解：n=20，r=4， 2380r44证明见38页。

若卷号差为2，3，。。。。。，公式为？

3.11 确定(2x-3y)5展开式中x4y和x2y4的系数。 解：1）x4y：C45*(2x)4*(3y)1，系数为-240

2）x2y4：系数为0。

3.12 确定(1+x)-5展开式中x4的系数。

nr1，n=5，r=4，则系数解：(1x)(1)xnrrr0r541为(1) 7044

3.13 确定(x +2y+3z)8展开式中x4y2x2的系数。 解：

8!*22*32151204!*2!*2!

3.14 证明组合等式：012k中n,k为正整数。

nn1n2nknk1，其k解：右边nk1是（n+k+1）元集合S{a1,a2,...,ank1}上k个元素

k子集的个数，这些子集可分为以下k+1类： 第1类：k元子集中不含a1的子集有 n kk  个;

nk1第2类：k元子集中含ak11而不含a2的子集是  个;

第3类：k元子集中含a1和a2，而不含a3的子集是

nk2 k2……

第k+1类：k元子集中含a1，a2，……, ak，而不含ak+1的子集是

由加法原理得证。 根据组合意义进行证明

n0

2223.15 利用 k22，求。 12n21kk解： 首先有：

n1nn10k1kkk（p51的(3)）

根据已知条件代入以上等式得：

ii1122nni(2)22...221212121i1i1 12n12n22...2...222111n2n12n12n2(...)...22211112nn1 又由...kkkk112nn1，12nn1 得......11122223n1n12(n1)n(n1)n(n1)n(n1)(2n1) 则原式2326663.16 在一局排球比赛中，双方最终的比分是25:11，在比赛过程中没有出现5平的比分，求有多少种可能的比分记录？

解：根据题意，相当于求从点(0,0)到点(25,11)且不经过(5,5)的非降路径数，即为：

25115525-511-5361026 -- 11-5115611 5

3.17 在一局乒乓球比赛中，运动员甲以11:7战胜运动员乙，若在比赛过程中甲从来没有落后过，求有多少种可能的比分记录？

解：根据题意，相当于求从点(0,0)到点(11,7)且从下方不穿过y=x的非降路径数，见58页，即为：

117111+1+7-2- 11-1 11+1

3.18把

20个苹果和20个橘子一次一个的分发给40个幼儿园的小朋友，如果要求分发过程中任意时刻篮子中余下的两种水果数目都不相同（开始和结束时除外），求有多少种分法方法？

解：根据题意，相当于求从点(0,0)到点(20,20)且不接

2n22n2触y=x的非降路径数，即为：2()n1n3838 n=20，则方法数为：2()192022n n1n

773.18计算和。

33766555532333231223解：1）

4444 5515915293123223619*727*6301

一个递推公式， 2）

576655565653331232nnn 2n1n1nn121 2

445544

1113011143042323122111(14*11)30(114*C4)16

3.19 （1）证明 S(n,3)=

方法一：先 考虑3个盒子不同，要保证每个盒子非空：总数为3n，排除到一个盒子为空和两个盒子为空的情况，即： 一个盒子为空（放到两个盒子去），例如第一个盒子为空,第二和第三不空：3（ 2n-2）

两个盒子为空，例如第一个和第二盒子为空：3*1 （3n-3（ 2n-2）-3）/3! 还可以直接考虑盒子相同。

（2）证明：相当于n个不同球放到相同的n-2个盒子，每个盒子非空，至少为1个，这样使得剩余的2个球要到n-2个盒子，即使得一个盒子有3个，或有二个盒子都装2个球： 使得一个盒子有3个球：C(n,3)

有二个盒子都装2个球：C（n,4）C(4,2)/2!

3.21（1）会议室中有2n+1个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？

解：如果没有附加则相当于把2n个相同的小球放到3

2n312n2个不同的盒子里，有 种方案，而不符合题意2n 2的摆法是有一排至少有n+1个座位。这相当于将n+1个座位先放到3排中的某一排，再将剩下的2n-(n+1)=n-1个座位任

意分到3排中，这样的摆法共有32n(n1)31n1种3 2  2方案，所以符合题意的摆法有：

2n2n1n2 23 2 2 可以用代数法

(2) 会议室中有2n个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？

习题四

4.1 在1到1000之间不能被2，5和11整除的整数有多少个？ 解：设S是这1000个数的集合，性质P2是可1是可被2整除，性质P被5整除，性质P3是可被11整除。

Ai{x|xSx具有性质P},(i1,2,3) i|A1|1000/2500，|A2|1000/5200，|A3|1000/1190 |A1A2|1000/10100，

|A1A3|1000/2245，

|A2A3|1000/5518，|A1A2A3|1000/1109 |A1A2A3|1000(50020090)(1004518)93

4.3 一项对于A,B,C三个频道的收视调查表明，有20%的用户收看A，16%的用户收看B，14%的用户收看C，8%的用户收看A和B，5%的用户收看A和C，4%的用户收看B和C，2%的用户都看。求不收看A,B,C任何频道的用户百分比？

解|A1A2A3|1(20%16%14%)(8%5%4%)2%65%

4.2 求1到1000之间的非完全平方，非完全立方，更不是非完全四次方的数有多少个？

解：设S是1000个数的集合， 性质P1是某数的完全平方， 性质P2是某数的完全立方， 性质P3是某数的完全四次方。

Ai{x|xSx具有性质P},(ii1,2,3) |A1|100031，|A32|100010，|A43|10005|AA612|10003，|A1A3|410005|A122A3|10001， |AA1212A3|10001 |A1A2A3|1000(31105)(351)1962

，4.4某杂志对100名大学新生的爱好进行调查，结果发现他们都喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求有多少人只喜欢看电影？

解：由题意可得，P1,P2,P3分别表示喜欢看球赛、电影和戏剧的学生，相应的学生集合分别为A1,A2,A3，依题意，这100名大学生中每人至少有三种兴趣中的一种，则A1A2A30 所以可得既喜欢看球赛有喜欢看电影的人有

|A1A2|(583852)100(1816)1226

因此只喜欢看电影的人有A2A1A2A2A3A1A2A3 =52-(26+16)+12=22人

4.5 某人有六位朋友，他跟这些朋友每一个都一起吃过晚餐12次，跟他们中任二位一起吃过6次晚餐，和任意三位一起吃过4次晚餐，和任意四位一起吃过3次晚餐，任意五位一起吃过2次晚餐，跟六位朋友全部一起吃过一次晚餐，另外，他自己在外吃过8次晚餐而没碰见任何一位朋友，问他共在外面吃过几次晚餐?

123456C612C66C64C63C62C61836

4.6 计算多重集S={4•a, 3•b, 4•c,6•d }的12-组合的个数？ 解：令T{a,b,c,d}的所有12组合构成W4121455

12其中|A|471120，|A17481， |28165451471，|A|56， |A3|120457431|A1A2|203，，

421|A1A3|102431|A2A3|203，，

401|A1A4|10411401， ， |A2A4|4|AA|13410|A1A2A3|0

|A1A2A3A4|455(12012016556)(20101204)50

4.7 计算多重集S={∞•a, 4•b, 5•c,6•d }的10-组合的个数？ 解：将a，其他思想同上题。

4101W286 10451441其中|A1|0，|A2|56，|A3|35，54431|A4|20，|A1A2|0，|A1A3|0，|A1A4|0，3|A2A3|0，|A2A4|0，|A3A4|0，|A1A2A3|0

|A1A2A3A4|286(563520)175

4.8 用容斥原理确定如下两个方程的整数解的个数。

1）x1+x2+x3=15，其中x1, x2, x3都是非负整数其都不大于7； 2） x1+x2+x3+x4=20，其中x1, x2, x3, x4都是正整数其都不大于9； 解：

1）x1x2x3150x17,0x27,0x37与{7a,7b,7c}的15组合数相等，为28 2）

x1x2x3x4201x19,1x29,1x39,1x49，因此用y1+1代替x1，y2+1代替x2，y3+1代替x3，y4+1代替x4有

y1y2y3y4160y18,0y28,0y38,0y48与{8a,8b,8c,8d}的16组合数相等为4

nnn4.9 定义D0=1，证明：n!DDn1D2012nD0 nn证明：考虑到n个数的全排列包含错位排列和非错排，其中Dk表

k示在n个数中任选k个，这个k个数构成了一个错排，而剩余的n-k个数还在原来的位置。

nnnnnn0n，显然n!0D01D12D2...nDn

（另一种方法：组合分析法） 4.10证明：Dn满足：

Dn(n1)(Dn1Dn2) D10,D21 ｎ为整数且ｎ３

证明：由定理4.3.1得

Dn1(n1)!(1111...(1)n1) 1!2!(n1)!111n2(n1)!(1...(1))(1)n1

1!2!(n2)!Dn2(n2)!(1Dn1Dn2111...(1)n2) 1!2!(n2)!111n2(1...(1))[(n2)!n](1)n11!2!(n2)!111...(1)n2)(1)n1(n1)1!2!(n2)!(n1)(Dn1Dn2)n!(1

1111n2n1n1(1...(1)(1)(1))

1!2!(n2)!(n1)!n!4.11有10名女士参加一个宴会，每人都寄存了一顶帽子和一把雨伞，

而且帽子、雨伞都是互不相同的，当宴会结束的离开的时候，如果帽子和雨伞都是随机的还回的，那么有多少种方法使得每位女士拿到的物品都不是自己的？

解：由于帽子全部拿错和雨伞全部拿错是两个相互的事件，设帽

子全错为

1D1010!(11111111111) 1!2!3!4!5!6!7!8!9!10!21雨伞全错为D10解 D1010!10! D10DD2e110210

4.13计算棋盘多项式R( )。 解： R( ) = x*R()+R( )

)

)]

=x*(1+3x+x2)+(1+x)*R(

= x3+3x2+x+(1+x)[xR()+R(

= x3+3x2+x+(1+x)[x(1+x)+(1+4x+2x2)] = 5x3+12x2+7x+1

4.14有A,B,C,D,E五种型号的轿车，用红、白、蓝、绿、黑五种颜色

进行涂装。要求A型车不能涂成黑色；B型车不能涂成红色和白色；C型车不能涂成白色和绿色；D型车不能涂绿色和蓝色；E型号车不能涂成蓝色，求有多少种涂装方案？ 解：A B C D E

红 白 蓝 绿 黑 1.若未规定不同车型必须涂不同颜色，则：

涂装方案43334432 2.若不同车型必须涂不同颜色，则：

禁区的棋盘多项式为： 1+8x+22x2+25x3+11x4+x5

所以：

5！-8*4！+22*3！-25*2！+11*1！-1=20

4.15计算(210),(105). （舍）

4.16计算T={∞•1, ∞•2, ∞•3，∞•4}的长度为4的圆排列数。 （舍）

补：（1）在1~2000中能被7整除，但不能被6和10整除的个数。 证明：A1,A2,A3表示被6、7和10整除的数的子集，所求：

A1A2A3A2A1A3A2A2(A1A3)A2(A2A1)(A2A3)A2(A2A1A2A3(A2A1)(A2A3))

=219

(2)在1~2000中至少被2、3和5两个数整除的数的个数？

A2A1A2A3A1A32A1A2A3=534

习题五

5.1 求如下数列的生成函数。

（1）ak(1)k(k1)；（2）ak(1)kk2k； （3）akk6； （4）akk(k2)；

nkn（5）akk； （6）ak3； 解：（1）由已知得

bkk1B(x)1

(1x)21 (x1)2故A(x)（2）设bk(2)k则G{bk}1 12x2x

(12x)2又因为akkbk故G{ak}x(G{bk})1bkk或者

B(x)x (1x)2（3）G{ak}G{bkk}G{ck6}（4）G{ak}x(G{bkk2})1x665x 22(1x)1x(1x)x(3x) (1x)3nkn1k1akkk （5）

1G{ak}(1x)n1（6）

kak3n4,4k13kbk kk3k3G{ak}x3(1x)4

5.2 求如下数列的指数生成函数。 （1）ak(1)k； （2）ak2kk!；

（3）ak

1； k1xke(x) 解： （1）Ge{ak}(1)k!k0k（2）Ge{ak}2kxkG{bk2k}k01 12x(3) Ge{ak}xf(x)1xkf(x)

k0(1k)!则

1xk1k0(1k)!1kx1ex1k0k!ex1故Ge{ak}

x

23x9x25.3 已知数列ak的生成函数是A(x)，求ak. 13x

2223kxk 解： A(x)3x而A(x)13x13xk023k,k1故ak

9,k1

5.4 求(1x4x8)100展开式中x20的系数是多少？

5(1) 若x8取0，则x4取5个，这种情况有C100种；

331(2) 若x8取1，则x4取3个，这种情况有C1100C99或C100C97； 2C(3) 若x8取2，则x4取1个，这种情况有C110099； 51312C100C99C100C99故系数为C100= 91457520。

其他方法

5.5 三个人每个人投一次骰子，有多少种方法使得总点数为9？

228种方法。又因为这解：这相当于有9个球，用隔板将其分成3组，共有C8次点数小于等于6，即711，171和117三种情况不符，故共有25种方法。

(xx2x3x4x5x6)3(xx)732kkxk(2)

5.6 求在102和104之间的各位数字之和等于5？

解：(1) 三位数时，相当于x1x2x35(1x15,0x25,0x35)的非

负

整

数

解

的

个

数

。

故中

G(x)(xx2x3x4x5)(1xx2x3x4x5)(1xx2x3x4x5)C5为G(x)展开式x5的系数。

(2) 四位数时，相当于

x1x2x3x45(1x15,0x25,0x35,0x45)的非负整数解的个

数。

5.7 一个1×n的方格图形用红、蓝、绿和橙四种颜色涂色，如果有

偶数个方格被涂成红色，还有偶数个方格被涂成绿色，求有多少种方案？

解：涂色方案数为bk则：

xGe{bk}(1x2!4!24x)2(1x2!3!23)2(exex22)(ex)2e4x2e2x1414k04k2k1xk4k!

因此：bk4k12k1，所以有4n12n1种方案。

5.8 有4个红球，3个黄球，3个蓝球，每次从中取出5个排成一行，

求排列的方案数？

解：设每次取出的k个球的排列数为bk，数列{bk}的指数型生成函数

为Ge{bk}则有

xxxxxxxxx而我们所求的是Ge{bk}(11!x2!3!4!)(11!2!3!)(11!2!3!)2342323x55!的

系数b5。故有b5220。

5.9 计算用3个A，3个G，2个C和1个U构成长度为2不同的RNA

链的数量。

x22x2解： (1x)(1x)(1x)中x2的系数C2，有C2=15.

225.10 计算和。 337解：(1)构造多项式x(x1)(x2)(x3)(x4)(x5)(x6)则即x3的系数

37b3，则b31524，故1524。

37n(2)1n12n233，n1n2n33n1n2n34477的非负整数解为(0,0,4), (1,2,3),

(0,2,2), (0,3,1), (0,4,0), (1,0,3), (1,1,2), (1,2,1) , (1,3,0), (2,0,2), (2,1,1) , (2,2,0) , (3,0,1), (3,1,0), (4,0,0)

7321332232233124113311213211223111231232 3122131122213311321143015.11设Bn表示把n元集划分成非空子集的方法数，我们称Bn为Bell数。

证明：Bn。

证明：当有1个盒子时，方法数b1，

n当有2个盒子时，方法数b2，

2nn12nnn1

当有k个盒子时，方法数bk，

当有n个盒子时，方法数bn，

当有n+1个盒子时，至少有一个空盒，不符。

故Bnbi

i1nnknnnnn123nn

5.12有重为1g的砝码重为1g的3个，重为2g的4个，重为4g的2

个，求能称出多少种重量？

解：即求多项式(1xx2x3)(1x2x4x6x8)(1x4x8)中展开式有

多少项 (除1外)，原多项式

(1xx2x3x4x5x6x7x8x9x10x11)(1x2x4x6x8)故共有

19种重量。

5.13 已知数列ak的指数生成函数是Ge(x)x25ex，求ak.

f(x)x25ex解：设

x2x3x5(1x..)2!3!2 ak=5, k不等于2 ak=7, k =2

补：3个l，2个2，5个3这十个数字能构成多少个4位数偶数。

解 问题是求多重集S＝{3个1，2个2，5个3}的4排列数，且要求排列的末尾为2（偶数）。可以把问题转化成求多重集S＝{3个1，1个2，5个3}, 其

指

数

生

成

函

数

为

x2x3x2x3x4x5Ge(x)1x(1x)1x2!3!2!3!4!5!3!3!3!3!3!x33!3! 3!1!2!1!2!3!1!2!1!1!1!2!1!3!x3203!x3展开后得的系数为

3!20，所以能组成20个4位数的偶数。

习题六

6.1 设f(n)1222n2，建立f(n)的递推关系并求解。 解：

f(n)f(n1)n2,(n2)f(1)1齐次特征方程： x10特征根： x1非齐次特解： f*(n)(b0b1nb2n2)n代入递推关系得：111b0，b1，b2623111 f(n)(nn2)n623

6.2 求解递推关系： （1） 解：

齐次特征方程： x27x120特征根： x14,x23齐次通解： f(n)c14c23代入递推关系得：c1-6，c210 f(n)64n103n#nnf(n)7f(n1)12f(n2)0,(n2)

f(0)4,f(1)6;

f(n)f(n2)0,(n2) （2）

f(0)0,f(1)2;解：

x210x1i,x2i

（3）解：

次特征方程： x4-5x36 x24x-80特征根： x1x2x32,x4-1次通解： f#(n)c12nc2n2nc3n22nc4(1)n代入推系得：8718，c2，c3-，c4-273624278n7n12n8 f(n)2n2-n2-(1)n27362427c1f(n)5f(n1)6f(n2)4f(n3)8f(n4),(n4)

f(0)0,f(1)1,f(2)1,f(3)2,;

f(n)3f(n1)2f(n2)1,(n2)（4）

f(0)4,f(1)6;解：

齐次特征方程： x23x20特征根： x12,x21非齐次特解： f*(n)b0n代入递推关系得：b01f#(n)c12nc2nc13，c21 f(n)32n1n

6.3 求解递推关系： （1）解：

f(n)4f(n1)4f(n2)3n1,(n2)

f(0)1,f(1)2;齐次特征方程： x24x40特征根： x1x22,非齐次特解： f*(n)b0b1n代入递推关系得：b013,b13f#(n)c12nc2n2n3n13c112，c210 f(n)122n10n2n3n13

（2）解：

齐次特征方程： x26x90特征根： x1x23,非齐次特解： f*(n)b0b1n代入递推关系得：b012,b14f#(n)c13nc2n3n4n12173 f(n)113n17n3n14n12c111，c2f(n)6f(n1)9f(n2)2n,(n2)

f(0)1,f(1)0;

f(n)4f(n1)32n,(n1)（3）

f(0)1,齐次特征方程： x40特征根： x4,非齐次特解： f*(n)2n代入递推关系得：解：

3f#(n)c14n32nc14， f(n)4n132n （4） 解：

齐次特征方程： x-20特征根： x2,非齐次特解： f*(n)b0b1n代入递推关系得：b0-2,b1-1f#(n)c12n-n-2c13， f(n)32n-n-2f(n)2f(n1)n,(n1)

f(0)1,

6.4 求解递推关系：

nf(n)(n1)f(n1)2n,(n1), （1）

f(0)273;2f(n)2f(n1)0（2）f(0)4;(n1),

22f(n)2f(n1)1（3）f(0)2;2f(n)5f(n1)（4）f(0)0;f(n),(n1),

(n1),

6.5 平面上有n条直线，它们两两相交且沿有三线交于一点，设这n条直线把平面分成f(n)个区域，求f(n)的递推关系并求解.

解：设n-1条直线把平面分成f(n-1)个区域，则第n条直线与前n-1条直线都有一个交点，即在第n条直线上有n-1个交点，并将其分成n段，这n段又把其所在的区域一分为二。

f(n)f(n1)n,(n2) f(1)2齐次特征方程： x10特征根： x1非齐次特解： f*(n)(b0b1n)n代入递推关系得：1b0b1，2(1n)nf#(n)c12代入递推关系得：c11 f(n)1(1n)n2

6.6 一个1n的方格图形用红、蓝两色涂色每个方格，如果每个方格只能涂一种颜色，且不允许两个红格相邻，设f(n)有种涂色方案，求f(n)的递推关系并求解.

解：

f(n-1) f(n-2) f(n)f(n1)f(n2), f(1)2，f(2)3(n2)

6.7 核反应堆中有和两种粒子，每秒钟内1个粒子可反应产生出3个粒子，而1个粒子又可反应产生出1个粒子和2个粒子.若在t=0s时刻反应堆中只有1个粒子，求t=100s时刻反应堆里将有多少个粒子和粒子，共有多少个粒子.

解：

设t时刻反应堆中粒子数为f(t)，粒子数为g(t)

在t-1时刻 在t时刻 f(t)g(t1),(n2)g(t)3f(t1)2g(t1)f(0)1,g(0)0g(t)3g(t2)2g(t1),(n2)g(0)0,g(1)3齐次特征方程： x22x30特征根： x13,x21齐次通解： g#(t)c13tc2(1)t代入递推关系得：33c1，c24433 g(t)3t(1)t443t133t3t1 f(t)3(1)(1)t

4444  g(t-1) 3f(t1)2g(t-1) f(t-1) g(t-1) 补：上有n个大圆，任意两个大圆皆相交，且没有三个大圆

通过同一点，则这些大圆所形成的区域数f(n)满足的递推关系是

f(n+1)= f(n)+2n，n>1, f(1)=2

f(n)可以由f(n)来生成，当在f(n)个大圆的基础上，在球面上再加上第n+1个大圆时，它同前n个大圆共得到2n个交点(因无三个大圆相交于一点)，而每增加一个交点就增加一个新的面，故共增加2n个面。所以有f(n+1)= f(n)+2n。

设P是平面上n个连通区域D1,D2,…Dn的公共交界点，如下图所示。现用k种颜色对其着色，要求有公共边界的相邻区域着以不同的颜色，令f(n)表示不同的着色方案。

有： f(n)= (k-1)f(n-2)+(k-2)f(n-1) （n≥4） f(2)=k(k-1) ， f(3)=k(k-1)(k-2)

(1) 有D1与Dn-1同色，此时Dn有k-1种方案，可将D1与D n-2看成相邻区域，则D1,D2, …, Dn-2的着色方案为f(n-2)。

(2) D1与Dn-1异色，此时Dn有k-2种方案，可将，则D1,D2, …, Dn-1的着色方案为f(n-1)。

(k-1)f(n-2)+(k-2)f(n-1)

另有：f(n)=k(k-1)n-1-f(n-1)

第七章

例n种颜色涂色装有7颗珠子的手镯，如果只考虑手镯的旋转，求有多少种涂色方案？

解 对象集D＝{1,2,3,4,5,6,7}，颜色集是R＝(1,2,3,…,n)，D上的置换群G＝{g0,g1,g2,…,g6}，其中gi表示旋转360°*i/7，因7是质数，所以除λ(g0)＝7外，其它λ(gi)＝1，(i=1,2,3,4,5,6)，代入Polya公式，得 L＝1/7*[n7+6n]

而四边形：转180时