《组合数学课件--关于线性常系数非齐次递推关系》由会员分享，可在线阅读，更多相关《组合数学课件--关于线性常系数非齐次递推关系（36页珍藏版）》请在金锄头文库上搜索。
1、第2章 递推关系与母函数2.1 递推关系2.2 母函数(生成函数)2.3 Fibonacci数列2.4 优选法与Fibonacci序列的应用2.5 母函数的性质2.6 线性常系数齐次递推关系2.7 关于常系数非齐次递推关系2.8 整数的拆分2.9 ferrers图像2.10 拆分数估计2.11 指数型母函数2.12 广义二项式定理2.13 应用举例2.14 非线性递推关系举例2.15 递推关系解法的补充12.7 关于线性常系数非齐次递推关系如下面的递推关系：称为k阶线性递推关系，其中若 c1,c2,ck都是常数，则称为常系数线性递 推关系，若bn=0，则称为是齐次的，否则 为非齐次的。22.1
2、0任意阶齐次递推关系设r1,r2,rs是线性常系数齐次递推关系的不同的特征根，并设hi是ri的重根 数，i=1,2,3,s。则3Fibonacci递归算法:int fibonacci(int n) if (n=1|n=2)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2); 2.1 递推关系时间复杂性：f(n)=f(n-1)+f(n-2)+142.7 关于线性常系数非齐次递推关系如果序列xn和yn满足非齐次递推关系，对应的齐次递推关系。则序列zn=xn-yn满足其对应的齐次递推关系。证明：略52.7 关于线性常系数非齐次递推关系特解与一般解:
3、例2：某人有n元钱，一次可买1元的矿泉水，也 可以买2元的（啤酒、方便面）的一种，直到所 有的钱花完为止(买东西的顺序不同，也算不同 方案)，求n元钱正好花完的买法方案数。解：递推关系：an=an-1+2an-2 a1=1,a2=3特征方程x2-x-2=0的根r1=-1，r2=26定理1 若fn 是线性常系数非齐次递推关系的特 解，则这个线性常系数非齐次递推关系的解有如下 形式：an=fn+对应的线性常系数齐次递推关系的解。证明：fn是特解，设sn 是一个解令tn=sn-fn 2.7 关于线性常系数非齐次递推关系则序列ti是线性常系数齐次递推关系的解sn=tn+fn 证毕72.7 关于线性常系
4、数非齐次递推关系一阶、二阶线性常系数非齐次递推关系(1)右端项为常数han+ban-1=c(n)(2)右端项为hmn,h为常数，m为已知整数。an+ban-1+can-2=c(n)8下面讨论若干特殊右端项的找特解的办法。(1) 猜解法:猜an解的可能情况?2.7 关于线性常系数非齐次递推关系an+ban-1= hmn,h为常数，m为已知整数。9下面讨论若干特殊右端项的找特解的办法。(1) 猜解法:设an=kmn2.7 关于线性常系数非齐次递推关系an+ban-1= hmn,h为常数，m为已知整数。kmn+bkmn-1= hmn,km+bk= hm,m等于-b时无效m是特征方程的根时无效10设a
5、n=kmn2.7 关于线性常系数非齐次递推关系an+ban-1+can-2 =hmn,h为常数，m为已知整数。kmn+bkmn-1+ckmn-2= hmn,km2+bkm+ck= hm2,分母为零时无效m是特征方程的根时无效11例1 假定特解为： 两边同除 以4n-2： 2.7 关于线性常系数非齐次递推关系12特征方程2.7 关于线性常系数非齐次递推关系13例2 假定特解为：c3n ,代入递推关系。无解！对于 这种情况怎 么处理?2.7 关于线性常系数非齐次递推关系14故导致二阶齐次递推关系，（1）式的解必然 是（2）式的解，但（2）式解不一定是（1） 式的解。(2)划为高阶齐次递推关系，通过
6、比较推测递 推关系的特解 an-ban-1=hmn, an-1-ban-2=hmn-1,an-ban-1=hmn, (1) man-1-mban-2=hmn,an-(b+m)an-1 +bman-2 =0 （2）2.7 关于线性常系数非齐次递推关系15若b=m,则解为:（2）式的特征方程是：x2- (b+m)x+bm=0, 它有两个特征根b和m。 若bm,则解为:2.7 关于线性常系数非齐次递推关系an=k1bn+k2mn, an=(k1+k2n)mn,16分别讨论如下：(a)若bm,则an-ban-1=hmn 的解必可写成如下形 式。an=k1bn+k2mn,定理1可知，非齐次递推关系的解可
7、表示为齐次递 推关系的解加上特解fn。比较可得：fn=k2mn,k2是待定系数，代入递推关系an-ban-1=hmn ， k2mn-bk2mn-1= hmnk2=hm/(m-b),因此fn=hm/(m-b)mn是特解2.7 关于线性常系数非齐次递推关系17解:2.7 关于线性常系数非齐次递推关系例3:18(b)若b=m,即an-ban-1=hbn 其中b和h都是已知常数。但当b=m时，对应的二阶齐次递 推关系an-(b+m)an-1 +bman-2 =0 的解为： an=(l+kn)bn2.7 关于线性常系数非齐次递推关系所以fn=knbn 令an=knbn， an-1=k(n-1)bn-1代
8、入递推关系。 knbn- k(n-1)bn=hbn,则kn-k(n-1)=h,k=h,192.7 关于线性常系数非齐次递推关系例4:20因此：那么特解为：例5：特征方程为：与所对应的二阶齐次递推关系的解比较:2.7 关于线性常系数非齐次递推关系21将其代入非齐次递推关系，得可得k=3/5,因此特解为：2.7 关于线性常系数非齐次递推关系22例6：2.7 关于线性常系数非齐次递推关系假设特解无解23例6：2.7 关于线性常系数非齐次递推关系假设特解24定理2 对于如下非齐次递推关系。的特征方程：的m重根，则递推关系的特解有以下形式：若b(n) 是p次多项式，如果r是线性齐次递推关系，2.7 关于
9、线性常系数非齐次递推关系若r不是K(x)=0的根，则特解是m=0时的形式。25例7 an+3an-1-10an-2=(-7)nn 对应的特征方程有两个特征根：2和-5，-7不是特征根，故 m=0，按定理，他的特解可写为：代入递推关系式：2.7 关于线性常系数非齐次递推关系26特解 : 因此一般解为：2.7 关于线性常系数非齐次递推关系27例2.43 an-3an-1+2an-2=6n2 ，a0=6,a1=7 右端项6n2可以看作是(1)n 6n2,有两个特征根：1和2。m=1,p=2,代入递推关系求出系数：2.7 关于线性常系数非齐次递推关系*28例题1: 求长度为n的0,1符号串，不出现 0
10、0的符号串总数。考虑一行n列方格，用红蓝两种颜色染色， 不允许两红色方格相邻。2.7 关于线性常系数非齐次递推关系2966. 求矩阵设第n-1项的乘积为解：2.7 关于线性常系数非齐次递推关系30只要求出K即可2.7 关于线性常系数非齐次递推关系31bm时代入初值得k=12.7 关于线性常系数非齐次递推关系3264. 从n个文字中取k个文字作允许重复 的排列，但不允许一个文字连续出现3次，求 这样的排列的数目。2.7 关于线性常系数非齐次递推关系64. 从k个文字中取n个文字作允许重复 的排列，但不允许一个文字连续出现3次，求 这样的排列的数目。33首先，假设取n个文字作允许重复的排列 ，不允许一个字连续出现3次的排列数为an,假设取n-1个文字最后一位为x，最后一 位与x不同的取法有(k-1)种，(k-1)an-1种。少算了最后一位也取x的情况，就是最 后两位都是x的情况，也就是最后两位与倒 数第三位不同的情况，有(k-1)an-2种。2.7 关于线性常系数非齐次递推关系342.7 关于线性常系数非齐次递推关系35可求出k1,k22.7 关于线性常系数非齐次递推关系36
