《组合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,根据行列式性质,
