组合2母函数递推关系.ppt

组合数学
帅天平
北京邮电大学数学系
Email: tpshuai@
第二章:递推关系与母函数
1,递推关系引入,i数列
2,常系数递推关系求解
3,母函数及其性质
4,用母函数求解递推关系
5,母函数的应用-整数剖分
6指数型母函数及其应用
7,非线性递推关系举例--几类特殊组合数
递推关系-引入1
利用递推关系进行计数的方法在算法分析中经常用到。
and ,
Mathematics for the analysis of algorithms
Birkhauser,Boston 1981.(3rd,1999)
中对递推关系及其应用有着非常精彩的叙述。
例1,Hanoi问题: 这是组合数学中的一个著名问题。N个圆盘依其半径大小,从下而上套在A柱上,如下图示。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。
递推关系-引入2
A B C
Hanoi问题是个典型的组合问题,第一步要设计
算法,进而估计它的复杂性,及估计工作量。
A B C
递推关系-引入3
算法:
N=2时
第一步先把最上面的一个圆盘套在B上

第二步把下面的一个圆盘移到C上

最后把B上的圆盘移到C上
到此转移完毕
对于一般n个圆盘的问题,
假定n-1个盘子的转移算法已经确定。
先把上面的n-1个圆盘经过C转移到B。
第二步把A下面一个圆盘移到C上
最后再把B上的n-1个圆盘经过A转移到C上
A B C
递推关系-引入4
上述算法是递归的运用。n=2时已给出算法;n=3时,第一步便利用算法把上面两个盘移到B上,第二步再把第三个圆盘转移到柱C上;最后把柱B上两个圆盘转移到柱C上。N=4,5,…以此类推。
递推关系-引入5
算法分析:令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转到C上;最后再一次将B上的n-1个盘子转移到C上。
n=2时,算法是对的,因此,n=3是算法是对的。以此类推。于是有
递推关系-引入6
算法复杂度为:
利用递推关系(a)式也可以依次求得h(1), h(2) , h(3) …,这样的连锁反应关系,叫做递推关系。
i数列是递推关系的又一个典型问题,该数列的本身有着许多应用。
问题:有雌雄兔子一对,假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子?
设满n个月时兔子对数为 Fn其中当月新生兔数目设为Nn 对。第n-1个月留下的兔子数目设为 On 对。
递推关系-i数列1
但
即第n-2个月所产的兔子到第n个月都有繁殖能力了.
由递推关系(1)式可依次得到
递推关系-i数列2