容斥原理及应用.ppt

1、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个注意：蓝色的数同时出现在两个序列中。,2,但答案不该是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：163=13容斥原理仅仅研究有限集合的交或并的计数。例：对于1,2,n的排列i1,i2,in，其中i11的排列有多少个？分析第一种方法：集合1,2,k-1,k+1,n的(n-1)-排列共有(n-1)!。现在将k置于这些,3,(n-1)

2、-排列的首位之前，就得到所有以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)！。,4,例:1到600中不能被6整除的整数的个数是多少？分析1到600共有600个数，能被6整除的有：600/6=100个。因此，不能被6整除的数有600-100=500个一般来说，对于集合S中的元素定义一种性质P，

3、xS，若x具有性质P，则P(x)为真。于是，所有具有性质P的元素的集合:,5,A=xxSP(x)而不具性质P的元素集合是：=SA=xxSxA=xxSP(x)显然=SA这就是容斥原理最简单的例子。将这个例子给予推广：令S是一些物体的集合，并令P1和P2,6,是S的每个物体可能具有或者不具有的两个性质我们目的是为了求出S中即不具有P1也不具有P2的两性质的物体的个数，按下列步骤：先求出S中所有物体的个数，然后去掉具有性质P1的物体个数，再去掉具有性质P2的物体个数，如果一些物体同时具有P1和P2两种性质，它们就会被去掉两次，那么我们需要再加回这些物体的个数，用符号表示如下：,7,令A1=xxSP1

4、(x),A2=xxSP2(x)表示那些即不具有P1也不具有P2性质的物体。我们有,S=,A2,A1,A1A2,8,由于上式左边表示那些既无性质P1也无性质P2的物体的个数，因此可以通过对等式右边增加1个性质P1、P2都不具有的物体，而加其他物体等于给等式右边增加0个,由此来证明等式的合理性；如果x是性质P1、P2都不具有的一个物体，那么它算作S的一个物体但不算作A1和A2的，并且它也不能算作A1A2的，因此，它的加入,9,为等式的右边净增加：100+0=1物体。如果x只具有性质P1，那么它为等式的右边净增加：110+0=0物体。如果x只具有性质P2，那么它为等式的右边净增加：101+0=0物体

5、。最后，如果x具有性质P1、P2，那么它为等式的右边净增加：111+1=0物体。因此等式右边的变化只与那些S中性质P1、P2,10,都不具有的物体个数有关。这就与等式的左边达到一致。更进一步，设S是集合，它上面定义了m个性质Pi（i1,2,m）,于是，具有性质Pi的元素的集合是：Ai=xxSPi(x),i1,2,m,11,对于1,2,m的任一r-组合i1,i2,ir，同时具有性质的元素的集合是：一般情况下，这一集合可能非空，此时，我们希望计算同时不具有性质P1,P2,Pm的集合：,12,中有多少个元素,容斥原理就是指出如何通过对确实具有这些性质的物体的计数来计算上述同时不具有性质Pi集合中物体

6、的个数。因此，在这种意义下，容斥原理“颠倒”了计数过程。下面的定理是将容斥原理推广到m个子集合上的情况，也就是将性质推广m个：P1,P2,Pm；,13,定理6.1.1集合S的不具备性质P1,P2,Pm的物体的个数由下式给出:,其中，第一个和对1,2,m的所有1-组合i,14,进行，第二个和对1,2,m的所有2-组合i,j进行，第三个和对1,2,m的所有3-组合i,j,k进行等等。m=2时我们已经讨论过了，当m=3时上式变成,15,当m=4时上式又变成：,m为一般的情况下，公式右边的展开如下：,16,公式右边的项数有如下情况：,17,公式的左边是对S的不具有性质Pi(i=1,2,.m)的物体的计

