容斥原理和广义容斥原理

点算的奥秘：容斥原理基本公式

「容斥原理」(Principle of Inclusion and Exclusion)(亦作「排容原理」)是「点算组合学」中的一条重要 原理。但凡略为复杂、包含多种限制条件的点算问题，都要用到这条原理。现在首先从一个点算问题说起。

例题1：设某班每名学生都要选修至少一种外语，其中选修英语的学生人数为25，选修法语的学生人 数为18，选修德语的学生人数为20，同时选修英语和法语的学生人数为8，同时选修英语和德语的学生人数为13 ，同时选修法语和德语的学生人数为6，而同时选修上述三种外语的学生人数则为3，问该班共有多少名学生？

答1：我们可以把上述问题表达为下图：

其中红色、绿色和蓝色圆圈分别代表选修英语、法语和德语的学生。根据三个圆圈之间的交叉关系，可把上图 分为七个区域，分别标以A至G七个字母。如果我们用这七个字母分别代表各字母所在区域的学生人数，那么根 据题意，我们有以下七条等式：(1) A+D+E+G = 25；(2) B+D+F+G = 18；(3) C+E+F+G = 20；(4) D+G = 8； (5) E+G = 13；(6) F+G = 6；(7) G = 3。现在我们要求的是A+B+C+D+E+F+G。如何利用以上数据求得答案？

把头三条等式加起来，我们得到A+B+C+2D+2E+2F+3G = 63。可是这结果包含了多余的D、E、F和G，必须设法把 多余的部分减去。由于等式(4)－(6)各有一个D、E和F，若从上述结果减去这三条等式，便可以把多余的D、E和 F减去，得A+B+C+D+E+F = 36。可是这么一来，本来重复重现的G却变被完全减去了，所以最后还得把等式(7)加 上去，得最终结果为A+B+C+D+E+F+G = 39，即该班共有39名学生。□

