组合数学第三讲课件.ppt

母函数与递推关系 若特征根出现k重根。不妨设a1是k的重根。则递推关系的解对应于a1的项为? ??????? ?????????????????????????? 其中A0, A1, ... , Ak 是k个待定常数 例：求下列n阶行列式dn的值。 * 母函数与递推关系 递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如 母函数与递推关系 §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 递推关系 定义：设(a0,a1,…,an,…)是一个序列，把该序列中 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上 到此转移完毕 母函数与递推关系 对于一般n个圆盘的问题， 假定n-1个盘子的转移算法已经确定。 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把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时，算法是对的