7、数，对右边增加1个性质Pi都不具有的物体x。公式右边的净增加数为：10+00+0+(-1)0m=1它在S中而不在其他子集Ai中。考虑恰好具有n(n1)个性质Pi(i=1,2,.n)的物体y,y这一个物体在S中仅占数量是,18,由于y恰好具有n个性质，它刚好是子集:A1,A2,A3,.Am中恰好n个的成员，它对Ai提供数值为：我们可以以种方式为y选择恰好具有一对性质Pi和Pj,那么y恰好是形式为AiAj,那些集合中的个成员，因此y给AiAj提供数值为：,对AiAjAk提供数值为：,19,等等。因此y对于公式右边提供数值增加为：,因为nm，若kn，则根据P82恒等式5-4上式为0，因此，如果y至少

8、具有一个性质Pi，那么它对公式右边的净增数值就是0。,20,实际上在集合的运算中，我们已经接触过容斥原理，例如：三个集合的元素关系有：ABC=A+B+CABACBC+ABC,A,B,C,21,例：一个学校中的某班只开三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？解：令：M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；那么：,22,M=170，P=130，C=120，MP=45MC=22，PC=20，MPC=3本题的目的

9、是要求出：的数字，由容斥原理的公式：MPC=M+P+CMPMCPC+MPC=170+130+120452220+3=336人,23,定理：设Ai(i=1,2,n)是有限集合，则：,证明：用数学归纳法证明。已知n=2时有：,24,设n-1时成立，即有：,所以在取n时就有：,25,由交、并运算的分配律，上式中最后一项有：,26,由假设n-1时成立n-1个集合并的元素计数公式将这n-1个两个集合交构成的并展开：,27,将n-1时成立展开式、以及上面的推导结果代入，原等式的左边为：,由假设n-1时成立n-1个集合并的元素计数公式,28,29,30,31,如果利用德.摩根律(De.Mogan)也能得到容

10、斥原理:,32,例1求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df子串的排列数。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，AB为同时出现ace、df的排列数。所以A=4！；B=5！；AB=3！；根据容斥原理，不出现ace和df的排列数为：,33,例:求从1到1000不能被5,6和8整除的整数的个数;解：我们将两个整数a,b或者三个整数a,b,c的最小公倍数记为：lcma,b或者lcna,b,c.令P1P2P3分别表示能被5,6,8整除的性质，S是1到1000的整数集合。Ai(i=1,2,3)是那些具有Pi性质的子集合，题意是要我们求出：,34

11、,首先：同时被5，6整除即是能被lcm5,6=30整除，同理lcm5,8=40，lcm6,8=24，那么：,35,同理lcm5,6,8=120，就有：由容斥原理，从1到1000不能被5,6和8整除的整数的个数等于：,36,例：求由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=2n,37,ABC=1a,b,c至少出现一次的n位符号串集合即为:它元素个数为：,38,例:

12、求不超过100的素数个数。解：因102=100，比10小的素数有2、3、5、7故不超过100的合数必然是2、3、5、7的倍数，而且不超过100的合数的因子不可能都超过10，通过求合数的补集来求素数个数。设：Ai为不超过100的数i的倍数集，i=2，3，5，7。,39,40,41,注意：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，7173，

13、79，83，89，97共计：25个,42,在容斥原理中，设集合的大小仅依赖于k而不依赖于在交中使用了哪k个集合。或者说Ai它们的基数一致；AiAj它们的基数一致;AiAjAk它们的基数一致;.这样就存在常数0,1,2,.m,使得0=S1=A1=A2=A3=Am,43,2=A1A2=A2A3=Am-1Am3=A1A2A3=Am-2Am-1Amm=A1A2A3Am-1Am即在Ai=Aj等情况下我们只统计Ai的个数，在这种情况下容斥原理可以简化成：,44,这是因为在容斥原理中出现的第k个求和包含个被加数，并且每个都等于k例：从0到99999有多少含有数字2,5,8的整数。解：设S是从0到99999的数字，加前导0就全是,45,五位字符串，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,46,总结,本次