容斥原理及应用.ppt

第六章客斥原理及用61容斥原理容斥原理是讨论包容和排斥的计数问题例:{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个注意:蓝色的数同时出现在两个序列中。但答案不该是10+6=16个,因为6,12,18在两类中重复计数,应减去。故答案是:16-3=13容斥原理仅仅研究有限集合的交或并的计数。例:对于{1,2,…,n}的排列,2…,in,其中i1≠1的排列有多少个?[分析]第一种方法:集合{1,2,k-1,k+1,…,m}的(n-1)-排列共有(n-1)!。现在将k置于这些(n-1)-排列的首位之前,就得到所有以k开始的n-排列,依然有(n-1)!个。由于k不能等于1,所以共有(m-1)m-1)个首位不为1的n排列第二种思路:{1,2,,以}的排列数是n!,{2,3,…,n}的(n-1)排列数是(n-1)!,每个(m-1)-排列的首位前置一个1,就得到所有首位为1的(n1)!个n-排列。于是,首位不为1的n-排列的个数是:n!-(n-1)!=(m-1)(n-1)!例:1到600中不能被6整除的整数的个数是多少?[分析]1到600共有600个数,能被6整除的600/6=100个。因此,不能被6整除的数有600-100=500个一般来说,对于集合S中的元素定义一种性质P,vx∈S,若x具有性质P,则P(x)为真。于是,所有具有性质P的元素的集合:A={x|xeS∧P(x)}而不具性质P的元素集合是:A=S-A={x|x∈S∧xA}={x|x∈S∧1P(x)显然|A|=|s|-|A这就是容斥原理最简单的例子。将这个例子给予推广:令S是一些物体的集合,并令P1和P2是S的每个物体可能具有或者不具有的两个性质我们目的是为了求出S中即不具有P1也不具有的***质的物体的个数,按下列步骤先求出S中所有物体的个数,然后去掉具有性质P1的物体个数,再去掉具有性质P2的物体个数,如果一些物体同时具有P和P2两种性质,它们就会被去掉两次,那么我们需要再如回这些物体的个数,用符号表示如下:令A1={x|xeS∧P1(x)},A2={x|xeS∧P2x)}A1=S-A1,A2=S-A2;集合A1∩A2表示那些即不具有P1也不具有P2性质的物体。我们有A1∩A2|=S|-41|-A2|+|41∩A2A1∩A2=A∪AA,∩AA由于上式左边表示那些既无性质P1也无性质P2的物体的个数,因此可以通过对等式右边增频个性质P1、P2都不具有的物体,而加其他物体等于给等式右边增加0个,由此来证明等式的合理性;如果x是性质P1、P2都不具有的一个物体,那么它算作S的一个物体但不算作A1和A2的,并且它也不能算作A1nA2的,因此,它的加入为等式的右边净增加:1-0-0+0=1物体。如果x只具有性质P1,那么它为等式的右边净增加:0+0=0物体如果x只具有性质P2,那么它为等式的右边净增加:1-0-1+0=0物体最后,如果x具有性质P1、P2,那么它为等式的右边净增加:1-1-1+1=0物体。因此等式右边的变化只与那些S中性质P1、P2都不具有的物体个数有关。这就与等式的左边A1∩A2达到一致更进一步,设S是集合,它上面定义了m个性质P1(i=1,2,…,m),于是,具有性质P的元素的集合是A2={x|x∈S∧P(x)},1,2