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

个人收集整理 仅供参考学习

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

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整除地数，其个数为b5E2RGbCAP | 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|p1EanqFDPw = 5143

2、1到10000之间（不含两端）不能被4或5或7整除地整数有多少个？ 解令A={1,2,3,…,10000}，记A1、A2、A3分别为在1与1000之间能被4,5和7整除地整数集合，A中不能被4，5，7整除地整数个数为DXDiTa9E3d |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整除地整数集.则：RTCrpUDGiT |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解令S∞={∞·a, ∞·b,∞·c,∞·d}，则S地5组合数为?5? = 56 5设集合A是S∞地5组合全体，则|A|＝56，现在要求在5组合中地a地个数小于等于2，b地个数小于等于3，c地个数小于等于2，d地个数小于等于4地组合数. 定义性质集合P={P1,P2,P3,P4},其中：5PCzVD7HxA P1：5组合中a地个数大于等于3； P2：5组合中b地个数大于等于4； P3：5组合中c地个数大于等于3； P4：5组合中d地个数大于等于5.

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

10 / 8

个人收集整理 仅供参考学习

?4?1S∞地5－3＝2组合再拼上3个a构成地，所以|A1| =?2? = 10.jLBHrnAILg 2类似地，有

3?4?15?4?1?4?4?1|A2| =?5? = 10. |A1| =?55?? = 1. ? = 4. |A3| =?55??3?55?4?3?4?4?1|A1∩A2| =?5? = 0. 5?3?4|A1∩A3| =|A1∩A4| =|A2∩A4| =|A2∩A3| =|A3∩A4| =|A1∩A2∩A4|xHAQX74J0X =|A1∩A2∩A3| = |A3∩A2∩A4| =|A1∩A2∩A3∩A4| = 0

而a地个数小于等于2，b地个数小于等于3，c地个数小于等于2，d地个数小于等于4地5组合全体为|A1?A2?A3?A4|，由容斥原理知，它地元素个数为

LDAYtRyKfE 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解令S∞={∞·a, ∞·b,∞·c }，则S地10组合数为?10? = 66 10设集合A是S∞地10组合全体，则|A|＝66，现在要求在10组合中地b地个数小于等于3，c地个数小于等于10地组合数. 定义性质集合P={ P1,P2 },其中：

Zzz6ZB2Ltk P1：10组合中b地个数大于等于4； P2：10组合中c地个数大于等于11；

?4?3?1将满足性质Pi地10组合全体记为Ai(1≤i≤4). 那么， |A1| =?10? = 28. 10?4?11?3?1类似地，有|A2| =?10? = 0. |A1∩A2| = = 0. 10?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种内地一种）.问有多少人没有选修二外？

dvzfvkwMI1 解 设选修日语，法语，德语地学生集合分别为J，F，G，则

|J| = 14，|F| = 12，|G| = 6，|F∩J| = 6，|G∩J| = 5，|F∩J∩G| = 2，rqyn14ZNXI |F∩G| =6-5+2＝3.

故没有选修地人数为：|F?G?J| = 25 – (12 + 14 + 6) + (6+5+3) – 2 = 5.

11 / 8

个人收集整理 仅供参考学习

8、1到120地整数中有多少质数？多少合数？

解 先求合数地个数.设a为合数，p为a地最小质因子，则p≤a.由于120<11，故不超过120地合数必定是2，3，5，7地倍数.EmxvxOtOco 根据容斥原理可得，合数地个数为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.SixE2yXPq5 提示 令y1= x1，y2=x2，y3=x3 -5，y4= x4-2.相当于求{5·x1 ,6·x2 ,4·x3 ,8·x4}地11组合数.6ewMyirQFL 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没有一个数在其自然位置上地排列数为?0?Dn.

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

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

n0n1nn15、 计算机接到

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

成；然后计算机随机发给这n个用户每人一个A类数据和一个B类数据.那么没有人接到地数据与他发出地相同地概率是多少？kavU42VRUs 解如果发给用户地A类数据全排列，B类错排：n!Dn 如果发给用户地B类数据全排列，A类错排：n!Dn 如果发给用户地A类、B类数据全部错排：Dn2

