1、2.1 母函数的概念与性质主讲教师 魏毅强教授联系电话 13513636491 Email Yiqiang Wei 2.1 母函数递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如1.问题的提出Yiqiang Wei x2项的系数 a1a2+a1a3+ an-1an， 中所有的项包括 n个元素 a1， a2， a n中取两个组合的全体；同理 x3项系数包含了从 n个元素 a1， a2， a n中取 3个元素组合的全体。以此类推。2.1 母函数若令 a1=a2= =a n=1， x2项的系
2、数中每一个组合有 1个贡献，其他各项以此类推。故有：Yiqiang Wei 另一方面：2.1 母函数Yiqiang Wei 比较等号两端 xk项对应系数，可得一等式2.1 母函数同样对于 (1+x)n(1+1/x)m ，（设 nm），用类似的方法可得等式：Yiqiang Wei 2.1 递 推关系与母函数对于序列 an，构造一函数关系G(x) =a0+a1x+a2x2+ + anxn+ ，称 G(x)为 序列 an 的 母函数 。上述母函数 也称为 普通型母函数 。注意到 ：v序列可能是有限的也可能是无限的，从而母函数可能是多项式 也可能是无穷级数 。v母函数的首项是零次幂项，对应序列首项 a
3、0Yiqiang Wei 例如，对于序列 1,1,1， 的母函数为2.1 递 推关系与母函数对于序列 Cnk的母函数为Fibonacci数列 Fn母函数为Yiqiang Wei 2.1 递 推关系与母函数注意到 ：序列与母函数是一一对应的v给定序列，可以写出形式母函数，进而通过求和可以得到序列的母函数。v给定母函数，可以将函数展开或幂级数展开成为多项式或幂级数形式，由展开式的唯一性，比较各项系数，可以求得对应序列。Yiqiang Wei 2.1 母函数比较等式两端的常数 ,即得所求事实上， (1+x)n(1+1/x)m =x-m(1+x)m+nYiqiang Wei 2.1 母函数又如等式：两端对 x求导，并 令 x=1 可得
