组合数学课件第六章递推关系.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合数学课件第六章递推关系,目录(2),第六章 递推关系,6、1 Fibonacci数列,6、2 常系数线性齐次递推关系得求解,6、3 常系数线性非齐次递推关系得求解,6、4 用迭代和归纳法求解递推关系,本章小结,习题,第七章 生成函数,7、1生成函数得定义和性质,7、2多重集得r-组合数,7、3正整数得划分,7、4指数生成函数与多重集得排列问题,7、5 Catalan数和Stiring数,本章小结,习题,第八章 Polya定理,8、1置换群中得共轭类与轨道,8、2 Polya定理得特殊形式及其应用,本章小结,习题,*,课程总结,第6章 递推关系,本章主要介绍递推关系得建立及几种常见得求解方法:,6、1 Fibonacci数列,6、2 常系数线性齐次递推关系得求解,6、3 常系数线性非齐次递推关系得求解,6、4 用迭代和归纳法求解递推关系,第6章 递推关系,教学目标:,1、掌握几种递推关系得建立方法;,2、理解并掌握常系数线性齐次及非齐次递推关系得求解方法;,3、能运用迭代归纳法求解递推关系;,4、记住并理解Fibonacci数得定义及递推公式,会推导Fibonacci数得一些性质,能运用她们解决一些组合计数问题。,重点:,递推关系得建立方法、常系数线性齐次及非齐次递推关系得求解方法、Fibonacci数和Catalan数得定义、递推公式及性质,难点:,Catalan数得定义、递推公式及性质,第6章 递推关系,6、1 递推关系定义,6、1 递推关系得建立,定义 6、1,设,H,(,n,)为一序列,把该序列中,H,(,n,)和她前面几个,H,(,i,)(0,i,n,-1)用等号(或大于、小于号)关联起来得方程称做一个递推关系(递归关系)。,如第3章得错排数,D,n,=(,n,-1)(,D,n,-1,+,D,n,-2,),(,n,3),和关系式,a,n,=3,a,n,-1,(,n,1)都就是递推关系。,如,a,0,=,d,0,a,1,=,d,1,a,k,=,d,k,d,i,为常数(,i,=0,1,k,),称为递推关系得初值。,如,D,1,=0,D,2,=1作为初值即可惟一得确定序列,(,D,0,D,1,D,n,),a,0,=1,作为初值即可惟一得确定序列,(1,3,3,2,3,n,)。,将递推关系和初值结合起来称为带初值得递推关系。如,6、1 递推关系建立例1-1,6、1 递推关系得建立(Fibonacci数列),例 题,例1、在一个平面上有一个圆和,n,条直线,这些直线中得每一条在圆内都同其她得直线相交。如果没有多于三条得直线相交于一点,试问这些直线将圆分成多少个不同区域？,6、1 递推关系建立例1-2,6、1 递推关系得建立,例 题,解：要求解这个问题，首先必须建立递推关系，然后求解递推关系即可。,设这,n,条直线将圆分成的区域数为,a,n,，如果有,n,-1条直线将圆分成,a,n,-1,个区域，那么再加入第,n,条直线与在圆内的其他,n,-1条直线相交。显然，这条直线在圆内被分成,n,条线段，而每条线段又将第,n,条直线在圆内经过的区域分成两个区域。这样，加入第,n,条直线后，圆内就增加了,n,个区域。而对于,n,=0，显然有,a,0,=1，于是对于每个整数,n,，可以建立如下带初值的递推关系,（求解方法以后几节再介绍）这就是问题的解答。,6、1 递推关系建立,例2,6、1 递推关系得建立,例 题,例2、在一个平面中,有,n,个圆两两相交,但任二个圆不相切,任三个圆无公共点,求这,n,个圆把平面分成多个区域？,解:设这,n,个圆将平面分成,a,n,个区域。,如图。易见,a,1,=2,a,2,=4。,现在假设前,n,-1个圆将平面分成了,a,n,-1,个区域,当加入第,n,个圆时,由题设,这个圆与前面得,n,-1个圆一定交于,2(,n,-1)个点,这2(,n,-1)个点把第,n,个圆,分成2(,n,-1)条弧,而每条弧正好将前,面得,n,-1个圆分成得区域中得其经过,得每个区域分成2个区域,故新加入得第,n,个圆使所成得区域数增加了2(,n,-1)。因此可以,建立如下带初值得递推关系:,求解这个递推关系可以得到问题得解答。,6、1 递推关系建立,例3-1,6、1 递推关系得建立,例 题,例3、“Fibonacci兔子问题”也就是组合数学中得著名问题之一。这个问题就是指:从某一年某一月开始,把雌雄各一得一对兔子放入养殖场中,从第二个月雌兔每月产雌雄各一得一对新兔。每对新兔也就是从第二个月起每月产一对兔子。试问第,n,个月后养殖场中共有多少对兔子？,6、1 递推关系建立,例3-1,表示幼兔,表示成兔,实线表示成长,虚线表示生殖,1:1,2:1,3:2,4:3,5:5,6:8,7:13,6、1 递推关系得建立,6、1 递推关系建立,例3-2,6、1 递推关系得建立,例 题,解：设第,n,个月时养殖场中兔子的对数为,F,n,。并定义,F,0,=1，显然有，,F,1,=1。,由于在第,n,个月时，除了有第,n,-1个月时养殖场中的全部兔子,F,n,-1,外，还应该有,F,n,-2,对新兔子，这是因为在第,n,-2个月就已经有的每对兔子，在第,n,个月里都应生一对新的兔子。因此,可以,建立如下带初值的递推关系,求解上式可以得到我们所需的答案。,注：利用该式我们可以推得,(,F,0,F,1,F,n,)=(1,1,2,3,5,8,13,21,34,55,),常称,F,n,为Fibonacci数，(,F,0,F,1,F,n,)为Fibonacci数列。,Fibonacci数列在数学中是一个奇特而又常见的序列，它在算法分析中起着重要的作用。,注:以上各例均为经典组合数学问题,在算法分析中常用;,对普通得递推关系无一般规则可解。,6、1 Fibonacci数列应用及性质,6、1 递推关系得建立,Fibonacci数列在组合计数中得应用,例:确定2,n,棋盘用多米诺牌完美覆盖得方法数,h,n,。,规定,h,0,=1、容易看到,h,1,=1,h,2,=2,h,3,=3。,h,n,=,h,n,1,满足斐波那契递推关系。,h,n,就是斐波那契数。,+,h,n,2,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,再如,一个人站在“梯子格”得起点处向上跳,从格外只能进入第1格,从格中,每次可向上跳一格或两格,问:可以用多少种方法,跳到第,n,格？,6、1 递推关系得建立,Fibonacci数列在组合计数中得应用,解:设跳到第,n,格得方法有 种。,由于她跳入第1格,只有一种方法;跳入第2格,必须先跳入第1格,所以也只有一种方法,从而,而能一次跳入第,n,格得,只有第,和第 两格,因此,跳入第 格得方法,数,就是跳入第 格得方法数 ,加上跳入,第 格得方法数 之和。,即 。综合得递推公式,容易算出,跳格数列 就就是斐波那契数列,1,1,2,3,5,8,13,21,34,6、1 递推关系得建立,Fibonacci数列在组合计数中得应用,6、1 Fibonacci数列应用及性质,6、1 递推关系得建立,类似得例子,奇妙得斐波那契序列,斐波那契螺旋线数,6、1 Fibonacci数列应用及性质,树杈,得数目,13,8,5,3,2,1,1,6、1 递推关系得建立,类似得例子,6、1 Fibonacci数列应用及性质(1),6、1 递推关系得建立,Fibonacci数列性质,1、Fibonacci数 可以表示为二项式系数之和,即,证明 当 时,有 ,即 ,所以只要证明下面得等式成立,即证,用归纳法。,当 时,有 成立。假设对 等式都成立,则有,6、1 Fibonacci数列应用及性质,由归纳法,命题成立。,6、1 递推关系得建立,Fibonacci数列性质,6、1 Fibonacci数列应用及性质(2),6、1 递推关系得建立,Fibonacci数列性质,2、Fibonacci数,证明,把以上各式得左边和右边分别相加,得,6、1 Fibonacci数列应用及性质(3-4),6、1 递推关系得建立,Fibonacci数列性质,3、Fibonacci数,证明,把以上各式得左边和右边分别相加,得,4、Fibonacci数,证明 由性质2和3即得、,6、1 Fibonacci数列应用及性质(5),6、1 递推关系得建立,Fibonacci数列性质,5、,证明,把以上各式得左边和右边分别相加,得,6、1 Fibonacci数列应用及性质(6),6、1 递推关系得建立,Fibonacci数列性质,6、,证明,由归纳法,等式成立。,对 进行归纳、,当 时,有,成立,假设对一切 有等式成立,则,6、1 Fibonacci数列应用及性质,6、1 递推关系得建立,Fibonacci数列性质,关于,Fibonacci数列,得性质还有许多,习题上也列出了一部分,这里就不一一介绍。,利用这些性质,我们可以将比较大得,n,得Fibonacci数化成较小得 得Fibonacci数,从而使计算更为方便。,6、2 常系数线递推关系次递推关系,6、2 常系数线性齐次递推关系,定义 6、2,若,H,(,n,)中相邻,k,+1项满足,H,(,n,)=,a,1,H,(,n-,1)+,a,2,H,(,n-,2)+,a,k,H,(,n-k,),(,n,k,)称之为,H,(,n,)得,k,阶常系数线性齐次递推关系。,其中,a,i,(,i,=1,2,k,)就是常数,且,a,k,0。,该递推关系还可以写作,H,(,n,)-,a,1,H,(,n-,1)-,a,2,H,(,n-,2)-,a,k,H,(,n-k,)=0、,H,(0)=,d,0,H,(1)=,d,1,H,(,k-,1)=,d,k,-1,称为初始条件,其中,d,i,(,i,=0,2,k,-1)就是常数;,定义 6、3,C,(,x,)=,x,k,-,a,1,x,k,-1,-,a,2,x,k,-2,-,a,k,称为上述递推关系得特征多项式;,C,(,x,)=0称为上述递推关系得特征方程;,该方程得,k,个根,q,1,q,2,q,k,称为上述递推关系得特征根、其中,q,i,(,i,=1,2,k,)就是复数、,6、2 常系数线递推关系次递推关系定理6、1,对此,有下面得定理,定理6、1,6、2 常系数线性齐次递推关系,设,k,阶常系数线性齐次递推关系,H(n),为,若,q,0,H(n),=,q,n,就是上述递推关系得解,当且仅当,q,就是上述特征方程得解。,证明:若,q,0,H(n),=,q,n,就是递推关系,得解,q,n,=,a,1,q,n,-1,+,a,2,q,n,-2,+,a,k,q,n,-,k,(,n,k,),q,k,=,a,1,q,k,-1,+,a,2,q,k,-2,+,a,k,q,就是特征方程,x,k,-,a,1,x,k,-1,-,a,2,x,k,-2,-,a,k,=0得根。,证毕。,定理6、2,若 都就是齐次递推关系得解,那么 也就是齐次递推关系得解。,证:由 就是齐次递推关系得解知,6、2 常系数线递推关系次递推关系定理6、2,6、2 常系数线性齐次递推关系,6、2 常系数线性齐次,相异特征根定理6、3,6、2 常系数线性齐次递推关系,6、2、1 相异特征根得解法,定理 6、3,若,q,1,q,2,q,k,为上述递推关系得特征根(相异),c,1,c,2,c,k,为任意常数,则,a,n,=,c,1,q,1,n,+,c,2,q,2,n,+,c,k,q,k,n,为上述递推关系得解。,证明：由于,q,i,(,i,=1,2,k,),是特征方程,x,k,-,b,1,x,k,-1,-,b,2,x,k,-2,-,b,k,=0的根，由定理6.1有,q,i,n,=,b,1,q,i,n,-1,+,b,2,q,i,n,-2,+,b,k,q,i,n,-k,，,i,=1,2,k,将上式两边同乘以,c,i,，然后从1到,k,求和有,因此,a,n,=,c,1,q,1,n,+,c,2,q,2,n,+,c,k,q,k,n,是递推关系,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的解。,6、2 常系数线性齐次相异特征根定义6、4,6、2 常系数线性齐次递推关系,6、2、1 相异特征根得解法,定义6、4,如果对于递推关系,H,(,n,)=,b,1,H,(,n-,1)+,b,2,H,(,n-,2)+,b,k,H,(,n-k,),得每个解,h,(,n,)都可以选择一组常数 使得,成立,则称,就是递推关系得通解,其中 为任意常数。,6、2 常系数线性齐次,相异特征根定理6、4,6、2 常系数线性齐次递推关系,6、2、1 相异特征根得解法,定理 6、4,若,q,1,q,2,q,k,为上述递推关系得特征根(相异),则,a,n,=,c,1,q,1,n,+,c,2,q,2,n,+,c,k,q,k,n,为上述递推关系得通解,其中,c,i,由初始条件确定。,证明：由定理6.2知，,a,n,=,c,1,q,1,n,+,c,2,q,2,n,+,c,k,q,k,n,是递推关系,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的解。只需证明，若该式满足递推关系式,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的任意初值条件式,a,0,=,d,0,a,1,=,d,1,a,k,-1,=,d,k,-1,所得到的关于,c,1,c,2,c,k,的线性方程组有惟一解即可。,由初值条件式,a,0,=,d,0,a,1,=,d,1,a,k,-1,=,d,k,-1,，我们得到,因此，上述线性方程组关于,c,1,c,2,c,k,有惟一的解。从而证明了,a,n,=,c,1,q,1,n,+,c,2,q,2,n,+,c,k,q,k,n,是递推关系的,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的通解。,例1、求递归关系,6、2 常系数线性齐次例1,6、2 常系数线性齐次递推关系,5、2、1 相异特征根得解法,例 题,6、2 常系数线性齐次,例2,6、2 常系数线性齐次递推关系,6、2、1 相异特征根得解法,例 题,例2、求递归关系,6、2 常系数线性齐次,例3-1,6、2 常系数线性齐次递推关系,6、2、1 相异特征根得解法,例 题,例3、用字母,a,b,和,c,组成长度就是,n,得字,如果要求没有两个,a,相邻,问这样得字有多少个？,解 设,h,(,n,)就是所求得字得个数,n,1、易见,长为1得且没有两个,a,相邻得字有,a,b,和,c,所以,h,(1)=3、长为2得没有 两个,a,相邻得字有,ab,ac,ba,bb,bc,ca,cb,cc,、所以,h,(2)=8、,设,n,3,如果字中得第一个字母就是,a,那么第二个字母只能就是,b,或,c,其余得字母可以有,h,(,n,-2)种方式来选择,因此以,a,开头得字有2,h,(,n-,2)个、如果字中得第一个字母就是,b,那么这样得字有,h,(,n,-1)个,同理以,c,开头得字也有,h,(,n,-1)个,由加法法则得,6、2 常系数线性齐次,例3-2,6、2 常系数线性齐次递推关系,6、2、1 相异特征根得解法,例 题,例3、用字母,a,b,和,c,组成长度就是,n,得字,如果要求没有两个,a,相邻,问这样得字有多少个？,6、2 常系数线性齐次,相同特征根定理6、5,6、2 常系数线性齐次递推关系,6、2、2 相同特征根得解法,定理 6、5,若,q,为上述递推关系得特征方程,C,(,x,)=0得一个,m,重特征根,则,q,n,nq,n,n,m-,1,q,n,为该递推关系得解。,证明:令,P,(,x,)=,x,k,-,b,1,x,k,-1,-,b,2,x,k,-2,-,b,k,P,n,(,x,)=,x,n-k,P,(,x,),=,x,n,-,b,1,x,n,-1,-,b,2,x,n,-2,-,b,k,x,n-k,。,由于,q,就是,P,(,x,)=0得,m,重根,故,q,也就是,P,n,(,x,)=0得,m,重根,由高等代数得知识知,q,也就是,P,n,(,x,)=0得(,m,-1)重根,那么,q,也就是,xP,n,(,x,)=0得(,m,-1)重根,即,q,就是方程,nx,n,-,b,1,(,n,-1),x,n,-1,-,b,2,(,n,-2),x,n,-2,-,b,k,(,n,-,k,),x,n-k,=0得(,m,-1)重根。类似地,q,就是方程,n,2,x,n,-,b,1,(,n,-1),2,x,n,-1,-,b,2,(,n,-2),2,x,n,-2,-,b,k,(,n,-,k,),2,x,n-k,=0得(,m,-2)重根。一般地,对任意得,i,i,m,q,就是方程,n,i,x,n,-,b,1,(,n,-1),i,x,n,-1,-,b,2,(,n,-2),i,x,n,-2,-,b,k,(,n,-,k,),i,x,n-k,=0得(,m,-,i,)重根。,即有,n,i,q,n,-,b,1,(,n,-1),i,q,n,-1,-,b,2,(,n,-2),i,q,n,-2,-,b,k,(,n,-k),i,q,n-k,=0。,分别令,i,=1,2,m,-1,知,nq,n,n,2,q,n,n,m,-1,q,n,都就是递推关系,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,得解,而,q,n,就是递推关系,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,得解在定理6、1中已经证明。,故定理得证。,6、2 常系数线性齐次,相同特征根定理6、6-1,6、2 常系数线性齐次递推关系,6、2、2 相同特征根得解法,定理 6、6,若,q,1,q,2,q,t,分别为上述递推关系的特征方程,C,(,x,)=0相异的,m,1,m,2,m,t,重特征根，,为该递推关系的通解，其中,c,ij,由初始条件确定。,6、2 常系数线性齐次,相同特征根定理6、6-2,6、2 常系数线性齐次递推关系,5、2、2 相同特征根得解法,证明：由定理6.4知，表达式,的右端每一项都是递推关系,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的解。故,a,n,也是该递推关系的解。现只需证明该式满足递推关系式,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的任意初值条件式,a,0,=,d,0,a,1,=,d,1,a,k,-1,=,d,k,-1,所得的线性方程组有惟一解即可。,将初值条件式,a,0,=,d,0,a,1,=,d,1,a,k,-1,=,d,k,-1,代入式(,A,)得到下列方程组：,这个方程组的系数行列式是,Vandermonde,行列式的一个推广。,其行列式之值为,故方程组有惟一解。,即,c,ij,(,i,=1,2,t,;,j,=1,2,m,i,)是由初值惟一确定，定理得证。,例4、求递归关系,6、2 常系数线性齐次,例4,6、2 常系数线性齐次递推关系,6、2、2 相同特征根得解法,例 题,例5、求递归关系,6、2 常系数线性齐次,例5,6、2 常系数线性齐次递推关系,6、2、2 相同特征根得解法,例 题,6、2 常系数线性齐次,例6,6、2 常系数线性齐次递推关系,6、2、2 相同特征根得解法,例 题,例6、求递归关系,6、2 常系数线性齐次,例7,6、2 常系数线性齐次递推关系,5、2、2 相同特征根得解法,例 题,例7、计算,n,阶行列式的值：,解：设具有以上形式的,n,阶行列式的值为,a,n,，按第一列展开有,显然,a,1,=2，,a,2,=3，于是可建立递推关系如下,这个递推关系就是例3所求解的递推关系，故由例3的结果可知,6、2 常系数线性齐次注意事项,6、2 常系数线性齐次递推关系,6、2、2 相同特征根得解法,注意:,建立递推关系关系时可考虑某个特定数值,如第一个、最后一个等;,k,次递推关系需要,k,个初值,一般从,a,0,开始(不妨假设);,结果需要验证(,n,=,k,+1,k,+2,)。,6、3 常系数线性非齐次定义,6、3 常系数线性非齐次递推关系,定义 6、4,若,H,(,n,)中相邻,k,+1项满足:,H,(,n,)=,b,1,H,(,n-,1)+,b,2,H(n-,2)+,b,k,H,(,n-k,)+,f,(,n,),(,n,k,),称之为,H,(,n,)得,k,阶常系数线性非齐次递推关系。其中,b,i,(,i,=1,2,k,)就是常数,且,b,k,0,f,(,n,)0,。,若,f,(,n,),=,0,称,=,b,1,H,(,n-,1)+,b,2,H(n-,2)+,b,k,H,(,n-k,)为上述递推关系导出得常系数线性齐次递推关系。,6、3 常系数线性非齐次,定理6、7-1,6、3 常系数线性非齐次递推关系,定理 6、7,若,为,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,+,f,(,n,),的一个特解，,为 =,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的一个通解，则,a,n,=,+,为原非齐次递推关系的通解。,证明：由于,是非齐次递推关系式导出的齐次线性递推关系式,即 的通解，故有,又由于 是非齐次递推关系,的一个特解，故有,将以上两式的两边分别相加得,由上式可见,是式的解。,设非线性齐次递推关系为:,a,n,=,b,1,a,n,-1,+b,2,a,n,-2,+,b,k,a,n,-,k,+,f,(,n,),6、3 常系数线性非齐次,定理6、7-2,6、3 常系数线性非齐次递推关系,定理 6、7,若,为,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,+,f,(,n,),的一个特解，,为 =,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的一个通解，则,a,n,=,+,为原非齐次递推关系的通解。,现只需证明,能满足式 的任意初值条件式 所导出的关于,c,1,c,2,c,k,为未知数的线性方程组,有惟一解即可。式中 。而这是显然的。因为该方程组的系数矩阵是一个,Verdermonde,矩阵，其行列式的值不为0。故定理得证。,6、3 常系数线性非齐次,定理6、7-3,6、3 常系数线性非齐次递推关系,定理 6、7,若,为,a,n,=,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,+,f,(,n,),的一个特解，,为 =,b,1,a,n,-1,+,b,2,a,n,-2,+,b,k,a,n,-,k,的一个通解，则,a,n,=,+,为原非齐次递推关系的通解。,注:定理6、7指出,若要求一个常系数线性非齐次递推关系式得通解,必须先求出这个递推关系所导出得常系数线性齐次递推关系得通解,然后再求这个递推关系式得一个特解,将其相加即可。,然而,求一个非齐次线性递推关系得特解,通常没有系统得方法,但当函数,f,(,n,)就是某些特殊形式时,才有一些规范得求法。,若,f,(,n,)为,n,的,k,次多项式，则,=,A,0,n,k,+,A,1,n,k,-1,+,A,k,，其中,A,0,A,1,A,k,为待定系数；若导出的常系数线性齐次递推关系特征根为1的,m,重根，则,=(,A,0,n,k,+,A,1,n,k,-1,+,A,k,),n,m,。,6、3 常系数线性非齐次特殊形式,6、3 常系数线性非齐次递推关系,可针对,f,(,n,)得某些特定形式,转化为齐次性。,若,f,(,n,)为,n,的形式，如,不是导出的常系数线性齐次递推关系特征根，则,=,A,n,，其中,A,为待定系数；若,是导出的常系数线性齐次递推关系的,k,重特征根根，则,=(,A,0,n,k,+,A,1,n,k,-1,+,A,k,),n,。,6、3 常系数线性非齐次,例1,6、3 常系数线性非齐次递推关系,例 题,例1、求递归关系,6、3常系数线性非齐次,例2-1,6、3 常系数线性非齐次递推关系,例 题,例2、“Hanoi塔”问题:,n,个大小不一得圆盘依半径得大小,从下而上得套在柱子,A,上。如图所示。现要求将所有得圆盘从柱子,A,上全部移到柱子,C,上,每次只允许从一根柱子上转移一个圆盘到另一根柱子上,且在转移过程中不允许出现大圆盘放到小圆盘上。试问至少要转移多少次才能将柱子上得,n,个圆盘全部转移到柱子,C,上去？,6、3常系数线性非齐次,例2-2,6、3 常系数线性非齐次递推关系,例 题,解：用,a,n,表示从一根柱子上的,n,个圆盘全部转移到另一根柱子上的转移次数。显然，,a,1,=1,a,2,=3。当,n,3时，要将柱子,A,上的,n,个圆盘转移到柱子,C,上，可以这样设想。先把柱子,A,上的,n,-1个圆盘转移到柱子,B,上，这需要转移,a,n,-1,次；然后把柱子,A,上最后一个圆盘转移到柱子,C,上，显然这需要转移一次；最后再把柱子,B,上的,n,-1个圆盘转移到柱子,C,上，这也需要转移,a,n,-1,次。经过这些步骤后，所有,A,上的,n,个圆盘就全部转移到柱子,C,上。由加法法则，这一共转移了2,a,n,-1,+1次。于是可以,建立如下带初值的递推关系,这就是我们,需要的结果。,6、3 常系数线性非齐次,例2-3,6、3 常系数线性非齐次递推关系,例 题,例2、求递归关系（Hanoi塔）,6、3 常系数线性非齐次,例3,6、3 常系数线性非齐次递推关系,例 题,例3、求递归关系,6、3 常系数线性非齐次,例4,6、3 常系数线性非齐次递推关系,例 题,例4、求递归关系,a,n,+2,a,n,-1,+,a,n,-2,=2,n,得通解。,6、3 常系数线性非齐次,例5,6、3 常系数线性非齐次递推关系,例 题,例5、求递归关系,a,n,-4,a,n,-1,+4,a,n,-2,=2,n,得通解。,6、3 常系数线性非齐次,例6,6、3 常系数线性非齐次递推关系,例 题,例6、求,S,n,=1+2+3+,n,。,6、3 常系数线性非齐次,例7,6、3 常系数线性非齐次递推关系,例 题,例7、求,S,n,=1,2,+2,2,+3,2,+,n,2,。,6、3 常系数线性非齐次,例8,6、3 常系数线性非齐次递推关系,例 题,例8、求,S,n,=1,3,+2,3,+3,3,+,n,3,。,6、4 迭代法,例,1,6、4 迭代法与归纳法,针对上述,k,阶常系数线性(非)齐次递推关系求解方法,当,k,较大时,面临着解高次方程和高阶线性方程组得困难;而且对一般得非齐次递推关系无系统得方法。,例 题,例1、求递归关系,解：这是常系数线性非齐次递推关系，可以用上节中的方法求解。这里用迭代法求解。反复应用递推关系式进行迭代有,6、4 迭代法,例,2-1,6、4 迭代法与归纳法,例 题,例2、给定,n,个实数,a,1,a,2,a,n,可以用多少种不同得方法构成她们得乘积？在这里我们认为相乘得顺序不同也就是不同得方法,如(,a,1,a,2,),a,3,与,a,1,(,a,2,a,3,)就是不同得方法、,解:设,h,(,n,)表示这,n,个数构成乘积得方法数、显然,h,(1)=1、假设,n,-1个数a,1,a,2,a,n,-1,得乘积已经构成,有,h,(,n,-1),个、任取其中得一个乘积,她就是由,n,-2次乘法得到得、对于其中得某一次相乘得两个因式,把,a,n,乘到一个因式得左边或右边,或乘到另个因式得左边或右边,共有四种加入,a,n,得方法、再根据加法法则,对于这个乘积加入,a,n,得方法就是4,(,n,-2),种、此外,还可以把,a,n,分别乘在整个乘积得左边或右边,所以加入,a,n,得方法数就是,4,(,n,-2)+2=4,n,-6、,根据以上得分析可以得到该问题得递推关系,6、4 迭代法,例,2-2,6、4 迭代法与归纳法,例 题,例2、求递归关系,解：这是一个非常系数线性非齐次递推关系。下面用迭代法求解。反复应用递推关系式进行迭代有,6、4 迭代法,例,3,6、4 迭代法与归纳法,例 题,例3、求递归关系,解：这是一个非线性递推关系。反复应用递推关系式进行迭代有,注：此例中的递推关系式还可以作一个变换变成一个常系数线性非齐次递推关系然后利用上节的方法求解。,