离散数学-.递推方程与生成函数

离散数学--.递推方程与生成函数1第一页，共四十一页，2022年，8月28日第10章递推方程与生成函数10.1递推方程及其应用10.2生成函数及其应用10.3指数生成函数及其应用10.4Catalan数与Stirling数2第二页，共四十一页，2022年，8月28日10.1递推方程及其应用10.1.1递推方程的定义及实例10.1.2常系数线性齐次递推方程的求解10.1.3常系数线性非齐次递推方程的求解10.1.4递推方程的其他解法10.1.5递推方程与递归算法3第三页，共四十一页，2022年，8月28日递推方程的定义定义10.1设序列a0,a1,…,an,…,简记为{an}.一个把an与某些个ai(i<n)联系起来的等式叫做关于序列{an}的递推方程.当给定递推方程和适当的初值就唯一确定了序列.

例如，

Fibonacci数列：1，1，2，3，5，8，…，记作{fn}.

递推方程fn

=fn1+fn2

初值

f0=1，f1=1

阶乘计算数列：1，2，6，24，5！，…,记作{F(n)}

递推方程F(n)=nF(n1)

初值F(1)=14第四页，共四十一页，2022年，8月28日化简得

an=6an1+8n1,

可以解得

an=(6n+8n)/2递推方程的实例——计数编码例1

一个编码系统用八进制数字对信息编码，一个码是有效的当且仅当含有偶数个7,求n位长的有效码字有多少个？解设所求有效码字为an个.分类处理、分步处理得到递推方程和初值如下：

an=7an1+8n1

an1

a1=7

5第五页，共四十一页，2022年，8月28日递推方程的实例——Hanoi塔例2

从A柱将这些圆盘移到C柱上去.如果把一个圆盘从一个柱子移到另一个柱子称作一次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小圆盘的上面.问把所有的圆盘的从A移到C总计需要多少次移动？初值是

T(1)=1可证明解是

T(n)=2n1移动n个盘子的总次数为T(n).因此得到递推方程

T(n)=2T(n1)+1.6第六页，共四十一页，2022年，8月28日递推方程的实例——算法分析例3

哪种排序算法在最坏情况下复杂度比较低？

插入排序，归并排序

插入排序

W(n)=W(n

1)+n1

W(1)=0解得W(n)=O(n2).归并排序，不妨设n=2k.

W(n)=2W(n/2)+n－1

W(1)=0解得W(n)=O(nlogn)7第七页，共四十一页，2022年，8月28日常系数线性齐次递推方程求解其中a1,a2,…,ak为常数，ak

0称为

k

阶常系数线性齐次递推方程

b0,b1,…,bk1为

k个初值实例：Fibonacci数列的递推方程定义10.2

常系数线性齐次递推方程的标准形：8第八页，共四十一页，2022年，8月28日常系数线性齐次递推方程

的公式解法特征方程、特征根递推方程的解与特征根的关系解的线性性质无重根下通解的结构求解实例有重根下通解的结构求解实例9第九页，共四十一页，2022年，8月28日特征方程与特征根

定义10.3特征方程

xk

a1xk1

…

ak

=0，特征方程的根称为递推方程的特征根

实例：递推方程fn=fn1+fn2

特征方程x2x1=0特征根10第十页，共四十一页，2022年，8月28日递推方程解与特征根的关系定理10.1

设q是非零复数，则qn

是递推方程的解当且仅当q是它的特征根.证

qn是递推方程的解⇔qna1qn1a2qn2

…akqnk

=0

⇔

qnk

(qk

a1qk1

a2qk2

…ak

)=0

⇔

qk

a1qk1

a2qk2

…ak=0⇔q是它的特征根注：这里递推方程指常系数线性齐次递推方程11第十一页，共四十一页，2022年，8月28日解的线性性质定理10.2

设h1(n)和h2(n)是递推方程的解，c1,c2为任意常数，则c1h1(n)+c2h2(n)也是这个递推方程的解.证将c1h1(n)+c2h2(n)代入该递推方程进行验证.推论若q1,q2,…,qk

是递推方程的特征根，则

c1q1n+c2q2n+…+ckqkn是该递推方程的解，其中c1,c2,…,ck是任意常数.注：这里的递推方程指的是常系数线性齐次递推方程12第十二页，共四十一页，2022年，8月28日无重根下通解的结构定义10.4

若对常系数线性齐次递推方程的每个解h(n)都存在一组常数c1,c2,…,ck使得

h(n)=c1q1n+c2q2n+…+ckqkn

成立，则称c1q1n+c2q2n+…+ckqkn为该递推方程的通解

定理10.3

设q1,q2,…,qk是常系数线性齐次递推方程不等的特征根，则

H(n)=c1q1n+c2q2n+…+ckqkn为该递推方程的通解.13第十三页，共四十一页，2022年，8月28日定理的证明证：H(n)是解.设h(n)是递推方程的任意解，h(0),h(1),…,h(k1)由初值b0,b1,…,bk1唯一确定.代入方程得到方程组系数行列式

当qi

qj时，方程组有唯一解14第十四页，共四十一页，2022年，8月28日求解实例例4Fibonacci数列：

fn=fn1+fn2，特征根为

通解为代入初值f0=1,f1=1,得解得

解是15第十五页，共四十一页，2022年，8月28日有重根下求解中的问题例5解特征方程

x24x+4=0

通解

H(n)=c12n+c22n=c2n

代入初值得：

c无解.问题：两个解线性相关16第十六页，共四十一页，2022年，8月28日有重根下的通解结构定理10.4

