组合数学引论课后复习资料部分.doc

组合数学引论课后答案
习题一
1.1 任何一组人中都有两个人，它们在该组内认识的人数相等。

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

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

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

1.5 将1.1节例5推广成从1,2，…，2n中任选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组成。（例如，3,我们有4,有5,有;……）

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

1.14 一位学生有37天时间准备考试，根据以往的经验，她知道至多只需要60个小时的复习时间，她决定每天至少复习1小时，证明：无论她的复习计划怎样，在此期间都存在一些天，她正好复习了13个小时。

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

出的数属于同一个鸽巢，即它们的最大公约数为1
1.16 针对1.1节的例6，当不是互素的两个整数时，举例说明例中的结论不一定成立

习题二
2.1 证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。
证明：
假设没有人谁都不认识：那么每个人认识的人数都为[11]，由鸽巢原理知，n个人认识的人数有1种，那么至少有2个人认识的人数相同。

假设有1人谁都不认识：那么其他1人认识的人数都为[12]，由鸽巢原理知，1个人认识的人数有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 证明：在任意选取的2个正整数中存在两个正整数，其差或和能被2n整除。（书上例题2.1.3）
证明：对于任意一个整数，它除以2n的余数显然只有2n种情况，即：0，1，2，…，22，21。而现在有任意给定的2个整数，我们需要构造1个盒子，即对上面2n个余数进行分组，共1组：
{0},{1，21},{2，22},{3,23},…，{11}，{n}。
根据鸽巢原理，2个整数，必有两个整数除以2n落入上面1个盒子里中的一个，若是{0}或{n}则说明它们的和及差都能被2n整除；若是剩下1组，因为一组有两个余数，余数相同则它们的差能被2n整除，不同则它们的和能被2n整除。证明成立。

2.7 一个网站在9天中被访问了1800次，证明：存在连续的3天，这个网站的访问量超多600次。
证明：
设网站在9天中访问数分别为a1，a2，...，a9 其中a129 = 1800，
令a123 = b1，a456 = b2，a789 = b3
因为（b123）/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 将一个矩形分成(1)行列的网格每个格子涂1种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。
证明：
（1）对每一列而言，有（1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。
（2）每列中两个单元格的不同位置组合有种，这样一列中两个同色单元格的位置组合共有 种情况
（3）现在有列，根据鸽巢原理，必有两列相同。证明结论成立。
2.10 一名实验员在50天里每天至少做一次实验，而实验总次数不超过75。证明一定存在连续的若干天，她正好做了24次实验。
证明：令b1，b2，...，b50 分别为这50天中他每天的实验数，并做部分和
a1 = b1，a2 = b12 ，。。
a50 = b1250 .
由题，>=1(1<<=50)且a50<=75
所以 1<1<a2<a3<…<a50<=75 (*)
考虑数列 a1，a2，...，a50，a1+24，a2+24，a50+24，它们都在1与75+24=99之间。
由鸽巢原理知，其中必有两项相等。由（*）知，a1，a2，...，a50互不相等，从而a1+24，50+24 也互不相等，所以一定存在1<<j<=50, 使得 = 24，即 24(b123+……)-(b12+…)=
所以从第1天到第j天这连续天中，她正好做了24次实验。

