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

《组合数学课件--第二章第三节关于线性常系数非齐次递推关系.ppt》由会员分享，可在线阅读，更多相关《组合数学课件--第二章第三节关于线性常系数非齐次递推关系.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 递推关系与母函数递推关系与母函数 2.1 2.1 递推关系递推关系 2.2 2.2 母函数母函数(生成函数生成函数)2.3 Fibonacci 2.3 Fibonacci数列数列 2.4 2.4 优选法与优选法与FibonacciFibonacci序列的应用序列的应用 2.5 2.5 母函数的性质母函数的性质 2.6 2.6 线性常系数齐次递推关系线性常系数齐次递推关系 2.7 2.7 关于常系数非齐次递推关系关于常系数非齐次递推关系 2.8 2.8 整数的拆分整数的拆分 2.9 2.9 ferrersferrers图像图像 2.10 2.10 拆分数估计拆分数估计 2.11 2.

2、11 指数型母函数指数型母函数 2.12 2.12 广义二项式定理广义二项式定理 2.13 2.13 应用举例应用举例 2.14 2.14 非线性递推关系举例非线性递推关系举例 2.15 2.15 递推关系解法的补充递推关系解法的补充12.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系如下面的递推关系：如下面的递推关系：称为称为k阶线性递推关系，其中若阶线性递推关系，其中若c1,c2,ck都是常数，则称为常系数线性都是常数，则称为常系数线性递推关系，若递推关系，若bn=0，则则称为是齐次的，否称为是齐次的，否则为非齐次的。则为非齐次的。22.10任意阶齐次递推关系任意阶齐次递推关

3、系设设r1,r2,rs是线性常系数齐次递推关系是线性常系数齐次递推关系的不同的特征根，并设的不同的特征根，并设hi是是ri的重根的重根数，数，i=1,2,3,s。则。则3Fibonacci递归算法递归算法: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)+142.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系如果序列如果序列xn和和yn满足满足非齐次递推关系，非齐次递推关系，对应的

4、齐次递推关系。对应的齐次递推关系。则序列则序列zn=xn-yn满足其对应的齐次递推关系。满足其对应的齐次递推关系。证明：略证明：略52.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系特解与一般解特解与一般解:例例2：某人有：某人有n元钱，一次可买元钱，一次可买1元的矿泉水，也元的矿泉水，也可以买可以买2元的（啤酒、方便面）的一种，直到所元的（啤酒、方便面）的一种，直到所有的钱花完为止有的钱花完为止(买东西的顺序不同，也算不同买东西的顺序不同，也算不同方案方案)，求，求n元钱正好花完的买法方案数。元钱正好花完的买法方案数。解：递推关系：解：递推关系：an=an-1+2an-2 a1

5、=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 关

