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

第二章第二章 母函数与递推关系母函数与递推关系2.1 母函数与指数型母函数母函数与指数型母函数2.2 递推关系与递推关系与Fibonacci数列数列2.3 线性常系数递推关系线性常系数递推关系2.4 非线性递推关系举例非线性递推关系举例2.5 应用举例应用举例第1页第1页2.1 母函数与指数型母函数母函数与指数型母函数1.母函数母函数2.母函数性质母函数性质3.整数拆分整数拆分4.Ferrers 图像图像5.指数型母函数指数型母函数第2页第2页1.母函数母函数母函数办法是一套非常有用办法，应用极广。这套办法系统叙述，最早见于Laplace在18名著概率解析理论。我们来看下列例子我们来看下列例子：两个骰子掷出两个骰子掷出6点，有多少种点，有多少种选法？选法？注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一个选法，按加法法则，共有2+2+1=5种不同选法。或者，第一个骰子除了或者，第一个骰子除了6以外都可选，有以外都可选，有5种选法，种选法，一旦第一个选定，第二个骰子就只有一个也许选法，一旦第一个选定，第二个骰子就只有一个也许选法，按乘法法则有按乘法法则有51=5种。种。第3页第3页但碰到用三个或四个骰子掷出但碰到用三个或四个骰子掷出n点，上述两办法就点，上述两办法就不胜其烦了。不胜其烦了。设想把骰子出现点数设想把骰子出现点数1,2,6和和t,t2,t6相应起来，相应起来，则每个骰子也许出现点数与则每个骰子也许出现点数与(t+t2+t6)中中t各次幂一各次幂一一相应。一相应。若有两个骰子，则若有两个骰子，则其中其中t6系数为系数为5，显然来自于，显然来自于这表明，这表明，掷出掷出6点办法一一相应于得到点办法一一相应于得到t6办法办法。第4页第4页故使两个骰子掷出故使两个骰子掷出n点办法数等价于求点办法数等价于求中中tn系数。系数。这个函数这个函数f(t)称为称为母函数母函数。母函数办法基本思想：母函数办法基本思想：把离散数列和幂级数一一相应起来，把离散数列间把离散数列和幂级数一一相应起来，把离散数列间互相结合关系相应成为幂级数间运算关系，最后由互相结合关系相应成为幂级数间运算关系，最后由幂级数形式来拟定离散数列结构。幂级数形式来拟定离散数列结构。第5页第5页再来看下面例子：再来看下面例子：若令若令a1=a2=an=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)关系时所起作用。关系时所起作用。定义定义：对于序列：对于序列a0,a1,a2,，函数，函数称为序列称为序列a0,a1,a2,母函数母函数。比如比如函数函数(1+x)n就是就是序列序列C(n,0),C(n,1),C(n,n)母母函数。函数。如若已知序列，则相应母函数可依据定义给出。如若已知序列，则相应母函数可依据定义给出。反之，假如已经求出序列母函数反之，假如已经求出序列母函数G(x)，则该序列也，则该序列也随之拟定。随之拟定。第10页第10页DDD输入输入u输出输出v例例1 下图是一逻辑回路，符号下图是一逻辑回路，符号D是一延迟装置，即是一延迟装置，即在时间在时间t输入一个信号给延迟装置输入一个信号给延迟装置D，在，在t+1时刻时刻D将将输出同样信号，符号输出同样信号，符号 表示加法装置。表示加法装置。若在若在t=0,1,2,时刻输入为时刻输入为u0,u1,u2,求在这些时刻求在这些时刻输出输出v0,v1,v2,第11页第11页显然，显然，普通有普通有若信号输入序列若信号输入序列u0,u1,母函数为母函数为U(x)，输出信号，输出信号序列序列v0,v1,母函数为母函数为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页令令an为从为从8位男同志中抽取出位男同志中抽取出n个允许组合数。由于个允许组合数。由于要男同志数目必须是偶数。故要男同志数目必须是偶数。故例例3 某单位有某单位有8个男同志，个男同志，5个女同志，现要组织一个女同志，现要组织一个由数目为偶数男同志和数目不少于个由数目为偶数男同志和数目不少于2女同志构成女同志构成小组，试求有多少种构成方式？小组，试求有多少种构成方式？因此序列因此序列a1,a2,a8相应母函数为：相应母函数为：第15页第15页类似可得女同志允许组合数相应母函数为类似可得女同志允许组合数相应母函数为其中其中xk系数就是构成符合要求系数就是构成符合要求k人小组数目。人小组数目。第16页第16页2.母函数性质母函数性质设序列设序列ak,bk相应母函数分别为相应母函数分别为A(x),B(x)。则下面两个性质显然成立：则下面两个性质显然成立：(1)A(x)=B(x)当且仅当当且仅当 ak=bk。(2)若若A(x)+B(x)=c0+c1x+c2x2+，则，则ck=ak+bk。性质性质1：若：若 则则 B(x)=xlA(x)。证证:第17页第17页则则例例4 已知已知性质性质2：若：若bk=ak+l，则，则则则例例5 已知已知第18页第18页性质性质3：若：若bk=a0+ak，则，则1:x:x2:xk:+)第19页第19页则则例例6 已知已知第20页第20页性质性质4：若：若bk=ak+ak+1+，则，则1:x:x2:+)第21页第21页性质性质5：若：若bk=kak，则，则性质性质6：若：若bk=ak/(1+k)，则，则则则例例7 已知已知第22页第22页性质性质7：若：若ck=a0bk+a1bk-1+ak-1b1+akb0，则，则1:x:x2:+)第23页第23页令令例例8 已知已知则则第24页第24页3.整数拆分整数拆分所谓正整数拆分即把正整数分解成若干正整数和。所谓正整数拆分即把正整数分解成若干正整数和。相称于把相称于把n个无区别球放到个无区别球放到n个无标志盒子，盒子允个无标志盒子，盒子允许空着，也允许放多于一个球。许空着，也允许放多于一个球。整数拆分成若干整数和，方法不一，不同拆分法总数叫做拆分数。拆分能够分为拆分能够分为无序拆分无序拆分和和有序拆分有序拆分；不允许重复拆不允许重复拆分分和和允许重复拆分允许重复拆分。第25页第25页例例9 若有若有1克、克、2克、克、3克、克、4克砝码各一枚，问能称克砝码各一枚，问能称出那几种重量？有几种也许方案？出那几种重量？有几种也许方案？从右端母函数知可称出从从右端母函数知可称出从1克到克到10克，系数便是方克，系数便是方案数。案数。比如右端有比如右端有2x5项，即称出项，即称出5克方案有克方案有2种：种：5=2+3=1+4。类似，称出类似，称出6克方案也有克方案也有2种：种：6=2+4=1+2+3。第26页第26页例10 求用1分、2分、3分邮票贴出不同数值方案数。以以x4为例，其系数为为例，其系数为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表示不同拆分数，则其对应母函数为：特殊，当特殊，当ai=i时，相应母函数为：时，相应母函数为：第29页第29页例13 把整数N无序拆分成整数a1,a2,an和，允许重复，求不同拆分数。不同解个数。这个问题相应于求不定方程这个问题相应于求不定方程令bN表示不同拆分数，则其对应母函数为：第30页第30页特殊，当特殊，当ai=i时，相应母函数为：时，相应母函数为：第31页第31页例14 把整数N无序拆分成奇整数和，允许重复，求不同拆分数。这相称于在上例中把这相称于在上例中把ai取成奇数，因此拆分数相应取成奇数，因此拆分数相应母函数为：母函数为：例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页设设bN表示表示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层格子构成图像，层格子构成图像，mi为第为第i层格子数。层格子数。当mimi+1，即上层格子数不少于下层格子数时，称之为Ferrers图像，以下图：每一层至少有一个格子。每一层至少有一个格子。绕虚线轴旋转所得图仍