递归关系及解法(共30张PPT)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章递归关系及解法,第一页，共30页。,例1,(“Hanoi塔”问题)：这是个组合数学中的著名问题。n个大小不一的圆盘依其半径大小，从下而上套在A柱上，如下图示。现要求将所有的圆盘从A柱上全部转移到C柱上,每次只允许从一个柱子上转移一个盘子到另一柱子上，且在转移过程中不允许出现大盘放在小盘上方。试问要转移多少次才能将柱A上的n个盘移到C柱上。,A B C,第二页，共30页。,例2,“Fibonacci兔子问题”：从某年某月(设为第0月)开始,把雌雄各一的一对小兔放入养殖场,假定两个月后长成成兔,并同时(即第二个月)开始每周产雌雄各一的一对小兔,新增的小兔也按此规律繁殖,问第n个月末养殖场共有多少对兔子?,第n月的兔子包括两部分:上月留下的和当月新生的,而新生的小兔数即为前月末的兔子数,所以,F,n,=F,n-1,+F,n-2,Fibonacci序列的性质:,第三页，共30页。,5.2 常系数线性齐次递归关系的解法,序列a,0,a,1,a,2,a,n,中相邻的k+1项之间的关系为,则称之为序列的k阶常系数线性齐次递归关系,其中系数b,i,为常数,i=1,2,k,且b,k,0。,与(5.2.1)相联系的方程,称之为递归关系(5.2.1)的特征方程，其根称为递归关系式的特征根。,第四页，共30页。,特征方程的根与递归关系的解之间的关系：,若q 0,a,n,=q,n,为递归关系(5.2.1)的解当且仅当q为特征方程(5.2.2)的根。,称式,为递归关系(5.2.1)的初值条件。,第五页，共30页。,若q,1,q,2,q,k,为递归关系式(5.2.1)的特征根，c,1,c,2,c,k,为任意常数，则,为递归关系(5.2.1)的解。,若对递归关系(5.2.1)的任意一个解a,n,，都存在一组常数c,1,c,2,c,k,使得,则称该式为递归关系式(5.2.1)的通解。,若q,1,q,2,q,k,为递归关系式(5.2.1)的k个互不相同的特征根，则式(5.2.4)为(5.2.1)的通解。,第六页，共30页。,例1,求Fibonacci序列的通项。,例2,求解递归关系,第七页，共30页。,注：若特征根有复根，复根成对出现，故设,则通解可表示为,其中,第八页，共30页。,例3,求解递归关系,第九页，共30页。,若递归关系(5.2.1)的特征方程(5.2.2)有一个m重根q，则q,n,nq,n,n,m-1,q,n,均为(5.2.1)的解。,设q,1,q,2,q,t,分别为特征方程(5.2.2)的相异的m,1,m,2,m,t,重根,且,则递归关系(5.2.1)的通解为,第十页，共30页。,例4,求解递归关系,例5,求解递归关系,第十一页，共30页。,5.3 常系数线性非齐次递归关系的解法,序列a,0,a,1,a,2,a,n,中相邻的k+1项之间的关系为,则称之为序列的k阶常系数线性非齐次递归关系,其中系数b,i,为常数,i=1,2,k,b,k,0,f(n)0,nk。,在式(5.3.1)中,若f(n)=0,则称,为由式(5.3.1)导出的常系数线性齐次递归关系。,第十二页，共30页。,若 为(5.3.1)的一个特解,而,()是由(5.3.1)导出的线性齐次递归关系(5.3.2)的通解,则,为(5.3.1)的通解。,注：由定理5.3.1知,要求(5.3.1)的通解,只要求它的一个特解及导出的齐次递归关系的通解即可。对非齐线性递归关系的特解,针对f(n)的特殊形式有以下情形:,第十三页，共30页。,1.f(n)是n的t次多项式,1不是齐次递归关系(5.3.2)的特征根,这时,(5.3.1)的特解形式为,其中 为待定常数。,例1 求解“Hanoi塔”问题的递归关系,例2 求解递归关系,第十四页，共30页。,1是齐次递归关系(5.3.2)的m重特征根(m,1),这时,(5.3.1)的特解形式为,其中 为待定常数。,例3 求解递归关系,第十五页，共30页。,2 f(n)是,n,的形式,不是导出的齐次线性递归关系的特征根,这时,(5.3.1)的特解形式为,其中 A为待定常数。,例4,求解递归关系,第十六页，共30页。,是导出的齐次线性递归关系的m重特征根,(m,1),这时,(5.3.1)的特解形式为,其中 A为待定常数。,例5,求解递归关系,第十七页，共30页。,f(n)=,n,g(n),其中g(n)为n的t次多项式,是导 出的齐次线性递归关系的m重特征根,(m0),这时,(5.3.1)的特解形式为,其中 为待定常数。,例6,求解递归关系,第十八页，共30页。,5.4 递归关系的其他解法,前面方法当k较大时，面临求解高阶方程及k个未知数k个方程的方程组求解困难问题。本节再介绍一些方法。,一、迭代法,例1 求解递归关系,二、归纳法,例2 求解递归关系,第十九页，共30页。,三、母函数法,主要思想:,用f(x)表示序列a,0,a,1,a,2,a,n,的普通母函数,即,利用递归关系a,n,的表达式与(5.4.1)间的关系将(5.4.1)化为关于f(x)的方程，即有,g(f(x)=0;,解出f(x)；,将f(x)的表达式展开成幂级数的形式，即得a,n,的初等表达式.,第二十页，共30页。,2)有一个m重根q，则qn,nqn,nm-1qn均为(5.,这时,(5.,n个大小不一的圆盘依其半径大小，从下而上套在A柱上，如下图示。,例1 求解“Hanoi塔”问题的递归关系,S2(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数。,令 ，若,一、第1类Stirling数,设q1,q2,qt分别为特征方程(5.,第1类Stirling数S1(n,k)满足,1)的特征方程，其根称为递归关系式的特征根。,特征方程的根与递归关系的解之间的关系：,这时,(5.,其中 为待定常数。,称之为递归关系(5.,其中 为待定常数。,例3,求解递归关系,例4,求解递归关系,第二十一页，共30页。,四、代换法,将序列a,0,a,1,a,2,a,n,的递归关系转换为关于新序列b,0,b,1,b,2,b,n,的递归序列。,例5,求解递归关系,五、将常系数线性非齐次递归关系转化为常系数齐次递归关系,例6,求a,n,-2a,n-1,=3的通解。,例7,求,第二十二页，共30页。,5.5 Stirling数,一、第1类Stirling数,令 ，若,则称S,1,(n,k)为第1类Stirling数，即为多项式x,n,中x,k,的系数。,当nk时，S,1,(n,k)=0。,第1类Stirling数S,1,(n,k)满足,第二十三页，共30页。,第1类Stirling数S,1,(n,k)的数值：,n k,1,2,3,4,5,6,7,1,1,2,-1,1,3,2,-3,1,4,-6,11,-6,1,5,24,-50,35,-10,1,6,-120,274,-255,85,-15,1,7,720,-1764,1624,-735,175,-21,1,第二十四页，共30页。,二、第2类Stirling数,若 则称S,2,(n,k)为第二类Stirling数。显然，当nk时，S,2,(n,k)=0。,第2类Stirling数S,2,(n,k)满足,第二十五页，共30页。,S,2,(n,k)的组合意义涉及集合的划分,S,2,(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数。,证明,设A(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数，只要证明A(n,k)满足定理5.5.3即可。,给定一个n+1个元素的集合,a,1,a,2,a,n+1,将它划分为k个不相交的非空子集,分以下两种情况:,(1)a,n+1,为k个子集中的一个子集，则将a,1,a,2,a,n,划分为k-1个子集的方式数为,A(n,k-1)。,(2)a,n+1,不为k个子集中的一个子集，则a,n+1,必为某个子集中的元素。这时，先将a,1,a,2,a,n,划分为k个子集共有A,(n,k)种方式，然后将,a,n+1,加到k个子集中的某一个，共有k种方式，从而得总的划分数为k,A,(n,k)。,由加法原理，,a,1,a,2,a,n+1,划分为k个子集的方式数为,A(n,k-1)+k,A,(n,k)。,所以有,A(n+1,k)=A(n,k-1)+k,A,(n,k)。,又将0 个元素的集合划分为0个不相交子集的方式数为1，所以A(0,0)=1。而不可能将n个元素的集合中的元素不放进任何一个集合中去，所以A(n,0)=0。,这样，A(n,k)满足定理5.5.3，所以,A(n,k)=S,2,(n,k)。,第二十六页，共30页。,说明：,(1)把n个不同的球放入k 个相同的盒子，而无一空盒等价于将n个元素的集合划分为k个不相交的非空子集，所以把n个不同的球放入k个相同盒子而无一空盒的放法共有,S,2,(n,k),种。,(2),S,2,(n,k)具有以下性质：,S,2,(n,n)=1,S,2,(n,k)=0 (nk,或 k=0n)；,S,2,(n,2)=2,n-1,-1;,S,2,(n,n-1)=C(n,2)。,第二十七页，共30页。,精品课件,！,第二十八页，共30页。,精品课件,！,第二十九页，共30页。,例2,设m,n均为正整数，mn。用组合分析的方法证明,证明,设有n只不同的球，m个盒子，它们的编号依次为1,2,m。把这n个球放入盒子中，允许有空盒且不限制放入盒子内的球的个数，共有m,n,种方法。,另一方面，n只不同的球放入特定的k个不同编号的盒子中去，没有一个空盒的方式数为k!,S,2,(n,k)，而从m个盒子中取k个盒子的方式数为C(m,k)，所以将n只不同的球放入m个不同的盒子中去且恰好有k个盒子非空的方式总数为C(m,k),k!,S,2,(n,k)，k取从1到m并把这些数相加即得到将n只不同的球放入m个不同盒子中且允许有空盒的方式数，所以,第三十页，共30页。,