组合数学课件--第二章第三节关于线性常系数非齐次递推关系.ppt

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 递推关系解法的补充,2,2.7 关于线性常系数非齐次递推关系,如下面的递推关系：,称为k阶线性递推关系，其中若c1,c2,ck都是常数，则称为常系数线性递推关系，若bn=0，则称为是齐次的，否则为非齐次的。,3,2.10任意阶齐次递推关系,设r1,r2,rs是线性常系数齐次递推关系,的不同的特征根，并设hi是ri的重根数，i=1,2,3,s。则,4,Fibonacci递归算法:,int fibonacci(int n) if (n=1|n=2) return(1); else return(fibonacci(n-1)+fibonacci(n-2); ,2.1 递推关系,时间复杂性：f(n)=f(n-1)+f(n-2)+1,5,2.7 关于线性常系数非齐次递推关系,如果序列xn和yn满足非齐次递推关系，,对应的齐次递推关系。,则序列zn=xn-yn满足其对应的齐次递推关系。,证明：略,6,2.7 关于线性常系数非齐次递推关系,特解与一般解:,例2：某人有n元钱，一次可买1元的矿泉水，也可以买2元的（啤酒、方便面）的一种，直到所有的钱花完为止(买东西的顺序不同，也算不同方案)，求n元钱正好花完的买法方案数。,解：递推关系：an=an-1+2an-2 a1=1,a2=3,特征方程x2-x-2=0的根r1=-1，r2=2,7,定理1 若fn 是线性常系数非齐次递推关系的特解，则这个线性常系数非齐次递推关系的解有如下形式： an=fn+对应的线性常系数齐次递推关系的解。,证明：fn是特解，设sn 是一个解,令tn=sn-fn,2.7 关于线性常系数非齐次递推关系,则序列ti是线性常系数齐次递推关系的解,sn=tn+fn 证毕,8,2.7 关于线性常系数非齐次递推关系,一阶、二阶线性常系数非齐次递推关系,(1)右端项为常数h,an+ban-1=c(n),(2)右端项为hmn,h为常数，m为已知整数。,an+ban-1+can-2=c(n),9,下面讨论若干特殊右端项的找特解的办法。,(1) 猜解法:,猜an解的可能情况?,2.7 关于线性常系数非齐次递推关系,an+ban-1= hmn,h为常数，m为已知整数。,10,下面讨论若干特殊右端项的找特解的办法。,(1) 猜解法:,设an=kmn,2.7 关于线性常系数非齐次递推关系,an+ban-1= hmn,h为常数，m为已知整数。,kmn+bkmn-1= hmn,km+bk= hm,m等于-b时无效,m是特征方程的根时无效,11,设an=kmn,2.7 关于线性常系数非齐次递推关系,an+ban-1+can-2 =hmn,h为常数，m为已知整数。,kmn+bkmn-1+ckmn-2= hmn,km2+bkm+ck= hm2,分母为零时无效,m是特征方程的根时无效,12,例1,假定特解为：,两边同除以4n-2：,2.7 关于线性常系数非齐次递推关系,13,特征方程,2.7 关于线性常系数非齐次递推关系,14,例2,假定特解为：c3n ,代入递推关系。,无解！对于这种情况怎么处理?,2.7 关于线性常系数非齐次递推关系,15,故导致二阶齐次递推关系，（1）式的解必然是（2）式的解，但（2）式解不一定是（1）式的解。,(2)划为高阶齐次递推关系，通过比较推测递推关系的特解,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 关于线性常系数非齐次递推关系,16,若b=m,则解为:,（2）式的特征方程是：x2-(b+m)x+bm=0, 它有两个特征根b和m。,若bm,则解为:,2.7 关于线性常系数非齐次递推关系,an=k1bn+k2mn,an=(k1+k2n)mn,17,分别讨论如下：,(a)若bm,则an-ban-1=hmn 的解必可写成如下形式。an=k1bn+k2mn,定理1可知，非齐次递推关系的解可表示为齐次递推关系的解加上特解fn。,比较可得：fn=k2mn,k2是待定系数，,代入递推关系an-ban-1=hmn ， k2mn-bk2mn-1= hmn,k2=hm/(m-b),因此fn=hm/(m-b)mn是特解,2.7 关于线性常系数非齐次递推关系,18,解:,2.7 关于线性常系数非齐次递推关系,例3:,19,(b)若b=m,即an-ban-1=hbn 其中b和h都是已知常数。,但当b=m时，对应的二阶齐次递推关系an-(b+m)an-1 +bman-2 =0 的解为： an=(l+kn)bn,2.7 关于线性常系数非齐次递推关系,所以fn=knbn 令an=knbn， an-1=k(n-1)bn-1代入递推关系。 knbn- k(n-1)bn=hbn,则kn-k(n-1)=h,k=h,20,2.7 关于线性常系数非齐次递推关系,例4:,21,因此：,那么特解为：,例5：,特征方程为：,与所对应的二阶齐次递推关系的解比较:,2.7 关于线性常系数非齐次递推关系,22,将其代入非齐次递推关系，得,可得k=3/5,因此特解为：,2.7 关于线性常系数非齐次递推关系,23,例6：,2.7 关于线性常系数非齐次递推关系,假设特解,无解,24,例6：,2.7 关于线性常系数非齐次递推关系,假设特解,25,定理2 对于如下非齐次递推关系。,的特征方程：,的m重根，则递推关系的特解有以下形式：,若b(n) 是p次多项式，如果r是线性齐次递推关系，,2.7 关于线性常系数非齐次递推关系,若r不是K(x)=0的根，则特解是m=0时的形式。,26,例7 an+3an-1-10an-2=(-7)nn,对应的特征方程,有两个特征根：2和-5，-7不是特征根，故m=0，按定理，他的特解可写为：,代入递推关系式：,2.7 关于线性常系数非齐次递推关系,27,特解:,因此一般解为：,2.7 关于线性常系数非齐次递推关系,28,例2.43 an-3an-1+2an-2=6n2 ，a0=6,a1=7,右端项6n2可以看作是(1)n 6n2,有两个特征根：1和2。,m=1,p=2,代入递推关系求出系数：,2.7 关于线性常系数非齐次递推关系,*,29,例题1: 求长度为n的0,1符号串，不出现00的符号串总数。,考虑一行n列方格，用红蓝两种颜色染色，不允许两红色方格相邻。,2.7 关于线性常系数非齐次递推关系,30,66. 求矩阵,设第n-1项的乘积为,解：,2.7 关于线性常系数非齐次递推关系,31,只要求出K即可,2.7 关于线性常系数非齐次递推关系,32,bm时,代入初值得k=1,2.7 关于线性常系数非齐次递推关系,33,64. 从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。,2.7 关于线性常系数非齐次递推关系,64. 从k个文字中取n个文字作允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。,34,首先，假设取n个文字作允许重复的排列，不允许一个字连续出现3次的排列数为an,假设取n-1个文字最后