Chap2-1母函数、整数拆分省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢您,2.1 母函数,母函数方法是一套非常有用方法，应用极广。这套方法系统叙述，最早见于Laplace在1812年名著,概,率解析理论。,两个骰子掷出6点，有多少种选法？,我们来看以下例子,第1页,我们也能够从另一角度来看，要使两个骰子掷,出6点，第一个骰子除了6以外都可选，这有5,种选法，一旦第一个选定，第二个骰子就只有,一个可能选法，,按乘法法则有51=5种。,注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一个选法，这些选法互斥且穷尽了出现6点一切可能选法，按加法法则，共有2+2+1=5种不一样选法。,第2页,但碰到用三个或四个骰子掷出,n,点，上述两方法就不胜其烦了。这就需要引进新方法。,第3页,若有两个骰子，则,第4页,这种对应把组合问题加法法则和幂级数,t,乘幂相加对应起来。,故使两个骰子掷出6点方法数等价于求,第5页,母函数思想很简单,即:,把离散数列和幂级数一一对应起来,把离散数列间相互结合关系对应成为幂级数间运算关系,最终由幂级数形式来确定离散数列结构.,看下面例子.,第6页,中全部项包含,n,个元素,a,1,，,a,2,，,a,n,中取,两个,组合全体；同理,x,3,项系数包含了从,n,个元素,a,1,，,a,2,，,a,n,中取3个元素组合全体。以这类推,。,若令,a,1,=,a,2,=,=,a,n,=,1,，在（2-1-1）式,项系数,中每一个组合有1个贡献,其它各项以这类推.,第7页,故有：,另首先：,第8页,比较等号两端项对应系数，可得一等式,第9页,一样对于,（设,）,比较等式两端常数项，即得公式,第10页,又如在等式,中令,x,=1 可得,第11页,(2-1-2)式等号两端对,x,求导可得：,等式(2-1-5)两端令,x,=1，得：,第12页,用类似方法还能够得到：,第13页,已可见函数,还能够类似地推出一些等式，但经过上面一些例子,关系时所起作用。对其它序列也有一样结果。现引进母函数概念以下：,在研究序列,称函数,G,(,x,),是序列,母函数,定义：,对于序列,结构一函数,第14页,如若已知序列 则对应母函数,G,(,x,),便,可依据定义给出。反之，如若以求得序列母函数,G,(,x,),，,则该序列也随之确定。,第15页,例1：,下列图是一逻辑回路，符号D是一延迟装置，即在时间,t,输入一个信号给延迟装置D，在,t,+1时刻D将输出一样信号，符号,表示加法装置,D,D,D,输入,u,输出,v,第16页,显然，,普通有,若在,时刻，输入信号,求相同时刻输出信号,第17页,若信号输入序列,u,0,u,1,母函数为,U,(,x,)，,输出信号序列,v,0,v,1,母函数为,V,(,x,)，,则,其中,被装置（图 2-12-1）特征所确定，能够看作是该装置传递函数，,第18页,例2：,有红球两个，白球、黄球各一个，试求有多少种不一样组合方案。,设,r，w，y,分别代表红球，白球，黄球。,第19页,由此可见，除一个球也不取情况外，有：,（a）取一个球组合数为3，即分别取红，白，黄。,（b）取两个球组合数为4，即两个红，一红一黄，一红一白，一白一黄。,（c）取三个球组合数为3，即两红一黄，两红一白，一红一黄一白。,（d）取四个球组合数为1，即两红一黄一白。,第20页,母函数为,共有1+3+4+3+1=12种组合方式。,令取,r,组合数为,则序列,第21页,例3：,某单位有8个男同志，5个女同志，现要组织一个有数目为偶数男同志和数目不少于2女同志组成小组，试求有多少种组成方式？,令,a,n,为从8位男同志中抽取出,n,个允许组合数。因为要男同志数目必须是偶数。,故,第22页,对应一母函数,类似可得女同志允许组合数对应母函数为,故数列,第23页,第24页,2.2 母函数性质,第25页,性质1:,证:,若,则,第26页,例.,已知,则,第27页,性质2:,则,若,第28页,证：,第29页,例.,第30页,性质3：,若,则,第31页,),:,:,:,:,1,2,1,0,2,1,0,2,2,1,0,1,0,0,L,L,L,L,L,L,L,L,L,L,L,L,L,L,L,L,+,+,+,+,+,=,+,+,=,+,=,=,n,n,a,a,a,a,b,n,x,a,a,a,b,x,a,a,b,x,a,b,证：,第32页,例.,已知,第33页,类似可得：,第34页,性质4,则,第35页,证,第36页,第37页,例,则,性质5,若,则,第38页,性质5和性质6结论是显而易见。,性质6,若,则,第39页,性质7,若,则,第40页,证:,第41页,已知,例.,则,第42页,所谓正整数拆分即把正整数分解成若干整数和，相当于把,n,个无区分球放到,n,个无标志盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数和，方法不一，不一样拆分法总数叫做拆分数。拆分能够分为,无序拆分,和,有序拆分,；,不允许重复拆分,和,允许重复拆分,。,2.3 整数拆分,-,2.3.1问题描述,第43页,2.3.2 问题举例,例1,若有1克、2克、3克、4克砝码各一枚，,问能称出那几个重量？有几个可能方案？,第44页,从右端母函数知可称出从1克到10克，,系数便是方案数。比如右端有 项，即,称出5克方案有2,一样，,故称出6克方案有2，称出10克方案有1,第45页,例2,求用1分、2分、3分邮票贴出不一样数,值方案数。,解:因邮票允许重复，故母函数为,以其中,x,为例，其系数为4，即4拆分成1、2、3之和拆分数为4，即,4,第46页,例3,若有1克砝码3枚、2克砝码4枚、4克砝,码2枚，问能称出那几个重量？各有几个,方案？,解:作母函数,第47页,第48页,第49页,第50页,第51页,例6 对,N,进行无序且允许重复剖分，使得剖分后正整数都是奇数，求这种剖分方案数,P,0,(,N,),母函数,G,0,(,x,).,解,：这是把,N,剖分成1,3,5,且允许重复。,类似于上例，我们有,第52页,例7 对,N,进行无序剖分，使得剖分后整数,都是2幂，求这种剖分方法数,P,t,(,N,)母,函数,G,t,(,x,).,解,：这相当于把,N,剖分成1,2,4,8,16,但不允许重复，类似于(a)可得,第53页,例8,整数,n,拆分成1，2，3，,m,和，并允许重复，若其中,m,最少出现一次，其母函数怎样？,若整数,n,拆分成1，2，3，,m,和，并允许重复，由(d)式，其母函数为,：,第54页,若拆分中,m,最少出现一次，其母函数则为：,第55页,等式(,g,)组合意义：即整数,n,拆分成1到,m,和拆分数减去拆分成1到,m-,1,和拆分数，即为最少出现一个,m,拆分数。,显然有,第56页,定理,1,整数剖分成不一样数和剖分数等于剖分,成奇数剖分数.,证实：设,b,N,表示,N,剖分成不一样正整数和剖分数，则序列,b,N,母函数为,第57页,定理2,N,剖分成其它数之和但重复数不超出2，,其剖分数等于它剖分成不被3整除数和剖,分数。,证实：,N,剖分成其它数之和但重复数不超出2剖分数所组成序列母函数为,第58页,第59页,定理,3,N,被剖分成其重复度不超出,k,次数和，其剖分数等于被剖分成不被,k,+,1,除尽数和剖分数,。,定理4,对一切,N,，有,P,t,(,N,)=1.,第60页,例9 若有1、2、4、8、16、32克砝码各一枚,问能称出那几个重量？有几个可能方案？,第61页,从母函数能够得知，用这些砝码能够称出从1,克到63克重量，而且方法都是唯一。,这问题能够推广到证实任一十进制数,n,可表示为,而且是唯一。,第62页,