组合数学引论课后答案

习题二

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只颜色选择，根据鸽巢原理，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有

=10种，这样一列中两个同色单元格的位置组合共有(52)10*4=40种情况。

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

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

+1+1列的网格每个格子涂12.9 将一个矩形分成(m+1)行m(m2)种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明：

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

+1种，这样一 （2）每列中两个单元格的不同位置组合有(m2)+1m种情况 列中两个同色单元格的位置组合共有 (m2)+1+1列，根据鸽巢原理，必有两列相同。证 （3）现在有m(m2)明结论成立。

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

24=aj-ai=(b1+b2+b3+…+bi+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+...+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)展开式中x的系数。

n?r?1?，n=5，r=4，则系数解：(1?x)??(?1)???x?n?rrr?0-54

?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元子集中不含a的子集有 ??n??? k1?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???1?2???n3.15 利用 k2?2?，求。 ??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)?1546

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?364

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， |A121?A2?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?，|A4|???56， |A3|???120????5??7??4?3?1?|A1?A2|???20??3?，，

?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组合数相等为489

n??n??n??n? 4.9 定义D0=1，证明：n!??D?D?D?????n??1??2??D0?0??1??2??n??n?证明：考虑到n个数的全排列包含错位排列和非错排，其中??Dk表

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

?n??n??n??n??n??n???????，显然n!???D0???D1???D2?...???Dn

?0??1??2??n??0??n?（另一种方法：组合分析法） 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雨伞全错为D10解

10!?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又因为ak?kbk故G{ak}?x(G{bk})1?bk?k?2x

(1?2x)2或者

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解： （1）Ge{ak}??(?1)?e(?x)

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?3x而A(x)?解： A(x)??2?3kxk 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(3) 若x8取2，则x4取1个，这种情况有C1100?C99； 5312故系数为C100?C1100?C99?C100?C99= 91457520。

其他方法

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

2解：这相当于有9个球，用隔板将其分成3组，共有C8?28种方法。又因为这

次点数小于等于6，即711，171和117三种情况不符，故共有25种方法。

(x?x2?x3?x4?x5?x6)3?(x?x)73??2?k?k??x?k(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则：

22xxeGe{bk}?(1?x(1?x2!?4!??)?2!?3!??)?(2423x?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}则有

xxxxxxx而我们所求的是Ge{bk}?(1?1!?x(1?1!?x(1?1!?x2!?3!?4!)?2!?3!)?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??7??7?n(2)????1n1?2n2?33，n1?n2?n3?3?n1?n2?n3?4?4的非负整数解为(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?21?33?22?32?23?31?24?11?33?11?21?32?11?22?31?11?23?12?32 ?3??12?21?31?12?22??13?31?13?21?14?3015.11设Bn表示把n元集划分成非空子集的方法数，我们称Bn为Bell数。

证明：Bn??????????。

证明：当有1个盒子时，方法数b1???，

?n?当有2个盒子时，方法数b2???，

?2??n??1??n??n??1??2??n??n? ?

当有k个盒子时，方法数bk???，

?

?n??k?当有n个盒子时，方法数bn???，

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

故Bn??bi??????????????

i?1n?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）? 解：

?f(n)?7f(n?1)?12f(n?2)?0,(n?2)

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

（2）??f(n)?f(n?2)?0,(n?2)

?f(0)?0,f(1)?2;x2?1?0解：

x1??i,x2?i

?f(n)?5f(n?1)?6f(n?2)?4f(n?3)?8f(n?4),(n?4)（3）?

f(0)?0,f(1)?1,f(2)?1,f(3)?2,;?解：

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

?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;

本文来源：https://www.bwwdw.com/article/gfzg.html