容斥原理及应用

1、第六章 容斥原理及应用6.1 是讨论和排斥的计数问题例: 1,2,3,. 20中2或3的倍数的个数解: 2的倍数是：2，4，6，8，10，12，14， 16，18，20。 共10个3的倍数是：3，6，9，12，15， 18。共 6个注意：蓝色的数同时出现在两个序列中。1但答案不该是10+6=16 个，因为6，12，18在两 类中重复计数，应减去。故答案是： 163 = 13 容斥原理仅仅研究有限集合的交或并的计数。例：对于1,2,n的排列i1, i2, , in，其中 i1 1的排列有多少个？分析 第一种方法：集合1,2, k-1, k+1, , n的 (n-1) -排列共有(n-1)!。现在

2、将k置于这些2 (n-1) -排列的首位之前，就得到所有以k开始的 n-排列，依然有 (n-1)!个。由于k不能等于1，所以共有(n-1)(n-1)!个首位不为1的n-排列。 第二种思路： 1,2,n的排列数是n!， 2,3,n 的(n-1)-排列数是(n-1)!，每个(n-1)-排列的首位前置一个1，就得到所有首位为1的(n-1)!个n-排列。于是，首位不为1的n-排列的个数是： n! (n-1)! = (n-1)(n-1)！。3例:1到600中不能被6整除的整数的个数是多少？ 分析 1到600共有600个数，能被6整除的有： 600/6=100个。 因此，不能被6整除的数有600-100=

3、500个一般来说，对于集合S中的元素定义一种性质P，x S ，若x具有性质P，则P(x)为真。于是，所有具有性质P的元素的集合:4 A=xx S P(x) 而不具性质P的元素集合是： = S A=xx S x A = xx S P(x) 显然 =SA 这就是容斥原理最简单的例子。将这个例子给予推广：令S是一些物体的集合，并令P1和P25 是S的每个物体可能具有或者不具有的两个性质 我们目的是为了求出S中即不具有P1也不具有P2的两性质的物体的个数，按下列步骤： 先求出S中所有物体的个数，然后去掉具有性质P1的物体个数，再去掉具有性质P2的物体个数，如果一些物体同时具有P1和P2两种性质，它们就

4、会被去掉两次，那么我们需要再加回这些物体的个数，用符号表示如下：6 令A1=xx S P1(x) , A2=xx S P2(x) 表示那些即不具有P1也不具有P2性质的物体。我们有S =A2A1A1 A27由于上式左边表示那些既无性质P1也无性质P2的 物体的个数，因此可以通过对等式右边增加1个性质P1 、P2都不具有的物体，而加其他物体等于给等式右边增加0个,由此来证明等式的合理性； 如果x是性质P1 、P2都不具有的一个物体，那么它算作S的一个物体但不算作A1和A2的，并且它也不能算作A1A2的，因此，它的加入8为等式的右边净增加：1 0 0 + 0 = 1 物体。 如果x只具有性质P1

5、，那么它为等式的右边净增加：1 1 0 + 0 = 0 物体。 如果x只具有性质P2 ，那么它为等式的右边净增加：1 0 1 + 0 = 0 物体。最后，如果x具有性质P1 、P2 ，那么它为等式的右边净增加：1 1 1 + 1 = 0 物体。 因此等式右边的变化只与那些S中性质P1 、P2 9都不具有的物体个数有关。这就与等式的左边 达到一致。更进一步，设S是集合，它上面定义了m个性质 Pi（i1, 2, , m）,于是，具有性质Pi的元素的集合是： Ai = xx S Pi(x) , i1, 2, , m10对于1, 2, , m的任一r-组合i1, i2, , ir，同时 具有性质 的元

6、素的集合是： 一般情况下，这一集合可能非空，此时，我们希望计算同时不具有性质P1, P2, , Pm的集合：11 中有多少个元素, 容斥原理就是指出如何通 过对确实具有这些性质的物体的计数来计算上述同时不具有性质Pi集合中物体的个数。因此，在这种意义下，容斥原理“颠倒”了计数过程。 下面的定理是将容斥原理推广到m个子集合上的情况，也就是将性质推广m个： P1, P2, , Pm ；12定理6.1.1 集合S的不具备性质P1, P2, , Pm的物 体的个数由下式给出:其中，第一个和对1,2,m的所有1-组合i13进行，第二个和对1,2,m的所有2-组合i, j 进行，第三个和对1,2,m的所有

7、3-组合i, j, k 进行等等。m = 2 时我们已经讨论过了，当 m=3 时上式变成14 当 m=4 时上式又变成：m为一般的情况下，公式右边的展开如下：15公式右边的项数有如下情况：16公式的左边是对 S的不具有性质Pi (i=1,2, .m) 的物体的计数，对右边增加1个性质Pi都不具有的物体x。公式右边的净增加数为： 1 0 + 0 0 + 0 + (-1)0m = 1 它在S中而不在其他子集Ai中。考虑恰好具有n (n1)个性质Pi (i=1,2, . n)的物体 y , y 这一个物体在S中仅占数量是17由于 y 恰好具有n个性质，它刚好是子集: A1, A2, A3,. Am中

