文档介绍：第二章母函数与递推关系
母函数与指数型母函数
递推关系与Fibonacci数列
线性常系数递推关系
非线性递推关系举例

母函数与指数型母函数
母函数与指数型母函数
母函数
母函数的性质
整数的拆分
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)，则该序列也随之确定。
母函数与指数型母函数