2-1-母函数与指数型母函数PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 母函数与递推关系,2.1,母函数与指数型母函数,2.2,递推关系与,Fibonacci,数列,2.3,线性常系数递推关系,2.4,非线性递推关系举例,2.5,应用举例,1,2.1,母函数与指数型母函数,母函数,母函数的性质,整数的拆分,Ferrers,图像,指数型母函数,2,1.,母函数,母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于,Laplace,在,1812,年的名著,概率解析理论。,我们来看如下的例子,：,两个骰子掷出,6,点，有多少种选法？,注意到，出现,1,，,5有两种选法，出现,2,，,4,也有两种选法，而出现,3,，,3,只有一种选法，按加法法则，共有,2+2+1=5,种不同选法。,或者，第一个骰子除了,6,以外都可选，有,5,种选法，一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有,51=5,种。,3,但碰到用三个或四个骰子掷出,n,点，上述两方法就不胜其烦了。,设想把骰子出现的点数,1,2,6,和,t,t,2,t,6,对应起来，则每个骰子可能出现的点数与,(,t+t,2+,+,t,6,),中,t,的各次幂一一对应。,若有两个骰子，则,其中,t,6,的系数为,5,，显然来自于,这表明，,掷出,6,点的方法一一对应于得到,t,6,的方法,。,4,故使两个骰子掷出,n,点的方法数等价于求,中,t,n,的系数。,这个函数,f,(,t,),称为,母函数,。,母函数方法的基本思想：,把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。,5,再来看下面的例子：,若令,a,1,=,a,2,=,=a,n,=,1,，则有,这就是二项式展开定理。,6,比较等号两端项对应系数，可以得到恒等式：,7,比较等式两端的常数项，可以得到恒等式：,8,中令,x,=1,可得,又如在等式,两端对,x,求导可得：,再令,x,=1,可得,类似还可以得到,9,还可以类似地推出一些等式，但通过上面一些例子,已可见函数,(1+,x,),n,在研究序列,C,(,n,0),C,(,n,1),C,(,n,n,),的关系时所起的作用。,定义,：对于序列,a,0,a,1,a,2,，函数,称为序列,a,0,a,1,a,2,的,母函数,。,例如,函数,(1+,x,),n,就是,序列,C,(,n,0),C,(,n,1),C,(,n,n,),的母函数。,如若已知序列，则对应的母函数可根据定义给出。,反之，如果已经求出序列的母函数,G,(,x,),，则该序列也随之确定。,10,D,D,D,输入,u,输出,v,例,1,下图是一逻辑回路，符号,D,是一延迟装置，即在时间,t,输入一个信号给延迟装置,D,，在t,+1,时刻,D,将输出同样的信号，符号,表示加法装置。,若在,t,=0,1,2,时刻的输入为,u,0,u,1,u,2,求在这些时刻的输出,v,0,v,1,v,2,11,显然，,一般的有,若信号输入的序列,u,0,u,1,的母函数为,U,(,x,),，输出的信号序列,v,0,v,1,的母函数为,V,(,x,),，则,其中,被装置的特性所确定，称为该装置的传递函数。,12,设,r,，,w,，,y,分别代表红球，白球，黄球。,例,2,有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。,(1),取一个球的组合数为,3,，即分别取红，白，黄。,(2),取两个球的组合数为,4,，即两个红的，一红一黄，一红一白，一白一黄。,(3),取三个球的组合数为,3,，即两红一黄，两红一白，一红一黄一白。,(4),取四个球的组合数为,1,，即两红一黄一白。,13,共有,1+3+4+3+1=12,种组合方式,。,令取,r,的组合数为,则序列,的母函数为,14,令,a,n,为从,8,位男同志中抽取出,n,个的允许组合数。由于要男同志的数目必须是偶数。故,例,3,某单位有,8,个男同志，,5,个女同志，现要组织一个由数目为偶数的男同志和数目不少于,2,的女同志组成的小组，试求有多少种组成方式？,因此序列,a,1,a,2,a,8,对应的母函数为：,15,类似可得女同志的允许组合数对应的母函数为,其中,x,k,的系数就是组成符合要求的,k,人小组的数目。,16,2.,母函数的性质,设序列,a,k,b,k,对应的母函数分别为,A,(,x,),B,(,x,),。,则下面的两个性质显然成立：,(1),A,(,x,)=,B,(,x,),当且仅当,a,k,=,b,k,。,(2),若,A,(,x,)+,B,(,x,)=,c,0,+,c,1,x,+,c,2,x,2,+,，则,c,k,=,a,k,+,b,k,。,性质,1,：若 则,B,(,x,)=,x,l,A,(,x,),。,证,:,17,则,例,4,已知,性质,2,：若,b,k,=,a,k,+,l,，则,则,例,5,已知,18,性质,3,：若,b,k,=a,0,+,+,a,k,，则,1:,x,:,x,2,:,x,k,:,+),19,则,例,6,已知,20,性质,4,：若,b,k,=,a,k,+,a,k,+1,+,，则,1:,x,:,x,2,:,+),21,性质,5,：若,b,k,=,ka,k,，则,性质,6,：若,b,k,=,a,k,/(1+,k,),，则,则,例,7,已知,22,性质,7,：若,c,k,=,a,0,b,k,+,a,1,b,k,-1,+,+,a,k,-1,b,1,+,a,k,b,0,，则,1:,x,:,x,2,:,+),23,令,例,8,已知,则,24,3.,整数的拆分,所谓正整数拆分即把正整数分解成若干正整数的和。,相当于把,n,个无区别的球放到,n,个无标志的盒子，盒子允许空着，也允许放多于一个球。,整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。,拆分可以分为,无序拆分,和,有序拆分,；,不允许重复的拆分,和,允许重复的拆分,。,25,例,9,若有,1,克、,2,克、,3,克、,4,克的砝码各一枚，问能称出那几种重量？有几种可能方案？,从右端的母函数知可称出从,1,克到,10,克，系数便是方案数。,例如右端有,2,x,5,项，即称出,5,克的方案有,2,种：,5=2+3=1+4,。,类似的，称出,6,克的方案也有,2,种：,6=2+4=1+2+3,。,26,例,10,求用,1,分、,2,分、,3,分的邮票贴出不同数值的方案数。,以,x,4,为例，其系数为,4,，即,4,拆分成,1,，,2,，,3,之和的允许重复的拆分数为,4,：,4=1+1+1+1,=1+1+2,=1+3,=2+2,。,注意邮票允许重复，因此母函数为：,27,例,11,若有,1,克砝码,3,枚、,2,克砝码,4,枚、,4,克砝码,2,枚，问能称出那几种质量？各有几种方案？,即可称出,1,至,19,克的质量，不同的方案数即为对应项前面的系数。,母函数为：,28,例,12,把整数,N,无序拆分成整数,a,1,a,2,a,n,的和，且不允许重复，求不同的拆分数。,的不同解的个数。,这个问题对应于求不定方程,令,b,N,表示不同的拆分数，则其对应的母函数为：,特殊的，当,a,i,=,i,时，对应的母函数为：,29,例,13,把整数,N,无序拆分成整数,a,1,a,2,a,n,的和，允许重复，求不同的拆分数。,的不同解的个数。,这个问题对应于求不定方程,令,b,N,表示不同的拆分数，则其对应的母函数为：,30,特殊的，当,a,i,=,i,时，对应的母函数为：,31,例,14,把整数,N,无序拆分成奇整数的和，允许重复，求不同的拆分数。,这相当于在上例中把,a,i,取成奇数，因此拆分数对应的母函数为：,例,15,把整数,N,无序拆分成,2,的幂次的和，求不同的拆分数。,这相当于把,N,拆分成,1,2,4,8,的和，但,不允许重复,。因此拆分数对应的母函数为：,32,例,16,把整数,N,无序拆分,1,2,m,的和，允许重复，求不同的拆分数。若要求,m,至少出现一次呢？,若无要求，由例,13,可知其母函数为：,若要求,m,至少出现一次，则拆分数对应的母函数为：,33,这个等式的组合意义很明显：整数,n,拆分成,1,到,m,的和的拆分数减去拆分成,1,到,m-,1,的和的拆分数，即为至少出现一个,m,的拆分数。,显然有,34,设,b,N,表示,N,剖分成不同正整数和的剖分数，则其对应的母函数为：,定理,1,整数剖分成不同整数的和的剖分数,(,不允许重复,),等于剖分成奇数的剖分数,(,允许重复,),。,35设,b,N,表示,N,剖分成,重复数不超过,2,的,正整数之和的剖分数，则其对应的母函数为：,定理,2,N,剖分成其他数之和但重复数不超过,2,，其剖分数等于它剖分成不被,3,整除的数的和的剖分数。,36,定理,3,N,被剖分成一些重复次数不超过,k,次的整数的和，其剖分数等于被剖分成不被,k,+1,除尽的数的和的剖分数,。,定理,4,对任意整数,N,，它被无序剖分成,2,的幂次的和的剖分方式一定唯一。,37,例,17,若有,1,、,2,、,4,、,8,、,16,克的砝码各一枚，问能称出那几种质量？有几种可能方案？,这说明用这些砝码可以称出从,1,克到,31,克的质量，而且方案都是唯一的。,实际上这说明整数的,二进制表示是唯一,的。,38,4.,Ferrers,图像,一个从上而下的,n,层格子组成的图像，,m,i,为第,i,层的格子数。,当,m,i,m,i,+1,，即上层的格子数不少于下层的格子数时，称之为,Ferrers,图像，如下图：,每一层至少有一个格子。,绕虚线轴旋转所得的图仍然是,Ferrers,图像。这样的两个,Ferrers,图像称为一对,共轭,的,Ferrers,图像。,39,(1),整数,n,拆分成,k,个数的和的拆分数，与数,n,拆分成最大数为,k,的拆分数相等。,因为整数,n,拆分成,k,个数的和的拆分可以用一个,k,行的图像表示。所得的,Ferrers,图像的共轭图像最上面一行有,k,个格子。例如：,利用,Ferrers,图像可以得到一些关于整数拆分的结果：,24=6+6+5+4+3,5,个数，最大数为,6,24=5+5+5+4+3+2,6,个数，最大数为,5,40,理由和,(1),相类似。,因此，拆分成最多不超过,m,个数的和的拆分数的母函数是：,(2),整数,n,拆分成最多不超过,m,个数的和的拆分数，与,n,拆分成最大不超过,m,的拆分数相等。,正好拆分成,m,个数的和的拆分数的母函数为,41,(3),整数,n,拆分成互不相同的若干奇数的和的的拆分数，与,n,拆分成自共轭的,Ferrers,图像的拆分数相等。,设整数,n,拆分为,n,=(2,n,1,+1)+(2,n,2,+1)+,+(2,n,k,+1),，其中,n,1,n,2,n,k,。,构造一个,Ferrers,图像，第一行第一列都是,n,1,+1,格，对应于,2,n,1,+1,，第二行第二列都是,n,2,+1,格，对应于,2,n,2,+1,，依此类推。,这样得到的,Ferrers,图像一定是自共轭的。,反过来，自共轭的,Ferrers,图像也可以对应到一些不同奇数的和。,42,例如,17=9+5+3,对应的,Ferrers,图像为：,(4),正整数,n,剖分成不超过,k,个数的和的剖分数，等于将,n+k,剖分成恰好,k,个数的剖分数。,不超过,k,层的,Ferrers,图像的每一层加上一个格子，一一对应到一个刚好,k,层的,Ferrers,图像。,43,5.,指数型母函数,考虑,n,个元素组成的多重集，其中,a,1,重复了,n,1,次，,a,2,重复了,n,2,次，,，,a,k,重复了,n,k,次，,n,=,n,1,+,n,2,+,+,n,k,。,从中取,r,个排列，求不同的排列数。,若,r,=,n,，即考虑,n,个元素的全排列，则不同的排列数为：,但是对于一般的,r,，情况就比较复杂了。,44,8,7,6,5,4,3,2,3,2,5,4,3,2,3,2,2,3,2,3,6,9,10,9,6,3,1,),1,(,),2,3,3,2,1,(,),1,)(,1,)1,(,),(,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,G,+,+,+,+,+,+,+,+,=,+,+,+,+,+,+,+,+,=,+,+,+,+,+,+,+,+,=,先看一个具体的问题：假设有,8,个元素，其中,a,1,重复,3,次，,a,2,重复,2,次，,a,3,重复,3,次。从中取,r,个组合，其组合数为,c,r,，则其对应的母函数为：,从,x,4,的系数可知，从这,8,个元素中取,4,个组合，不同的组合数为,10,。,这,10,个组合可从下面的展开式中得到：,45,其中,4,次方项表示了所有从,8,个元素中取,4,个的组合方案。,例如 表示一个,a,1,三个,a,3,的组合，表示两个,a,1,两个,a,3,的组合，依此类推。,46,接下来讨论从这,8,个元素中取,4,个的不同排列总数。,以,两个,a,1,两个,a,3,组合,为例，不同排列数为,4!/(2!2!),。,同样一个,a,1,三个,a,3,的不同排列数为,4!/(1!3!),。,依此类推可以得到不同的排列总数为：,47,为了便于计算，利用上述特点，形式地引进函数,从右边很容易可以看出，取,2,个的排列数为,9,，取,3,个的排列数为,28,，取,4,个的排列数为,70,依此类推。,48,定义,：对于序列,a,0,a,1,a,2,，函数,称为序列,a,0,a,1,a,2,对应的,指数型母函数,。,这样，对于一个多重集，其中,a,1,重复,n,1,次，,a,2,重复,n,2,次，,，,a,k,重复,n,k,次，,从中取,r,个排列的不同排列数所对应的指数型母函数为：,49,例,18,求下列数列的指数型母函数：,50,例,19,由,1,，,2,，,3,，,4,四个数字组成的五位数中，要求数,1,出现次数不超过,2,次，但不能不出现；,2,出现次数不超过,1,次；,3,出现次数最多,3,次，可以不出现；,4,出现次数为偶数。求满足上述条件的数的个数。,设满足上述条件的,r,位数个数为,c,r,，则其对应的指数型母函数为：,51,由此可见满足条件的5,位数共,215,个。,52,例,20,求由,1,，,3,，,5,，,7,，,9,五个数字组成的,n,位数的个数，要求其中,3,，,7,出现的次数为偶数，其他,1,，,5,，,9,出现次数不加限制。,设满足上述条件的,n,位数个数为,c,n,，则其对应的指数型母函数为：,53,因此,54,例,21,7,个有区别的球放进,4,个有标志的盒子里，要求,1,，,2,两个盒子必须有偶数个球，第,3,个盒子有奇数个球，求不同的方案个数。,这相当于从,1234,这,4,个数中取,7,个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。,这样的排列数所对应的指数型母函数为：,55,因此,56,例,22,r,个有标志的球放进,n,个不同的盒子里，要求无一空盒，问有多少种不同的分配方案？,这相当于从,1,到,n,这,n,个数字中取,r,个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。,这样的排列数所对应的指数型母函数为：,要求无一空盒即相当于要求每个数字至少出现一次。,57,因此,58,