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

《组合数学引论课后答案(部分).docx》由会员分享，可在线阅读，更多相关《组合数学引论课后答案(部分).docx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学引论课后答案习题一1.1 任何一组人中都有两个人，它们在该组内认识的人数相等。1.2 任取 11 个整数，求证其中至少有两个数，它们的差是 10 的倍数1.3 任取 n+1 个整数，求证其中至少有两个数，它们的差是 n 的倍数1.4 在 1.1 节例 4 中证明存在连续的一些天，棋手恰好下了 k 盘棋(k=1,2,，21).问是否可能存在连续的一些天，棋手恰好下了 22 盘棋2bllbb-l=f”2。令证明设 伈 妇，妗 分别为这11 周内他每天下棋的盘数 ，叶 b1 舫 b-n由于 bi ;:a= 1( 1冬ii )和 bi +bi+1 + + h:i+612( 1 冬 i71) 警

2、所以J 冬a 1 a2 : . a7112 x 11 = 132考虑序列a, a2, 宜，77, a1 +，k，2 十 k ,. , 。71 k(补)它们的值都是 I -132 + k 之间的整数。由于 k21，所以 132 +k153，而序列（希） 的项数为1习，由鸽巢原理可知豐序列( * )中a1, a2, , a”.与 ,a 1 -1- k, ai+ 从 , a 71 + k 之间必有2 项相等，即存在 1 i j 77， 使aj = a, + 1则k = a 一 ” i = bi+l + b心 bi即从第 i + 1 天到第j 天这连续j - ,i 天中,.他刚好下了K 盘棋。当 k

3、= 22 时，只有两种情况：(l)a l ,“ 2, 嘈. ，a 7J, a1 4 22, a,2 t 22 , 嘈. 鲁” “+2 2 这 I又项中有2 项相等。此时由上面的讨论知结论成立 ，即他在连续若干夭恰好下 22 盘棋。(2) ai, a2,., a:r, a1 + 22, a2 + 22, , a71 + 22 这154项中没有 2 项是相等的。此时它们恰好分别l取 154。由于,23121 + 22 ,a 2 + 22 u= 600 由推论2.2.2知，b1，b2，b3中至少有一个数大于等于600。所以存在有连续的三天，访问量大于等于600次。2.8 将一个矩形分成 5 行 41

4、 列的网格，每个格子涂 1 种颜色，有 4 种颜色可以选择，证明： 无论怎样涂色，其中必有一个由格子构成的矩形的 4 个角上的格子被涂上同一种颜色。证明：首先对一列而言，因为有5行，只有4只颜色选择，根据鸽巢原理，则必有两个单元格的(5)颜色相同。另外，每列中两个单元格的不同位置组合有 2 =10种，这样一列中两个同色单元格的位置组合共有10*4=40种情况。而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。(m + 1)2.9 将一个矩形分成(m+1)行m2+ 1列的网格每个格子涂 1 种颜色，有 m 种颜色可以选择，证明

5、：无论怎么涂色，其中必有一个由格子构成的矩形的 4 个角上的格子被涂上同一种颜色。证明：（1） 对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。(m + 1)（2） 每列中两个单元格的不同位置组合有2种，这样一列中两个同色单元格的位置组合(m + 1)共有2m 种情况(m + 1)（3） 现在有m2+ 1列，根据鸽巢原理，必有两列相同。证明结论成立。2.10 一名实验员在 50 天里每天至少做一次实验，而实验总次数不超过 75。证明一定存在连续的若干天，她正好做了 24 次实验。证明：令b1，b2，.，b50 分别为这50天中他每天的实验数，并做部分和a1 = b

