组合数学(61)省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 容斥原理及应用,6.1 容斥原理,第1页,回顾：加法原理,基本计数原理：加法原理,S=,S,1,S,2,S,m,，,S,i,S,j,，,i,j,则,：,|S|=|,S,1,|+|,S,2,|+|,S,m,|,条件,S,i,S,j,是非常苛刻，假如存在重合即,S,i,S,j,，那么怎样计数？,第2页,内容,6.1,容斥原理,处理含有重合集合并集计数原理。,第3页,6.1,容斥原理,一个简单例子,例,.,计算,1,到,600,中不能被,6,整除整数个数。,解,：,1,到,600,中能被,6,整除整数个数为,600/6=100,个。所以，,1,到,600,中不能被,6,整除整数个数是,600,100=500,个。,A,=|,S|,|,A|,第4页,一个问题,？,1到600中不能被6或5整除整数个数？,A,B,加法原理用于不相交集累计数，含有相交集合,怎样计数,？,第5页,容斥原理,研究有限集合,交或并,计数,。,简单计数问题：,容斥原理,B,A,第6页,A,1,和,A,2,分别是,S,中含有性质,P,1,和,P,2,元素集合，,S,中不含有性质,P,1,或,P,2,元素个数：,注意到：,S,A,2,A,1,A,1,A,2,第7页,定义一个计数函数,:,x,(,A,)=,1,当,x,A,0,当x,A,那么，只需证实：,对,x,S,下式成立,x,(,A,1,A,2,)=,x,(,S,),x,(,A,1,),x,(,A,2,)+,x,(,A,1,A,2,),注意到：,|A,1,A,2,|=,x,(,A,1,A,2,),x,S,第8页,S,中元素可分为,4,种情况：,1,）,x,不属于,A,1,和,A,2,;,左边,=1;,右边,=1,0,0,+0=1,2,）,x,属于,A,1,且,不属于,A,2,;,左边,=0;,右边,=1,1,0,+0=0,3,）,x,属于,A,2,不属于,A,1,;,左边,=0;,右边,=1,0,1,+0=0,4,）,x,属于,A,1,又属于,A,2,;,左边,0;,右边,=1,1,1,+1=0,S,A,2,A,1,A,1,A,2,x,(,A,1,A,2,)=,x,(,S,),x,(,A,1,),x,(,A,2,)+,x,(,A,1,A,2,),所以：,第9页,普通情形：容斥原理计数,定理,6.1.1,集合,S,不含有性质,P,1,P,2,P,m,物体个数：,|,S,|,|,A,i,|+|,A,i,A,j,|,A,i,A,j,A,k,|,+(,1),m,|,A,1,A,2,A,m,|,其中，第一个求和对集合,1,2,m,全部,1-,组合进行,第二个求和对集合,1,2,m,全部,2-,组合进行,依这类推,.,第10页,容斥原理证实：,验证每个元素在等式两边计数相等,。,1,）设,x,不含有性质,P,1,P,2,P,m,，左边计数为：,x,(,A,1,A,1,A,m,)=1,右边计数为：,1,0+0,0+(1)0,m,=1,2,）设,y,含有其中,n,(1),个,性质，那么，左边计数为：,y,(,A,1,A,1,A,m,)=0,第11页,右边计数：,y,(,S,)=1=,y,(,A,i,)=,n=,i,=1,m,因为：,y,S,因为,A,1,A,m,中有,n,个包含了,y,。,y,(,A,i,A,j,)=,i,j,是,1,.,m,2-,组合,注意,y,(,A,i,A,j,)=1,当且仅当,y,A,i,和,y,A,j,，所以，上式左边等于从,n,个物体取出,2,个组合个数,。类似可证：,y,(,A,i,A,j,A,k,)=,i,j,k,是,1,.,m,3-,组合,第12页,继续下去，最终式子右边最终一项：,y,(,A,1,A,1,A,m,)=,所以，右边等于：,0,这么,S,每个元素在两边含有相同计数。证实了定理。,第13页,推论,6.1.2,含有性质,P,1,P,2,P,m,物体个数：,|,A,i,|,A,i,A,j,|+,|,A,i,A,j,A,k,|,+(,1),m+,1,|,A,1,A,2,A,m,|,第14页,例,例,:,求,1,到,1000,不能被,5,6,或,8,整除数个数,.,解,：设,A,1,A,2,和,A,3,分别是,1,到,1000,中被,5,6,和,8,整除数集合，那么：,|A,1,|=,1000/5=200,|A,2,|=,1000/6=166,|A,3,|=,1000/8=125,而,|A,1,A,2,|=,1000/30=33,|A,1,A,3,|=,1000/40=25,|A,2,A,3,|=,1000/24=41,第15页,|A,1,A,2,A,3,|=,1000/120=8,由容斥原理，,=1000,(200+166+125)+(33+25+41)8,=600,第16页,例2,字,母,M,A,T,H,I,S,F,U,N,存在多少排列使得单词,MATH,IS,和,FUN,都不出现？,解9,个字母组成全部排列集合为,S,。,A,1,是,MATH,出现排列集合；,A,2,是,IS,出现排列集合；,A,3,是,FUN,出现排列集合。,利用容斥原理。,第17页,尤其情况例子,一些应用中，各个性质含有一定对称性，可简化公式。即,若,1,=|A,1,|=|A,2,|=|A,m,|,2,=|A,1,A,2,|=|A,m,1,A,m,|,3,=|A,1,A,2,A,3,|=|A,m,2,A,m,1,A,m,|,m,=|A,1,A,2,A,m,|,那么，,0,1,+,2,3,+,(1),k,k,+(1),m,m,第18页,应 用,例,.,从,0,到,99999,中有多少含有数字,2,5,和,8,整数,。,解：设,A,1,，,A,2,和,A,3,分别是不包含,数字,2,5,和,8,集合，需要计算,0,到,99999,整数个数：,0,=10,5,1,=|A,1,|=|A,2,|=|A,3,|=9,5,2,=|A,1,A,2,|=8,5,3,=|A,1,A,2,A,3,|=7,5,所以，答案为：,10,5,39,5,+38,5,-7,5,第19页,作业,6.6,习题,1.,3.,第20页,