资源描述：
《组合2母函数递推关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、组合数学帅天平北京邮电大学数学系Email:tpshuai@gmail.com1TPSHUAI第二章:递推关系与母函数1,递推关系引入，Fibonacci数列2,常系数递推关系求解3,母函数及其性质4,用母函数求解递推关系5,母函数的应用-整数剖分6指数型母函数及其应用7,非线性递推关系举例--几类特殊组合数2TPSHUAI2.1递推关系-引入1利用递推关系进行计数的方法在算法分析中经常用到。D.H.GreeneandD.E.Knuth,MathematicsfortheanalysisofalgorithmsBirkhauser
2、,Boston1st,1981;3rd,1999.中对递推关系及其应用有更广泛的叙述。3TPSHUAI例1,Hanoi问题：这是组合数学中的一个著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。2.1递推关系-引入2ABC4TPSHUAIHanoi问题是个典型的组合问题,第一步要设计算法，进而估计它的复杂性，及估计工作量。ABC2.1递推关系-引入3算法：N=
3、2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上最后把B上的圆盘移到C上到此转移完毕5TPSHUAI对于一般n个圆盘的问题，假定n-1个盘子的转移算法已经确定。先把上面的n-1个圆盘经过C转移到B。第二步把A下面一个圆盘移到C上最后再把B上的n-1个圆盘经过A转移到C上ABC2.1递推关系-引入46TPSHUAI上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移
4、到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，…以此类推。2.1递推关系-引入57TPSHUAI算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有2.1递推关系-引入6算法复杂度为：利用递推关系(a)式也可以依次求得h(1),h(2),h(3)…，这样的连锁反应关系，叫做递推关系。8TPSHUAIFibonacci数列是递推关系的又一个典型问题，该数列
5、的本身有着许多应用。问题：有雌雄兔子一对，假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为Fn其中当月新生兔数目设为Nn对。第n-1个月留下的兔子数目设为On对。2.1递推关系-Fibonacci数列19TPSHUAI但即第n-2个月所产的兔子到第n个月都有繁殖能力了.由递推关系(1)式可依次得到2.1递推关系-Fibonacci数列210TPSHUAI趣味结论2.1递推关系-Fibonacci数列711TPSHUAI证明：2.1递推关系-Fibonacci数列812TPSHUAI证
6、明：2.1递推关系--Fibonacci数列913TPSHUAI证明：2.1递推关系-Fibonacci数列1014TPSHUAI确定一个数列{an}的最常用的方法是给出一般项an的表达式得到该数列的母函数建立数列所满足的递推关系—即建立一种规则，使得通过这种规则数列的每一项可由其前面的项唯一确定.2.1递推关系更一般的递推关系。15TPSHUAI递推关系可分为有限阶和无限阶两种2.1递推关系一个r-阶递推关系定义为：有正整数r以及一个r+1元函数F，使得对所有nr,有关系式16TPSHUAI定义1如果序列{an}满足则(2)称
7、为{an}的k阶常系数线性递推关系,(2i)称为{an}的初始条件。若b(n)=0，称为齐次的，否则称为非齐次的。2.1递推关系-线性常系数递推关系17TPSHUAI2.1递推关系-线性常系数递推关系定义2如果序列{an}满足称为{an}的特征多项式.C(x)=0称为{an}的特征方程.则(2-1)称为{an}的k阶常系数线性齐次递推关系,(2-2)称为{an}的初始条件。18TPSHUAI2.1递推关系例：1×n棋盘用红、白、蓝三种颜色着色,不允许相邻两格都着红色,求着色方案数.解:设an表示满足条件的着色方案数.123……n-
8、1n19TPSHUAI2.1递推关系在该棋盘上着色,其方案可分成如下四类:1)1着白色,余下的是1×(n-1)的棋盘,它所满足条件的着色方案数是an-1;2)1着蓝色,余下的是1×(n-1)的棋盘,它所满足条件的着色方案数是an-13)1着红色,2
