李凡长组合数学课后习题答案习题

第二章 容斥原理与鸽巢原理

1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000.

记A1、A2、A3分别为在1与1000之间能被4,5和7整除的整数集合，则有：

|A1| = L10000/4」=2500, |A2| = L10000/5」=2000, |A3| = L10000/7」=1428,

于是A1∩A2 表示A中能被4和5整除的数,即能被20 整除的数，其个数为

| A1∩A2|=L10000/20」=500；

同理， | A1∩A3|=L10000/28」=357,

| A2∩A3|=L10000/35」=285,

A1 ∩A2 ∩ A3 表示A中能同时被4,5,7整除的数，即A中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为 文档来自于网络搜索 | A1∩A2∩A3|=L10000/140」= 71.

由容斥原理知，A中不能被4，5，7整除的整数个数为 |A1?A2?A3|

= |A| - (|A1| + |A2| +|A3|) + (|A1∩A2| + |A1∩A3| +|A3∩A2|) - |A1∩A2∩A3|文档来自于网络搜索 = 5143

2、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A1、A2、A3分别为在1与1000之间能被4,5和7整除的整数集合，A中不能被4，5，7整除的整数个数为 文档来自于网络搜索 |A1?A2?A3| = |A| - |A1?A2?A3| - 2 = 10000 - L10000/140」- 2 = 9927

3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多少个？

解 令A1表示在1与10000之间能被4和5整除的整数集，A2表示4和5整除，也能被7整除的整数集。则：文档来自于网络搜索 |A1| = L10000/20」= 500, |A2| = L10000/140」= 71,

所以1与10000之间能被4和5整除但不能被7整除的整数的个数为：500-71=429。 4、计算集合{2·a, 3·b, 2·c, 4·d}的5组合数.

?4?1? = 56 解 令S∞={∞·a, ∞·b,∞·c,∞·d}，则S的5组合数为?55设集合A是S∞的5组合全体，则|A|＝56，现在要求在5组合中的a的个数小于等于2，b的个数小于等于3，c的个数小于等于2，d的个数小于等于4的组合数. 定义性质集合P={P1,P2,P3,P4},其中： 文档来自于网络搜索 P1：5组合中a的个数大于等于3； P2：5组合中b的个数大于等于4； P3：5组合中c的个数大于等于3； P4：5组合中d的个数大于等于5.

将满足性质Pi的5组合全体记为Ai(1≤i≤4). 那么，A1中的元素可以看作是由

10 / 7

?4?1? = 10.文档来自于网络搜索 S∞的5－3＝2组合再拼上3个a构成的，所以|A1| =?22类似地，有

3?4?15?4?1?4?4?1? = 10. |A1| =?55?? = 1. ? = 4. |A3| =?55?|A2| =?5?3?55?4?3?4?4?1? = 0. |A1∩A2| =?55?3?4| A1∩A3| = | A1∩A4| = | A2∩A4| = | A2∩A3| = | A3∩A4| = | A1∩A2∩A4| 文档来自于网络搜索 = | A1∩A2∩A3| = | A3∩A2∩A4| =| A1∩A2∩A3∩A4| = 0

而a的个数小于等于2，b的个数小于等于3，c的个数小于等于2，d的个数小于等于4的5组合全体为|A1?A2?A3?A4|，由容斥原理知，它的元素个数为文档来自于网络搜索 56-(10+4+10+1)-(0+0+0+0+0+0)+(0+0+0)-0=31。 5、计算{∞·a, 3·b, 10·c}的10组合数.

?3?1? = 66 解 令S∞={∞·a, ∞·b,∞·c }，则S的10组合数为?1010设集合A是S∞的10组合全体，则|A|＝66，现在要求在10组合中的b的个数小于等于3，c的个数小于等于10的组合数. 定义性质集合P={ P1,P2 },其中： 文档来自于网络搜索 P1：10组合中b的个数大于等于4； P2：10组合中c的个数大于等于11；

?4?3?1? = 28. 将满足性质Pi的10组合全体记为Ai(1≤i≤4). 那么， |A1| =?1010?4?11?3?1? = 0. |A1∩A2| = = 0. 类似地，有 |A2| =?1010?11故由容斥原理知，所求组合数为 66-(28+0)-0 =38。 6、求集合{a·x, b·y, c·z}的m组合数（a,b,c全非无穷大）. 解 用上面的方法可以得出该集合的m组合数为：

????????????????????????????????????????3?m?1m3?m?a?1?1r?a?13?m?b?1?1r?b?13?m?a?b?2?1r?a?b?23?m?b?c?2?1r?b?c?2m?b?122?mmm?a?12m?c?12m?a?b2m?a?c2m?c?b2???????3?m?c?1?1r?c?13?m?c?a?2?1r?c?a?2??????3?m?c?a?b?3?1r?c?a?b?3?

m?a?b?c?12?7、 某班学生25人可以选修二外，其中有14人选修日语，12人选修法语，5人选修日语和德语，6人选修法语和日语，2人选修这3种语言，而且6个选修德语的都选了另一种外语（这3种内的一种）。问有多少人没有选修二外？文档来自于网络搜索 解 设选修日语，法语，德语的学生集合分别为J，F，G，则

