第五章递归关系及解法.

第五章递推关系及其解法§5.1递归关系的建立----在计算机科学特别是算法分析中有广泛的应用定义5.1.1设{a0,a1,a2,…,an,…}为一序列,把该序列中an与它前面的几个ai关(0≤i≤n-1)联起来的方程称为一个递归关系.例1(“Hanoi塔”问题)：这是一个组合数学中的著名问题。n个大小不一的圆盘依其半径大小，从下而上套在A柱上，如下图示。现要求将所有的圆盘从A柱上全部转移到C柱上,每次只允许从一个柱子上转移一个盘子到另一柱子上，且在转移过程中不允许出现大盘放在小盘上方。试问要转移多少次才能将柱A上的n个盘移到C柱上。ABC例2“Fibonacci兔子问题”：从某年某月(设为第0月)开始,把雌雄各一的一对小兔放入养殖场,假定两个月后长成成年兔,并同时(即第二个月)开始每月产雌雄各一的一对小兔,新增的小兔也按此规律繁殖,问第n个月末养殖场共有多少对兔子?第n月的兔子包括两部分:上月留下的和当月新生的,而新生的小兔数即为前月末的兔子数,所以Fn=Fn-1+Fn-2Fibonacci序列的性质:§5.2常系数线性齐次递归关系的解法定义5.2.1序列{a0,a1,a2,…,an,…}中相邻的k+1项之间的关系为则称之为序列的k阶常系数线性齐次递归关系,其中系数bi为常数,i=1,2,…,k,且bk≠0。定义5.2.2与(5.2.1)相联系的方程称之为递归关系(5.2.1)的特征方程，其根称为递归关系式的特征根。)1.2.5()(,02211knabababaknknnn)2.2.5()(,02211knbxbxbxkkkk特征方程的根与递归关系的解之间的关系：1.特征根无重根定理5.2.1若q≠0,an=qn为递归关系(5.2.1)的解当且仅当q为特征方程(5.2.2)的根。定义5.2.3称式为递归关系(5.2.1)的初值条件。)1.2.5(,,,,111100kkhahaha定理5.2.2若q1,q2,…,qk为递归关系式(5.2.1)的特征根，c1,c2,…,ck为任意常数，则为递归关系(5.2.1)的解。定义5.2.4若对递归关系(5.2.1)的任意一个解an，都存在一组常数c1,c2,…,ck使得则称该式为递归关系式(5.2.1)的通解。定理5.2.3若q1,q2,…,qk为递归关系式(5.2.1)的k个互不相同的特征根，则式(5.2.4)为(5.2.1)的通解。,2211nkknnnqcqcqca)4.2.5(,2211nkknnnqcqcqca例1求Fibonacci序列的通项。例2求解递归关系.0,2,1)3(,22210321aaanaaaannnn注：若特征根有复根，复根成对出现，故设则通解可表示为其中,,21ixix,sincos)()(212211ncncxAxAannnnn.)(i,,arctan,21221122AAcAAc例3求解递归关系.0,1)2(,2121aanaaannn2.特征根有重根定理5.2.4若递归关系(5.2.1)的特征方程(5.2.2)有一个m重根q，则qn,nqn,…,nm-1qn均为(5.2.1)的解。定理5.2.5设q1,q2,…,qt分别为特征方程(5.2.2)的相异的m1,m2,…,mt重根,且则递归关系(5.2.1)的通解为,1kmtiitimjnijijniqnca111.例4求解递归关系例5求解递归关系.3,2)3(,22121aanaaannn.2,1,0,1)4(,25332104321aaaanaaaaannnnn§5.3常系数线性非齐次递归关系的解法定义5.3.1序列{a0,a1,a2,…,an,…}中相邻的k+1项之间的关系为则称之为序列的k阶常系数线性非齐次递归关系,其中系数bi为常数,i=1,2,…,k,bk≠0,f(n)≠0,n≥k。定义5.3.2在式(5.3.1)中,若f(n)=0,则称为由式(5.3.1)导出的常系数线性齐次递归关系。)1.3.5()(),(2211knnfabababaknknnn)2.3.5()(,02211knabababaknknnn定理5.3.1若为(5.3.1)的一个特解,而()是由(5.3.1)导出的线性齐次递归关系(5.3.2)的通解,则为(5.3.1)的通解。注：由定理5.3.1知,要求(5.3.1)的通解,只要求它的一个特解及导出的齐次递归关系的通解即可。对非齐线性递归关系的特解,针对f(n)的特殊形式有以下情形:nakiniinqca1*timjnijijniqnca111**nnnaaa1.f(n)是n的t次多项式⑴1不是齐次递归关系(5.3.2)的特征根这时,(5.3.1)的特解形式为其中为待定常数。例1求解“Hanoi塔”问题的递归关系例2求解递归关系,1110ttttnAnAnAnAattAAAA,,,,110.1)2(1211anaann.3)1(3201annaann⑵1是齐次递归关系(5.3.2)的m重特征根(m≥1)这时,(5.3.1)的特解形式为其中为待定常数。例3求解递归关系,)(1110mttttnnAnAnAnAattAAAA,,,,110.2)2()1(211annaann2f(n)是βn的形式⑴β不是导出的齐次线性递归关系的特征根这时,(5.3.1)的特解形式为其中A为待定常数。例4求解递归关系.nnAa.1,0)2(31071021aanaaannnn⑵β是导出的齐次线性递归关系的m重特征根(m≥1)这时,(5.3.1)的特解形式为其中A为待定常数。例5求解递归关系.nmnnAa.24421的通解nnnnaaa⑶f(n)=βng(n),其中g(n)为n的t次多项式,β是导出的齐次线性递归关系的m重特征根(m≥0)这时,(5.3.1)的特解形式为其中为待定常数。例6求解递归关系.)(1110nmttttnnAnAnAnAattAAAA,,,,110.1,0)2()5(21031021aannaaannnn§5.4递归关系的其他解法前面方法当k较大时，面临求解高阶方程及k个未知数k个方程的方程组,求解困难问题。本节再介绍一些方法。一、迭代法例1求解递归关系二、归纳法例2求解递归关系.1)1(01annaann.2)2()1(211annaann三、母函数法主要思想:⑴用f(x)表示序列{a0,a1,a2,…,an,…}的普通母函数,即⑵利用递归关系an的表达式与(5.4.1)间的关系将(5.4.1)化为关于f(x)的方程，即有g(f(x))=0;⑶解出f(x)；⑷将f(x)的表达式展开成幂级数的形式，即得an的初等表达式.)1.4.5(,)(02210nnnnnxaxaxaxaaxf例3求解递归关系例4求解递归关系.1,1)2(,1021FFnFFFnnn.1,0)2(,2)2()1(1021aanaanannnn四、代换法将序列{a0,a1,a2,…,an,…}的递归关系转换为关于新序列{b0,b1,b2,…,bn,…}的递归序列。例5求解递归关系五、将常系数线性非齐次递归关系转化为常系数齐次递归关系例6求an-2an-1=3的通解。例7求.2)1(,2)1(11anannannn.?1nkk§5.5Stirling数一、第1类Stirling数令，若则称S1(n,k)为第1类Stirling数，即为多项式[x]n中xk的系数。约定：当nk时，S1(n,k)=0。定理5.5.1第1类Stirling数S1(n,k)满足)1()2)(1(nxxxxxn,),(01nkknxknSx.0,0)0,(,0)0,0()0,0(,),()1,(),1(11111nnSSknknnSknSknS由定理5.4.1得第1类Stirling数S1(n,k)的数值：nk1234567112-1132-314-611-61524-5035-1016-120274-22585-1517720-17641624-735175-211二、第2类Stirling数若则称S2(n,k)为第二类Stirling数。显然，当nk时，S2(n,k)=0。定理5.5.2第2类Stirling数S2(n,k)满足,),(02nkknxknSx.0,0)0,(,1)0,0()0,0(,),()1,(),1(22222nnSSknknkSknSknSS2(n,k)的组合意义涉及集合的划分。定理5..5.3S2(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数。证明设A(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数，只要证明A(n,k)满足定理5.5.2即可。给定一个n+1个元素的集合{a1,a2,…,an+1},将它划分为k个不相交的非空子集,分以下两种情况:(1){an+1}为k个子集中的一个子集，则将{a1,a2,…,an}划分为k-1个子集的方式数为A(n,k-1)。(2){an+1}不为k个子集中的一个子集，则an+1必为某个子集中的元素。这时，先将{a1,a2,…,an}划分为k个子集共有A(n,k)种方式，然后将an+1加到k个子集中的某一个，共有k种方式，从而得总的划分数为kA(n,k)。由加法原理，{a1,a2,…,an+1}划分为k个子集的方式数为A(n,k-1)+kA(n,k)。所以有A(n+1,k)=A(n,k-1)+kA(n,k)。又将0个元素的集合划分为0个不相交子集的方式数为1，所以A(0,0)=1。另一方面，不可能将n个元素的集合中的元素不放进任何一个集合中去，所以A(n,0)=0。这样，A(n,k)满足定理5.5.3，所以A(n,k)=S2(n,k)。说明：(1)把n个不同的球放入k个相同的盒子而无一空盒，等价于将n个元素的集合划分为k个不相交的非空子集，所以把n个不同的球放入k个相同盒子而无一空盒的放法共有S2(n,k)种。(2)S2(n,k)具有以下性质：①S2(n,n)=1,S2(n,k)=0(nk,或k=0n)；②S2(n,2)=2n-1-1;③S2(n,n-1)=C(n,2)。例2设m,n均为正整数，m≤n。用组合分析的方法证明证明设有n只不同的球，m个盒子，它们的编号依次为1,2,…,m。把这n个球放入盒子中，允许有空盒且不限制放入盒子内的球的个数，共有mn种方法。另一方面，n只不同的球放入特定的k个不同编号的盒子中去，没有一个空盒的方式数为k!S2(n,k)，而从m个盒子中取k个盒子的方式数为C(m,k)，所以将n只不同的球放入m个不同的盒子中去且恰好有k个盒子非空的方式总数为C(m,k)k!S2(n,k)，k取从1到m并把这些数相加即得到将n只不同的球放入m个不同盒子中且允许有空盒的方式数，所以!.),(21kknSkmmkn)0(.!),(!),(2121kmmkmkknSkmkknSkmnkmk时