6、1，a2 = b1+b2 ，。a50 = b1+b2+.+b50 .由题，bi=1(1=i=50)且a50=75 所以 1=a1a2a3a50=75(*)考虑数列 a1，a2，.，a50，a1+24，a2+24，a50+24，它们都在1与75+24=99之间。由鸽巢原理知，其中必有两项相等。由（*）知，a1，a2，.，a50互不相等，从而a1+24，.a50+24 也互不相等，所以一定存在1=ij=50, 使得aj = ai+24，即24=aj-ai=(b1+b2+b3+bi+bj)-(b1+b2+bi)= bi+ b1i+ 2+ .+ bj所以从第i+1天到第j天这连续j-i天中，她正好做了

7、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 证明：从1200中任意选取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。证明：

8、要证 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！所以有C5 *5!*5!10! ，共 14400

9、 种不同的安排方法。103.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 名运动员，那么有多少种分法？解：1) C 6 *C 6 *C 6 种181262) C 6 *C 6 *C 6 /3!181

10、263.4 教室有两排，每排 8 个座位。现有学生 14 人，其中的 5 个人总坐在前排，4 个人总坐在后排，求有多少种方法将学生安排在座位上？解：前排 8 个座位，5 人固定，共C5 *5! 种方法；后排 8 个座位，4 人固定，共C 4 *4! 种方法；88前排和后排还剩 7 个座位，由剩下的 5 人挑选 5 个座位，共C5 *5! 种方法；则一共有7C5 *C 4 *C5 *5!*5!*4! 种安排方法。8873.5 将英文字母表中的 26 个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？解：先排 21 个辅音字母，共有 21！再将 5 个元音插入到 22 个空隙中， P

11、522故所求为 21!P522(插入法)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 与

12、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! =277202!4!5!3!3!5!3!4!4!当然了，容斥原理，生成函数也可以做。3.9 求方程 x + x12+ x + x34= 20 ，满足 x1 2

13、, x2 0, x3 5, x4 -1 的整数解的个数。解：令 y1= x - 2 0, y12= x 0, y23= x - 5 0, y34= x + 1 04则有 y + y12+ y + y34= 14 ，由定理 3.3.3，解个数为： 14 + 4 -1 = 17 = 17 = 680141433.10 书架上有 20 卷百科全书，从中选出 4 卷使得任意两本的卷号都不相邻的选法有多少种？解：n=20，r=4， n - r + 1 = 20 - 4 + 1 = 17 = 2380r4 4 证明见 38 页。若卷号差为 2，3，。，公式为？3.11 确定(2x-3y)5 展开式中 x4

14、y 和 x2y4 的系数。解：1） x4 y ： C 4 *(2 x)4 *( -3y)1 ，系数为-24052） x2 y4 ：系数为 0。3.12 确定(1+x)-5 展开式中 x4 的系数。解：- n + r -1，n=5，r=4，则系数为 5 + 4 -1(1+ x) n =(-1)r xr(-1)4 = 70r =0r43.13 确定(x +2y+3z)8 展开式中 x4y2x2 的系数。解：8!4!*2!*2!*2 2 *32 = 151203.14 证明组合等式： n + n +1 + n + 2 +L + n + k = n + k +1 ，其中 n,k 为正整数。 0 1 2

15、 kk 解：右边 n + k + 1 是（n+k+1）元集合S = a , a ,., a上 k 个元素子集的个数，这些子集可k12n+k +1分为以下 k+1 类： n + k 第 1 类：k 元子集中不含 a 的子集有个; k1 n + k - 1第 2 类：k 元子集中含a 而不含 a 的子集是k - 1 12个; n + k - 2第 3 类：k 元子集中含a 和 a ，而不含 a 的子集是123 k - 2 n 第 k+1 类：k 元子集中含 a ，a ，, a ，而不含 a的子集是12k由加法原理得证。k+1 0 根据组合意义进行证明 k k 213.15 利用 k 2 = 2 +

16、 ，求12 + 22 +L + n 2 。 解： 首先有： n +1 n n -1 0 k + = + +L + （p51 的(3)）1 k k k 根据已知条件代入以上等式得：nn i i 1 1 2 2 n n 21212121i2 =(2 + ) = 2 + + 2 + + . + 2 + i=1i=1 = 2 1 + 2 2 . + 2 n + 1 + 2 + . + n 2 2 2 1 1 1 = 2( 1 + 2 . + n ) + 1 + 2 + . + n 2 2 2 1 1 1 k k k k + 1又由 1 + 2 + . + n = n +1 1 1 1 2 2 223得

