1、 组合数学组合数学 第六讲第六讲容斥原理容斥原理1一一 . 引言引言容斥原理是组合数学中的一个重要容斥原理是组合数学中的一个重要 原理原理 ,它在计数问题中占有很重要地位它在计数问题中占有很重要地位 . 容斥原理所研究的问题是与若干有容斥原理所研究的问题是与若干有限集的交、并或差有关的计数限集的交、并或差有关的计数 . 在实际工作中在实际工作中 , 有时要计算具有某种有时要计算具有某种性质的元素个数性质的元素个数 . 例例 : 某单位举办一个外语培训班某单位举办一个外语培训班 , 开设开设英语英语 , 法语两门课法语两门课 . 2设设 U为该单位所有人集合为该单位所有人集合 , A,B分别为分
2、别为学英语学英语 , 法语人的集合法语人的集合 , 如图所示如图所示 . 学两门外语的人数为学两门外语的人数为 |AB|, 只学一门只学一门外语的人数为外语的人数为 |AB|-|AB|, 没参加学习没参加学习的人数为的人数为 |U|-|AB|. 3l在一些计数问题中在一些计数问题中 , 经常遇到经常遇到 间接间接 计计算一个集合中算一个集合中 具有某种性质的元素个具有某种性质的元素个数数 比起比起 直接直接 计算来得简单计算来得简单 . 例例 : 计算计算 1到到 700之间不能被之间不能被 7整除的整整除的整数个数数个数 . l直接计算相当麻烦直接计算相当麻烦 ,间接计算非常容易间接计算非常
3、容易. l先计算先计算 1到到 700之间能被之间能被 7整除的整数整除的整数个数个数 =700/ 7=100, 所以所以 1到到 700之间不之间不能被能被 7整除的整数个数整除的整数个数 =700-100=600. 4l因此因此 , 当直接求解受阻或无法达到目当直接求解受阻或无法达到目的时的时 , 应考虑间接求解方法应考虑间接求解方法 . 所谓所谓 “曲曲径通幽径通幽 ”, 说的就是这个道理说的就是这个道理 . l上面举的间接计数的例子是利用了如上面举的间接计数的例子是利用了如下原理：下原理： 如果如果 A是集合是集合 S的子集的子集 , 则则 A中的元素个数等于中的元素个数等于 S中的元
4、素个数减中的元素个数减去不在去不在 A中的元素个数中的元素个数 , 这个原理可这个原理可写成写成5我们的目的并不仅仅是讨论这样我们的目的并不仅仅是讨论这样一个简单的原理一个简单的原理 , 而是讨论这个原而是讨论这个原理的一个重要推广理的一个重要推广 , 称之为称之为 容斥原容斥原理理 ,并且将它运用到若干问题上去并且将它运用到若干问题上去 , 其中包括：其中包括：错位排列、有限制的排列、禁错位排列、有限制的排列、禁位排列和棋阵多项式位排列和棋阵多项式 等等 .6DeMorgan定理定理 : 设设 A, B为全集为全集 U的任意的任意两个子集两个子集 , 则则DeMorgan定理的推广定理的推广
5、 : 设设 A1,A2, ,An为为U的子集的子集 , 则则二二 . 容斥原理容斥原理71. 两个集合的容斥原理两个集合的容斥原理 l设设 A和和 B是分别具有性质是分别具有性质 P1和和 P2的元的元素的集合素的集合 , 则则例例 6.1 求求 1到到 500之间能被之间能被 5或或 7整除的整除的正整数个数正整数个数 . 解解 设设 A为被为被 5整除的整数集合整除的整数集合 , B为被为被 7整除的整数集合整除的整数集合 , 用用 x表示表示 x的整数的整数部分部分 , 则有则有8同时被同时被 5和和 7整除的整数个数整除的整数个数故能被故能被 5或或 7整除的整数个数整除的整数个数92. 三个集合上的容斥原理三个集合上的容斥原理设设 A, B, C为任意三个集合为任意三个集合 , 则有则有3. n个集合上的容斥原理个集合上的容斥原理 : 设设 A1,A2, ,An是有限集合是有限集合 , 则有则有10