|J| = 14，|F| = 12，|G| = 6，|F∩J| = 6，|G∩J| = 5，|F∩J∩G| = 2，文档来自于网络搜索 11 / 7

|F∩G| =6-5+2＝3。

故没有选修的人数为：|F?G?J| = 25 – (12 + 14 + 6) + (6+5+3) – 2 = 5。 8、1到120的整数中有多少质数？多少合数？

解 先求合数的个数。设a为合数，p为a的最小质因子，则p≤a。由于120<11，故不超过120的合数必定是2，3，5，7的倍数。文档来自于网络搜索 根据容斥原理可得，合数的个数为89，质数为119-89 = 30。 9、求方程x1 + x2 + x3 = 10的大于2的整数解的个数. 解 相当于求S={∞·a, ∞·b,∞·c }的10-2*3＝4组合数的个数。

?10、 求方程

4?3?14?＝15

x1 + x2 + x3 + x4 = 18的非负整数解的个数，其中0≤x1≤5, 0≤x2≤6, 5

≤x3≤9, 2≤x4≤10.文档来自于网络搜索 提示 令y1= x1，y2=x2，y3=x3 -5，y4= x4-2。相当于求{5·x1 ,6·x2 ,4·x3 ,8·x4}的11组合数。文档来自于网络搜索 11、 一花店某时只有6枝红玫瑰，7枝粉玫瑰和8枝黄玫瑰。这时要从中选12枝做花篮，问有多少种选法？ 提示 相当于求S={6·a, 7·b,8·c }的12组合数的个数。

12、 某人要给5个朋友每人一件生日礼物，问礼物全部送错的概率是多少？ 解 D5 = 5!

13、 对集合{1,2,…,10}的元素进行排列，恰有5个元素在其自然位置上的排列有多少种？

.解 任意选出5个元素放在其自然位置上，其余的全部错排：

??D5

10514、 说明组合恒等式

n!???D???Dn0nn1n?1?????D

nn0的组合意义.（设D0 = 1）

解 S={1,2,…,n}排列可分成下列情况：

n?Dn。 没有一个数在其自然位置上的排列数为?0恰有i（i=1,2,…,n）个数在其自然位置上的排列数为?in?Dn-i。 S的所有排列的个数为n!。根据加法原理，有： n! =

??Dn + ??Dn-1 +…+ ??D0

n0n1nn15、 计算机接到

n个用户的信号，每个信号都由一个A类数据加一个B类数据组

成；然后计算机随机发给这n个用户每人一个A类数据和一个B类数据。那么没有人接到的数据与他发出的相同的概率是多少？文档来自于网络搜索 解 如果发给用户的A类数据全排列，B类错排：n!Dn 如果发给用户的B类数据全排列，A类错排：n!Dn 如果发给用户的A类、B类数据全部错排：Dn2

则没有人接到的数据与他发出的相同的方案数为：n!Dn+ n!Dn- Dn。

12 / 7

所求概率为：(2* n!Dn- Dn)/( n!)2。

16、 把20个相同的球放入5个不同的盒子，其中前2个盒子每个最多可以放6个球。问共有多少种不同的方法？ 解

??i?06i?2?1i???

20?i20?i17、 10个人在舞会中跳舞。问有多少种方法？若在第二支舞曲中，每个人都换了舞伴呢？

解 从原来的每一对舞伴种选出一个，让这5个人错排：25D5。

18、 证明：n对夫妻围坐于一圆桌旁，假定n位妻子w1,w2,…,wn先坐好，将丈夫们h1,h2,,…hn插在两个妻子之间，则正好有r对夫妻相邻而坐的方案数为文档来自于网络搜索 n2nM(n,r)＝?(?1)k?r?k?rk?r??(n?k)! 2n?k2n?kk证明 设N是h1,h2,…,hn的所有排列的集合 令 A1：h1坐在w1右边的排列；

A2：h1坐在w1左边的排列； A3：h2坐在w2右边的排列；

A4：h2坐在w2左边的排列； ……

A2n-1：hn坐在wn左边的排列； A2n：hn坐在wn左边的排列。

注意：Ai和Ai+1不可能同时成立i=1,2,…,2n。

若依序将A1，A2，…，A2n沿一圆周排列，则 |Ai∩Ai+1| = 0 （i=1,2,…,2n）

文档来自于网络搜索 假如Ai1,Ai2,...,Aik沿圆周有两个相邻时，则Ai1?Ai2?...?Aik＝0。 总之：

（1） 对于整数k，n

a(k) =

1?i1?i2?...?ik?2n?Ai1?Ai2?...?Aik＝0。

（2） 对于1≤k≤n，根据n对夫妻问题，有

a(k) =

由容斥原理有：

M(n,r)＝?(?1)k?r?k r?a(k)k?r2n?r1?i1?i2?...?ik?2n?Ai1?Ai2?...?Aik＝

2nk?2n?k?1k?1??(n?k)!。

2n2n?k?1＝?(?1)k?r?k?k?1?(n?k)! r?k?rnkn2n ＝?(?1)k?r?k?rk?r??(n?k)!

2n?k2n?kk19、 A,B,C,D,E五位学生选课，共有a,b,c,d,e五门课可选。由于基础不同，A

13 / 7