2-1 母函数与指数型母函数.ppt

文档介绍：第二章母函数与递推关系
母函数与指数型母函数
i数列
线性常系数递推关系
非线性递推关系举例
应用举例
母函数与指数型母函数
母函数
母函数的性质
整数的拆分
Ferrers 图像
指数型母函数
1. 母函数
母函数方法是一套非常有用的方法,应用极广。这套方法的系统叙述,最早见于Laplace在1812年的名著—概率解析理论。
我们来看如下的例子:两个骰子掷出6点,有多少种选法?
注意到,出现1,5有两种选法,出现2,4也有两种选法,而出现3,3只有一种选法,按加法法则,共有2+2+1=5种不同选法。
或者,第一个骰子除了6以外都可选,有5种选法,一旦第一个选定,第二个骰子就只有一种可能的选法,按乘法法则有5×1=5种。
但碰到用三个或四个骰子掷出n点,上述两方法就不胜其烦了。
设想把骰子出现的点数1,2,…,6和t,t2,…,t6对应起来,则每个骰子可能出现的点数与(t+t2+…+t6)中t的各次幂一一对应。
若有两个骰子,则
其中t6的系数为5,显然来自于
这表明,掷出6点的方法一一对应于得到t6的方法。
故使两个骰子掷出n点的方法数等价于求
中tn的系数。
这个函数f(t)称为母函数。
母函数方法的基本思想:
把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造。
再来看下面的例子:
若令a1=a2= …=an=1,则有
这就是二项式展开定理。
比较等号两端项对应系数,可以得到恒等式:
比较等式两端的常数项,可以得到恒等式:
中令x=1 可得
又如在等式
两端对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)的母函数。
如若已知序列,则对应的母函数可根据定义给出。
反之,如果已经求出序列的母函数G(x),则该序列也随之确定。