容斥原理

容斥原理

在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

原理1

如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。（A∪B = A+B - A∩B)

例1 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？

分析

依题意，被计数的事物有语、数得满分两类，“数学得满分”称为“A类元素”，“语文得满分”称为“B类元素”，“语、数都是满分”称为“既是A类又是B类的元素”，“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。

答案

15+12-4=23

试一试

电视台向100人调查前一天收看电视的情况，有62人看过2频道，34人看过8频道，其中11人两个频道都看过。两个频道都没看过的有多少人？

100-（62+34-11）=15

1

原理2

如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）

例1某校六⑴班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25

人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？

分析：参加足球队的人数25人为A类元素，参加排球队人数22人为B类元素，参加游泳队的人数24人为C类元素，既是A类又是B类的为足球排球都参加的12人，既是B类又C类的为足球游泳都参加的9人，既是C类又是A类的为排球游泳都参加的8人，三项都参加的是A类B类C类的总和设为X。注意：这个题说的每人都参加了体育训练队，所以这个班的总人数即为A类B类和C类的总和。

答案：25+22+24-12-9-8+X=45 解得X=3

例2分母是1001的最简分数一共有多少个？分析：这一题实际上就是找分子中不能与

1001进行约分的数。由于1001=7×11×13，所以就是找不能被7，11，13整除的数。

解答：1~1001中，有7的倍数1001/7 = 143 （个)；有11的倍数1001/11 = 91 （个），有13的倍数1001/13 = 77 （个）；有7´11=77的倍数1001/77 = 13 （个），有7´13=91的倍数1001/91 = 11 （个），有11´13=143的倍数1001/43 = 7 （个）.有1001的倍数1个。

由容斥原理知：在1~1001中，能被7或11或13整除的数有（143+91+77）（-13+11+7）+1=281（个），从而不能被7、11或13整除的数有1001-281=720（个）.也就是说，分母为1001的最简分数有720个。

公式

也可表示为 设S为有限集,

,则

2

两个集合的容斥关系公式：A∪B = A+B - A∩B (∩：重合的部分）

三个集合的容斥关系公式：A∪B∪C = A+B+C - A∩B - B∩C - C∩A +A∩B∩C

详细推理如下：

1、 等式右边改造 = {[（A+B - A∩B）+C - B∩C] - C∩A }+ A∩B∩C 2、文氏图分块标记如右图图：1245构成A，2356构成B，4567构成C 3、等式右边（）里指的是下图的1+2+3+4+5+6六部分： 那么A∪B∪C还缺部分7。

4、等式右边[]号里+C（4+5+6+7）后，相当于A∪B∪C多加了4+5+6三部分， 减去B∩C（即5+6两部分）后，还多加了部分4。

5、等式右边{}里减去C∩A （即4+5两部分）后，A∪B∪C又多减了部分5， 则加上A∩B∩C（即5）刚好是A∪B∪C。 对于容斥原理我们可以利用数学归纳法证明： 证明：当

时，等式成立(证明略)。 假设

时结论成立，则当 时，

3

所以当

时，结论仍成立。因此对任意

，均可使所证等式成立。[1]

4