离散数学101递推方程与生成函数课件.ppt

《离散数学101递推方程与生成函数课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章递推方程与生成函数1第10章递推方程与生成函数10.1递推方程及其应用10.2生成函数及其应用10.3指数生成函数及其应用10.4Catalan数与Stirling数210.1递推方程及其应用10.1.1递推方程的定义及实例10.1.2常系数线性齐次递推方程的求解10.1.3常系数线性非齐次递推方程的求解10.1.4递推方程的其他解法10.1.5递推方程与递归算法3递推方程的定义定义10.1设序列a0,a1,…,an,…,简记为{an}.一个把an与某些个ai(i

2、推方程和适当的初值就唯一确定了序列.例如，Fibonacci数列：1，1，2，3，5，8，…，记作{fn}.递推方程fn=fn1+fn2初值f0=1，f1=1阶乘计算数列：1，2，6，24，5！，…,记作{F(n)}递推方程F(n)=nF(n1)初值F(1)=14化简得an=6an1+8n1,可以解得an=(6n+8n)/2递推方程的实例——计数编码例1一个编码系统用八进制数字对信息编码，一个码是有效的当且仅当含有偶数个7,求n位长的有效码字有多少个？解设所求有效码字为an个.分类处理、分步处理得到递推方程和初值如下：a

3、n=7an1+8n1an1a1=75递推方程的实例——Hanoi塔例2从A柱将这些圆盘移到C柱上去.如果把一个圆盘从一个柱子移到另一个柱子称作一次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小圆盘的上面.问把所有的圆盘的从A移到C总计需要多少次移动？初值是T(1)=1可证明解是T(n)=2n1移动n个盘子的总次数为T(n).因此得到递推方程T(n)=2T(n1)+1.6递推方程的实例——算法分析例3哪种排序算法在最坏情况下复杂度比较低？插入排序，归并排序插入排序W(n)=W(n1)+n1W(1)=0解得W(

4、n)=O(n2).归并排序，不妨设n=2k.W(n)=2W(n/2)+n－1W(1)=0解得W(n)=O(nlogn)7常系数线性齐次递推方程求解其中a1,a2,…,ak为常数，ak0称为k阶常系数线性齐次递推方程b0,b1,…,bk1为k个初值实例：Fibonacci数列的递推方程定义10.2常系数线性齐次递推方程的标准形：8常系数线性齐次递推方程的公式解法特征方程、特征根递推方程的解与特征根的关系解的线性性质无重根下通解的结构求解实例有重根下通解的结构求解实例9特征方程与特征根定义10.3特征方程xka1xk1…

5、ak=0，特征方程的根称为递推方程的特征根实例：递推方程fn=fn1+fn2特征方程x2x1=0特征根10递推方程解与特征根的关系定理10.1设q是非零复数，则qn是递推方程的解当且仅当q是它的特征根.证qn是递推方程的解⇔qna1qn1a2qn2…akqnk=0⇔qnk(qka1qk1a2qk2…ak)=0⇔qka1qk1a2qk2…ak=0⇔q是它的特征根注：这里递推方程指常系数线性齐次递推方程11解的线性性质定理10.2设h1(n)和h2(n)是递推方程的解，c1,c2为任意常

6、数，则c1h1(n)+c2h2(n)也是这个递推方程的解.证将c1h1(n)+c2h2(n)代入该递推方程进行验证.推论若q1,q2,…,qk是递推方程的特征根，则c1q1n+c2q2n+…+ckqkn是该递推方程的解，其中c1,c2,…,ck是任意常数.注：这里的递推方程指的是常系数线性齐次递推方程12无重根下通解的结构定义10.4若对常系数线性齐次递推方程的每个解h(n)都存在一组常数c1,c2,…,ck使得h(n)=c1q1n+c2q2n+…+ckqkn成立，则称c1q1n+c2q2n+…+ckqkn为该递推方程

7、的通解定理10.3设q1,q2,…,qk是常系数线性齐次递推方程不等的特征根，则H(n)=c1q1n+c2q2n+…+ckqkn为该递推方程的通解.13定理的证明证：H(n)是解.设h(n)是递推方程的任意解，h(0),h(1),…,h(k1)由初值b0,b1,…,bk1唯一确定.代入方程得到方程组系数行列式当qiqj时，方程组有唯一解14求解实例例4Fibonacci数列：fn=fn1+fn2，特征根为通解为代入初值f0=1,f1=1,得解得解是15有重根下求解中的问题例5解特征方程x24x+4=0通解H(n)=c1

8、2n+c22n=c2n代入初值得：c无解.问题：两个解线性相关16有重根下的通解结构定理10.4设q1,q2,…,qt是递推方程的不相等的特征根，且qi的重数为ei，i=1,2,…,t，令那么通解17求解实例例6求解以下递推方程其中待定常数满足以下