2.11 证明：从{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个数为
a12,…70,
a1+42+4,…70+4,
a1+92+9,…70+9,
取值范围209，共210个数

2.13 证明：对于任意大于等于2的正整数n，都有R(2)。
证明：
要证R（2，n）= n，用红蓝两色涂色的边。
当2时，R(2,2)=2，因为不管用红还是蓝色都是完全二边形。
假设当时 成立 ，即存在R(2)（没有一条红边，只有蓝边），
当1时，R（2，1）
若无红边，要想有完全1边形，必得有1个点，即R（2，1）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.3 18名排球运动员被分成三个组，使得每组有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.7 15个人围坐一个圆桌开会，如果先生A拒绝和先生B和C相邻，那么有多少种排坐方式？
解：15人圆排列14！；
A与B相邻有2*1414=2*13!；
A与C相邻有2*1414=2*13!；
A与同时相邻有2*1313=2*12!；
于是A不与B、C相邻的坐法共14 2*13 2*13 2*12!（用到了容斥原理）
3.8 确定多重集的11-排列数？
解：M的11排列=[{a}]的11排列+[{b}]的11排列+[{c}]的11排列，即=27720
当然了，容斥原理，生成函数也可以做。
3.9求方程，满足的整数解的个数。
解：令
则有，由定理3.3.3，解个数为：

3.10书架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少种？
解：20，4，
证明见38页。
若卷号差为2，3，。。。。。，公式为？

3.11确定(23y)5展开式中x4y和x2y4的系数。
解：1）：，系数为-240
2）：系数为0。

3.12确定(1)-5展开式中x4的系数。
解：，5，4，则系数为

3.13 确定(x +23z)8展开式中x4y2x2的系数。
解：
3.14 证明组合等式：，其中为正整数。
解：右边是（1）元集合上k个元素子集的个数，这些子集可分为以下1类：
第1类：k元子集中不含a1的子集有 个;

第2类：k元子集中含a1而不含a2的子集是 个;

第3类：k元子集中含a1和a2，而不含a3的子集是
……
第1类：k元子集中含a1，a2，……, ，而不含1的子集是
由加法原理得证。
根据组合意义进行证明
3.15利用 ，求。
解： 首先有：
（p51的(3)）
根据已知条件代入以上等式得：

又由
得，
则原式
3.16在一局排球比赛中，双方最终的比分是25:11，在比赛过程中没有出现5平的比分，求有多少种可能的比分记录？
解：根据题意，相当于求从点(0,0)到点(25,11)且不经过(5,5)的非降路径数，即为：

3.17在一局乒乓球比赛中，运动员甲以11:7战胜运动员乙，若在比赛过程中甲从来没有落后过，求有多少种可能的比分记录？
解：根据题意，相当于求从点(0,0)到点(11,7)且从下方不穿过的非降路径数，见58页，即为：

3.18把20个苹果和20个橘子一次一个的分发给40个幼儿园的小朋友，如果要求分发过程中任意时刻篮子中余下的两种水果数目都不相同（开始和结束时除外），求有多少种分法方法？
解：根据题意，相当于求从点(0,0)到点(20,20)且不接触的非降路径数，即为：
20，则方法数为：

3.19计算和。
解：1）

一个递推公式，

2）

3.20 （1）证明 S(n,3)=
方法一：先 考虑3个盒子不同，要保证每个盒子非空：总数为3n，排除到一个盒子为空和两个盒子为空的情况，即：
一个盒子为空（放到两个盒子去），例如第一个盒子为空,第二和第三不空：3（ 22）
两个盒子为空，例如第一个和第二盒子为空：3*1
（33（ 22）-3）/3!
还可以直接考虑盒子相同。
（2）证明：相当于n个不同球放到相同的2个盒子，每个盒子非空，至少为1个，这样使得剩余的2个球要到2个盒子，即使得一个盒子有3个，或有二个盒子都装2个球：
使得一个盒子有3个球：C(n,3)
有二个盒子都装2个球：C（n,4）C(4,2)/2!

3.21（1）会议室中有21个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？
解：如果没有附加限制则相当于把2n个相同的小球放到3个不同的盒子里，有种方案，而不符合题意的摆法是有一排至少有1个座位。这相当于将1个座位先放到3排中的某一排，再将剩下的2(1)1个座位任意分到3排中，这样的摆法共有种方案，所以符合题意的摆法有：

可以用代数法
(2) 会议室中有2n个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？
习题四
4.1 在1到1000之间不能被2，5和11整除的整数有多少个？
解：设S是这1000个数的集合，性质是可被2整除，性质是可被5整除，性质是可被11整除。

，，
，，，

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

4.2 求1到1000之间的非完全平方，非完全立方，更不是非完全四次方的数有多少个？
解：设S是1000个数的集合，
性质是某数的完全平方，
性质是某数的完全立方，
性质是某数的完全四次方。
，，
，，，

4.4某杂志对100名大学新生的爱好进行调查，结果发现他们都喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求有多少人只喜欢看电影？
解：由题意可得，P123分别表示喜欢看球赛、电影和戏剧的学生，相应的学生集合分别为A123，依题意，这100名大学生中每人至少有三种兴趣中的一种，则
所以可得既喜欢看球赛有喜欢看电影的人有

因此只喜欢看电影的人有
=52-(26+16)+12=22人

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

4.6 计算多重集{4•a, 3•b, 4•c,6•d }的12-组合的个数？
解：令
其中，，
，，
，，，，， ，

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

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

4.8 用容斥原理确定如下两个方程的整数解的个数。
1）x123=15，其中x12, x3都是非负整数其都不大于7；
2）x1234=20，其中x12, x3, x4都是正整数其都不大于9；
解：
1）与{7a,7b,7c}的15组合数相等，为28
2）
，因此用代替，代替，代替，代替有
与{8a,8b,8c,8d}的16组合数相等为489

4.9 定义D0=1，证明：
证明：考虑到n个数的全排列包含错位排列和非错排，其中表示在n个数中任选k个，这个k个数构成了一个错排，而剩余的个数还在原来的位置。
，显然
（另一种方法：组合分析法）

4.10证明：满足：
　　ｎ为整数且ｎ３
证明：由定理4.3.1得

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

雨伞全错为解

4.13计算棋盘多项式R( )。

解：
R( ) = x*R()( )
*(1+32)+(1)*R( )
= x3+3x2(1)[()()]
= x3+3x2(1)[x(1)+(1+42x2)]
= 5x3+12x2+71

4.14有五种型号的轿车，用红、白、蓝、绿、黑五种颜色进行涂装。要求A型车不能涂成黑色；B型车不能涂成红色和白色；C型车不能涂成白色和绿色；D型车不能涂绿色和蓝色；E型号车不能涂成蓝色，求有多少种涂装方案？
解：A B C D E
红
白
蓝
绿
黑
1.若未规定不同车型必须涂不同颜色，则：
涂装方案
2.若不同车型必须涂不同颜色，则：
禁区的棋盘多项式为：
1+822x2+25x3+11x45
所以：
5！-8*4！+22*3！-25*2！+11*1！-1=20
4.15计算
（舍）
4.16计算{∞•1, ∞•2, ∞•3，∞•4}的长度为4的圆排列数。
（舍）
补：（1）在1~2000中能被7整除，但不能被6和10整除的个数。
证明：A123表示被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不同的链的数量。
解： 中的系数，有=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设表示把元集划分成非空子集的方法数，我们称为数。
证明：。
证明：当有1个盒子时，方法数，
当有2个盒子时，方法数，

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

当有n个盒子时，方法数，
当有1个盒子时，至少有一个空盒，不符。
故

5.12有重为1g的砝码重为1g的3个，重为2g的4个，重为4g的2个，求能称出多少种重量？
解：即求多项式中展开式有多少项
(除1外)，原多项式
故共有19种重量。
5.13 已知数列的指数生成函数是，求.
解：设
5, k不等于2
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）

6.5 平面上有n条直线，它们两两相交且沿有三线交于一点，设这n条直线把平面分成个区域，求的递推关系并求解.
解：设1条直线把平面分成个区域，则第n条直线与前1条直线都有一个交点，即在第n条直线上有1个交点，并将其分成n段，这n段又把其所在的区域一分为二。

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

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

在1时刻

在t时刻

补：上有n个大圆，任意两个大圆皆相交，且没有三个大圆通过同一点，则这些大圆所形成的区域数f(n)满足的递推关系是
f(1)= f(n)+2n，n>1(1)=2，f(n)可以由f(n)来生成，当在f(n)个大圆的基础上，在球面上再加上第1个大圆时，它同前n个大圆共得到2n个交点(因无三个大圆相交于一点)，而每增加一个交点就增加一个新的面，故共增加2n个面。所以有f(1)= f(n)+2n。
设P是平面上n个连通区域D12,…的公共交界点，如下图所示。现用k种颜色对其着色，要求有公共边界的相邻区域着以不同的颜色，令f(n)表示不同的着色方案。
求它所满足的递推关系。
有： f(n)= (1)f(2)+(2)f(1)（n≥4）f(2)(1) f(3)(1)(2)

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

(1)f(2)+(2)f(1)
另有：f(n)(1)1(1)

第七章

例n种颜色涂色装有7颗珠子的手镯，如果只考虑手镯的旋转，求有多少种涂色方案？
解 对象集D＝{1,2,3,4,5,6,7}，颜色集是R＝(1,2,3,…)，D上的置换群G＝{g012,…6}，其中表示旋转360°*7，因7是质数，所以除λ(g0)＝7外，其它λ()＝1，(1,2,3,4,5,6)，代入公式，得
L＝1/7*[n7+6n]

而四边形：转180时
P22 6,8,9