容斥原理及应用.ppt

《容斥原理及应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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在两类中重复计数，应减去。故答案是：16－3=13容斥原理仅仅研究有限集合的交或并的计数。例：对于{1,2,…,n}的排列i1,i2,…,in，其中i1≠1的排列有多少个？[分析]第一种方法：

2、集合{1,2,…,k-1,k+1,…,n}的(n-1)-排列共有(n-1)!。现在将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

3、到600中不能被6整除的整数的个数是多少？[分析]1到600共有600个数，能被6整除的有：600/6=100个。因此，不能被6整除的数有600-100=500个一般来说，对于集合S中的元素定义一种性质P，xS，若x具有性质P，则P(x)为真。于是，所有具有性质P的元素的集合:4A={xxS∧P(x)}而不具性质P的元素集合是：=S－A={xxS∧xA}={xxS∧┐P(x)}显然=S－A这就是容斥原理最简单的例子。将这个例子给予推广：令S是一些物体的集合，并令P1和P25是S的每个

4、物体可能具有或者不具有的两个性质我们目的是为了求出S中即不具有P1也不具有P2的两性质的物体的个数，按下列步骤：先求出S中所有物体的个数，然后去掉具有性质P1的物体个数，再去掉具有性质P2的物体个数，如果一些物体同时具有P1和P2两种性质，它们就会被去掉两次，那么我们需要再加回这些物体的个数，用符号表示如下：6令A1={xxS∧P1(x)},A2={xxS∧P2(x)}表示那些即不具有P1也不具有P2性质的物体。我们有S=A2A1A1∩A27由于上式左边表示那些既无性质P1也无性质P2的物体的个数，因此可

5、以通过对等式右边增加1个性质P1、P2都不具有的物体，而加其他物体等于给等式右边增加0个,由此来证明等式的合理性；如果x是性质P1、P2都不具有的一个物体，那么它算作S的一个物体但不算作A1和A2的，并且它也不能算作A1∩A2的，因此，它的加入8为等式的右边净增加：1–0–0+0=1物体。如果x只具有性质P1，那么它为等式的右边净增加：1–1–0+0=0物体。如果x只具有性质P2，那么它为等式的右边净增加：1–0–1+0=0物体。最后，如果x具有性质P1、P2，那么它为等式的右边净增加：1–1–1+1=0物体。因

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

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

8、一般的情况下，公式右边的展开如下：15公式右边的项数有如下情况：16公式的左边是对S的不具有性质Pi(i=1,2,….m)的物体的计数，对右边增加1个性质Pi都不具有的物体x。公式右边的净增加数为：1–0+0–0+0+……+(-1)0m=1它在S中而不在其他子集Ai中。考虑恰好具有n(n≥1)个性质Pi(i=1,2,….n)的物体y,y这一个物体在S中仅占数量是17由