组合数学引论课后答案(部分).doc

组合数学引论课后答案(部分).doc

《组合数学引论课后答案(部分).doc》由会员分享，可在线阅读，更多相关《组合数学引论课后答案(部分).doc（31页珍藏版）》请在冰点文库上搜索。

组合数学引论课后答案

习题一

1.1任何一组人中都有两个人，它们在该组内认识的人数相等。

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

1.3任取n+1个整数，求证其中至少有两个数，它们的差是n的倍数

1.4在1.1节例4中证明存在连续的一些天，棋手恰好下了k盘棋（k=1,2,…，21）.问是否可能存在连续的一些天，棋手恰好下了22盘棋

1.5将1.1节例5推广成从1,2，…，2n中任选n+1个数的问题

1.6从1,2,…,200中任取100个整数，其中之一小于16，那么必有两个数，一个能被另一个整除

1.7从1,2,…,200中取100个整数，使得其中任意两个数之间互相不能整除

1.8任意给定52个数，它们之中有两个数，其和或差是100的倍数

1.9在坐标平面上任意给定13个整点（即两个坐标均为整数的点），则必有一个以它们中的三个点为顶点的三角形，其重心也是整点。

1.10上题中若改成9个整点，问是否有相同的结论？

试证明你的结论

1.11证明：

一个有理数的十进制数展开式自某一位后必是循环的。

1.12证明：

对任意的整数N，存在着N的一个倍数，使得它仅有数字0和7组成。

（例如，N=3,我们有;N=4,有;N=5,有;……）

1.13

（1）在一边长为1的等边三角形中任取5个点，则其中必有两个点，该两点的距离至多为；

（2）在一边长为1的等边三角形中任取10个点，则其中必有两个点，该两点的距离至多为；

（3）确定，使得在一边长为1的等边三角形中任取个点，则其中必有两个点，该两点的距离至多为；

1.14一位学生有37天时间准备考试，根据以往的经验，她知道至多只需要60个小时的复习时间，她决定每天至少复习1小时，证明：

无论她的复习计划怎样，在此期间都存在一些天，她正好复习了13个小时。

1.15从1,2,…,2n中任选n+1个整数，则其中必有两个数，它们的最大公约数为1

出的数属于同一个鸽巢，即它们的最大公约数为1

1.16针对1.1节的例6，当m,n不是互素的两个整数时，举例说明例中的结论不一定成立

习题二

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个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。

证明：

有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种，这样一列中两个同色单元格的位置组合共有10*4=40种情况。

而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。

2.9将一个矩形分成（m+1）行列的网格每个格子涂1种颜色，有m种颜色可以选择，证明：

无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明：

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

（2）每列中两个单元格的不同位置组合有种，这样一列中两个同色单元格的位置组合共有种情况

（3）现在有列，根据鸽巢原理，必有两列相同。

证明结论成立。

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

所以从第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。

证明：

要证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！

所以有，共14400种不同的安排方法。

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

如果第一位数字不能是0，那么最多能有多少个电话号码？

解：

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

3.318名排球运动员被分成A,B,C三个组，使得每组有6名运动员，那么有多少种分法？

如果是分成三个组（不可区别），使得每组仍有6名运动员，那么有多少种分法？

解：

1）种

2）/3!

3.4教室有两排，每排8个座位。

现有学生14人，其中的5个人总坐在前排，4个人总坐在后排，求有多少种方法将学生安排在座位上？

解：

前排8个座位，5人固定，共种方法；后排8个座位，4人固定，共种方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共种方法；则一共有种安排方法。

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

解：

先排21个辅音字母，共有21！

再将5个元音插入到22个空隙中，

故所求为

（插入法）

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.715个人围坐一个圆桌开会，如果先生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确定多重集的11-排列数？

解：

M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列，即=27720

当然了，容斥原理，生成函数也可以做。

3.9求方程，满足的整数解的个数。

解：

令

则有，由定理3.3.3，解个数为：

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

解：

n=20，r=4，

证明见38页。

若卷号差为2，3，。

。

。

。

。

，公式为？

3.11确定（2x-3y）5展开式中x4y和x2y4的系数。

解：

1）：

，系数为-240

2）：

系数为0。

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

解：

，n=5，r=4，则系数为

3.13确定（x+2y+3z）8展开式中x4y2x2的系数。

解：

3.14证明组合等式：

，其中n,k为正整数。

解：

右边是（n+k+1）元集合上k个元素子集的个数，这些子集可分为以下k+1类：

第1类：

k元子集中不含a1的子集有个;

第2类：

k元子集中含a1而不含a2的子集是个;

第3类：

k元子集中含a1和a2，而不含a3的子集是

……

第k+1类：

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

由加法原理得证。

根据组合意义进行证明

3.15利用，求。

解：

首先有：

（p51的（3））

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

又由

得，

则原式

3.16在一局排球比赛中，双方最终的比分是25:

11，在比赛过程中没有出现5平的比分，求有多少种可能的比分记录？

解：

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

3.17在一局乒乓球比赛中，运动员甲以11:

7战胜运动员乙，若在比赛过程中甲从来没有落后过，求有多少种可能的比分记录？

解：

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

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

解：

根据题意，相当于求从点（0,0）到点（20,20）且不接触y=x的非降路径数，即为：