6、于线性常系数非齐次递推关系关于线性常系数非齐次递推关系一阶、二阶线性常系数非齐次递推关系一阶、二阶线性常系数非齐次递推关系(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下面讨论若干特殊右端项的找特解的办法。下

7、面讨论若干特殊右端项的找特解的办法。(1)猜解法猜解法:设设an=kmn2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系an+ban-1=hmn,h为常数，为常数，m为已知整数。为已知整数。kmn+bkmn-1=hmn,km+bk=hm,m等于等于-b时无效时无效m是特征方程的根时无效是特征方程的根时无效10设设an=kmn2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系an+ban-1+can-2=hmn,h为常数，为常数，m为已知整数。为已知整数。kmn+bkmn-1+ckmn-2=hmn,km2+bkm+ck=hm2,分母为零时无效分母为零时无效m是特征方

8、程的根时无效是特征方程的根时无效11例例1 假定特解为：假定特解为：两边同除两边同除以以4n-2：2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系12特征方程特征方程2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系13例例2 假定特解为：假定特解为：c3n,代入递推关系。代入递推关系。无解！对于无解！对于这种情况怎这种情况怎么处理么处理?2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系14故导致二阶齐次递推关系，（故导致二阶齐次递推关系，（1）式的解必然）式的解必然是（是（2）式的解，但（）式的解，但（2）式解不一定是（）式解不一定是（1）式的解

9、。式的解。(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 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系15若若b=m,则解为则解为:（2）式的特征方程是：）式的特征方程是：x2-(b+m)x+bm=0,它有两个特征根它有两个特征根b和和m。若若bm,则解为则解为:2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系an=k1bn+k2

10、mn,an=(k1+k2n)mn,16分别讨论如下：分别讨论如下：(a)若若bm,则则an-ban-1=hmn 的解必可写成如下形的解必可写成如下形式式。an=k1bn+k2mn,定理定理1可知，非齐次递推关系的解可表示为齐次递可知，非齐次递推关系的解可表示为齐次递推关系的解加上特解推关系的解加上特解fn。比较可得：比较可得：fn=k2mn,k2是待定系数，是待定系数，代入递推关系代入递推关系an-ban-1=hmn，k2mn-bk2mn-1=hmnk2=hm/(m-b),因此因此fn=hm/(m-b)mn是特解是特解2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系17解解:2

11、.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系例例3:18(b)(b)若若b=m,b=m,即即a an n-ba-ban-1n-1=hbhbn n其中其中b b和和h 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代入递推关系。代入递推关系。knbn-k(n-1)bn=hbn,则则kn-k(n-1)=h,k=h,19

12、2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系例例4:20因此：因此：那么特解为：那么特解为：例例5：特征方程为：特征方程为：与所对应的二阶齐次递推关系的解比较与所对应的二阶齐次递推关系的解比较:2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系21将其代入非齐次递推关系，得将其代入非齐次递推关系，得可得可得k=3/5,因此特解为：因此特解为：2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系22例例6：2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系假设特解假设特解无解无解23例例6：2.7 关于线性常系数非齐次递推关系关于线性常

13、系数非齐次递推关系假设特解假设特解24定理定理2 对于如下非齐次递推关系。对于如下非齐次递推关系。的特征方程：的特征方程：的的m重根，则递推关系的特解有以下形式：重根，则递推关系的特解有以下形式：若若b(n)是是p次多项式，如果次多项式，如果r是线性齐次递推关系，是线性齐次递推关系，2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系 若若r不是不是K(x)=0的根，则特解是的根，则特解是m=0时的形式。时的形式。25例例7 an+3an-1-10an-2=(-7)nn 对应的特征方程对应的特征方程 有两个特征根：有两个特征根：2和和-5，-7不是特征根，故不是特征根，故m=0，按

14、定理，他的特解可写为：，按定理，他的特解可写为：代入递推关系式：代入递推关系式：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符号串，

15、不出现符号串，不出现00的符号串总数。的符号串总数。考虑一行考虑一行n列方格，用红蓝两种颜色染色，列方格，用红蓝两种颜色染色，不允许两红色方格相邻。不允许两红色方格相邻。2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系2966.求矩阵求矩阵设第设第n-1项的乘积为项的乘积为解：解：2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系30只要求出只要求出K即可即可2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系31bmbm时时代入初值得代入初值得k=1k=12.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系32 64.64.从从n n个文

16、字中取个文字中取k k个文字作允许重复个文字作允许重复的排列，但不允许一个文字连续出现的排列，但不允许一个文字连续出现3 3次，求次，求这样的排列的数目。这样的排列的数目。2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系 64.64.从从k k个文字中取个文字中取n n个文字作允许重复个文字作允许重复的排列，但不允许一个文字连续出现的排列，但不允许一个文字连续出现3 3次，求次，求这样的排列的数目。这样的排列的数目。33 首先，假设取首先，假设取n n个文字作允许重复的排列，个文字作允许重复的排列，不允许一个字连续出现不允许一个字连续出现3 3次的排列数为次的排列数为an,假设

17、取假设取n-1n-1个文字最后一位为个文字最后一位为x x，最后一，最后一位与位与x x不同的取法有不同的取法有(k-1)(k-1)种，种，(k-1)(k-1)an-1种。种。少算了最后一位也取少算了最后一位也取x x的情况，就是最的情况，就是最后两位都是后两位都是x x的情况，也就是最后两位与倒的情况，也就是最后两位与倒数第三位不同的情况，有数第三位不同的情况，有(k-1)(k-1)an-2种。种。2.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系342.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系35可求出可求出k1,k22.7 关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系36