17、1 + 2 + . + n = n +1 ， 1 + 2 + . + n = n +1 3 2 666则原式= 2 n +1 + n +1 = 2(n -1)n(n +1) + n(n +1) = n(n +1)(2n +1)3.16 在一局排球比赛中，双方最终的比分是 25:11，在比赛过程中没有出现 5 平的比分，求有多少种可能的比分记录？解：根据题意，相当于求从点(0,0)到点(25,11)且不经过(5,5)的非降路径数，即为： 25 +11 5 + 5 25 - 5 +11- 536 10 2611 - 5 11- 5 = 11 - 5 6 3.17 在一局乒乓球比赛中，运动员甲以 1

18、1:7 战胜运动员乙，若在比赛过程中甲从来没有落后过，求有多少种可能的比分记录？解：根据题意，相当于求从点(0,0)到点(11,7)且从下方不穿过 y=x 的非降路径数，见 58 页，即为： 11+ 7 -1- 11+1+7-211-1 11+1 3.18 把 20 个苹果和 20 个橘子一次一个的分发给 40 个幼儿园的小朋友，如果要求分发过程中任意时刻篮子中余下的两种水果数目都不相同（开始和结束时除外），求有多少种分法方法？ 解：根据题意，相当于求从点(0,0)到点(20,20)且不接触 y=x 的非降路径数，即为： 2n - 2 2n - 2 2 2n 2( n -1 - n) = n

19、+1 n n=20，则方法数为： 38 38 19202( - )3.19 计算7 和 7 。33 7 = 6 + 36 = 5 + 2 5 + 3 5 + 35323 2 23 1 解：1） = 1+ 5 5 + 9 5 = 1+ 5 4 + 2 4 + 9 4 + 3423 12 23 = 6 +19*7 + 27*6 = 301一个递推公式， n = n = nn2 = 2n-1 -1 2n - 1n -1 2）7 = 6 + 6 6 = 5 + 5 5 + 6 5 + 5 5 33312 23 = 1+115 + 30 5 = 1+11 4 + 4 4 + 30 4 + 4 4 23

20、12 23 = 1+11(1+ 4*11) + 30(11+ 4* C 2 ) = 154643.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 个，

21、或有二个盒子都装 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 + 22n = 种方案，而不符合题意的摆法是有一排至少有 n+1 个座位。这相当于将2n+1 个座位先放到 3 排中的某一排，再将剩下的 2n-(n+1)=n-1 个座位任意分到 3 排中，这样 2n - (n +1) + 3 -1 n +1的摆法共有3 2 =

22、3 2 种方案，所以符合题意的摆法有：2 22 2n + 2 - 3 n +1 = n + 2可以用代数法(2) 会议室中有 2n 个座位，现摆成 3 排，要求任意两排的座位都占大多数，求有多少种摆法？习题四4.1 在 1 到 1000 之间不能被 2，5 和 11 整除的整数有多少个？解：设 S 是这 1000 个数的集合，性质 P 是可被 2 整除，性质 P 是可被 5 整除，性质 P 是可被 11 整除。123A =x | x S x具有性质P,( i = 1,2,3)ii| A |= 1000/ 2 = 500 ，| A12|= 1000/5 = 200，| A3|= 1000/11

23、= 90| A A12|= 1000/10 = 100 ，| A A13|= 1000/ 22 = 45 ，| A A23|= 1000/ 55 = 18 ，| A A A23|= 1000/110 = 91| A1 A A23|= 1000 - (500 + 200 + 90) + (100+ 45 +18) - 9 = 3644.3 一项对于 A,B,C 三个频道的收视调查表明，有 20%的用户收看 A，16%的用户收看 B，14% 的用户收看 C，8%的用户收看 A 和 B，5%的用户收看 A 和 C，4%的用户收看 B 和 C，2%的用户都看。求不收看 A,B,C 任何频道的用户百分比

