内容发布更新时间 : 2024/11/15 8:23:13星期一 下面是文章的全部内容请认真阅读。

习 题 四

习题四（容斥原理）

1．试求不超过200的正整数中素数的个数。

解：因为152?225,132?169，所以不超过200的合数必是2,3,5,7,11,13的倍数，

而且其因子又不可能都超过13。

设Ai为数i不超过200的倍数集，i?2,3,5,7,11,13，则

?200??200??200??200? A2??，，， ?100A??66A??40A??28，357????????2??3??5??7??200??200??200? A11??，，?18A??15AA??33， 1323?????11132?3???????200??200??200?，，AA??9， A2A5???20AA??1421127??????2?11??2?5??2?7??200??200??200?，，A2A13???7AA??9， AA??133735?????2?133?73?5???????200??200??200?，，AA??5， A3A11???6AA??557313??????5?7??3?11??3?13??200??200??200?，，A5A11???3AA??2， AA??3711513?????5?117?115?13???????200??200??200?，，A7A13???2AA??1AAA??6， 1113235??????7?13??11?13??2?3?5??200??200??200?，，A2A3A7???4AAA??3AAA??2 23112313?????2?3?72?3?112?3?13???????200??200??200?A2A5A7???2AAA??1AAA??1，，， 25112513??????2?5?7??2?5?11??2?5?13??200??200?A2A7A11???1AAA??1， ，2713???2?7?112?7?13?????200??200??200?A2A11A13???0AAA??1 AAA??1，，3511357?????2?11?133?5?113?5?7??????第1页（共11页）

习 题 四

?200??200?，A3A5A13???1AAA??0，…， 3711????3?5?13??3?7?11?200?200???，…， A2A3A5A7???0AAAAAA??0，23571113???2?3?5?72?3?5?7?11?13????A2?A3?A5?A?7i?ijA?A1311?i?jk?S??A??A?iiAj??i?j?k?l?mA?iAjAk?AiAjAkAll?i?j?k?AiAjAkAlA?m?i?AiAjAkAlAmAn?jk??lm?n?(1?00?66?40?2?81815)所以 ?200

?(33?2?0?14?9?7?1?3?9?6?5??5?3?32?(6?4??3?2?2?1?1??1?1?0?1?0)1?01?0?0?4121)但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中， 故所求的素数个数为：41?6?1?46

2．问由1到2000的整数中：

（1）至少能被2，3，5之一整除的数有多少个？

（2）至少能被2，3，5中2个数同时整除的数有多少个？ （3）能且只能被2，3，5中1个数整除的数有多少个？ 解：设Ai为1到2000的整数中能被i整除的数的集合，i?2,3,5，

?2000??2000??2000?A??666A??400， 则A2??，，?100035?????352???????2000??2000??2000??333AA??200 A2A3??，，AA??133， 2535??????2?3??2?5??3?5??2000??66， A2A3A5???2?3?5?? （1）即求A2?A3?A5，根据容斥原理有：

A2?A3?A5?A?(AA2?A2A?3A?53A?2A5A)?3A5AA235 ?1000?666?400?(333?200?133)?66?1466

（2）即求A2A3?A2A5?A3A5，根据容斥原理有：

第2页（共11页）

习 题 四

A2A3?AA2?5AA35235 ?A2A3?AA(AAAAA2?5AA3?52?3A5AA2?35A)?2A3A5A

?333?200?133?2?66?534 （3）即求N[1]，根据Jordan公式有：

11N[1]?q1?C2q2?C3q3

?A2?A3?A5?2?(A2A3?A2A5?A3A5)?3?A2A3A5?1000?666?400?2?(333?200?133)?3?66?932

3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。 解：设Ai为1到500的整数中能被i整除的数的集合，i?3,5,7，

?500??500??500? 则A3??，，?166A??100A??71， 57?????357???????500??500??500? A3A5??，，?33AA??14， AA??235737??????3?5??5?7??3?7??500? A3A5A7???4， ?3?5?7?? 满足条件的整数个数为：A3A5A7，根据容斥原理有： A3A5A7?

4．某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次。问该人共参加几次会议？ 解：设S为该人参加的所有会议组成的集合，

设Ai表示该人与第i个朋友相遇的所有会议构成的子集，i?1,2,?,6，则 R1?Ai?12，i?1,2,?,6

