母函数与指数型母函数市公开课金奖市赛课一等奖课件.pptx

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