24容斥原理.doc

第二十四章 容斥原理 内容精要 在很多计数问题中常用到数学上的一个包含与排除原理，也成为容斥原理。 容斥原理 1 如果有 s 个东西，其中具有性质 A 的有 a 个，具有性质 B 的有 b 个，既具有性 质 A 又具有性质 B（即 AB）的有 C 个， 那么，具有性质 A、B 及 AB 的（记作 N）有 N=a+b-c( 个) A A B B 如下图 = b a 或 c=a+b-N 那么，既不具有性质 A 也不具有性质 B（记作 M）的有 M=S- （a+b-c）(个 ) 容斥原理 2 如果有 s 个东西，其中具有性质 A 的有 a 个，具有性质 B 的有 b 个，其中具有 性质 C 的有 c 个，既具有性质 A 又具有性质 B（即 AB ）的有 d 个 , 既具有性质 A 又具有性质 C（即 AC）的有 e 个,既具有性质 B 又具有性质 C（即 BC）的有 f 个同时具有性质 A、B、C（即 ABC）的有 g 个 . 那么，具有性质 A 或性质 B 或性质 C（记作 N）的有 N=a+b+c-d-e-f+g （个） B AB A ABC BC AC C 如下图 b C e d a = ＋ ＋ － － － f g ＋ 或 g=N-(a+b+c-d-e-f) 为更好地说明容斥原理，我们要介绍一些集合的初步知识。 记号 A∪B 表示所有属于集合 A 或属于集合 B 的元素所组成的集合。就是右边示意图中两 个圆所覆盖的部分。集合 A∪B 叫做集合 A 与集合 B 的并集 .“∪”读作“并” ，“A∪B”读 B A 作“A 并 B” 记号 A∩B 表示所有既属于集合 A 也属于 集合 B 中的元素的全体。就是上图中阴影部分所表示的集合。即是由集合 A、B 的公共的 元素所组成的集合 它称为集合 A、B 的交集。符号“∩”读作“交” ，“A∩B”读作“ A 交 B”。 例 1 五（1）班 46 名学生都订了报纸，订阅《小学生数学报》的有 41 人，订阅《中国少 年报》的有 32 人.分别有多少人两种报纸都订阅？ 分析：我们可以用集合圈来表示，如图， A 圈表示订阅《小学生数学报》的有 41 人，B 圈 表示订阅《中国少年报》的有 32 人。那么两种报纸都订阅的学生人数就是这两个圈的交叉 C B A 41 人 32 人 部分 C。 从上图中看出，订阅《小学生数学报》的有 41 人，加上订阅《中国少年报》的有 32 人，共 73 人，恰好把两种报纸都订阅的学生人数多算 一次，所以两种报纸都订阅的学生人数 =订阅《小学生数学报》的人数 +订阅《中国少年报》 的人数 -全班人数。 41+32-46=27 答：有 27 人订阅两种报纸。 例 2 求 100 以内既是 5 的倍数又是 7 的倍数的数的个数。 分析： 100 以内 5 的倍数有 100÷ 5=20（个），7 的倍数有 100÷ 7=14......2 即 14（个）。但以 100 内既 5 是的倍数又是 7 的倍数的数的个数并不是 20+14=34（个）。因为在 100 以内既是 5 的倍数，又是 7 的倍数，如 35，这些数在计算 5 和 7 的倍数时，重复统计了，因为要求 100 以内既是 5 的倍数又是 7 的倍数的数的个数是， 还应减去 100 以内 5 与 7 的公倍数的个 数。 100 以内 5 的倍数有 100÷ 5=20（个） 100 以内 7 的倍数有 100÷ 7=14......2 即 14（个） 100 以内 35 的倍数有 100÷ 35=2......30 即 2（个） 20+14-2=32( 个 ) 答 100 以内既是 5 的倍数又是 7 的倍数的数的个数是 32 个。 例 3 某校友学生 960 人其中 510 人订阅《中国少年报》 ，330 人订阅《少年文艺》 ；120 人订 阅《中小学数学教学报》 ，其中有 270 人订阅 2 种报刊，有 58 人订阅 3 种报 .问这个学校中 没有订阅任何报刊刊的学生有多少人？ 分析：设 A={ 订《中国少年报》的学生 } B={ 订《少年文艺》的学生 } C={ 订《中小学数学教学报》的学生 } I={ 全校学生 } 则问题是要求 A∪B∪C 在 I 中的补集 A∪B∪C 所含元素的个数： A∪B∪C=960－ A∪B∪ C =960-（510+330+120-270+58 ）=212（人） 答：全校有 212 名学生没订于任何报刊。 例 4 六年级学生参加课外活动， 有 32 人参加科技小组， 有 24 人参加排球队， 有 27 人参加 绘画小组，其中既参加科技小组又参加排球队的有 10 人，既参加科技小组又参加绘画小组 的有 14 人，既参加排球又参加绘画小组的有 9 人，有 4 人 3 项活动