8、恰好n个的成员，它对 Ai提供数值为：我们可以以 种方式为y 选择恰好具有一对性质Pi 和Pj ,那么y恰好是形式为AiAj , 那些集合中的 个成员，因此y给 AiAj 提供数值为： ,对 AiAj Ak提供数值为： 18 等等。因此y对于公式右边提供数值增加为：因为nm，若kn，则 根据P82恒等式5-4上式为0，因此，如果y至少具有一个性质Pi ，那么它对公式右边的净增数值就是0。19实际上在集合的运算中，我们已经接触过容斥 原理，例如：三个集合的元素关系有：ABC=A+B+CABACBC +ABCABC20例：一个学校中的某班只开三门课程：数学、 物理、化学。已知修这三门课的学生分别

9、有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？解：令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；那么：21M=170，P=130，C=120，MP=45 MC=22，PC =20，MPC=3本题的目的是要求出： 的数字，由容斥原理的公式：MPC=M+P+CMP MCPC +MPC =170+130+120452220+3 =336人22定理：设Ai (i=1,2,n)是有限集合，则： 证明：用数学归纳法证明。已知 n=2时有： 23 设 n-1时成立，即有

10、：所以在取n时就有：24由交、并运算的分配律，上式中最后一项有： 25由假设n-1时成立n-1个集合并的元素计数公式将这n-1个两个集合交构成的并展开：26将n-1时成立展开式、以及上面的推导结果代入，原等式的左边为：由假设n-1时成立n-1个集合并的元素计数公式27282930如果利用德.摩根律(De.Mogan)也能得到容斥原理:31例1 求a,b,c,d,e,f六个字母的全排列中不允许出 现ace和df子串的排列数。 解：设A为ace作为一个元素出现的排列集，B为 df作为一个元素出现的排列集，AB为同时出现ace、df的排列数。所以A= 4！； B= 5！；AB= 3！；根据容斥原理，

11、不出现ace和df的排列数为：32例:求从1到1000不能被5,6和8整除的整数的个数; 解：我们将两个整数a,b或者三个整数a,b,c的最小公倍数记为：lcma,b或者lcna,b,c. 令P1 P2 P3分别表示能被5,6,8整除的性质，S是1到1000的整数集合。Ai ( i=1,2,3 ) 是那些具有Pi性质的子集合，题意是要我们求出：33 首先：同时被5，6整除即是能被lcm 5, 6 = 30整除，同理lcm 5, 8 = 40 ，lcm 6, 8 = 24，那么：34同理lcm 5, 6, 8 = 120 ，就有：由容斥原理，从1到1000不能被5,6和8整除的整数的个数等于：3

12、5例： 求由a,b,c,d四个字母构成的n位符号串中， a,b,c至少出现一次的符号串数目。解：令A、B、C分别为n位符号串中不出现a,b,c符号的集合。 由于n位符号串中每一位都可取a,b,c,d四种符号中的一个，故不允许出现各字母的n位符号串的个数应是: A=B= C= 3n， AB = AC=BC = 2n36 AB C= 1 a,b,c至少出现一次的n位符号串集合即为: 它元素个数为：37例: 求不超过100的素数个数。解：因 102=100，比10小的素数有2、3、5、7 故不超过100的合数必然是2、3、5、7的倍数，而且不超过100的合数的因子不可能都超过10，通过求合数的补集来

13、求素数个数。 设： Ai为不超过100的数i的倍数集， i = 2，3，5，7 。383940 注意：22并非就是不超过100的素数个数， 因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过100的素数个数为： 22+4-1=25 小于100的素数它们是： 2， 3， 5， 7，11，13，17，19，23，29， 31， 37，41，43，47，53，59，61，67，71 73，79，83，89，97 共计：25个41 在容斥原理中，设集合的大小仅依赖于k而不依赖于在交中使用了哪k个集合。或者说Ai它们的基数一致； AiAj它们的基数一致;

14、AiAjAk它们的基数一致;. 这样就存在常数0, 1, 2, .m,使得 0=S 1= A1= A2= A3= Am422= A1A2= A2A3= = Am-1Am 3= A1A2A3= Am-2Am-1Am m= A1A2A3 Am-1Am即在Ai= Aj等情况下我们只统计Ai的个数，在这种情况下容斥原理可以简化成：43这是因为在容斥原理中出现的第k个求和包含个被加数，并且每个都等于k例：从0到99999有多少含有数字2,5,8的整数。解：设S是从0到99999的数字，加前导0就全是44 五位字符串，S就是多重集50,51,52,. 59 的5-排列，令P1,P2 ,P3分别是整数但不包含有数字2，5，8这个性质，令A1,A2 ,A3分别是S中具有性质P1,P2 ,P3的整数集合。题意思求出集合 的元素个数。利用前面的知识可知0= 105， 1= 95，2= 85， 3= 75答案为： 105 - 95- 85- 75 = 105 - 395+385- 75