1、 第第六六讲讲 容斥原理容斥原理 在一些计数问题中，经常遇到有关集合元素个数的计算。我们用|A|表示有限集 A 的元 素的个数。在两个集合的研究中，已经知道，求两个集合并集的元素个数，不能简单地把两 个集合的元素个数相加， 而要从两根集合的个数之中减去重复计算的元素个数， 用式子可以 表示成 |AB|=|A|+|B|AB|。【来源：21cnj*y.co*m】 我们称这一公式为包含与排除原理，简称为容斥原理。 包含与排除原理|告诉我们，要计算两个集合 A、B 的并集 AB 的元素个数，可以分一 下两步进行： 第一步：分别计算集合 A、B 的元素个数，然后加起来。即先求|A|+|B|（意思是把 A
2、、B 的一切元素都“包含”进来，加在一起）；【出处：21 教育名师】 第二步“从上面的和中减去交集的元素的个数，即减去|AB|（意思是“排除”了重复 计算的元素的个数）。【版权所有：21 教育】 例 1求不超过 20 的正整数中是 2 的倍数或 3 的倍数的数共有多少？ 解：设 I=1、2、3、19、20，A=I 中 2 的倍数，B=I 中 3 的倍数。 显然题目中要求计算并集 AB 的元素个数，即求|AB|。 我们知道 A=2、4、6、20，所以|A|=10， B=3、6、9、12、15、18，|B|=6。 AB=I 中既是 2 的倍数又是 3 的倍数=6、12、18，所以|AB|=3， 根
3、据容斥原理有|AB|=|A|+|B|AB|=10+63=13. 答：所求的数共有 13 个。 此题可以直观地用图表示如下： 15 9 3 20 181614 12 108 6 4 2 BA 例 2某班统计考试成绩，数学得 90 分以上的有 25 人，语文得 90 分以上的有 21 人， 两科中至少有一科在 90 分以上的有 38 人，问两科都在 90 分以上的有多少人？ 解：设 A=数学在 90 分以上的学生，B=语文在 90 分以上的学生， 由题意知|A|=25，|B|=21。 AB=数学、语文至少一科在 90 分以上的学生，|AB|=38。 AB=数学、语文都在 90 分以上的学生， 由容
4、斥原理知|AB|=|A|+|B|AB|， 所以|AB |=|A|+|B|AB|=25+2138=8。 答：两科都在 90 分以上的有 8 人。 画图分析一下： n y x B A 其中 A 的人数是 x+n=25，B 的人数是 y+n=21，AB 的人数是 x+n+y=38，求 n 等于多 少？ 很明显 n=(x+n)+(y+n)(x+y+n)=25+2138=8。 例 3如图所示，一个边长为 2 的正方形与一个边长为 3 的正方形放在桌面上，它们 所盖住的面积有多大？ 1.5 1.5 2 2 3 3 解：如果把两个正方形的面积加起来是 32+22=9+4=13，就会发现多计算了一块阴影的 面
5、积，应该从上面的和中减去这一部分。21 教育名师原创作品 因此两个正方形所覆盖住的面积是 32+221.52=132.25=10.75。 例 4有 100 位旅客，其中 10 人既不懂英语又不懂俄语，有 75 人懂英语，83 人懂俄 语。问既懂英语又懂俄语的有多少人？21*cnjy*com 解：设 A=懂英语的旅客，B=懂俄语的旅客，那么英语或俄语至少懂一种的旅客是 AB，而两种语言都懂的旅客是 AB。 由题意|A|=75，|B|=83，|AB|=10010=90， 根据容斥原理得|AB|=|A|+|B|AB|=75+8390=68. 答：两种语言都懂的旅客有 68 人。 对于任意三个有限集合
6、 A、B、C，我们可以将上面的容斥原理推广得到如下的公式： |ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|。 三个集合的容斥原理告诉我们要计算并集 ABC 的元素个数，可以分三步进行： 第一步：求|A|+|B|+|C|； 第二步：减去|AB|，|BC|，|CA|； 第三步：加上|ABC|。 结合下图作出说明。 C VII VIV IV III II I B A 由于 ABC 可以有七个部分组成， 其中 I、 II、 III 部分的元素仅属于某个集合， 而 IV、 V、VI 部分的元素分别属于某两个集合，第 VII 部分则是三个集合的交集。 由于 ABC 的元素分别来自集合 A
7、、B、C，因此先计算|A|+|B|+|C|。 在这个和里，第 I、II、III 部分的元素只计算了一次，而第 IV、V、VI 部分的元素各自 计算了两次，第 VII 部分的元素计算了三次。21世纪*教育网 在第二步中减去了|AB|，|BC|，|CA|后，得|A|+|B|+|C|AB|BC|AC|， 这样显然消除了第 IV、V、VI 部分的元素的重复计算，但是请注意同时对第 VII 部分 的元素是减去了三次，这样第 VII 部分的元素都被减去了，因此必须补回来，即再加上 |ABC|。 综上所述得|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|。 例 5某校组织棋类比赛，分成围棋、
8、中国象棋、国际象棋三个组进行。参加围棋比赛 的有 42 人，参加中国象棋比赛的有 51 人，参加国际象棋比赛的有 30 人。同时参加围棋和 中国象棋比赛的有 13 人，同时参加围棋和国际象棋比赛的有 7 人，同时参加中国象棋和国 际象棋比赛的有 11 人，其中三种棋都参加的有 3 人。问参加棋类比赛的共有多少人？ 解：设 A=参加围棋比赛的人，B=参加中国象棋比赛的人，C=参加国际象棋比赛 的人。那么参加棋类比赛的人的集合为 ABC。21 cn jy com 由题意知，|A|=42，|B|=51，|C|=30，又|AB|=13，|AC|=7，|BC|=11，|ABC|=3。 根据容斥原理得 |
9、ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|=42+51+3013711+3=95 （人） 。 答：参加棋类比赛的共有 95 人。 画图来计算： 8 4 3 10 30 15 25 C VI V IV III II I B A C VI V IV III II I B A A、B、C 三个圆表示三个集合，先把三个圆相交的最中间部分填上 3， 由于同时参加围棋和中国象棋比赛的有 13 人，所以第 IV 部分应该是 10 人； 同时参加中国象棋和国际象棋比赛的有 11 人，所以第 V 部分应该是 8 人； 同时参加围棋和国际象棋比赛的有 7 人，所以第 VI 部分应该是 4 人；
10、 再根据参加围棋比赛的有 42 人，于是第 I 部分是 421034=25 人； 参加中国象棋比赛的有 51 人，于是第 II 部分是 511038=30 人； 参加国际象棋比赛的有 30 人。于是第 III 部分是 30834=15 人； 由此得出参加棋类比赛的总人数是 25+30+15+10+8+4+3=95（人）。 例 6边长分别为 6、5、2 的三个正方形，如图所示放在桌面上，问它们所盖住的面积 是多大？ A2 B2C2 D2 D1 C1 B1 A1 D C B A 1 5 2 3 6 解：设 R 表示正方形区域 ABCD，M 表示正方形区域 A1B1C1D1，N 表示正方形区域 A2
11、B2C2D2，则|R|=36，|M|=25，|N|=4，|RM|=9，|RN|=2，|MN|=2，|RMN|=1， 所以|MMN|=|R|+|M|+|N|RM|RN|MN|+|RMN| =36+25+4922+1=53. 答：三个正方形所盖住的面积是 53. 例 7某班学生手中分别拿有红、黄、蓝三种颜色的球。已知手中有红球的共有 34 人， 手中有黄球的共有 26 人，手中有篮球的共有 18 人，其中手中有红、黄、蓝三种球的有 6 人，而手中只有红、黄两种球的有 9 人，手中只有黄、蓝两种球的有 4 人，手中只有红、蓝 两种球的有 3 人，那么这个班共有多少人？21 教育网 解：设 A、B、C
12、 分别表示手中有、红球、黄球、篮球的人的集合， 由题意，画出图来逐一填上人数计算。 5 7 4 3 9 6 C 16 B A C VI V IV III III B A 最中间应该填上 6，由手中只有红、黄两种球的有 9 人，手中只有红、蓝两种球的有 3 人，手中只有黄、蓝两种球的有 4 人，则在区域 VI、V、VI 中分别填上 9、3、4。 最后由手中有红球的共有 34 人，手中有黄球的共有 26 人，手中有篮球的共有 18 人， 可以填出区域 I、II、III 内分别填上 16、7、5。21 世纪教育网版权所有 所以全班共有 16+7+5+9+3+4+6=50（人）。 答：全班共有 50
13、人。 解法 2：设 A、B、C 分别表示手中有、红球、黄球、篮球的人的集合， 则|A|=34，|B|=26，|C|=18，所以|A|+|B|+|C|=34+26+18=78， 显然这样的计算中对于区域 IV、V、VI 的部分重复计算了一次（需要减去 1 次），而 对于区域 VII 的部分重复计算了两次，也就是计算了三次（需要减去 2 次）。 所以全班人数是 34+26+18(9+4+3)26=50（人）。 答：全班共有 50 人。 例 8求 1 到 200 的自然数中不能被 2、3、5 中任何一个数整除的数有多少个？ 解： 设 A=1 到 200 中间能被 2 整除的自然数； B=1 到 20
14、0 中间能被 3 整除的自然数； C=1 到 200 中间能被 5 整除的自然数；www.21-cn- 那么 AB=1 到 200 中间能被 2 3 整除的自然数；AC=1 到 200 中间能被 2 5 整除 的自然数；BC=1 到 200 中间能被 3 5 整除的自然数；ABC=1 到 200 中间能被 2 3 5 整除的自然数； 21*cnjy*com 求出|A|=100，|B|=66，|C|=40，|AB|=33，|AC|=20，|BC|=13，|ABC|=6， 所以|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC| =100+66+40332013+6=146. 这是 1
15、 到 200 中间的自然数至少有能被 2、3、5 中一个数整除的数的个数。 所以 1 到 200 的自然数中不能被 2、3、5 中任何一个数整除的数有 200146=54（个）。 练 习 题 1某班有团员 23 人，这个班里男生共有 20 人，则这个班里女生团员比男生非团员多 人。 解：设男生团员为 x 人，则女生团员为 23x 若，男生非团员为 20x 人， 所以这个班里女生团员比男生非团员多(23x)(20x)=3（人）。 答：这个班里女生团员比男生非团员多 3 人。 2一张纸片的面积为 7，另一张是边长为 2 的正方形纸片，把这两张纸片放在桌子上，覆 盖的面积为 8，则两张纸片重合部分的
16、面积是 。www-2-1-cnjy-com 解：设第一张纸片为 A，第二张纸片为 B， 则|A|=7，|B|=4，|AB|=8，所以|AB|=7+48=3. 答：两张纸片重合部分的面积是 3. 3从 1 到 100 的自然数中， （1）不能被 6 或 10 整除的数有 个； （2）至少能被 2、3、5 中一个数整除的数有 个。 解：（1）设 A=1 到 100 中被 6 整除的数，B=1 到 100 中被 10 整除的数， AB=1 到 100 中被 30 整除的数，其中 30 是 6 与 10 的最小公倍数。 则|A|=16，|B|=10，|AB|=3，所以|AB|=|A|+|B|AB|=1
17、6+103=23. 在1到100中能被6或10整除的数有23个， 不能被6或10整除的数有10023=77 （个） 。 答：不能被 6 或 10 整除的数有 77 个。 （2）设 C=1 到 100 中被 2 整除的数；D=1 到 100 中被 3 整除的数；E=1 到 100 中被 5 整除的数；CD=1 到 100 中既能被 2 整除又能被 3 整除的数；CE=1 到 100 中既能被 2 整除又能被 5 整除的数；DE=1 到 100 中既能被 3 整除又能被 5 整除的数； CDE=1 到 100 中同时能被 2、3、5 整除的数；2-1-c-n-j-y |C|=50、|D|=33，|
18、E|=20，|CD|=16，|CE|=10，|DE|=6，|CDE|=3， 所以|CDE|=|C|+|D|+|E|CD|CE|DE|+|CDE| =50+33+2016106+3=74（个）。 答：至少能被 2、3、5 中一个数整除的数有 74 个。 4盛夏的一天，有 10 个同学去冷饮店，向服务员交了一份需要冷饮的统计表：要可乐、雪 碧、果汁的各有 5 人；可乐、雪碧都要的有 3 人；可乐、果汁都要的有 2 人；雪碧、果汁都 要的有 2 人，三样都要的只有 1 人。证明：其中有 1 人这三种饮料都没有要。 解：设 A=要可乐的同学，B=要雪碧的同学，C=要果汁的同学， 则|A|=5，|B|=
19、5，|C|=5，|AB|=3，|AC|=2，|BC|=2，|ABC|=1， 所以|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC| =5+5+5322+1=9（人）。 可见一定有 1 人没有要饮料。 5对 100 个学生课外学科活动的调查结果如下：32 人参加数学小组；20 人参加英语小组； 45 人参加生物小组。其中 15 人既参加了数学小组又参加了生物小组；7 人既参加了英语小 组又参加了数学小组；10 人既参加了英语小组又参加了生物小组。还有 30 人没有参加上述 任何一个学科小组。2 1 c n j y （1）求三个学科小组都参加的人数； （2） 在文氏图的 8 个小区域
20、内填入相应的学生人数， 其中 A、 B、 C 分别代表参加数学、 英语、生物小组的学生的集合，被调查的 100 个学生的集合为全集 I。 C I B A 解：（1）设 A=参加数学小组的学生；B=参加英语小组的学生；C=参加生物小组的学 生；AB=既参加数学小组又参加英语小组的学生；AC=既参加数学小组又参加生物 小组的学生；BC=既参加英语小组又参加生物小组的学生；ABC=三个小组都参 加的学生，ABC=三个小组中至少参加一个小组的学生【来源：21世纪教育网】 则|A|=32，|B|=20，|C|=45，|AB|=7，|AC|=15，|BC|=10， |ABC|=10030=70. 根据容斥原理 | ABC |= |ABC |A|B|C|+|AB|+|AC|+|BC| =70322045+7+15+10=5（人）。 答：三个小组都参加的有 5 人。 （2） 30 5 25 5 C I 15 10 8 2 B A
