母函数与递推关系 递推关系是计数的一个强有力的工具，特别 是在做算法分析时是必需的递推关系的求解主 要是利用母函数当然母函数尚有其他用处，但 这主要是介绍解递推关系上的应用例如 母函数与递推关系 §1 母函数 定义：给定序列(a0,a1,…,an,…)，记为{an}.函数 f(x)= a0+a1x+…+anxn+… 称为该序列的普通母函数，简称母函数 例 常数列(1,1,…)的母函数为 f(x)= 1+x+…+xn+…=1/(1-x) 数列{C(n,i)},i=0,1,2,…n的母函数为 这里的母函数只是“形式幂级数”，运算均按收敛 幂级数进行 母函数与递推关系 母函数的组合意义：考察 母函数与递推关系 其中： x前的系数为a,b,c的所有可重1-组合， x2前的系数为a,b,c的所有可重2-组合， 一般地： xn前的系数为a,b,c的所有可重n-组合， 在前式中取a=b=c=1,则xn前的系数为a,b,c的所有 可重n-组合数F(3,n). 母函数与递推关系 所以，构造某组合问题的组合数an的母函数f(x) 的基本方法为： 用一个乘积因子(1+x+x2+…)来代表一个所选元素 ，若该元素可重复n次，则因子中应出现xn。
例 设有2个红球，3个白球，1个黑球和1个黄球. 求从这些球中取出5个的不同方案数 解：设从所给球中取出i个的不同方案数为ai,则 由题设可得{ai}的母函数为 母函数与递推关系 例 求用1元和2元的钞票支付n元的不同方式数 解：设所求不同方式数为an,则由题设可得{an}的 母函数为 母函数与递推关系 于是 母函数与递推关系 定义：给定序列(a0, a1,…,an,…)，记为{an}.函数 称为该序列的指数型母函数,简称指数母函数 例 常数列(1,1,…)的母函数为 例 从 n 个不同元素中取 r 个的排列数P(n，r)指 数母函数为： 母函数与递推关系 例 n 个不同元素的可重 r-排列数 nr (r = 0, 1, 2, … )的指数母函数为 例 求用1,2,3,4,5五个数字组成的n位数的个数， 要求1出现的次数为偶数，2 出现的次数为奇数， 并且3至少出现一次 解：设所求n位数的个数为an ，则由题设可得 {an}的指数母函数为： 母函数与递推关系 母函数与递推关系 从而有 所以 母函数与递推关系 §2 递推关系 定义：设(x0, x1, …, xn, …)是一个序列，把该序 列中 an 与它前面几个ai(0≤in)关联起来的方程 称为递推关系。
序列中的一些已知条件称为初 始条件 例如 母函数与递推关系 利用递推关系进行计数这个方法在算法分析 中经常用到，举例说明如下： 例一. Hanoi Tower（河内塔）问题：n个圆 盘依其半径大小，从下而上套在A柱上，如下图 示每次只允许取一个移到柱B或C上，而且不 允许大盘放在小盘上方若要求把柱A上的n个 盘移到C柱上请设计一种方法来，并估计要移动 几个盘次现在只有A、B、C三根柱子可用 A B C 母函数与递推关系 Hanoi问题是个典型的问题，第一步要设计 算法，进而估计它的复杂性，集估计工作量 算法：n = 2时 A B C 第一步先把最上面的一个圆盘套在B上 第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕 母函数与递推关系 z 对于一般n个圆盘的问题， n 假定n-1个盘子的转移算法已经确定 z 先把上面的n-1个圆盘经过C转移到B z 第二步把A下面一个圆盘移到C上 z 最后再把B上的n-1个圆盘经过A转移到C上 A B C 母函数与递推关系 上述算法是递归的运用。
n=2时已给出算法； n=3时，第一步便利用算法把上面两个盘移到B上 ，第二步再把第三个圆盘转移到柱C上；最后把 柱B上两个圆盘转移到柱C上n=4，5，…以此类 推 算法分析：令h(n)表示n个圆盘所需要的转移 盘次根据算法先把前面n-1个盘子转移到B上； 然后把第n个盘子转到C上；最后再一次将B上的n- 1个盘子转移到C上 n=2时，算法是对的，因此，n=3是算法是对 的以此类推于是有 母函数与递推关系 算法复杂度为： H(x)是序列 的母函数给 定了序列，对应的母函数也确定了反过来也 一样，求得了母函数，对应的序列也就可得而 知了当然，利用递推关系(*)式也可以依次求 得 ，这样的连锁反应关系，叫做递 推关系 母函数与递推关系 §2 递推关系的求解方法 一，迭代法 例如前面的Hanoi Tower（河内塔）问题： 我们有 母函数与递推关系 母函数与递推关系 二，母函数法 例如前面的Hanoi Tower（河内塔）问题： 由递推关系，我们有 我们设{an}的母函数为 母函数与递推关系 由递推关系可得 故有 母函数与递推关系 解得 所以 母函数与递推关系 三，常系数线性递关系的 解法 定义：若序列（a1, a2,…）满足 则称序列{an}为k阶常系数线性递推关系。
若 f (n) = 0 则称序列{an}为k阶常系数线性齐次 递推关系 称： xk+b1xk-1+.+bk-1x+bk = 0 为k阶常系数线性递推关系的特征方程 母函数与递推关系 1，齐次常系数线性递关系的解法 n 若递推关系的特征多项式有k个相异实根x1, x2,…, xk，则递推关系的通解为： 其中c1, c2,…, ck为任意常数 若对递推关系再给出一组k个初始值，还可以由 通解求出满足初始条件的唯一解 母函数与递推关系 例 求解： 解：此递推关系的特征方程为 其特征根为 故其通解为 母函数与递推关系 由初始条件可得 F0 = 0，将F0 = 0， F1 = 1代入得 解得 所以 母函数与递推关系 n 若特征根出现一对共轭复根x1=a+bi , x2= a-bi 时，则递推关系的通解可表示为： 若对递推关系再给出一组k个初始值，还可以由 通解求出满足初始条件的唯一解 其中 母函数与递推关系 例：求下列n阶行列式dn的值 解：根据行列式性质，有 母函数与递推关系 此递推关系的特征方程为 其特征根为 故其通解为 母函数与递推关系 由初始条件 d1 = 1，d2 = 0得 解得 所以 母函数与递推关系 n 若特征根出现k重根。
不妨设a1是k的重根 则递推关系的解对应于a1的项为 其中A0, A1, . , Ak 是k个待定常数 例：求下列n阶行列式dn的值 母函数与递推关系 解：根据行列式性质，有 此递推关系的特征方程为 其特征根为 故其通解为 母函数与递推关系 由初始条件 d1 = 2，d2 = 3得 解得 所以 母函数与递推关系 2，非齐次常系数线性递关系的解法 所对应的齐次递推关系 定义：我们称齐次递推关系 母函数与递推关系 定理：递增推关系（**）的通解为 n f(n)是n的t次多项式的形式 若1 不是(*)的特征方程的根,则(**)有特解形式为 母函数与递推关系 若1 是(*)的特征方程的m重根，则(**)有特解形 式为 例 求和式 解：设 从则可得 母函数与递推关系 其对应的齐次递推关系为 其特征方程为 其对应的齐次递推关系的通解为 因为1 是特征方程式的1 重根，f(n)是n的三次多 项式所以有下列形式的特解： 代入题上的递推关系得 母函数与递推关系 于是可得方程组 从而解得 所以原递推关系的通解为 母函数与递推关系 代入初始条件a1=1得 解得 C = 0 ,故有 母函数与递推关系 n f(n)是 b n 的形式( b 为常数)。
若b 不是(*)的特征方程的根，则(**)有特解形式 为 若b 是(*)的特征方程的m重根，则(**)有特解形 式为 母函数与递推关系 例 求解下列递推关系 其对应的齐次递推关系的通解为 解：其对应的齐次递推关系为 其特征方程为 母函数与递推关系 因为2 是特征方程式的1 重根，所以有下列形式 的特解： 代入题上的递推关系，求解得 所以原递推关系的通解为 代入初始条件a0 = 0， a1 = 1得 母函数与递推关系 从而解得 所以原递推关系的解为 人有了知识，就会具备各种分析能力， 明辨是非的能力 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。