组合数学(西安电子科技大学(第二版))容斥原理省公开课一等奖全国示范课微课金奖PPT课件.pptx

第4章 容斥原理,第1页,引言,容斥原理,应用,限制排列与棋盘多项式,莫比乌斯反演公式,第2页,4.1,引言,例 在一根长木棍上有两种刻度线，第一个刻度线将木棍分成,10,等份，第二种将木棍分成,12,等份。假如沿每条刻度线将木棍锯断，木棍总共被锯成多少段？,第3页,4.1,引言,例 在一根长木棍上有三种刻度线，第一个刻度线将木棍分成,10,等份，第二种将木棍分成,12,等份，第三种将木棍分成,15,等份。假如沿每条刻度线将木棍锯断，木棍总共被锯成多少段？,第4页,4.1,引言,第5页,4.1,引言,第6页,4.1,引言,第7页,4.2,容斥原理,第8页,4.2,容斥原理,第9页,4.2,容斥原理,第10页,4.2,容斥原理,第11页,4.2,容斥原理,第12页,4.2,容斥原理,第13页,4.2,容斥原理,第14页,4.2,容斥原理,第15页,4.2,容斥原理,第16页,4.3,应用,第17页,例,1,与,1000,之间不能被,4,5,和,6,整除整数有多少个？,解,:,令,A,=1,2,3,1000,，则,|,A,|=1000.,记,A,1,、,A,2,、,A,3,分别为在,1,与,1000,之间能被,4,5,和,6,整除整数,集合，则有：,|,A,1,|=,L,1000/4,=250,|,A,2,|=,L,1000/5,=200,|,A,3,|=,L,1000/6,=166,4.3,应用,第18页,于是,A,1,A,2,表示,A,中能被,4,和,5,整除数,即能被,20,整除数，其个数为,|,A,1,A,2,|=,L,1000/20,=50,；,同理,|,A,1,A,3,|=,L,1000/12,=83,|,A,2,A,3,|=,L,1000/30,=33,4.3,应用,第19页,A,1,A,2,A,3,表示,A,中能同时被,4,5,6,整除数，即,A,中能被,4,5,6,最小公倍数,lcm,(4,5,6)=60,整除数，其个数为,|,A,1,A,2,A,3,|=,L,1000/60,=16.,由容斥原理知，,A,中不能被,4,5,6,整除整数个数为,:,4.3,应用,第20页,例,六一儿童节快到了，有爱心巧手妈妈做了,3,个布娃娃、,4,个小布熊、,5,个布兔子共,12,个布玩具，现选,10,个送给某儿童福利院，假如忽略同类玩具差异那么有多少种选送方法？,此问题相当于求,S,=3,a,4,b,5,c,10-,组合数,.,4.3,应用,第21页,例,求,S,=3,a,4,b,5,c,10-,组合数,.,解,:,令,S,=,a,b,c,，则,S,10-,组合数为,设集合,A,是,S,10-,组合全体，则,|,A,|,66,，现在要求在,10,组合中,a,个数小于等于,3,，,b,个数小于等于,4,，,c,个,数小于等于,5,组合数,.,定义性质集合,P,P,1,P,2,P,3,其中：,P,1,：,10,组合中,a,个数大于等于,4,；,P,2,：,10,组合中,b,个数大于等于,5,；,P,3,：,10,组合中,c,个数大于等于,6.,将满足性质,P,i,10-,组合全体记为,A,i,(1,i,3).,4.3,应用,第22页,那么，,A,1,中元素能够看作是由,S,10,4,6,组合再拼上,4,个,a,组成，所以,同理，,类似地，,而,a,个数小于等于,3,，,b,个数小于等于,4,，,c,个数小于等于,5,10-,组合全体为 由容斥原理知，它元素个数为,:,4.3,应用,第23页,例,确定在非负整数,x,1,x,2,x,3,x,4,小于7,时，方程,x,1,+,x,2,+,x,3,+,x,4,=10,整数解个数。,解,设,S,为该方程整数解非负整数解集合，,|,S,|=286,令,P,i,是性质,x,i,=8(,i,=1,2,3,4),并令,A,i,为,S,中含有性质,P,i,集合，问题变为求,A,1,是方程,x,1,+,x,2,+,x,3,+,x,4,=10(,x,1,=8,x,2,=0,x,3,=0,x,3,=0),整数解集合。,类似地，,而,A,i,(,i,=1,2,3,4),任意两个以及两个以上交集均为空集，故,4.3,应用,第24页,4.3,应用,第25页,例,在一次聚会上有,n,为男士和,n,位女士。这,n,位女士能够有多少种方法选择男舞伴？假如每个人必须换舞伴，那么第二次跳舞又有多少种选择方法？,4.3,应用,第26页,证实,：,令,S,是,1,2,n,全排列全体，则,|,S,|,n,!,.,定义,S,上性质集合,P,=,P,1,P,2,P,3,.,P,n,其中,P,i,表示排列中,i,在其自然次序位置上,(1,i,n,),.,令,A,i,为,S,中满足性质,P,i,全排列集合,.,因,A,i,中每一个全排列形如,j,1,j,i,-1,ij,i,+1,j,n,，,而,j,1,j,i,-1,j,i,+1,j,n,是,1,2,i,-1,i,+1,n,全排列，所以有,|,A,i,|=(,n,-1)!(1i,n,).,同理，有,|,A,i,A,j,|=(,n,-2)!(1,i,j,n,).,普通地，有,|,A,i,1,A,i,2,A,ik,|=(,n,-,k,)!,，,其中,1,i,1,i,2,i,k,n,且,i,1,i,2,i,k,互不相等,.,4.3,应用,第27页,而,D,n,为,S,中不满足性质,P,i,元素个数，由容斥原理，有,4.3,应用,第28页,例,确定,1,2,3,4,5,6,7,8,没有偶数在它自然位置上排列数。,例,确定,1,2,n,恰有,k,个整数在它们自然位置上排列数。,4.3,应用,第29页,4.3,应用,第30页,4.3,应用,第31页,4.3,应用,第32页,4.3,应用,第33页,4.3,应用,第34页,4.3,应用,第35页,4.3,应用,第36页,4.4,限制排列与棋盘多项式,第37页,4.4,限制排列与棋盘多项式,第38页,4.4,限制排列与棋盘多项式,第39页,4.4,限制排列与棋盘多项式,例,8,个小孩围坐在旋转木马上，问有多少种变换座位方法，使得每个小孩前面坐都不是原来小孩？,第40页,解,将围坐在旋转木马上,8,个小孩按逆时针方向用,1,2,8,编号,那么,问题就是在,1,2,8,循环排列中没有模式,12,23,78,81,全体数目。,设,S,是,1,2,8,循环排列全体，则,|S|=7!,。,设,A,1,=,S,中,1,和,2,连续排在一起循环排列,A,2,=,S,中,2,和,3,连续排在一起循环排列,A,8,=,S,中,8,和,1,连续排在一起循环排列,则问题归结为求,4.4,限制排列与棋盘多项式,第41页,(1)|,A,i,|=6!,i,=1,2,8.,(2)|,A,i,A,j,|=5!.,|,A,i,1,A,i,2,A,ik,|=(8-,k,)!,所以，,4.4,限制排列与棋盘多项式,第42页,6.4,、,5,带有禁止位置排列,例,求多重集,S=3,a,4,b,2,c,排列数，其中同一个字母全体不得连续出现（比如，,abbbbcaac,是不允许，而,abbbacacb,是允许）。,第43页,4.4,限制排列与棋盘多项式,第44页,4.4,限制排列与棋盘多项式,第45页,4.4,限制排列与棋盘多项式,第46页,4.4,限制排列与棋盘多项式,第47页,4.4,限制排列与棋盘多项式,第48页,4.4,限制排列与棋盘多项式,第49页,4.4,限制排列与棋盘多项式,第50页,4.4,限制排列与棋盘多项式,第51页,4.4,限制排列与棋盘多项式,第52页,4.4,限制排列与棋盘多项式,第53页,再见,第54页,