12容斥原埋.doc

1、第十二讲 容斥原埋在很多计数问题中常用到数学上的一个包含与排除原理，也称为容斥原理.为了说明这个原理，我们先介绍一些集合的初步知识。在讨论问题时，常常需要把具有某种性质的同类事物放在一起考虑.如：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）班的每一位同学均是集合 A的

2、一个元素.又如在例 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 表示所有既属于集合

3、A 也属于集合 B 中的元素的全体.就是上页图中阴影部分所表示的集合.即是由集合 A、 B 的公共元素所组成的集合.它称为集合 A、B 的交集.符号“”读作 “交”，“AB”读作“A 交 B”.如例 3 中的集合 A、B，则 AB= 2，4。下面再举例介绍补集的概念。例 4 设集合 I=1，3，5，7，9，集合 A=3，5，7。补集（或余集），如右图中阴影部分表示的集合（整个长方形表示集合I）.对于两个没有公共元素的集合 A 和 B，显然有 |AB|=|A|+|B|。例如，A=1，2， ，100，B=101，则所以|AB|1011001=|A|B| 。如果集合 A 与 B 有公共元素，例如A1

4、，2，100，B90，91， 101，则AB（90，91，100，AB=1，2，101.此时，|AB|与|A|+|B|有什么关系呢？在这个例中，|AB|=101， |A|B| 10012=112 。所以|AB|=|A|+|B|-11我们注意到，11 恰为 AB 的元素个数.这是合理的，因为在求|AB|时，90，91，100 这 11 个数各被计入一次，而在求|A|B|时，这 11 个数各被计入两次（即多算了一次），并且这 11 个数组成的集合恰为 AB.因此得到|AB|=|A|+|B|-|A B|，（1）这就是关于两个集合的容斥原理：集合 A 与 B 的并的元素个数，等于集合A 的元素个数与集

5、合 B 的元素个数的和，减去集合 A 与 B 的交的元素个数。（1）是容斥原理的第一个公式.我们还可以用右图来说明.如图我们用 N1、N2、N3 分别表示 AB 中互不重叠的部分的元素个数。可见：|A|=N1N3，|B|=N2N3，|A B|=N3.因此|AB|=N1 N2N3（ N1N3）+ （N2N3）-N3=|A|+|B|-|AB| 。我们知道，当集合 A 与 B 没有公共元素时，有|AB|A|+|B|.实际上这是公式（1）的特殊情形，因为此时例 5 桌上有两张圆纸片 A、B.假设圆纸片 A 的面积为 30 平方厘米，圆纸片 B 的面积为 20 平方厘米.这两张圆纸片重叠部分的面积为 1

6、0 平方厘米.则这两张圆纸片覆盖桌面的面积由容斥原理的公式（1）可以算出为：AB=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

7、 整除的数，则AB=在 1100 的自然数中能被 21 整除的数。1003331，A33。1007142，B=14。10021416，AB=4。由容斥原理的公式（1）：AB3314-4=43。答：在 1100 的自然数中能被 3 或 7 整除的数有 43 个。例 7 求在 1100 的自然数中不是 5 的倍数也不是 6 的倍数的数有多少个？分析 如果在 1100 的自然数中去掉 5 的倍数、6 的倍数，剩下的数就既不是 5 的倍数也不是 6 的倍数，即问题要求的结果。解：设 A在 1100 的自然数中 5 的倍数的数，B=在 1100 的自然数中 6 的倍数的数，数.为此先求AB。10050=

8、20，A=20又1006164，B=1610030310，AB=3 ，AB= A + B- AB =20 16-333。答：在 1100 的自然数中既不是 5 的倍数又不是 6 的倍数的数共67 个。我们也可以把公式（1）用于求几何图形的面积.这时，A 和 B 是平面上的两个点集（即点的集合），都是几何图形.A ，B ，分别表示 A 的面积，B 的面积，。例 8 设下面图中正方形的边长为 1 厘米，半圆均以正方形的边为直径，求图中阴影部分的面积。分析 如图，四个直径为 1 厘米的半圆不但盖住了正方形，还有四个重叠部分.这正好是要求的阴影部分的面积.或者，用 A 表示上、下两个半圆，用 B 表示

9、左、右两个半圆，则 AB 为边长为 1 厘米的正方形，A B为图中阴影部分.由（1）可得AB= A + B- AB ，因此可求出阴影部分的面积。解法 1：大正方形面积=4 个直径为 1 厘米的半圆面积-阴影图形面积-11 0.57（平方厘米）。上页图（a ）中阴影面积 =0.57（平方厘米）。答：阴影面积为 0.57 平方厘米。上面的例子是把一组事物按两种不同的性质来分类后，求具有其中一种性质的元素个数问题.如果把一组事物按三种不同性质来分类后，求具有其中一种性质的元素个数的公式该是什么样的呢？我们仍用图形来说明它具有与公式（1）类似的公式：ABC =ABC-AB-A C-B C ABC， （

10、2）其中 ABC=A（BC），ABC=A（BC）.右图中三个圆 A、B、C 分别表示具有三种不同性质的集合，并如图用 M1、M2 、M3 、M7 表示由三个圆形成的内部互不重叠的部分所含元素的个数，可见：ABC M1M2+M7（M1M4M6 M7）+（M2M4M5M7 ）+（M3M5M6M7）-（M4+M7）+（M5+M7）+（M6 M7）M7ABC-AB-BC-AC+A B C，即公式（2）成立。事实上这个规律还可推广到按多种性质来分类的情形.设集合 M 中的每个元素至少具有 t 种性质中的一种，用 n1表示各个具有 1 种性质的集合中的元素个数的和，n 2表示各个具有 2 种性质的集合中元

11、素个数的和，n t表示具有 t 种性质的集合中元素的个数，则集合 M 中元素的个数 m 为：m=n 1-n2n 3-n4+nt最后一项当 t 为偶数时取“-”号，否则取“ ”号。例 9 某校有学生 960 人，其中 510 人订阅“中国少年报”，330 人订阅“少年文艺”，120 人订阅“中小学数学教学报”；其中有 270 人订阅两种报刊，有 58 人订阅三种报刊.问这个学校中没有订阅任何报刊的学生有多少人？解：设 A订“中国少年报”的学生，B=订“ 少年文艺”的学生，C=订“ 中小学数学教学报”的学生，I=全校学生，=212（人）。答：全校有 212 名学生没订阅任何报刊。解：如右图，设这次竞赛共有 k 道题，用集合 A、B 分别表示甲、乙答错的题目.图中字母 a、b、c 、d 分别表示集合 A、B 在全部题目作成的集合 I 中形成的各个无重复部分的元素个数，可见 d 为问题所求.依题意列方程：注意到 a、b、c 、d 均表示题目的道数，应为自然数或零，因此 k为 12 的倍数：12、24、.k=12 ， b1，c 2，a=1 ，d=12-（abc）=12-（121）=8（道）。答：甲、乙两人都对的题共 8 道。