在以上例题中，给定的数据是三个集合的元素个数以及这些集合之间的交集的元素个数。在该题的解答中，我 们交替加上及减去这些给定的数据。如果我们用S1、S2和S3分别代表选修 英语、法语和德语学生的集合，那么我们要求的答案就是|S1 ∪ S2 ∪ S3|，而该题的解答则可以重新表达为 |S1 ∪ S2 ∪ S3| = (|S1| + |S2| + |S3|) − (|S1 ∩ S2| + |S1 ∩ S3| + |S2 ∩

容斥原理

公呈教育·大禹治水

预习目标：

1.明确容斥问题的计算方法。（尤其注意重叠的部分在题目中是如何体现的）

2.容斥问题的分类：二元容斥、三元容斥、多元容斥（多元容斥在预习阶段可作为研究内容）

预习题目：

【习题】某高校志愿者90人去支援某次冬运会，53人到滑雪场地，82人到滑冰场地，有6人既没到滑雪场地，也没到滑冰场地，既到滑冰场又到滑雪场的人是（ ）。

A.45人

B.51人

C.29人

D.47人

【习题】某医院统计某天求诊的病人，内科150人，外科90人，内外科都求诊的20人，这天一共有（ ）病人？

A.240

B.220

C.200

D.170

【习题】野生动物保护机构考查某圈养动物的状态，在n(n为正整数)天中观察到：(1)有7个不活跃日(一天中有出现不活跃的情况)； (2)有5个下午活跃； (3)有6个上午活跃；(4)当下午不活跃时，上午必活跃，则n等于：

A.7

B.8

C.9

D.10

【习题】某校对五年级100名同学进行学习兴趣调查，结果有58人喜欢语文，有38人喜欢数学，有52人喜欢外语。而且喜欢语文和数学（但不喜欢外语）的有6人，喜欢数学和外语（但不喜欢语文）的有4人，三科都喜欢的有12人，而且每人至少喜欢一科。问有多少同学只喜欢语文？

A.27

B.34

C.14 D.26

【习题】五年级一班共有55个学生，在暑假期间都参加了特长培训班，35人参加书法班，28人参加美术班，31人参加舞蹈班，其中以上三种特长培训班都参加的有6人，则有（ ）人只参加了一种特长培训班？

A.45

B.33

C.29

D.22

【习题】三个学生共解出30道数学题，每人都解出了其中的12道，且每道题都有人解出。只有一人解出的题叫做难题，只有两个人解出的题叫做中等题，三人都解出的题叫做容易题。在这30道题中，难题、中等题、容易题均有，且题数各不相等，则难题的题数是（ ）？

A.14

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

2、五（1）班36个同学在一次测验中，答对第一题的有25人，答对第二题的有23人，两题都答对的有15人。问有几个同学两题都不对？

容斥原理（也称包含与排斥原理或逐步淘汰原理或取舍原理） 在计数时，为了既不重复也不遗漏，人们研究出一种新的方法，这种间接的计数方法称为容斥原理。其基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。这个原理直观易懂，思路明确，方法也是程式化，是学习组合数学中计数问题的一个十分重要的基本工具。

1、对于两个有限集合A、B的容斥原理,如图：

BABABA

2、对于三个有限集合A、B、C的容斥原理，如图：

CBACBBABACBACBA

容斥原理的灵活运用

导入

知识精讲

【例1】如图所示：

（1）已知：∠AOB=90°，∠COD=80°。∠COB=30°，求∠AOD。

（2）已知：∠AOB=100°，∠COD=70°，∠AOD=135°，求∠COB。

【巩固】

1、如图，桌面上放有两本书，A的面积是56，B的面积是48，桌面面积是200，书本未覆盖部分面积是116，求两本书重叠部分的面积。

例题精讲

BADBCAO2、如下图，矩形ABCD中，AB＝6厘米，BC＝4厘米，扇形ABE半径AE＝6厘米，扇形CBF的半径CB=4厘米，求阴影部分的面积。

【例2】50 名同学面向老师站成一行．老师先让大家从左至右按 1，2，3，…，49，50 依次报数；再让报数是4的倍数的同学向后转，接着又让报数是6的倍数的同学向后转。问：现在面向老师的同学还有多少名?

【巩固】

1、有 100 盏亮着的电灯，各有一个拉线开关控制着，现按其顺序编号为 1，2，3，…，100，然后将编号为2的倍数的灯线拉一下，再将编号为3 的倍数的灯线拉一下，这时亮着的灯有多少盏？

容斥原理之三者容斥问题

浙江行测答题技巧：容斥原理之三者容斥问题

中公教育考试研究院宋丽娜：容斥原理是行测数学运算中常考知识点。容斥原理是指在计数时，必须注意无一重复，且无遗漏。这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

例1：一个班级的学生数学和语文每人至少喜欢其中一种，其中喜欢数学课的有49人，喜欢语文课的有52人，二者都喜欢的有21人，则这个班级有多少人?

中公点拨：本题就是一个容斥问题，解决此问题的方法就是先算：49+52=101(把含于某内容中的所有对象的数目先计算出来)，然后再把计数时重复计算的数目排斥出去即：101-21=80人，则整个班级的人数就有80人。

三者容斥问题是行测数学运算中常考也相对较复杂的容斥问题。所谓三者容斥是指在题干中有三种集合(集合就是具有共同属性所以元素的的整体，例如上题中喜欢数学的人构成一个集合)。

三者容斥问题有一个基本公式：A，B，C代表三个集合，则有

A∪BUC=A+B+C-A∩B-A∩C-B∩C+ A∩B∩C

这个公式表达的含义是，A+B+C再减去两两相交之后，中间E(即A∩B∩C)这部分被减没了。而容斥原理的基本思想是计数时不重复不漏掉，故要再加回来，所以又加了一个A∩B∩C。

例2. 实验小学的小记者对本校100名同学进行调查，调查他们对三种大球(篮球、足球、排球)的与否。结果显示：他们都至少喜欢三种大球中的一种，其中有58人喜欢篮球，有68人喜欢足球，有62人喜欢排球，而且，篮球和足球都喜欢的有45人，足球和排球都喜欢的有33人，三种球都喜欢的有12人。篮球和排球都喜欢的多少人?

中公教育解析：由题意可画图如下：

则有上述公式可知：