资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计数问题是组合数学研究的重要问题之一。,已学过的一些计数方法：如 加法法则，母函数方法等；,两个重要的计数原理：,容斥原理,和,P,lya,计数定理,。,本次课我们先学习容斥原理及其应用。,3.1,容斥原理,解：,2,的倍数是：,2,，,4,，,6,，,8,，,10,，,12,，,14,，,16,，,18,，,20,。共,10,个；,3.1,容斥原理,例,1,求,不超过,20,的正整数,中,2,或,3,的倍数的个数。,否！因为,6,，,12,，,18,在两类中重复计数，应减去。,3,的倍数是：,3,，,6,，,9,，,12,，,15,，,18,。共,6,个；,答案是,10+6,=16,个吗？,故答案是：,16-,3,=,13,对于求两个有限集合,A,和,B,的并的元素数目,，我们,有,即具有性质,A,或,B,的元素的个数等于具有性质,A,的元素个数和具有性质,B,的元素个数减去同时具有性质,A,和,B,的元素个数。,(1),定理,1,3.1,容斥原理,3.1,容斥原理,A,B,A,B,U,3.1,容斥原理,定理,2,3.1,容斥原理,A,B,C,A,B,A,B,C,B,C,A,C,U,例,2,一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有,170,、,130,、,120,人；同时修数学、物理的学生,45,人；同时修数学、化学的,20,人；同时修物理化学的,22,人。同时修三门的,3,人。假设每个学生至少修一门课，问这学校共有多少学生？,3.1,容斥原理,解：,令,A,为修数学的学生集合；,B,为修物理的学生集合；,C,为修化学的学生集合,；,即学校学生数为,336,人。,3.1,容斥原理,同理可推出：,利用数学归纳法可得一般的定理：,3.1,容斥原理,3.1,容斥原理,(4),定理,3,设,是有限集合，则,3.1,容斥原理,(5),容斥原理,指的就是,（,4,）,和,（,5,）,式。,用来计算有限集合的,并,或,交,的元素个数。,例,3,求从,1,到,500,的整数中能被,3,或,5,除尽的数的个数,.,3.1,容斥原理,解：,令,A,为从,1,到,500,的整数中被,3,除尽的数的集,合，,B,为被,5,除尽的数的集合,被,3,或,5,除尽的数的个数为,解：,令,A,、,B,、,C,分别为不出现,a,，,b,，,c,符号的集合。,即有,3.1,容斥原理,例,4,求由,a,b,c,d,四个字母构成的,n,位符号串中,a,b,c,都,至少出现一次的符号串数目。,a,b,c,都,至少出现一次的,n,位符号串,数目,为,3.1,容斥原理,例,5,用,26,个英文字母作,不允许重复,的全排列，要求排除,dog,，,god,，,gum,，,depth,，,thing,字样的出现，求满足这些条件的排列数。,3.1,容斥原理,解：,所有排列中，令,则,出现,dog,字样的排列，相当于把,dog,作为一个单元参加排列，故,类似有：,由于,god,dog,不可能在一个排列中同时出现，故：,3.1,容斥原理,由于,gum,dog,可以在,dogum,中同时出现，故有：,类似有,3.1,容斥原理,3.1,容斥原理,其余多于,3,个集合的交集都为空集。,3.1,容斥原理,故满足要求的排列数为：,1.,再解错排问题,n,个元素依次给以标号,1，2，,n,。,n,个元素,的全排列中，求每个元素,都不在自己原来位置,上的排列数。,设,A,i,为,元素,i,在第,i,位上的全体排列,i,=,1,2,n,。,则有,|,U,|=,n,!,，,因元素,i,不能动，因而有：,3.2,容斥原理,应,用,同理,每个元素都不在原来位置的排列数为,3.2,容斥原理,应,用,3.2.,容斥原理,应,用,2.1,棋盘多项式,n,个不同元素的一个全排列可看做,n,个相同的棋子在,n,n,的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子,x,x,x,x,x,排列,41352,对应于如图所示的布局。,3.2.,容斥原理,应,用,可以把棋盘的形状推广到任意形状：,布子规定同上。,令,r,k,(C),表示,k,个棋子布到棋盘,C,上的方案数。,3.2.,容斥原理,应,用,r,1,()=1,r,1,()=2,r,1,()=2,r,2,()=0,r,2,()=1,3.2.,容斥原理,应,用,规定,r,0,(,C,)=1,，,包括,C=,时。,设,C,i,是棋盘,C,的某一指定格子所在的行与列都去掉后所得的棋盘；,C,e,是仅去掉该格子后的棋盘。,在上面定义下，显然有,r,k,(C,)=,r,k,-,1,(C,i,),r,k,(C,e,),3.2.,容斥原理,应,用,从而,R(C),=,r,k,(C,),x,k,=1+,r,k,-,1,(C,i,)+,r,k,(C,e,),x,k,=,x,r,k,(C,i,),x,k,+,r,k,(C,e,),x,k,=,x,R(C,i,)+R(C,e,)(3),k,=0,k,=1,k,=0,k,=0,定义,1,设,C,为一棋盘，称,R(C)=,r,k,(C,),x,k,为,C,的棋盘多项式。,k,=0,3.2.,容斥原理,应,用,例如：,R()=1+,x,；,R()=,x,R,()+R()=,x,+(1+,x,)=1+2,x,；,R()=,x,R()+R(),=,x,(1+,x,)+1+,x,=1+2,x,+,x,2,3.2.,容斥原理,应,用,如果,C,由相互分离的,C,1,，,C,2,组成，即,C,1,的任一格子所在的行和列中都没有,C,2,的格子。则有：,R(C)=,(,r,i,(C,1,),r,k-i,(C,2,),x,k,=(,r,i,(C,1,),x,i,)(,r,j,(C,2,),x,j,),j,=0,n,n,k,n,i,=0,i,=0,k,=0,R(C)=R(C,1,)R(C,2,),(4),i,=0,k,r,k,(C,)=,r,i,(C,1,),r,k-i,(C,2,),故,3.2.,容斥原理,应,用,利用,(,),和,(,),，可以把较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。,例,:,R,(),=,x,R,()+,R,(),=,x,(1+,x,),2,+(1+2,x,),2,=1+5,x,+6,x,2,+,x,3,*,R,(),=,x,R,()+,R,(),=1+6,x,+10,x,2,+4,x,3,*,3.2.,容斥原理,应,用,2.2,有禁区的排列,例,设对于排列,P=P,1,P,2,P,3,P,4,，,规定,P,1,，,P,4,，,P,2,，,P,4,2,。,1 2 3 4,P,1,P,2,P,3,P,4,这样的排列对应于有,禁区的布子。如左图,有影线的格子表示禁,区。,3.2.,容斥原理,应,用,定理,:,设,r,k,为,k,个棋子布入禁区的方案数，,k=,1,2,n,。则,有禁区的布子方案数（即禁区内不布子的方案数）为,n,!,r,1,(,n,1)!,r,2,(,n,2)!,(,1),n,r,n,(,1),k,r,k,(,n,k,)!,k,=0,n,3.2.,容斥原理,应,用,例,2,四位工人,，,A,B,C,D,四项任,务。,条件如下：,不干,B,；,不干,B,、,C,；,不干,C,、,D,；,不干,D,。,问有多少种可行方案？,3.2.,容斥原理,应,用,解,:,由题意，可得如下棋盘：,其中有影线的格子表示禁区。,A B C D,1 2 3 4,R,()=,1+6,x,+10,x,2,+4,x,3,方案数,=,4!,6(4,1)!+10(4,2)!,4(4,3)!,+0(4,4)!=4,3.2.,容斥原理,应,用,例,3,三论错排问题,错排问题对应的是,n,n,的棋盘的,主对角线,上的格子是禁区,的布子问题。,C=,R(C)=,则有,故错排问题的解为,:,欧拉函数,是,指,小于,n,且与,n,互素的正整数的个数。,设,1,到,n,的,n,个数中,p,i,倍数的集合为,解,：若,n,分解为素数的乘积,3.2.,容斥原理,应,用,3,欧拉函数,(,n,),3.2.,容斥原理,应,用,则有,3.2.,容斥原理,应,用,即比,60,小且与,60,互素的数有,16,个：,1,，,7,，,11,，,13,，,17,19,23,，,29,，,31,，,37,，,41,，,43,，,47,，,49,，,53,，,59,。,3.2.,容斥原理,应,用,
展开阅读全文