容斥原理讲义

骆老师教室容斥原理例题在很多计数问题中常用到数学上的一个包含与排除原理，也称为容斥原理。为了说明这个原理，我们先介绍一些集合的初步知识。在讨论问题时，常常需要把具有某种性质的同类事物放在一起考虑。如：A=｛五（1）班全体同学｝。我们称一些事物的全体为一个集合。A=｛五（1）班全体同学｝就是一个集合。B=｛全体自然数｝=｛1，2，3，4，…｝是一个具体的有无限多个元素的集合。C=｛在1，2，3，…，100中能被3整除的数｝=｛3，6，9，12，…，99｝是一个具有有限多个元素的集合。通常集合用大写的英文字母A、B、C、…表示。构成这个集合的事物称为这个集合的元素。如上面例子中五（1）班的每一位同学均是集合A的一个元素。又如在例1中任何一个自然数都是集合B的元素。像集合B这种含有无限多个元素的集合称为无限集。像集合C这样含有有限多个元素的集合称为有限集。有限集合所含元素的个数常用符合︱A︱、︱B︱、︱C︱、…表示。记号A∪B表示所有属于集合A或属于集合B的元素所组成的集合，就是下边示意图中两个圆所覆盖的部分。集合A∪B叫做集合A与的并集。“∪”读作“并”，“A∪B”读AAB设集合A=｛1，2，3，4｝，集合B=｛2，4，6，8｝，则A∪B=｛1，2，3，4，6，8｝。元素2，4在集合A、B中都有，在并集中只写一个。记号A∩B表示所有既属于集合A也属于集合B中的元素的全体。就是上面图中阴影部分所表示的集合。即是由集合A、B的公共元素所组成的集合。它称为集合A、B的交集。符号“∩”读作“交”，“A∩B”读作“A交B”。如例3中的集合A、B，则A∩B=｛2，4｝。设集合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∩=（表示空集，即没有元素的集合）。实验小学各年级都参加的一次书法比赛中，四年级与五年级共有20人获奖，在获奖者中有16人不是四年级的，有12人不是五年级的。该校书法比赛获奖的总人数是多少人？分析由“16人不是四年级的”可知：16人是五年级和其他年级的；由“12人不是五年级的”可知：12人是四年级和其它年级的。用16＋12可算出四年级加五年级以及两个其它年级的人数和，再减去20就得两个其他年级的人数，这样其他年级的人数是：（16＋12－20）÷2=4人，该校参加书法比赛获奖的总人数是4＋20=24人。在100个外语教师中，懂英语的有75人，懂日语的有45人，其中必然有既懂英语又懂日语的老师。问：只懂英语的老师有多少人？分析显然，两种语言都懂的人在懂英语的75人中统计过一次，在懂日语的45人中又统计过一次。因此，75＋45=120人，比100多出的20人就是两种语言都懂的人数。然后，从懂英语的75人中减去两种语言都懂的20人，就是只懂英语的人数了：75－20=55人。求在1至100的自然数中能被3或7整除的数的个数。分析解这类问题时首先要知道在一串连续自然数中能被给定整数整除的数的个数规律是：在n个连续自然数中有且仅有一个数能被n整除。根据这个规律我们可以很容易地求出在1至100中能被3整除的数的个数为33个，被7整除的数的个数为14个，而其中被3和7都能整除的数有4个。因而得到：解：设A=｛在1～100的自然数中能被3整除的数｝，B=｛在1～100的自然数中能被7整除的数｝，则A∩B=｛在1～100的自然数中能被21整除的数｝。因为100÷3=33…1，所以︱A︱=33；因为100÷7=14…2，所以︱B︱=14；因为100÷21=4…16，所以︱A∩B︱=4。由容斥原理的公式（1）：︱A∪B︱=33+14-4=43。答：在1～100的自然数中能被3或7整除的数有43个。求在1～100的自然数中不是5的倍数也不是6的倍数的数有多少个？分析如果在1～100的自然数中去掉5的倍数、6的倍数，剩下的数就既不是5的倍数也不是6的倍数，即问题要求的结果。解：设A=｛在1～100的自然数中5的倍数的数｝B=｛在1～100的自然数中6的倍数的数｝则问题就是要求A∪B在集合｛1，2，…，100｝中的补集A∪B的元素个数。为此先求︱A∪B︱。因为100÷5=20，所以︱A︱=20又因为100÷6=16…4，所以︱B︱=16因为100÷30=3…10，所以︱A∩B︱=3︱A∪B︱=︱A︱＋︱B︱－︱A∩B︱20＋16－3=33所以A∪B=100－︱A∪B︱=100－33=67（个）答：在1～100的自然数中既不是5的倍数又不是6的倍数的数共67个。上面的例子是把一组事物按两种不同的性质来分类后，求具有其中一种性质的元素个数问题。如果把一组事物按三种不同性质来分类后，求具有其中一种性质的元素个数的公式该是什么样的呢？我们仍用图形来说明它具有与公式（1）类似的公式：︱A∪B∪C︱=︱A︱＋︱B︱＋︱C︱－︱A∩B︱－︱A∩C︱－︱B∩C︱＋︱A∩B∩C︱，（2）【非常重要，三个集合的容斥关系】例题如下

假设有100人参加了三个兴趣小组。其中参加