《组合数学第三讲课件》由会员分享，可在线阅读，更多相关《组合数学第三讲课件（43页珍藏版）》请在金锄头文库上搜索。
1、母函数与递推关系,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,母函数与递推关系,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前的系
2、数为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元的
3、钞票支付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 ，则由题
4、设可得an的指数母函数为：,母函数与递推关系,母函数与递推关系,从而有,所以,母函数与递推关系,2 递推关系,定义：设(a0,a1,an,)是一个序列，把该序列中 an 与它前面几个ai(0in)关联起来的方程称为递推关系。序列中的一些已知条件称为初始条件。,例如,母函数与递推关系,利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：,例一. Hanoi Tower（河内塔）问题：N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三
5、根柱子可用。,母函数与递推关系,Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。,算法：,N=2时,第一步先把最上面的一个圆盘套在B上,第二步把下面的一个圆盘移到C上,最后把B上的圆盘移到C上,到此转移完毕,母函数与递推关系,对于一般n个圆盘的问题，,假定n-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,母函数与递推关系,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆
6、盘转移到柱C上。N=4，5，以此类推。,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,母函数与递推关系,算法复杂度为：,H(x)是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。,母函数与递推关系,2 递推关系的求解方法,一，迭代法,例如前面的Hanoi Tower（河内塔）问
7、题：,我们有,母函数与递推关系,母函数与递推关系,二，母函数法,例如前面的Hanoi Tower（河内塔）问题：,由递推关系，我们有,我们设an的母函数为,母函数与递推关系,由递推关系可得,故有,母函数与递推关系,解得,所以,母函数与递推关系,三，常系数线性递关系的 解法,若 f (n) = 0 则称序列an为k阶常系数线性齐次 递推关系。,称： xk+b1xk-1+.+bk-1x+bk = 0 为k阶常系数线性递推关系的特征方程。,母函数与递推关系,1，齐次常系数线性递关系的解法,若递推关系的特征多项式有k个相异实根x1, x2, xk，则递推关系的通解为：,其中c1, c2, ck为任意常
8、数。,若对递推关系再给出一组k个初始值，还可以由 通解求出满足初始条件的唯一解。,母函数与递推关系,例 求解：,解：此递推关系的特征方程为,其特征根为,故其通解为,母函数与递推关系,由初始条件可得 F0 = 0，将F0 = 0， F1 = 1代入得,解得,所以,母函数与递推关系,若特征根出现一对共轭复根x1=a+bi , x2= a-bi 时，则递推关系的通解可表示为：,若对递推关系再给出一组k个初始值，还可以由 通解求出满足初始条件的唯一解。,其中,母函数与递推关系,例：求下列n阶行列式dn的值。,解：根据行列式性质，有,母函数与递推关系,此递推关系的特征方程为,其特征根为,故其通解为,母函
9、数与递推关系,由初始条件 d1 = 1，d2 = 0得,解得,所以,母函数与递推关系,若特征根出现k重根。不妨设a1是k的重根。则递推关系的解对应于a1的项为 其中A0, A1, . , Ak 是k个待定常数,例：求下列n阶行列式dn的值。,母函数与递推关系,解：,根据行列式性质，有,此递推关系的特征方程为,其特征根为,故其通解为,母函数与递推关系,由初始条件 d1 = 2，d2 = 3得,解得,所以,母函数与递推关系,2，非齐次常系数线性递关系的解法,母函数与递推关系,定理：递增推关系（*）的通解为,f(n)是n的t次多项式的形式。,若1 不是(*)的特征方程的根,则(*)有特解形式为,母函
10、数与递推关系,若1 是(*)的特征方程的m重根，则(*)有特解形 式为,例 求和式,解：设,从则可得,母函数与递推关系,其对应的齐次递推关系为,其特征方程为,其对应的齐次递推关系的通解为,因为1 是特征方程式的1 重根，f(n)是n的三次多 项式。所以有下列形式的特解：,代入题上的递推关系得,母函数与递推关系,于是可得方程组,从而解得,所以原递推关系的通解为,母函数与递推关系,代入初始条件a1=1得,解得 C = 0 ,故有,母函数与递推关系,f(n)是 b n 的形式( b 为常数)。,若b 不是(*)的特征方程的根，则(*)有特解形式 为,若b 是(*)的特征方程的m重根，则(*)有特解形 式为,母函数与递推关系,例 求解下列递推关系,其对应的齐次递推关系的通解为,解：其对应的齐次递推关系为,其特征方程为,母函数与递推关系,因为2 是特征方程式的1 重根，所以有下列形式 的特解：,代入题上的递推关系，求解得,所以原递推关系的通解为,代入初始条件a0 = 0， a1 = 1得,母函数与递推关系,从而解得,所以原递推关系的解为,
