容斥原理讲义.doc

骆老师教室容斥原理例题在很多计数问题中常用到数学上的一个包含与排除原理，也称为容斥原理。为了说明这个原理，我们先介绍一些集合的初步知识。在讨论问题时，常常需要把具有某种性质的同类事物放在一起考虑。如：A=五（1）班全体同学。我们称一些事物的全体为一个集合。A=五（1）班全体同学就是一个集合。例1. B=全体自然数=1，2，3，4，是一个具体的有无限多个元素的集合。例2. C=在1，2，3，100 中能被3 整除的数=3，6，9，12，99是一个具有有限多个元素的集合。例3. 通常集合用大写的英文字母A、B、C、表示。构成这个集合的事物称为这个集合的元素。如上面例子中五（1）班的每一位同学均是集合A 的一个元素。又如在例1 中任何一个自然数都是集合B 的元素。像集合B 这种含有无限多个元素的集合称为无限集。像集合C 这样含有有限多个元素的集合称为有限集。有限集合所含元素的个数常用符合A、B、C、表示。例4. 记号AB 表示所有属于集合A 或属于集合B 的元素所组成的集合，就是下边示意图中两个圆所覆盖的部分。集合AB 叫做集合A与的并集。“”读作“并”，“AB”读A B 例5. 设集合A=1，2，3，4，集合B=2，4，6，8， 则AB=1，2，3，4，6，8。元素2，4 在集合A、B 中都有，在并集中只写一个。记号AB 表示所有既属于集合A 也属于集合B 中的元素的全体。就是上面图中阴影部分所表示的集合。即是由集合A、B 的公共元素所组成的集合。它称为集合A、B 的交集。符号“”读作“交”，“AB”读作“A 交B”。如例3 中的集合A、B，则AB=2，4。例6. 设集合I=1，3，5，7，9，集合A=3，5，7，=属于集合，但不属于集合A 的全体元素=1，9。我们称属于集合I 但不属于集合A 的元素的集合为集合A 在集合I 中的补集（或余集），如下图中阴影部分表示的集合（整个长方形表示集合I），常记作。如例4 中 =1，9就是集合A在集合I 中的补集。显然，A 和没有公共元素，即A = （ 表示空集，即没有元素的集合）。A 此外，A =I。对于两个没有公共元素的集合A 和B，显然有AB=AB。例如，A=1，2，100， B=101， 则AB=1，2，100，101， AB= ，所以AB=101=1001=AB。如果集合A 与B 有公共元素，例如A =1，2，100， B =90，91，101，则AB =90，91，100， AB=1，2，100，101。此时，AB与AB有什么关系呢？在这个例中，AB=101，AB=10012=112，所以AB=AB11。我们注意到，11 恰为AB 的元素个数，这是合理的，因为在求AB时，90，91，100 这11 个数各被计入一次，而在求AB时，这11 个数各被计入两次（即多算了一次），并且这11 个数组成的集合恰为AB。因此得到：AB=ABAB （1）【重要公式，两个集合的容斥关系公式】这就是关于两个集合的容斥原理：集合A 与B 的元素个数，等于集合A 的元素个数与集合B 的元素个数的和，减去集合A 与B 的交集的元素个数。（1） 是容斥原理的第一个公式，我们还可以用下图来说明。如图我们用N1、N2、N3 分别表示AB 中互不重叠的部分的元素个数。可见：A=N1N3，B=N2N3，AB=N3，因此AB=N1N2N3=（N1N2）+（N2N3）-N3=ABAB。我们知道，当集合A 与B 没有公共元素时，有AB=AB。实际上这是公式（1）的特殊情形，因为此时AB=0例7. 桌面上有两张圆纸片A、B。假设圆纸片A 的面积为30平方厘米，圆纸片B 的面积为20 平方厘米。这两张圆纸片重叠部分的面积为10 平方厘米，则这两张圆纸片覆盖桌面的面积由容斥原理的公式（1）可以算出为：AB=30+20-10=40（平方厘米）。例8. 五年级96名学生都订了报纸，有64人订了少年报，有48人订了小学生报。两种报纸都订的有多少人？分析 用左边的圆表示订少年报的64人，右边的圆表示订小学报的48人，中间重叠部分表示两种报刊都订的人数。显然，两种报刊都订的人数被统计了两次：6448=112人，比总人数多11296=16人，这16人就是两种报刊都订的人数。例9. 某校教师至少懂得英语和日语中的一种语言。已知有35人懂英语，34人懂日语，两种语言都懂的有21人。这个学校共有多少名教师？分析 把懂英语和懂日语的人数加起来得3534=69人，但是，两种语言都懂的21人被统计过两次，应该从69里去掉一个21才能得出这个地区外语教师的总人数：6921=48人。例10. 学校开展课外活动，共有250人参加。其中参加象棋组和乒乓球组的同学不同时活动，参加象棋组的有83人，参加乒乓球组的有86人，这两个小组都参加的有25人。问这250名同学中，象棋组、乒乓球组都不参加的有多少人？分析 两个小组都参加的有25人，因此，至少参加这两种小组的一个小组的人数是848625=144人，所以，这两个小组都不参加的人数是250144=106人。例11. 实验小学各年级都参加的一次书法比赛中，四年级与五年级共有20人获奖，在获奖者中有16人不是四年级的，有12人不是五年级的。该校书法比赛获奖的总人数是多少人？分析 由“16人不是四年级的”可知：16人是五年级和其他年级的；由“12人不是五年级的”可知：12人是四年级和其它年级的。用1612可算出四年级加五年级以及两个其它年级的人数和，再减去20就得两个其他年级的人数，这样其他年级的人数是：（161220）2=4人，该校参加书法比赛获奖的总人数是420=24人。例12. 在100个外语教师中，懂英语的有75人，懂日语的有45人，其中必然有既懂英语又懂日语的老师。问：只懂英语的老师有多少人？分析 显然，两种语言都懂的人在懂英语的75人中统计过一次，在懂日语的45人中又统计过一次。因此，7545=120人，比100多出的20人就是两种语言都懂的人数。然后，从懂英语的75人中减去两种语言都懂的20人，就是只懂英语的人数了：7520=55人。例13. 求在1 至100 的自然数中能被3 或7 整除的数的个数。分析解这类问题时首先要知道在一串连续自然数中能被给定整数整除的数的个数规律是：在n 个连续自然数中有且仅有一个数能被n 整除。根据这个规律我们可以很容易地求出在1 至100 中能被3 整除的数的个数为33 个，被7 整除的数的个数为14 个，而其中被3 和7 都能整除的数有4 个。因而得到：解：设A=在1100 的自然数中能被3 整除的数，B=在1100 的自然数中能被7 整除的数，则AB=在1100 的自然数中能被21 整除的数。因为1003=331，所以A=33；因为1007=142，所以B=14；因为10021=416，所以AB=4。由容斥原理的公式（1）： AB=33+14-4=43。答：在1100 的自然数中能被3 或7 整除的数有43 个。例14. 求在1100 的自然数中不是5 的倍数也不是6 的倍数的数有多少个？分析如果在1100 的自然数中去掉5 的倍数、6 的倍数，剩下的数就既不是5 的倍数也不是6 的倍数，即问题要求的结果。解：设A=在1100 的自然数中5 的倍数的数B=在1100 的自然数中6 的倍数的数则问题就是要求AB 在集合1，2，100中的补集A B的元素个数。为此先求AB。因为1005=20，所以A=20又因为1006=164，所以B=16因为10030=310，所以AB=3AB=ABAB20163=33所以A B =100AB=10033=67（个）答：在1100 的自然数中既不是5 的倍数又不是6 的倍数的数共67 个。上面的例子是把一组事物按两种不同的性质来分类后，求具有其中一种性质的元素个数问题。如果把一组事物按三种不同性质来分类后，求具有其中一种性质的元素个数的公式该是什么样的呢？我们仍用图形来说明它具有与公式（1）类似的公式：ABC=ABCABAC