离散数学-生成函数及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,10.2,生成函数及其应用,牛顿二项式定理与牛顿二项式系数,10.2.2,生成函数的定义及其性质,10.2.3,生成函数的应用,1,牛顿二项式系数,定义,10.5,设,r,为实数，,n,为整数，引入形式符号,称为,牛顿二项式系数,.,例如,2,牛顿二项式定理,定理,10.6,（牛顿二项式定理）,设,为实数，则对一切实数,x,y,，,|,x,/,y,|1,，有,若,=,m,，其中,m,为正整数，那么,3,重要展开式,令,x,=,z,，,y,=1,，那么牛顿二项式定理就变成,在上面式子中用,z,代替,z,，则有,4,生成函数的定义,定义,10.6,设序列,a,n,，构造形式幂级数,G,(,x,)=,a,0,+,a,1,x,+,a,2,x,2,+,a,n,x,n,+,称,G,(,x,),为序列,a,n,的,生成函数,.,例如，,C,(,m,n,),的生成函数为,(1+,x,),m,给定正整数,k,k,n,的生成函数为,G,(,x,)=1+,kx,+,k,2,x,2,+,k,3,x,3,+=,5,生成函数的性质,1.,b,n,=,a,n,为常数，则,B,(,x,)=,A,(,x,),2.,c,n,=,a,n,+,b,n,则,C,(,x,)=,A,(,x,)+,B,(,x,),5,b,n,=,a,n,+,l,则,6,生成函数的性质,(,续,),8,b,n,=,n,a,n,为常数，,则,B,(,x,)=,A,(,x,),9,b,n,=,na,n,则,B,(,x,)=,xA,(,x,),7,证明,证,8,有关级数的结果,9,由序列求生成函数,例,1,求序列,a,n,的生成函数,(1),a,n,=7 3,n,(2),a,n,=,n,(,n,+1),解,10,由生成函数求序列通项,例,2,已知,a,n,的生成函数为,求,a,n,解,.,11,生成函数的应用,求解递推方程,计数多重集的,r,组合数,不定方程的解,整数拆分,12,求解递推方程,例,1,a,n,5,a,n,1,+6,a,n,2,=0,a,0,=1,a,1,=,2,G,(,x,)=,a,0,+,a,1,x,+,a,2,x,2,+,a,3,x,3,+,5,x G,(,x,)=,5,a,0,x,5,a,1,x,2,5,a,2,x,3,-,6,x,2,G,(,x,)=+6,a,0,x,2,+6,a,1,x,3,+,(1,5,x,+6,x,2,),G,(,x,)=,a,0,+(,a,1,5,a,0,),x,13,求解递推方程,(,续,),例,2,解：设,h,n,的生成函数为,14,求解递推方程,(,续,),15,多重集的,r,-,组合数,S,=,n,1,a,1,n,2,a,2,n,k,a,k,的,r,组合数就是不定方程,x,1,+,x,2,+,x,k,=,r,x,i,n,i,i=,1,2,k,的非负整数解的个数,的展开式中,y,r,的系数,生成函数,16,多重集的,r,-,组合数,(,续,),例,3,S,=3,a,4,b,5,c,的,10,组合数,解：生成函数,G,(,y,),=(1+,y,+,y,2,+,y,3,)(1+,y,+,y,2,+,y,3,+,y,4,)(1+,y,+,y,2,+,y,3,+,y,4,+,y,5,),=(1+2,y,+3,y,2,+4,y,3,+4,y,4,+3,y,5,+2,y,6,+,y,7,)(1+,y,+,y,2,+,y,3,+,y,4,+,y,5,),=(1+3,y,10,+2,y,10,+,y,10,+),N,=6,组合方案,a,a,a,b,b,b,b,c,c,c,a,a,a,b,b,b,c,c,c,c,a,a,a,b,b,c,c,c,c,c,a,a,b,b,b,b,c,c,c,c,a,a,b,b,b,c,c,c,c,c,a,b,b,b,b,c,c,c,c,c,17,不定方程解的个数,基本的不定方程,x,1,+,x,2,+,x,k,=,r,，,x,i,为自然数,18,不定方程解的个数,(,续,),带限制条件的不定方程,x,1,+,x,2,+,x,k,=,r,，,l,i,x,i,n,i,带系数的不定方程,p,1,x,1,+,p,2,x,2,+,p,k,x,k,=,r,，,x,i,N,生成函数,生成函数,19,重量,0,1,2,3,4,5,6,7,8,9,10,11,12,方案,1,1,2,1,2,1,2,1,2,1,2,1,1,实例,例,4,1,克砝码,2,个，,2,克砝码,1,个，,4,克砝码,2,个，问能称出,哪些重量，方案有多少？,解：,x,1,+2,x,2,+4,x,3,=,r,0,x,1,2,0,x,2,1,0,x,3,2,G,(,y,)=(1+,y,+,y,2,)(1+,y,2,)(1+,y,4,+,y,8,),=1+,y,+2,y,2,+,y,3,+2,y,4,+,y,5,+2,y,6,+,y,7,+2,y,8,+,y,9,+2,y,10,+,y,11,+,y,12,20,有序,无序,不重复,4=4,4=1+3,4=3+1,4=4,4=1+3,重复,4=4,4=1+3,4=3+1,4=2+2,4=2+1+1,4=1+2+1,4=1+1+2,4=1+1+1+1,4=4,4=1+3,4=2+2,4=2+1+1,4=1+1+1+1,正整数拆分,拆分,的定义：将给定正整数,N,表示成若干个正整数之和,.,拆分的分类,21,无序拆分,基本模型：将,N,无序拆分成正整数,a,1,a,2,a,n,a,1,x,1,+,a,2,x,2,+,a,n,x,n,=,N,不允许重复,允许重复,22,实例,例,5,证明任何正整数都可以唯一表示成,2,进制数,.,对应于将任何正整数,N,拆分成,2,的幂，,2,0,2,1,2,2,2,3,且不允许重复,.,生成函数,对于所有的,n,系数是,1,，这就证明唯一的表法,.,23,无序拆分,个数限制,例,6,给定,r,求,N,允许重复无序拆分成,k,个数,(,k,r,),的方法数,解,N,允许重复无序拆分成,k,个数（,k,r,）的方案,N,允许重复无序拆分成正整数,k,（,k,r,）的方案,做下述,Ferrers,图,将图以,y,=,x,对角线翻转,180,度，,得到,共轭的,Ferrers,图,.,16=6+5+3+2,（,k,4,）,对应每个数不超过,4,的拆分,:,16=4+4+3+2+2+1,这种拆分数的生成函数为,24,有序拆分,定理,10.7,将,N,允许重复地有序拆分成,r,个部分的方案数为,C,(,N,1,r,1).,证 设,N,=,a,1,+,a,2,+,a,r,是满足条件的拆分，则令,r,1,个,S,i,取值为,1,2,N,1,，方法数为,C,(,N,1,r,1).,推论,对,N,做任意重复的有序拆分，方案数为,不允许重复有序拆分：不允许重复无序拆分,+,全排列,25,。