R2?AiAj?6，R3?AiAjAk?4，R4?AiAjAkAl?3，R5?AiAjAkAlAm?2，

A1 R6?A1A2A3A4A5?6，

A3A?5A3A5A?373?4?2 9A1?A2?A3?A4?A5?A6 则，

135?C6R1?C62R2?C6R3?C64R4?C6R5?C66R6?6?12?15?6?20?4?15?3?6?2?1?28

则该人共参加会议次数为： S?28?5?33（次）。

第3页（共11页）

习 题 四

5．n位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？ 解：设S表示所有n位四进制数构成的集合，

Ai为不出现i的数的集合，i?1,2,3，

则A1?A2?A3?3n，A1A2?A1A3?A2A3?2n，A1A2A3?1， 则由逐步淘汰原理，可得

6．某照相馆给n个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能？

（1）没有任何一个人得到自己的照片； （2）至少有一人得到自己的相片； （3）至少有两人得到自己的照片；

解：以任一种装法为元素构成的集合记为S，则S?n!。

设Ai表示第i个人拿到自己的照片的所有装法组成的集合。则公共数

R1?Ai?(n?1)!，同理R2?AiAj?(n?2)!，……， Rk?Ai1Ai2?Aik?(n?k)!,k?1,2,?,n

A1?A2?A3?S?(A1?A2?A3)?(A1A2?A1A3?A2A3)?A1A2A3?4?3nn?1?3?2?1n

（1）即求N[0]，由问题的性质可知，这是一个错排问题，所以

1??11N[0]?Dn?n!?1?????(?1)n?

n!??1!2!1??11 （2）即求L[1]，L[1]?S?N[0]?n!?Dn?n!?????(?1)n?1?

n!??1!2!? 方法二：

问题即：将所有可能的分配方案－没有任何一人得到自己的照片的方案，则，符合条件的方案数为：n!?Dn， ? 方法三：

问题即求：

?n??n?n?1?n?A1?A2???An???R1???R2?????1???Rn?1??2??n?

n?11??111?n!????????1??n!??1!2!3!第4页（共11页）

习 题 四

（3）问题即求：L[2]?S?N[0]?N[1]，

L[2]?S?N[?0N][1])3)!3!n!?2)!?n?(2n!?3!(3)!

11213n?1n1?n!?Dn?(C1Cn1R1?CC(1)CnC2nR?2CCn3R??3??nRn

2!n!?n!?Dn?(n?n(?1?)!?n?(1!2n!(?2)!n!n!???(?1)n?1?0!)(n?1)!n!0!??111?n!?Dn?n??(n?1)!(1?????(?1)n?1)?1!2!(n?1)!???n!?Dn?nDn?1

7．把{a,a,a,b,b,b,c,c,c}排成相同字母互不相邻的排列，有多少种排法？

9!解：设S为所有排列的组成的集合，则S??1680，

3!3!3! 设Ai：表示排列中有相邻i个元素都是a的排列集合；i?2,3；

设Bi：表示排列中有相邻i个元素都是b的排列集合；i?2,3； 设Ci：表示排列中有相邻i个元素都是c的排列集合；i?2,3； 则：A3?B3?C3?7!5!?140，A3B3?A3C3?B3C3??20， 1!3!3!1!1!3! A3B3C3?3!?6，（即将aaa、bbb或ccc看为一个元素）

A2?B2?C2?8!7!??1120?140?980

1!1!3!3!1!3!3!（将aa与a看做为不同的两个元素参与排列，但在出现aaa时就重复计算，(aa)a、a(aa)看为两个不同的排列，因此aaa多计算了一次）

因为A2?B2为aa,bb图象都出现的排列集合，当我们将aa与a，bb与b看作不同的两对元素进行排列时，在aa与a相遇而成aaa图象及bb与b相遇而成bbb图象时会产生重复计数。

1q2） 当aaa图象与bbb图象恰出现一个时，重复因子为2；（N[1]?q1?C2当图象aaa与图象bbb同时出现时，重复因子为4。 所以A2B2?A2C2?B2C2?7!?6!6!5!?5!1????C2???3??580 3!?3!3!3!?3!因为A2?B2?C2为aa，bb，cc图象出现的排列集合，当我们将aa与a，bb与b，cc与c看作不同的三对元素进行排列时，在aa与a相遇而成aaa图象，bb

第5页（共11页）