n=20，则方法数为：

3.19计算和。

解：

1）

一个递推公式，

2）

3.20

（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个不同的盒子里，有种方案，而不符合题意的摆法是有一排至少有n+1个座位。

这相当于将n+1个座位先放到3排中的某一排，再将剩下的2n-（n+1）=n-1个座位任意分到3排中，这样的摆法共有种方案，所以符合题意的摆法有：

可以用代数法

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

习题四

4.1 在1到1000之间不能被2，5和11整除的整数有多少个？

解：

设S是这1000个数的集合，性质是可被2整除，性质是可被5整除，性质是可被11整除。

，，

，，，

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

求不收看A,B,C任何频道的用户百分比？

解

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

解：

设S是1000个数的集合，

性质是某数的完全平方，

性质是某数的完全立方，

性质是某数的完全四次方。

，，

，，，

4.4某杂志对100名大学新生的爱好进行调查，结果发现他们都喜欢看球赛和电影、戏剧。

其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求有多少人只喜欢看电影？

解：

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

所以可得既喜欢看球赛有喜欢看电影的人有

因此只喜欢看电影的人有

=52-（26+16）+12=22人

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

4.6 计算多重集S={4•a,3•b,4•c,6•d}的12-组合的个数？

解：

令

其中，，

，，

，，，，，，

4.7 计算多重集S={∞•a,4•b,5•c,6•d}的10-组合的个数？

解：

将，其他思想同上题。

其中，，，，，，，，，，

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

1）x1+x2+x3=15，其中x1,x2,x3都是非负整数其都不大于7；

2）x1+x2+x3+x4=20，其中x1,x2,x3,x4都是正整数其都不大于9；

解：

1）与{7a,7b,7c}的15组合数相等，为28

2）

，因此用代替，代替，代替，代替有

与{8a,8b,8c,8d}的16组合数相等为489

4.9定义D0=1，证明：

证明：

考虑到n个数的全排列包含错位排列和非错排，其中表示在n个数中任选k个，这个k个数构成了一个错排，而剩余的n-k个数还在原来的位置。

，显然

（另一种方法：

组合分析法）

4.10证明：

Dn满足：

　　ｎ为整数且ｎ３

证明：

由定理4.3.1得

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

解：

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

雨伞全错为解

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型号车不能涂成蓝色，求有多少种涂装方案？

解：

ABCDE

红

白

蓝

绿

黑

1.若未规定不同车型必须涂不同颜色，则：

涂装方案

2.若不同车型必须涂不同颜色，则：

禁区的棋盘多项式为：

1+8x+22x2+25x3+11x4+x5

所以：

5！

-8*4！

+22*3！

-25*2！

+11*1！

-1=20

4.15计算

（舍）

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

（舍）

补：

（1）在1~2000中能被7整除，但不能被6和10整除的个数。

证明：

A1,A2,A3表示被6、7和10整除的数的子集，所求：

=219

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

=534

习题五

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

（1）；

（2）；

（3）；（4）；

（5）；（6）；

解：

（1）由已知得

故

（2）设则

又因为故

或者

（3）

（4）

（5）

（6）

5.2求如下数列的指数生成函数。

（1）；

（2）；

（3）；

解：

（1）

（2）

（3）

则故

5.3已知数列的生成函数是，求.

解：

而

故

5.4求展开式中的系数是多少？

（1）若取0，则取5个，这种情况有种；

（2）若取1，则取3个，这种情况有或；

（3）若取2，则取1个，这种情况有；

故系数为=91457520。

其他方法

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

解：

这相当于有9个球，用隔板将其分成3组，共有种方法。

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

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

解：

（1）三位数时，相当于的非负整数解的个数。

故中为展开式的系数。

（2）四位数时，相当于的非负整数解的个数。

5.7一个1×n的方格图形用红、蓝、绿和橙四种颜色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，求有多少种方案？

解：

涂色方案数为则：

因此：

，所以有种方案。

5.8有4个红球，3个黄球，3个蓝球，每次从中取出5个排成一行，求排列的方案数？

解：

设每次取出的k个球的排列数为，数列的指数型生成函数为则有

而我们所求的是的系数。

故有。

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

解：

中的系数，有=15.

5.10 计算和。

解：

（1）构造多项式则即的系数，则，故。

（2），的非负整数解为（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）

5.11设表示把元集划分成非空子集的方法数，我们称为Bell数。

证明：

。

证明：

当有1个盒子时，方法数，

当有2个盒子时，方法数，

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

当有n个盒子时，方法数，

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

故

5.12有重为1g的砝码重为1g的3个，重为2g的4个，重为4g的2个，求能称出多少种重量？

解：

即求多项式中展开式有多少项

（除1外），原多项式

故共有19种重量。

5.13已知数列的指数生成函数是，求.

解：

设

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},

其指数生成函数为

展开后得的系数为20，所以能组成20个4位数的偶数。

习题六

6.1设，建立的递推关系并求解。

解：

6.2求解递推关系：

（1）

解：

（2）

解：

（3）

解：

（4）

解：

6.3求解递推关系：

（1）

解：

（2）

解：

（3）

解：

（4）

解：

6.4求解递推关系：

（1）

（2）

（3）

（4）