《第十二讲 容斥原理.doc》由会员分享，可在线阅读，更多相关《第十二讲 容斥原理.doc（12页珍藏版）》请在金锄头文库上搜索。
1、奥博教育培训 http:/第十二讲 容斥原理在很多计数问题中常用到数学上的一个包含与排除原理，也称为容斥原理。为了说明这个原理，我们先介绍一些集合的初步知识。在讨论问题时，常常需要把具有某种性质的同类事物放在一起考虑。如：A=五（1）班全体同学。我们称一些事物的全体为一个集合。A=五（1）班全体同学就是一个集合。例1 B=全体自然数=1，2，3，4，是一个具体的有无限多个元素的集合。例2 C=在1，2，3，100中能被3整除的数=3，6，9，12，99是一个具有有限多个元素的集合。通常集合用大写的英文字母A、B、C、表示。构成这个集合的事物称为这个集合的元素。如上面例子中五（1）班的每一位同学
2、均是集合A的一个元素。又如在例1中任何一个自然数都是集合B的元素。像集合B这种含有无限多个元素的集合称为无限集。像集合C这样含有有限多个元素的集合称为有限集。有限集合所含元素的个数常用符合A、B、C、表示。记号AB表示所有属于集合A或属于集合B的元素所组成的集合，就是下边示意图中两个圆所覆盖的部分。集合AB叫做集合A与集合B的并集。“”读作“并”，“AB”读作“A并B”。 例3 设集合A=1，2，3，4，集合B=2，4，6，8，则AB=1，2，3，4，6，8。元素2，4在集合A、B中都有，在并集中只写一个。记号AB表示所有既属于集合A也属于集合B中的元素的全体。就是上面图中阴影部分所表示的集合
3、。即是由集合A、B的公共元素所组成的集合。它称为集合A、B的交集。符号“”读作“交”，“AB”读作“A交B”。如例3中的集合A、B，则AB=2，4。例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=（表示空集，即没有元素的集合）。 此外，A=I。对于两个没有公共元素的集合A和B，显然有AB=AB。例如，A=1，2，100，B=101，
4、则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=ABA （1）这就是关于两个集合的容斥原理：集合A与B的元素个数，等于集合A的元素
5、个数与集合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例5 桌面上有两张圆纸片A、B。假设圆纸片A的面积为30平方厘米，圆纸片B的面积为20平方厘米。这两张圆纸片重叠部分的面积为10平方厘米，则这两张圆纸片覆盖桌面的面积由容斥原理的公式（1）可以算出为：AB=
6、30+20-10=40（平方厘米）。例6 求在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
7、=4。由容斥原理的公式（1）：AB=33+14-4=43。答：在1100的自然数中能被3或7整除的数有43个。例7 求在1100的自然数中不是5的倍数也不是6的倍数的数有多少个？分析 如果在1100的自然数中去掉5的倍数、6的倍数，剩下的数就既不是5的倍数也不是6的倍数，即问题要求的结果。解：设A=在1100的自然数中5的倍数的数B=在1100的自然数中6的倍数的数则问题就是要求AB在集合1，2，100中的补集的元素个数。为此先求AB。因为1005=20，所以A=20又因为1006=164，所以B=16因为10030=310，所以AB=3AB=ABAB20163=33所以=100AB=1003
8、3=67（个）答：在1100的自然数中既不是5的倍数又不是6的倍数的数共67个。我们也可以把公式（1）用于求几何图形的面积。这时，A和B是平面上的两个点集（即点的集合），都是几何图形，A，B，分别表示A的面积，B的面积，例8 设下面图中正方形的边长为1厘米，半圆均以正方形的边为直径，求图中阴影部分的面积。 分析 如图，四个直径为1厘米的半圆不但盖住了正方形，还有四个重叠部分，这正好是要求的阴影部分的面积。或者，用A表示上、下两上半圆，用B表示左、右两个半圆，则AB为边长为1厘米的正方形，AB为图中阴影部分。由（1）可得AB=ABAB因此可求出阴影部分的面积。解法1：因为大正方形面积=4个直径为
9、1厘米的半圆面积阴影图形面积，所以，阴影图形面积=2个直径为1厘米的圆面积正方形面积=2（）211=0.57（平方厘米）。解法2：我们从图（a）的对称性分出其中的图形，图中叶状阴影图形面积的一半等于半径为厘米的圆面积的减去边为厘米的正方形面积的，即：一个叶状阴影面积=（）2 = =0.57（平方厘米）所以，上页图（a）中阴影面积=0.57（平方厘米）答：阴影面积为0.57平方厘米。上面的例子是把一组事物按两种不同的性质来分类后，求具有其中一种性质的元素个数问题。如果把一组事物按三种不同性质来分类后，求具有其中一种性质的元素个数的公式该是什么样的呢？我们仍用图形来说明它具有与公式（1）类似的公式
10、：ABC=ABCABACBCABC，其中ABC=A（BC），ABC= A（BC）。下图中三个圆A、B、C分别表示具有三种不同性质的集合，并如图用M1、M2、M3、M7表示由三个圆形成的内部互不重叠的部分所含元素的个数，可见：ABC= M1M2M7=（M1M4M6M7）（M2M4M5M7）（M3M5M6M7）（M4M7）（M5M7）（M6M7）M7=ABCABACBCABC。事实上这个规律还可推广到按多种性质来分类的情形。设集合M中的每个元素至少具有t种性质中的一种，用n1表示各个具有1种性质的集合中的元素个数的和，n2表示各个具有2个性质的集合中元素个数的和，nt表示具有t种性质的集合中元素的
11、个数，则集合M中元素的个数m为：m=n1n2n3n4nt最后一项当t为偶数时取“”号，否则取“”号。例9 某校有学生960人，其中510人订阅“中国少年报”，330人订阅“少年文艺”，120人订阅“中小学数学教学报”；其中有270人订阅两种报刊，有58人订阅三种报刊。问这个学校中没有订阅任何报刊的学生有多少人？解：设A=订“中国少年报”的学生B=订“少年文艺”的学生C=订“中小学数学教学报”的学生I=全校学生则问题是要求ABC在I中的补集所含元素的个数：=960ABC=960（51033012027058）=212（人）。答：全校有212名学生没订阅任何报刊。例10 在一次数学竞赛中，甲答错了
12、题目总数的，乙答错了3道，甲、乙都错的题占题目总数的，求甲、乙都答对的题目数。 解：如上图，设这次竞赛共有k道题，用集合A、B分别表示甲、乙答错的题目，图中字母a、b、c、d分别表示集合A、B在全部题目作成的集合I中形成的各个无重复部分的元素个数，可见d为问题所求。依题意列方程： ac= (1) cb=3 (2) c= (3)将（3）代入（1）：a=,所以a=注意到a、b、c、d均表示题目的道数，应为自然数或0，因此k为12的倍数：12、24、。将（3）代入（2）：b=3 b=3所以k=12，b=1，c=2，a=1，d=12(abc)=12(121)=8（道）答：甲、乙两人都对的题共8道。习
13、题 十 二1，某班有50人，会游泳的有27人，会体操的有18人，都不会的有15人。问既会游泳又会体操的有多少人？2，在11000这1000个自然数中，不能被2、3、5中任何一个数整除的数有多少个？3，五环图中每一个环内径为4厘米，外径为5厘米。其中两两相交的小曲边四边形（下图中阴影部分）的面积相等。已知五个圆环盖住的总面积是122.5平方厘米，求每个小曲边四边形的面积。 4，某班全体学生进行短跑、游泳和篮球三项测验，有4个学生这三项均未达到优秀，其余每人至少一项达到优秀，这部分学生达到优秀的项目及人数如下表： 短 跑游 泳篮 球短跑及游泳游泳及篮球短跑及篮球三 项17人18人15人6人6人6人2人问这个班有多少名学生？5，有100位学生回答A、B两题，A、B两题都没回答对的有10人，有75人答对A题，83人答对B题，问有多少人A、B两题都答对？6，在一次数学竞赛中甲答题题目总数的，乙答对7道题，两人都对的题目是题目总数的。问：甲答对了多少道题？1
