母函数与指数型母函数.ppt
《母函数与指数型母函数.ppt》由会员分享,可在线阅读,更多相关《母函数与指数型母函数.ppt(58页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第二章第二章 母函数与递推关系母函数与递推关系2.1 母函数与指数型母函数母函数与指数型母函数2.2 递推关系与递推关系与Fibonacci数列数列2.3 线性常系数递推关系线性常系数递推关系2.4 非线性递推关系举例非线性递推关系举例2.5 应用举例应用举例2.1 母函数与指数型母函数母函数与指数型母函数1.母函数母函数2.母函数的性质母函数的性质3.整数的拆分整数的拆分4.Ferrers 图像图像5.指数型母函数指数型母函数1.母函数母函数母函数方法是一套非常有用的方法,应用极广。这母函数方法是一套非常有用的方法,应用极广。这套方法的系统叙述,最早见于套方法的系统叙述,最早见于Laplac
2、e在在1812年的年的名著名著概率解析理论。概率解析理论。我们来看如下的例子我们来看如下的例子:两个骰子掷出两个骰子掷出6点,有多少点,有多少种选法?种选法?注意到,出现注意到,出现1,5有两种选法,出现有两种选法,出现2,4也有两也有两种选法,而出现种选法,而出现3,3只有一种选法,按加法法则,只有一种选法,按加法法则,共有共有2+2+1=5种不同选法。种不同选法。或者,第一个骰子除了或者,第一个骰子除了6以外都可选,有以外都可选,有5种选法,种选法,一旦第一个选定,第二个骰子就只有一种可能的选一旦第一个选定,第二个骰子就只有一种可能的选法,按乘法法则有法,按乘法法则有51=5种。种。但碰到
3、用三个或四个骰子掷出但碰到用三个或四个骰子掷出n点,上述两方法就点,上述两方法就不胜其烦了。不胜其烦了。设想把骰子出现的点数设想把骰子出现的点数1,2,6和和t,t2,t6对应起来,对应起来,则每个骰子可能出现的点数与则每个骰子可能出现的点数与(t+t2+t6)中中t的各次的各次幂一一对应。幂一一对应。若有两个骰子,则若有两个骰子,则其中其中t6的系数为的系数为5,显然来自于,显然来自于这表明,这表明,掷出掷出6点的方法一一对应于得到点的方法一一对应于得到t6的方法的方法。故使两个骰子掷出故使两个骰子掷出n点的方法数等价于求点的方法数等价于求中中tn的系数。的系数。这个函数这个函数f(t)称为
4、称为母函数母函数。母函数方法的基本思想:母函数方法的基本思想:把离散数列和幂级数一一对应起来,把离散数列间把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造。后由幂级数形式来确定离散数列的构造。再来看下面的例子:再来看下面的例子:若令若令a1=a2=an=1,则有,则有这就是二项式展开定理。这就是二项式展开定理。比较等号两端项对应系数,可以得到恒等式:比较等号两端项对应系数,可以得到恒等式:比较等式两端的常数项,可以得到恒等式:比较等式两端的常数项,可以得到恒等式:中令中令x=1
5、 可得可得又如在等式又如在等式两端对两端对x求导可得:求导可得:再令再令x=1 可得可得类似还可以得到类似还可以得到还可以类似地推出一些等式,但通过上面一些例子还可以类似地推出一些等式,但通过上面一些例子已可见函数已可见函数(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)的的母函数。母函数。如若已知序列,则对应的母函数可根据定义给出。如若已
6、知序列,则对应的母函数可根据定义给出。反之,如果已经求出序列的母函数反之,如果已经求出序列的母函数G(x),则该序列,则该序列也随之确定。也随之确定。DDD输入输入u输出输出v例例1 下图是一逻辑回路,符号下图是一逻辑回路,符号D是一延迟装置,即是一延迟装置,即在时间在时间t输入一个信号给延迟装置输入一个信号给延迟装置D,在,在t+1时刻时刻D将将输出同样的信号,符号输出同样的信号,符号 表示加法装置。表示加法装置。若在若在t=0,1,2,时刻的输入为时刻的输入为u0,u1,u2,求在这些时求在这些时刻的输出刻的输出v0,v1,v2,显然,显然,一般的有一般的有若信号输入的序列若信号输入的序列
7、u0,u1,的母函数为的母函数为U(x),输出,输出的信号序列的信号序列v0,v1,的母函数为的母函数为V(x),则,则其中其中被装置的特性所确定,称为该装置的传递函数。被装置的特性所确定,称为该装置的传递函数。设设r,w,y 分别代表红球,白球,黄球。分别代表红球,白球,黄球。例例2 有红球两个,白球、黄球各一个,试求有多少种有红球两个,白球、黄球各一个,试求有多少种不同的组合方案。不同的组合方案。(1)取一个球的组合数为取一个球的组合数为3,即分别取红,白,黄。,即分别取红,白,黄。(2)取两个球的组合数为取两个球的组合数为4,即两个红的,一红一黄,即两个红的,一红一黄,一红一白,一白一黄
8、。一红一白,一白一黄。(3)取三个球的组合数为取三个球的组合数为3,即两红一黄,两红一白,即两红一黄,两红一白,一红一黄一白。一红一黄一白。(4)取四个球的组合数为取四个球的组合数为1,即两红一黄一白。,即两红一黄一白。共有共有1+3+4+3+1=12种组合方式种组合方式。令取令取r的组合数为的组合数为 ,则序列则序列的母函数为的母函数为令令an为从为从8位男同志中抽取出位男同志中抽取出n个的允许组合数。由个的允许组合数。由于要男同志的数目必须是偶数。故于要男同志的数目必须是偶数。故例例3 某单位有某单位有8个男同志,个男同志,5个女同志,现要组织一个女同志,现要组织一个由数目为偶数的男同志和
9、数目不少于个由数目为偶数的男同志和数目不少于2的女同志的女同志组成的小组,试求有多少种组成方式?组成的小组,试求有多少种组成方式?因此序列因此序列a1,a2,a8对应的母函数为:对应的母函数为:类似可得女同志的允许组合数对应的母函数为类似可得女同志的允许组合数对应的母函数为其中其中xk的系数就是组成符合要求的的系数就是组成符合要求的k人小组的数目。人小组的数目。2.母函数的性质母函数的性质设序列设序列ak,bk对应的母函数分别为对应的母函数分别为A(x),B(x)。则下面的两个性质显然成立:则下面的两个性质显然成立:(1)A(x)=B(x)当且仅当当且仅当 ak=bk。(2)若若A(x)+B(
10、x)=c0+c1x+c2x2+,则,则ck=ak+bk。性质性质1:若:若 则则 B(x)=xlA(x)。证证:则则例例4 已知已知性质性质2:若:若bk=ak+l,则,则则则例例5 已知已知性质性质3:若:若bk=a0+ak,则,则1:x:x2:xk:+)则则例例6 已知已知性质性质4:若:若bk=ak+ak+1+,则,则1:x:x2:+)性质性质5:若:若bk=kak,则,则性质性质6:若:若bk=ak/(1+k),则,则则则例例7 已知已知性质性质7:若:若ck=a0bk+a1bk-1+ak-1b1+akb0,则,则1:x:x2:+)令令例例8 已知已知则则3.整数的拆分整数的拆分所谓正
11、整数拆分即把正整数分解成若干正整数的和。所谓正整数拆分即把正整数分解成若干正整数的和。相当于把相当于把n个无区别的球放到个无区别的球放到n个无标志的盒子,盒个无标志的盒子,盒子允许空着,也允许放多于一个球。子允许空着,也允许放多于一个球。整数拆分成若干整数的和,办法不一,不同拆分法整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。的总数叫做拆分数。拆分可以分为拆分可以分为无序拆分无序拆分和和有序拆分有序拆分;不允许重复的不允许重复的拆分拆分和和允许重复的拆分允许重复的拆分。例例9 若有若有1克、克、2克、克、3克、克、4克的砝码各一枚,问能克的砝码各一枚,问能称出那几种重量?有几种
12、可能方案?称出那几种重量?有几种可能方案?从右端的母函数知可称出从从右端的母函数知可称出从1克到克到10克,系数便是克,系数便是方案数。方案数。例如右端有例如右端有2x5项,即称出项,即称出5克的方案有克的方案有2种:种:5=2+3=1+4。类似的,称出类似的,称出6克的方案也有克的方案也有2种:种:6=2+4=1+2+3。例例10 求用求用1分、分、2分、分、3分的邮票贴出不同数值的方分的邮票贴出不同数值的方案数。案数。以以x4为例,其系数为为例,其系数为4,即,即4拆分成拆分成1,2,3之和的允之和的允许重复的拆分数为许重复的拆分数为4:4=1+1+1+1 =1+1+2 =1+3 =2+2
13、。注意邮票允许重复,因此母函数为:注意邮票允许重复,因此母函数为:例例11 若有若有1克砝码克砝码3枚、枚、2克砝码克砝码4枚、枚、4克砝码克砝码2枚,枚,问能称出那几种质量?各有几种方案?问能称出那几种质量?各有几种方案?即可称出即可称出1至至19克的质量,不同的方案数即为对应项克的质量,不同的方案数即为对应项前面的系数。前面的系数。母函数为:母函数为:例例12 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和,且的和,且不允许重复,求不同的拆分数。不允许重复,求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程令令bN表示不同的拆分
14、数,则其对应的母函数为:表示不同的拆分数,则其对应的母函数为:特殊的,当特殊的,当ai=i时,对应的母函数为:时,对应的母函数为:例例13 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和,允的和,允许重复,求不同的拆分数。许重复,求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程令令bN表示不同的拆分数,则其对应的母函数为:表示不同的拆分数,则其对应的母函数为:特殊的,当特殊的,当ai=i时,对应的母函数为:时,对应的母函数为:例例14 把整数把整数N无序拆分成奇整数的和,允许重复,无序拆分成奇整数的和,允许重复,求不同的拆分数。求
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 函数 指数
限制150内