《组合2母函数递推关系》由会员分享,可在线阅读,更多相关《组合2母函数递推关系(252页珍藏版)》请在金锄头文库上搜索。
1、组合数学,帅天平,北京邮电大学数学系,Email: ,TP SHUAI,2,第二章:递推关系与母函数,1,递推关系引入,Fibonacci数列2,常系数递推关系求解3,母函数及其性质4,用母函数求解递推关系5,母函数的应用-整数剖分6指数型母函数及其应用7,非线性递推关系举例-几类特殊组合数,TP SHUAI,3,2.1 递推关系-引入1,利用递推关系进行计数的方法在算法分析中经常用到。,D.H.Greene and D.E.Knuth, Mathematics for the analysis of algorithms Birkhauser,Boston 1st, 1981; 3rd,19
2、99. 中对递推关系及其应用有更广泛的叙述。,TP SHUAI,4,例1,Hanoi问题: 这是组合数学中的一个著名问题。N个圆盘依其半径大小,从下而上套在A柱上,如下图示。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,2.1 递推关系-引入2,TP SHUAI,5,Hanoi问题是个典型的组合问题,第一步要设计算法,进而估计它的复杂性,及估计工作量。,2.1 递推关系-引入3,算法:,N=2时,第一步先把最上面的一个圆盘套在B上, ,第二步把下面的一个圆盘移到C上, ,最后把
3、B上的圆盘移到C上,到此转移完毕,TP SHUAI,6,对于一般n个圆盘的问题,,假定n-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,2.1 递推关系-引入4,TP SHUAI,7,上述算法是递归的运用。n=2时已给出算法;n=3时,第一步便利用算法把上面两个盘移到B上,第二步再把第三个圆盘转移到柱C上;最后把柱B上两个圆盘转移到柱C上。N=4,5,以此类推。,2.1 递推关系-引入5,TP SHUAI,8,算法分析:令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B
4、上;然后把第n个盘子转到C上;最后再一次将B上的n-1个盘子转移到C上。 n=2时,算法是对的,因此,n=3是算法是对的。以此类推。于是有,2.1 递推关系-引入6,算法复杂度为:,利用递推关系(a)式也可以依次求得h(1), h(2) , h(3) ,这样的连锁反应关系,叫做递推关系。,TP SHUAI,9,Fibonacci数列是递推关系的又一个典型问题,该数列的本身有着许多应用。,问题:有雌雄兔子一对,假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子?,设满n个月时兔子对数为 Fn其中当月新生兔数目设为Nn 对。第n-1个月留下的兔子数目设为 On 对。,2.1
5、递推关系-Fibonacci数列1,TP SHUAI,10,但,即第n-2个月所产的兔子到第n个月都有繁殖能力了.,由递推关系(1)式可依次得到,2.1 递推关系-Fibonacci数列2,TP SHUAI,11,趣味结论,2.1 递推关系-Fibonacci数列7,TP SHUAI,12,证明:,2.1 递推关系-Fibonacci数列8,TP SHUAI,13,证明:,2.1 递推关系- -Fibonacci数列9,TP SHUAI,14,证明:,2.1 递推关系-Fibonacci数列10,TP SHUAI,15,确定一个数列an的最常用的方法是给出一般项an的表达式得到该数列的母函数建
6、立数列所满足的递推关系即建立一种规则,使得通过这种规则数列的每一项可由其 前面的项唯一确定.,2.1 递推关系,更一般的递推关系。,TP SHUAI,16,递推关系可分为有限阶和无限阶两种,2.1 递推关系,一个r-阶递推关系定义为:有正整数r 以及一个r+1元函数F,使得对所有nr, 有关系式,TP SHUAI,17,定义1 如果序列an满足,则(2)称为an的 k 阶常系数线性递推关系,(2i)称为an 的初始条件。若b(n)=0,称为齐次的,否则称为非齐次的。,2.1 递推关系-线性常系数递推关系,TP SHUAI,18,2.1递推关系-线性常系数递推关系,定义2 如果序列an满足,称为
7、an 的特征多项式.C(x)=0称为an的特征方程.,则(2-1)称为an的 k阶常系数线性齐次递推关系, (2-2)称为an 的初始条件。,TP SHUAI,19,2.1递推关系,例:1n 棋盘用红、白、蓝三种颜色着色,不允许相邻两格都着红色,求着色方案数.解: 设an 表示满足条件的着色方案数.,TP SHUAI,20,2.1递推关系,在该棋盘上着色,其方案可分成如下四类:1)1着白色,余下的是1(n-1)的棋盘,它所满足条件的着色方案数是an-1 ;2) 1着蓝色,余下的是1(n-1)的棋盘,它所满足条件的着色方案数是 an-13) 1着红色,2着蓝色,余下的是1(n-2) 的棋盘,它所
8、满足条件的着色方案数是an-2;4) 1着红色,2着白色,余下的是1(n-2) 的棋盘,它所满足条件的着色方案数是an-2.,TP SHUAI,21,2.1递推关系,故总的着色方案数为:,TP SHUAI,22,2.2 母函数-引入1,母函数方法是一套非常有用的方法,应用极广。这套方法的系统叙述,最早见于Laplace在1812年的名著概率解析理论。,两个色子掷出6点,有多少种选法?,我们来看如下的例子,TP SHUAI,23,2.2 母函数-引入2,我们也可以从另一角度来看,要使两个色子掷出6点,第一个色子除了6以外的都可选,这有5种选法,一旦第一个选定,第二个色子就只有一种可能的选法按乘法
9、法则有5*1=5种,注意到,出现1,5有两种选法,出现2,4也有两种选法,而出现3,3只有一种选法,这些选法互斥且穷尽了出现6点的一切可能的选法,按加法法则,共有2+2+1=5种不同选法。,TP SHUAI,24,但碰到用三个或四个色子掷出n点,上述两方法就不胜其烦了。这就需要引进新的方法。,2.2 母函数-引入3,TP SHUAI,25,2.2 母函数-引入4,TP SHUAI,26,这种对应把组合问题的加法法则和幂级数的t的乘幂的相加对应起来。,故使两个色子掷出6点的方法数等价于求,2.2 母函数-引入5,TP SHUAI,27,母函数的思想很简单 即:把离散数列和幂级数一一对应起来,把离
10、散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造.,再看下面的例子.,2.2 母函数-引入6,TP SHUAI,28,2.2 母函数-引入7,中所有的项包括 n个元素a1,a2, an中取两个组合的全体;同理 x3 项系数包含了从 n个元素a1,a2, an中取3个元素组合全体。以此类推。,若令a1=a2= =an=1,在(2-1-1)式,项系数,中每一个组合有1个贡献,其他各项以此类推.,TP SHUAI,29,2.2 母函数-引入8,故有:,另一方面:,TP SHUAI,30,比较等号两端项对应系数,可得一等式,2.2 母函数-引入9,TP SHUAI
11、,31,2.2 母函数-引入10,用类似的方法可得等式:,证法如下:,TP SHUAI,32,比较等式两端的常数项,即得公式(2-1-3),2.2 母函数-引入11,TP SHUAI,33,又如等式:,令x=1 可得,2.2 母函数-引入12,TP SHUAI,34,(2-1-2)式等号的两端对x求导可得:,等式(2-1-5)两端令x =1,得:,2.2 母函数-引入13,TP SHUAI,35,2.2 母函数-引入14,用类似的方法还可以得到:,等式两端对x求导再令x =1,得:,TP SHUAI,36,2.2 母函数-引入15,已可见函数,还可以类似地推出一些等式,但通过上面一些例子,的关
12、系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下:,在研究序列,TP SHUAI,37,2.2 母函数-引入16,TP SHUAI,38,利用母函数求解Fibonacci数列(Fn=Fn-1+Fn-2, F1=F2=1):设,2.2 母函数-引入17,TP SHUAI,39,2.2 母函数-引入18,TP SHUAI,40,2.2 母函数-引入19,TP SHUAI,41,其中,2.2 母函数-引入20,TP SHUAI,42,42,几个基本的母函数,TP SHUAI,43,43,几个基本的母函数,TP SHUAI,44,2.3母函数的性质1,一个序列和它的母函数一一对应。给了序
13、列便得知它的母函数;反之,求得母函数序列也随之而定。这种关系颇像数学中的积分变换,特别酷似离散序列的Z变换。如前的例子所示的那样,为了求满足某种递推关系的序列,可把它转换为求对应的母函数G(x),G(x) 可能满足一代数方程,或代数方程组,甚至于是微分方程。,最后求逆变换,即从已求得的母函数G(x)得到序列an。关键在于要搭起从序列到母函数,从母函数到序列这两座桥。这一节便是以此为目的的。,TP SHUAI,45,2.3母函数的性质2,TP SHUAI,46,性质1:,证:,2.3母函数的性质3,TP SHUAI,47,性质2:,则,若,2.3母函数的性质4,TP SHUAI,48,证:,2.
14、3母函数的性质5,TP SHUAI,49,性质3:,若,则,2.3母函数的性质6,TP SHUAI,50,2.3母函数的性质7,证:,TP SHUAI,51,例. 已知,2.3母函数的性质8,TP SHUAI,52,类似可得:,2.3母函数的性质9,TP SHUAI,53,性质4,则,2.3母函数的性质10,TP SHUAI,54,证,2.3母函数的性质11,TP SHUAI,55,2.3母函数的性质12,TP SHUAI,56,例,则,性质5,2.3母函数的性质13,TP SHUAI,57,性质5和性质6的结论是显而易见的。,性质6,2.3母函数的性质14,TP SHUAI,58,性质7,若
15、,则,2.3母函数的性质15,TP SHUAI,59,证:,2.3母函数的性质16,TP SHUAI,60,已知,例1.,则,2.3母函数的性质17,TP SHUAI,61,2.4 母函数求解线性常系数递推关系1,以二阶齐次线性常系数递推关系为例,TP SHUAI,62,2.4 母函数解线性常系数递推关系2,TP SHUAI,63,2.4 母函数解线性常系数递推关系3,TP SHUAI,64,2.4 母函数解线性常系数递推关系4,TP SHUAI,65,2.4 母函数解线性常系数递推关系5,TP SHUAI,66,2.4 母函数解线性常系数递推关系6,证明:(1) r1,r2为两相异的实根.,TP SHUAI,67,2.4 母函数解线性常系数递推关系7,TP SHUAI,68,2.4 母函数解线性常系数递推关系8,故,TP SHUAI,69,2.4母函数求解线性常系数递推关系9,TP SHUAI,70,2.4 母函数求解线性常系数递推关系10,TP SHUAI,71,2.4母函数求解线性常系数递推关系11,TP SHUAI,72,2.4母函数求解线性常系数递推关系12,TP SHUAI,73,例4:求下列n阶行列式dn 的值.,2.4母函数求解线性常系数递推关系13,TP SHUAI,74,根据行列式性质,