组合数学课件a

第5章递推关系,本章主要介绍递推关系的建立及几种常见的求解方法：常系数齐次递推关系常系数非齐次递推关系迭代法归纳法,5.1递推关系定义,5.1递推关系的建立,定义5.1,设an为一序列，把该序列中an和它前面几个ai(0in)关联起来的方程称做一个递推关系（递归关系）。,如Dn=(n-1)(Dn-1+Dn-2)，(n3)和关系式an=3an-1，(n1)都是递推关系。如a0=d0,a1=d1,ak=dk，di为常数(i=0,1,k)，称为递推关系的初值。如D1=0,D2=1作为初值即可惟一的确定序列(D0,D1,Dn,)，a0=1作为初值即可惟一的确定序列(1,3,32,3n,)。将递推关系和初值结合起来称为带初值的递推关系。如,5.1递推关系建立例1-1,5.1递推关系的建立,例题,例1、在一个平面上有一个圆和n条直线，这些直线中的每一条在圆内都同其他的直线相交。如果没有三条直线相交于一点，试问这些直线将圆分成多少个不同区域？,5.1递推关系建立例1-2,5.1递推关系的建立,例题,解：要求解这个问题，首先必须建立递推关系，然后求解递推关系即可。设这n条直线将圆分成的区域数为an，如果有n-1条直线将圆分成an-1个区域，那么再加入第n条直线与在圆内的其他n-1条直线相交。显然，这条直线在圆内被分成n条线段，而每条线段又将第n条直线在圆内经过的区域分成两个区域。这样，加入第n条直线后，圆内就增加了n个区域。而对于n=0，显然有a0=1，于是对于每个整数n，可以建立如下带初值的递推关系（求解方法以后几节再介绍）这就是问题的解答。,5.1递推关系建立例2-1,5.1递推关系的建立,例题,例2、“Hanoi塔”问题：n个大小不一的圆盘依半径的大小，从下而上的套在柱子A上。如图所示。现要求将所有的圆盘从柱子A上全部移到柱子C上，每次只允许从一根柱子上转移一个圆盘到另一根柱子上，且在转移过程中不允许出现大圆盘放到小圆盘上。试问至少要转移多少次才能将柱子上的n个圆盘全部转移到柱子C上去？,5.1递推关系建立例2-2,5.1递推关系的建立,例题,解：用an表示从一根柱子上的n个圆盘全部转移到另一根柱子上的转移次数。显然，a1=1,a2=3。当n3时，要将柱子A上的n个圆盘转移到柱子C上，可以这样设想。先把柱子A上的n-1个圆盘转移到柱子B上，这需要转移an-1次；然后把柱子A上最后一个圆盘转移到柱子C上，显然这需要转移一次；最后再把柱子B上的n-1个圆盘转移到柱子C上，这也需要转移an-1次。经过这些步骤后，所有A上的n个圆盘就全部转移到柱子C上。由加法法则，这一共转移了2an-1+1次。于是可以建立如下带初值的递推关系这就是我们需要的结果。,5.1递推关系建立例3-1,5.1递推关系的建立,例题,例3、“Fibonacci兔子问题”也是组合数学中的著名问题之一。这个问题是指：从某一年某一月开始，把雌雄各一的一对兔子放入养殖场中，从第二个月雌兔每月产雌雄各一的一对新兔。每对新兔也是从第二个月起每月产一对兔子。试问第n个月后养殖场中共有多少对兔子？,5.1递推关系建立例3-2,5.1递推关系的建立,例题,解：设第n个月时养殖场中兔子的对数为Fn。并定义F0=1，显然有，F1=1。由于在第n个月时，除了有第n-1个月时养殖场中的全部兔子Fn-1外，还应该有Fn-2对新兔子，这是因为在第n-2个月就已经有的每对兔子，在第n个月里都应生一对新的兔子。因此可以建立如下带初值的递推关系求解上式可以得到我们所需的答案。注：利用该式我们可以推得(F0,F1,Fn,)=(1,1,2,3,5,8,13,21,34,55,)常称Fn为Fibonacci数，(F0,F1,Fn,)为Fibonacci数列。Fibonacci数列在数学中是一个奇特而又常见的序列，它在算法分析中起着重要的作用。具体性质以后讨论。,5.1递推关系建立例4,5.1递推关系的建立,例题,例4、在一个平面中，有n个圆两两相交，但任二个圆不相切，任三个圆无公共点，求这n个圆把平面分成多个区域？,解：设这n个圆将平面分成an个区域。如图。易见，a1=2,a2=4。现在假设前n-1个圆将平面分成了an-1个区域，当加入第n个圆时，由题设这个圆与前面的n-1个圆一定交于2(n-1)个点，这2(n-1)个点把第n个圆分成2(n-1)条弧，而每条弧正好将前面的n-1个圆分成的区域中的其经过的每个区域分成2个区域，故新加入的第n个圆使所成的区域数增加了2(n-1)。因此可以建立如下带初值的递推关系：求解这个递推关系可以得到问题的解答。,5.2常系数线性齐次定义,5.2常系数线性齐次递推关系,定义5.2,若an中相邻k+1项满足an=b1an-1+b2an-2+bkan-k，(nk)称之为an的k阶常系数线性齐次递推关系。其中bi(i=1,2,k)是常数，且bk0。a0=d0,a1=d1,ak-1=dk-1称为初始条件，其中di(i=0,2,k-1)是常数；C(x)=xk-b1xk-1-b2xk-2-bk称为上述递推关系的特征多项式；C(x)=0称为上述递推关系的特征方程；该方程的方程根称为上述递推关系的特征根。,5.2常系数线性齐次相异特征根定理1,5.2常系数线性齐次递推关系,5.2.1相异特征根的解法,定理5.1,若q0,an=qn是上述递推关系的解，当且仅当q是上述特征方程的解。,证明：若q0,an=qn是递推关系an=b1an-1+b2an-2+bkan-k的解qn=b1qn-1+b2qn-2+bkqn-k(nk)qk=b1qk-1+b2qk-2+bkq是特征方程xk-b1xk-1-b2xk-2-bk=0的根。证毕。,5.2常系数线性齐次相异特征根定理2,5.2常系数线性齐次递推关系,5.2.1相异特征根的解法,定理5.2,若q1,q2,qk,为上述递推关系的特征根（相异），c1,c2,ck为任意常数，则an=c1q1n+c2q2n+ckqkn为上述递推关系的解。,证明：由于qi(i=1,2,k)是特征方程xk-b1xk-1-b2xk-2-bk=0的根，由定理5.1有qin=b1qin-1+b2qin-2+bkqin-k，i=1,2,k将上式两边同乘以ci，然后从1到k求和有因此an=c1q1n+c2q2n+ckqkn是递推关系an=b1an-1+b2an-2+bkan-k的解。,5.2常系数线性齐次相异特征根定理3-1,5.2常系数线性齐次递推关系,定义5.3,若an为上述递推关系的任一解，且存在一组适当常数c1,c2,ck使得an具有表达式an=c1q1n+c2q2n+ckqkn，称该表达式为上述递推关系的通解。,5.2.1相异特征根的解法,定理5.3,若q1,q2,qn为上述递推关系的特征根（相异），则an=c1q1n+c2q2n+ckqkn为上述递推关系的通解，其中ci由初始条件确定。,5.2常系数线性齐次相异特征根定理3-2,5.2常系数线性齐次递推关系,5.2.1相异特征根的解法,证明：由定理5.2知，an=c1q1n+c2q2n+ckqkn是递推关系an=b1an-1+b2an-2+bkan-k的解。只需证明，若该式满足递推关系式an=b1an-1+b2an-2+bkan-k的任意初值条件式a0=d0,a1=d1,ak-1=dk-1所得到的关于c1,c2,ck的线性方程组有惟一解即可。由初值条件式a0=d0,a1=d1,ak-1=dk-1，我们得到因此，上述线性方程组关于c1,c2,ck有惟一的解。从而证明了an=c1q1n+c2q2n+ckqkn是递推关系的an=b1an-1+b2an-2+bkan-k的通解。,例1、求递归关系,5.2常系数线性齐次例1,5.2常系数线性齐次递推关系,5.2.1相异特征根的解法,例题,5.2常系数线性齐次例2,5.2常系数线性齐次递推关系,5.2.1相异特征根的解法,例题,例2、求递归关系,5.2常系数线性齐次相同特征根定理4,5.2常系数线性齐次递推关系,5.2.2相同特征根的解法,定理5.4,若q为上述递推关系的特征方程C(x)=0的一个m重特征根，则qn,nqn,nm-1qn为该递推关系的解。,证明：令P(x)=xk-b1xk-1-b2xk-2-bk，Pn(x)=xn-kP(x)=xn-b1xn-1-b2xn-2-bkxn-k。由于q是P(x)=0的m重根，故q也是Pn(x)=0的m重根，由高等代数的知识知，q也是Pn(x)=0的(m-1)重根，那么q也是xPn(x)=0的(m-1)重根，即q是方程nxn-b1(n-1)xn-1-b2(n-2)xn-2-bk(n-k)xn-k=0的(m-1)重根。类似地，q是方程n2xn-b1(n-1)2xn-1-b2(n-2)2xn-2-bk(n-k)2xn-k=0的(m-2)重根。一般地，对任意的i,im,q是方程nixn-b1(n-1)ixn-1-b2(n-2)ixn-2-bk(n-k)ixn-k=0的(m-i)重根。即有niqn-b1(n-1)iqn-1-b2(n-2)iqn-2-bk(n-k)iqn-k=0。分别令i=1,2,m-1，知nqn,n2qn,nm-1qn都是递推关系an=b1an-1+b2an-2+bkan-k的解，而qn是递推关系an=b1an-1+b2an-2+bkan-k的解在定理5.1中已经证明。故定理得证。,5.2常系数线性齐次相同特征根定理5-1,5.2常系数线性齐次递推关系,5.2.2相同特征根的解法,定理5.5,若q1,q2,qt分别为上述递推关系的特征方程C(x)=0相异的m1,m2,mt重特征根，为该递推关系的通解，其中cij由初始条件确定。,例3、求递归关系,5.2常系数线性齐次例3,5.2常系数线性齐次递推关系,5.2.2相同特征根的解法,例题,例4、求递归关系,5.2常系数线性齐次例4,5.2常系数线性齐次递推关系,5.2.2相同特征根的解法,例题,5.2常系数线性齐次例5,5.2常系数线性齐次递推关系,5.2.2相同特征根的解法,例题,例5、求递归关系,5.3常系数线性非齐次定义,5.3常系数线性非齐次递推关系,定义5.4,若an中相邻k+1项满足an=b1an-1+b2an-2+bkan-k+f(n)，(nk)称之为an的k阶常系数线性非齐次递推关系。其中bi(i=1,2,k)是常数，且bk0，f(n)0。,若f(n)=0，称=b1an-1+b2an-2+bkan-k为上述递推关系导出的常系数线性齐次递推关系。,5.3常系数线性非齐次定理6-3,5.3常系数线性非齐次递推关系,定理5.6,若为an=b1an-1+b2an-2+bkan-k+f(n)的一个特解，为=b1an-1+b2an-2+bkan-k的一个通解，则an=+为原非齐次递推关系的通解。,注：定理5.6指出，若要求一个常系数线性非齐次递推关系式的通解，必须先求出这个递推关系所导出的常系数线性齐次递推关系的通解，然后再求这个递推关系式的一个特解，将其相加即可。然而，求一个非齐次线性递推关系的特解，通常没有系统的方法，但当函数f(n)是某些特殊形式时，才有一些规范的求法。,5.3常系数线性非齐次特殊形式,5.3常系数线性非齐次递推关系,5.3常系数线性非齐次例1,5.3常系数线性非齐次递推关系,例题,例1、求递归关系（Hanoi塔）,5.3常系数线性非齐次例2,5.3常系数线性非齐次递推关系,例题,例2、求递归关系,5.3常系数线性非齐次例3,5.3常系数线性非齐次递推关系,例题,例3、求递归关系,5.3常系数线性非齐次例4,5.3常系数线性非齐次递推关系,例题,例4、求递归关系an+2an-1+an-2=2n的通解。,5.3常系数线性非齐次例5,5.3常系数线性非齐次递推关系,例题,例5、求递归关系an-4an-1+4an-2=2n的通解。,5.3常系数线性非齐次例6,5.3常系数线性非齐次递推关系,例题,例6、求Sn=1+2+3+n。,5.3常系数线性非齐次例7,5.3常系数线性非齐次递推关系,例题,例7、求Sn=12+22+32+n2。,5.3常系数线性非齐次例8,5.3常系数线性非齐次递推关系,例题,例8、求Sn=13+23+33+n3。,5.4迭代法例1,5.4迭代法与归纳法,针对上述k阶常系数线性（非）齐次递推关系求解方法，当k较大时，面临着解高次方程和高阶线性方程组的困难；而且对一般的非齐次递推关系无系统的方法。,例题,例1、求递归关系,解：这是常系数线性非齐次递推关系，可以用上节中的方法求解。这里用迭代法求解。反复应用递推关系式进行迭代有,5.4迭代法例2,5.4迭代法与归纳法,例题,例2、求递归关系,解：这是一个非常系数线性非齐次递推关系。下面用迭代法求解。反复应用递推关系式进行迭代有,5.4迭代法例3,5.4迭代法与归纳法,例题,例3、求递归关系,解：这是一个非线性递推关系。反复应用递推关系式进行迭代有注：此例中的递推关系式还可以作一个变换变成一个常系数线性非齐次递推关系然后利用上节的方法求解。,5.4归纳法例4,5.4迭代法与归纳法,例题,例4、求递归关系,解：这是5.1中例4所导出的递推关系。在5.3中已经求出该递推关系的解。下面我们用归纳法求解。先用初值条件a1=2求出前几项，并观察其规律。由上面所得到的值，我们可以猜想解的一般的公式为为了证实上述猜想确实是递推关系的解，我们用归纳法证之。由上面计算前几项的值，显然，当n=1,2,3,4,5时，结论成立。设n=k时，结论成立，即有则当n=k+1时，有可见，当n=k+1时，结论也是成立的。,5.4归纳法例5,5.4迭代法与归纳法,例题,例5、求递归关系,解：与例4一样，先求前几项的值于是，我们可以猜想解的一般的公式为然后用归纳法证明以上猜想是正确的。n=0,1,2,3,结论显然成立。设n=k时，结论成立，即有则当n=k+1时，有可见，当n=k+1时，结论也是成立的。,五、差分表*,1.数列的差分表,2.实函数的差分表,3.差分表由第一行确定,4.差分表由第一列(左边沿)确定,5.多项式函数的广义组合数表示,6.有关数列的求和,1.数列的差分表,考虑数列令称为1阶差分。,1.数列的差分表,的差分表,2.实函数的差分表,设f(x)为实函数,对x取值0,1,2,得到一个数列f(n),这数列的k阶差分就称为f(x)