设q1,q2,…,qt是递推方程的不相等的特征根，且qi的重数为ei，i=1,2,…,t，令那么通解17第十七页，共四十一页，2022年，8月28日求解实例例6

求解以下递推方程其中待定常数满足以下方程组

原方程的解为

解特征方程x4+x33x25x2=0,特征根21,1,2通解为18第十八页，共四十一页，2022年，8月28日常系数线性非齐次递推方程求解递推方程的标准型通解结构特解的求法多项式函数指数函数组合形式19第十九页，共四十一页，2022年，8月28日递推方程的标准型及通解证代入验证,H(n)是解.下面证明任意解h(n)为某个齐次解与特解H*(n)之和.设h(n)为递推方程的解，则h(n)H*(n)是齐次解，即h(n)是一个齐次解与H*(n)之和.定理10.5设是对应齐次方程的通解，H*(n)是一个特解，则

是递推方程的通解.

20第二十页，共四十一页，2022年，8月28日特解的形式——多项式解设an*=P1n2+P2n

+P3,代入递推方程得

P1n2+P2n

+P32[P1(n1)2+P2(n1)+P3]=2n2整理得P1n2+(4P1P2)n+(2P1+2P2P3)=2n2

解得P1=2,P2=8,P3=12，原方程的通解为an=c2n2(n2+4n+6)例7

找出递推方程an

2an1=2n2

的通解如果f(n)为n次多项式，则特解一般也是n次多项式21第二十一页，共四十一页，2022年，8月28日实例例8Hanoi塔

T(n)=2T(n1)+1

T(1)=1解令T*(n)=P代入方程

P=2P+1解得P=–1

T(n)=c2n–1,代入初值得c=1,解为T(n)=2n–1.22第二十二页，共四十一页，2022年，8月28日例9

求解关于顺序插入排序算法的递推方程解设特解为W*(n)=P1n+P2，代入递推方程，得

P1n+P2(P1(n1)+P2)=n1无解.设特解W*(n)=P1n2+P2n,代入递推方程得

(P1n2+P2n)(P1(n1)2+P2(n1))=n1解得

P1=1/2,P2=1/2.通解为

W(n)=c1n+n(n1)/2=c+n(n1)/2代入初值W(1)=0，得到W(n)=n(n1)/2=O(n2).实例(续)23第二十三页，共四十一页，2022年，8月28日特解的形式——指数f(n)为指数函数

n，若

不是特征根，则特解为

H*(n)=P

n

其中P为待定常数.例10

通信编码问题解an=6an1+8n1,a1=7设

a*n=P8n1,代入得

P=4通解an=c6n+48n1

代入初值得

an=(6n+8n)/224第二十四页，共四十一页，2022年，8月28日特解的形式——指数(续)若是e重特征根，则特解为Pne

n

例11

H(n)–5H(n–1)+6H(n–2)=2n，解令H*(n)=Pn2n

代入得

Pn2n–5P(n–1)2n–1+6P(n–2)2n–2=2n

解得P=–

2特解

H*(n)=–

n2n+1

25第二十五页，共四十一页，2022年，8月28日特解的组合形式例12

an–

2an–1=n+3n

a0=0解设特解为

an*=P1n+P2+P33n代入原方程得

(P1n+P2+P33n)–2[P1(n–1)+P2+P33n–1]=n+3n解得P1=–

1,P2=–2,P3=3通解an=c2n–n

–

2+3n+1

代入初值得c=–1，

an=–2n–n–2+3n+126第二十六页，共四十一页，2022年，8月28日换元法迭代归纳法——递归树差消法尝试法应用实例

递推方程的其他解法27第二十七页，共四十一页，2022年，8月28日换元法思想：通过换元转化成常系数线性递推方程

解令代入得bn=2bn–1+1，

b0=4解得例13an>028第二十八页，共四十一页，2022年，8月28日实例解

H(k)=2H(k–1)+2k–1

H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1

H*(k)=k2k+1通解H(k)=c2k+k2k+1代入初值得c=–1

H(k)=–2k+k2k+1

W(n)=nlogn–n+1例14

归并排序29第二十九页，共四十一页，2022年，8月28日迭代归纳法——归并排序例1530第三十页，共四十一页，2022年，8月28日迭代归纳法——错位排列例16

Dn

=(n–1)(Dn–1+Dn–2)解：31第三十一页，共四十一页，2022年，8月28日差消法——化简递推方程例1732第三十二页，共四十一页，2022年，8月28日积分近似33第三十三页，共四十一页，2022年，8月28日递归树——二分归并排序T(n)n-1T(n/2)T(n/2)n/2-1n/2-1T(n/4)T(n/4)T(n/4)T(n/4)n/4-1n/4-1n/4-1n/4-1

……….1111111……111111111T(n)=nk–(1+2+…+2k1)=nk–(2k–1)=nlogn–n+1n1n2n4...n2k1k层34第三十四页，共四十一页，2022年，8月28日(1)T(n)=C,左边=O(1)尝试法例18

(2)T(n)=cn,左边=cn,35第三十五页，共四十一页，2022年，8月28日尝试法(续)(3)T(n)=cn2,左边=cn2(4)T(n)=cnlogn,左边=cnlogn

36第三十六页，共四十一页，2022年，8月28日积分近似37第三十七页，共四十一页，2022年，8月28日分治策略与递归算法n为输入规模，n/b为子问题输入规模，a为子问题个数，d(n)为分解及综合的代价38第三十八页，共四十一页，2022年，8月28日分治策略与递归算法(续)(1)d(n)=c