24、？解| A A A |= 1- (20% +16% +14%) + (8% + 5% + 4%) - 2% = 65%1234.2 求 1 到 1000 之间的非完全平方，非完全立方，更不是非完全四次方的数有多少个？ 解：设 S 是 1000 个数的集合，性质 P1是某数的完全平方，性质 P 是某数的完全立方，2性质 P 是某数的完全四次方。 A =x | x S x具有性质P,( i = 1,2,3)3ii| A |= 1000 = 31，| A |= 3 1000 = 10 ，| A |= 4 1000 = 5123| A A|= 6 1000 = 3，| A A|= 4 1000 = 5

25、，| A A |= 12 1000 = 1，121323| A A12 A |= 12 1000 = 13| A A12 A |= 1000 - (31+10 + 5) + (3 + 5 +1) -1 = 96234.4 某杂志对 100 名大学新生的爱好进行调查，结果发现他们都喜欢看球赛和电影、戏剧。其中 58 人喜欢看球赛，38 人喜欢看戏剧，52 人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18 人，既喜欢看电影又喜欢看戏剧的有 16 人，三种都喜欢看的有 12 人，求有多少人只喜欢看电影？解：由题意可得，P1,P2,P3 分别表示喜欢看球赛、电影和戏剧的学生，相应的学生集合分别为 A1,

26、A2,A3，依题意，这 100 名大学生中每人至少有三种兴趣中的一种，则 A1 A2 A3 = 0所以可得既喜欢看球赛有喜欢看电影的人有| A A12|= (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

27、 次晚餐而没碰见任何一位朋友，问他共在外面吃过几次晚餐?C1 12 - C 2 6 + C3 4 - C 4 3 + C5 2 - C 6 1+ 8 = 366666664.6 计算多重集 S=4a, 3b, 4c,6d 的 12-组合的个数？12解：令T = a, b, c, d的所有12组合构成W = 4 +12 -1 = 455其中 4 + 7 -1， 4 + 8 -1，| A |= = 120| A |= = 1651728| A |= 4 + 7 -1 = 120 ，| A |= 4 + 5 -1 = 56，3745| A A|= 4 + 3 -1 = 20，| A A|= 4 +

28、2 -1 = 10 ，| A A|= 4 + 0 -1 = 1 ，123132140| A A|= 4 + 3 -1 = 20，| A A |= 4 +1-1 = 4，| A A |= 4 + 0 -1 = 1，233241340| A A12 A |= 03| A1 A A A234|= 455 - (120+120 +165 + 56) + (20 +10 +1 + 20 + 4) = 504.7 计算多重集 S=a, 4b, 5c,6d 的 10-组合的个数？ 解：将 a ，其他思想同上题。 4 +10 -1W = 10 = 286 4 + 5 -1 4 + 4 -1 4 + 3 -1其

29、中| A|= 0 ，| A|= = 56，| A|= = 35，| A|= = 20，1253443| A A12|= 0，| A A13|= 0 ，| A A14|= 0，| A2 A |= 0，| A A324|= 0 ，| A A34|= 0，| A A12 A |= 03| A A12 A A34|= 286 - (56 + 35 + 20) = 1754.8 用容斥原理确定如下两个方程的整数解的个数。1）x +x +x =15，其中 x ,x x 都是非负整数其都不大于 7；12312, 32）x +x +x +x =20，其中 x ,x x x 都是正整数其都不大于 9；1234解：12, 3, 41）x + x + x123为 282）= 15(0 x1 7,0 x2 7,0 x3 7)与7a,7b,7c的 15 组合数相等，x + x12+ x + x34= 20(1 x1 9,1 x2 9,1 x3 9,1 x4 9)，因此用 y +1代替1x ， y +1代替 x ， y +1代替 x ， y +