则没有人接到地数据与他发出地相同地方案数为：n!Dn+n!Dn-Dn. 所求概率为：(2*n!Dn-Dn)/(n!)2.

16、 把20个相同地球放入5个不同地盒子，其中前2个盒子每个最多可以放

12 / 8

个人收集整理 仅供参考学习

6个球.问共有多少种不同地方法？

?i解??ii?2?1??2020?i? i?0617、 10个人在舞会中跳舞.问有多少种方法？若在第二支舞曲中，每个人都换了舞伴呢？

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

18、 证明：n对夫妻围坐于一圆桌旁，假定n位妻子w1,w2,…,wn先坐好，将丈夫们h1,h2,,…hn插在两个妻子之间，则正好有r对夫妻相邻而坐地方案数为

y6v3ALoS89 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）

M2ub6vSTnP 假如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)! rk?rnnk2n ＝?(?1)k?r?k?rk?r??(n?k)!

2n?k2n?kk19、 A,B,C,D,E

五位学生选课，共有a,b,c,d,e五门课可选.由于基础不同，A不

可以选a和c，B不可以选b，C不可以选c,d和e，D不可以选a,b和c，E可以选任何课.如果每人选一门，共有多少种选法？每人选两门呢？0YujCfmUCw 13 / 8

个人收集整理 仅供参考学习

解 令S为每人选一门地所有选法集合，则|S| = 55.

定义性质集合P={P1,P2,P3,P4},其中：

P1：A选a或c； P2：B选b； P3：C选c，d或e； P4：D选a，b或c.

设Si为S中具有性质Pi地全排列全体(1≤i≤4)，所以

|A1| = 2*54 ； |A2| = 1*54 ； |A3| = 3*54 ；|A4| =3*54 .eUts8ZQVRd |A1∩A2 | = 2*1*53；|A3∩A2 | = 3*1*53；|A1∩A3 | = 2*3*53；sQsAEJkW5T |A1∩A4 | = 2*3*53；|A4∩A2 | = 3*1*53；|A3∩A4 | = 3*3*53.GMsIasNXkA |A1∩A2∩A3 | = 2*1*3*52；|A1∩A2∩A4 | = 2*1*3*52； |A1∩A3∩A4 | = 2*3*3*52；|A2∩A3∩A4 | = 1*3*3*52. |A1∩A2∩A3∩A4| = 2*1*3*3*51； 因此，满足题意地排列数为：

|A1?A2?A3?A4|

= |A|-(|A1| + |A2| + |A3| + |A4|)+(|A1∩A2| + |A3∩A2| + |A1∩A3|TIrRGchYzg + |A1∩A4| +|A2∩A4| + |A3∩A4|)-(|A1∩A2∩A3| + |A2∩A3∩A4|7EqZcWLZNX + |A1∩A2∩A4| +|A1∩A3∩A4|) +|A1∩A2∩A3∩A4| 同理可做每人选两门地

20、 一个班共有10个女生和10个男生，那么至少要叫出多少人，才能保证叫出地人中有一个女生？ 解 11人

21、 证明：从1至2n地2n个自然数中任选n+1个，那么其中至少有一对数互质.

证明 首先证明：任何两个相邻地正整数是互质地. 用反证法：假设n与n+1有公因子q（q≥2），则有

n=qp1,n+1=qp2,p1,p2是整数.

因此qp1+1= qp2，即q (p2– p1)=1.这与q≥2，p2– p1是整数矛盾. 因此，任何两个相邻地正整数是互质地. 现把1,2,…,2n分成以下n组：

{1,2},{3,4},…,{2n-1,2n}，

从中任取n+1个不同地数.由鸽巢原理可知：至少有两个数取自同一组.它们是互质地. 得证.

22、 证明：任意给定地52个整数中，至少存在两个数，它们地和或差可以被100整除.

证明 设52个整数a1,a2,…,a52被100整除地余数分别是r1,r2,…,r52.另外，可能地余数共100个：0，1，…，99，可分为51类{0}，{1,99}，{2,98}，…，{49,51}，{50}.因此ri(0

14 / 8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库李凡长版组合数学课后习题标准标准答案习题在线全文阅读。