组合数学母函数与递推关系

第二章—递推关系与母函数主讲教师数学学院魏毅强教授联系电话[phone]Email:[e-mail]@tyut.edu.cn目录2.1递推关系与母函数2.2母函数2.1—递推关系与母函数[e-mail]利用递推关系进行计数是最重要的一种组合计数方法，该方法在算法分析中经常用到，举例说明如下：例1(Hanoi塔问题)：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。2.1递推关系与母函数2.1.1引例[e-mail]2.1递推关系与母函数ABCHanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，即估计工作量。[e-mail]=2时的算法：第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上最后把B上的圆盘移到C上到此转移完毕ABC2.1递推关系与母函数[e-mail]2.1递推关系与母函数假定n-1个盘子的转移算法已经确定。对于一般n个圆盘的问题，先把上面的n-1个圆盘经过C转移到B。第二步把A下面一个圆盘移到C上最后再把B上的n-1个圆盘经过A转移到C上[e-mail]2.1递推关系与母函数上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。n=4，5，…以此类推。[e-mail]算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。1)1()1.1.2(2n,1)1(2)(hnhnh2.1递推关系与母函数[e-mail]2.1递推关系与母函数1)1(h12121)1(2)2(2hh1211)-2(21)2(2)3(32hh是关系式(2.1.1)的初始条件，于是，由(2.1.1)依次可得1211)-2(21)3(2)4(43hh故，由数学归纳发可得（证明略）1n1,-2)([e-mail]2.1递推关系与母函数利用关系式(2.1.1)，在给定初值h(1)的条件下，可以依次求得h(2),h(3),h(4)，…，这样的连锁反应关系，叫做递推关系。下面介绍一种求解（2.1.1）的形式算法，所谓形式算法指的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。132)()3()2()1()(kkxkhxhxhxhxH设则21)1)1-(2)1()()(kkkkxkhxhxkhxH（[e-mail]2.1递推关系与母函数222)1-(2)1)1-(2)(kkkkkkxxkhxxkhxxH（xxxxHxxxxkhxxxHkk1)(21)(2)(221整理得)21)(1()(xxxxH[e-mail]2.1递推关系与母函数000)12()2(kkkkkkkxxx012)(kkhk，比较H(x)的定义，可知一般地，称H(x)为递推关系Fn的母函数。注意到xxxxxxH112-11)21)(1()([e-mail]问题：有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？例2(Fibonacci数列)Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。2.1递推关系与母函数[e-mail]设满n个月时兔子对数为Fn，其中当月新生兔数目设为Nn对，第n个月留下的老兔子数目设为On对。则有nnnONF211,nnnnnFONFO即1(2.1.2)3n,2121FFFFFnnn这就是Fibonacci数列。2.1递推关系与母函数[e-mail]2.1递推关系与母函数1F121，F211123FFF312234FFF是关系式(2.1.2)的初始条件，于是，由(2.1.2)依次可得523345FFF故，由数学归纳发可得（证明略）,835456FFF[e-mail]1)(kkkxFxG___________________)())(()(22xGxxxGxxxxGxxGxx)()1(2设2.1递推关系与母函数则345523441233:::FFFxFFFxFFFx[e-mail])2511)(2511(1)(2xxxxxxxG2.1递推关系与母函数0)(51]2511125111[51kkkkxxx251512,251512其中[e-mail]2.1递推关系与母函数)(51nnnF)251(51)(51nnnnF)(0,1|251|||nn所以由于故，对充分大的n，有[e-mail]618.12511nnFF1618.1nnFF2.1递推关系与母函数121618.0nnnnFFFF0.618法是优化理论方法中最主要的方法之一[e-mail]2.1.2定义2.1递推关系与母函数如果序列{an}满足关系an=f(an-1,an-2,…,an-k)，在给定初值a0,a1,.,…,ak-1条件下，可以依次求得ak,ak+1，…，这样的连锁反应关系，就叫做递推关系。上述递推关系也称为k阶递推关系。[e-mail]2n,1)1(2)(nhnh3n,21nnnFFF2.1递推关系与母函数例如是一阶递推关系是二阶递推关系[e-mail]2.1递推关系与母函数对于序列{an}，构造一函数关系G(x)=a0+a1x+a2x2+…+anxn+……，称G(x)为序列{an}的母函数。上述母函数也称为普通型母函数。注意到：序列可能是有限的也可能是无限的，从而母函数可能是多项式也可能是无穷级数。母函数的首项是零次幂项，对应序列首项[e-mail]例如，对于序列{1,1,1，…}的母函数为2.1递推关系与母函数xxxxxxHkk-111)(032对于序列{Cnk}的母函数为nnkkknnnnnnnxxCxCxCxCCxH)1()(02210Fibonacci数列{Fn}母函数为1)(kkkxFxG21xxx[e-mail]2.1递推关系与母函数注意到：序列与母函数是一一对应的给定序列，可以写出形式母函数，进而通过求和可以得到序列的母函数。给定母函数，可以将函数展开或幂级数展开成为多项式或幂级数形式，由展开式的唯一性，比较各项系数，可以求得对应序列。[e-mail]例3.求n位十进制数中出现偶数个5的数的个数。先从分析n位十进制数p1p2…pn-1pn含偶数个5的数的结构入手2.1递推关系与母函数解若n-1位十进制数p1p2…pn-1含有偶数个5，则pn可取0,1,2,3,4,6,7,8,9中的任意一个；若n-1位十进制数p1p2…pn-1含有奇数个5，则pn只可取一个[e-mail]2.1递推关系与母函数令an表示n位十进制数中出现偶数个5的数的个数令bn表示n位十进制数中出现奇数个5的数的个数则119nnnbaa119nnnabb1,811ba且这是关于序列{an}和{bn}的联立关系[e-mail]2.1递推关系与母函数设序列{an}和{bn}的母函数分别为A(x)和B(x)，则23212321)()(xbxbbxBxaxaaxA______________________________8)()()91(xxBxAx221221)()99)([e-mail]2.1递推关系与母函数______________________1)()()91(xxAxBx221221)()99)(9xaxaxxAxbxbxxB同理故得关于母函数A(x)和B(x)得联立方程组：1)()91()(8)()()91(xBxxxAxxBxAx{23212321)()([e-mail]919122)91(xx)101)(81(xx)101)(81(8719118)101)(81(1)(xxxxxxxxA)101)(81(11891)101)(81(1)(xxxxxxxxB2.1递推关系与母函数解得[e-mail]2.1递推关系与母函数)1019817(21)101)(81(871)(xxxxxxA由于0)10987(21kkkkx010298271kakkk，所以[e-mail]2.1递推关系与母函数同理0)10987(21kkkkx010298271kbkkk，所以)1019817(21)101)(81(1)(xxxxxxB[e-mail]2.1递推关系与母函数解法二：注意到:n-1位的十进制数的全体共有9×10n-2，从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：121109nnnab类似于解法一,我们有119[e-mail]8,1098121aaannn代入,我们有这是一个一阶递推关系.2.1递推关系与母函数设数列{an}母函数为11)(kkkxax