1、1主要内容主要内容l 递推方程的定义及实例递推方程的定义及实例l 递推方程的公式解法递推方程的公式解法l 递推方程的其他解法递推方程的其他解法l 生成函数及其应用生成函数及其应用l 指数生成函数及其应用指数生成函数及其应用l Catalan数与数与Stirling数数第十三章第十三章 递推方程与生成函数递推方程与生成函数213.1递推方程的定义及实例递推方程的定义及实例定义定义13.1 设序列设序列 a0, a1, , an, , 简记为简记为 an . 一个把一个把 an 与与某些个某些个ai (in) 联系起来的等式叫做关于序列联系起来的等式叫做关于序列 an 的的递推方递推方程程. 当给
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) = 1 3例例1 从从A柱将这些圆盘移到柱将这些圆盘移到C柱上去柱上去. 如果把一个圆盘从如果把一个圆盘从一个柱子移到另一个柱子称作一次移动，在移动和放置一个柱子移到另一个柱子称作一次移动，在移动和
3、放置时允许使用时允许使用B柱，但不允许大圆盘放到小圆盘的上面柱，但不允许大圆盘放到小圆盘的上面. 问问把所有的圆盘的从把所有的圆盘的从A移到移到C总计需要多少次移动？总计需要多少次移动？初值是初值是 T(1)=1 可证明解是可证明解是 T(n)=2n 1 移动移动n个盘子的总次数为个盘子的总次数为T(n). 因此得到递推方程因此得到递推方程 T(n) = 2T(n 1) +1. 递推方程的实例递推方程的实例:Hanoi塔塔4两个排序算法两个排序算法归并算法归并算法 Mergesort (A,p,r) / 对对A的下标的下标p到到r之间数排序之间数排序1. if p 0 and Ai key5.
4、 do Ai+1 Ai; i i 17. Ai+1 key 5递推方程的实例递推方程的实例:算法分析算法分析例例2 哪种排序算法在最坏情况下复杂度比较低？哪种排序算法在最坏情况下复杂度比较低？ 插入排序，归并排序插入排序，归并排序 插入排序插入排序 W(n) = W(n 1) + n 1 W(1) = 0解得解得 W(n) = O(n2). 归并排序，不妨设归并排序，不妨设 n = 2k. W(n) = 2W(n/2) + n1 W(1) = 0解得解得 W(n) = O(nlogn) 613.2 递推方程的公式解法递推方程的公式解法l 特征方程、特征根特征方程、特征根l 递推方程的解与特征根
5、的关系递推方程的解与特征根的关系l 无重根下通解的结构无重根下通解的结构l 求解实例求解实例l 有重根下通解的结构有重根下通解的结构l 求解实例求解实例7 121021)1(,.,)2(,)1(,)0(0)(.)2()1()(kkbkHbHbHbHknHanHanHanH其中其中 a1, a2, , ak为常数，为常数，ak 0 称为称为 k 阶常系数线性齐次递推方程阶常系数线性齐次递推方程 b0, b1, , bk 1 为为 k 个个初值初值定义定义13.2 常系数线性齐次递推方程的标准形：常系数线性齐次递推方程的标准形： 1, 11021fffffnnn常系数线性齐次递推方程常系数线性齐次
6、递推方程实例：实例：Fibonacci 数列的递推方程数列的递推方程8特征方程与特征根特征方程与特征根 121021)1(,.,)2(,)1(,)0(0)(.)2()1()(kkbkHbHbHbHknHanHanHanH 定义定义13.3 特征方程特征方程 xk a1xk 1 ak = 0， 特征方程的根称为递推方程的特征方程的根称为递推方程的 特征根特征根 实例：实例： 递推方程递推方程 fn = fn 1 + fn 2 特征方程特征方程 x2 x 1 = 0 251,251 特征根特征根9递推方程解与特征根的关系递推方程解与特征根的关系定理定理13.1 设设 q 是非零复数，则是非零复数，
7、则 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 0） q 是它的特征根是它的特征根 定理定理13.2 设设 h1(n) 和和 h2(n) 是递推方程的解，是递推方程的解，c1,c2为任意常数为任意常数,则则 c1h1(n)+c2h2(n) 也是这个递推方程的解也是这个递推方程的解.推论推论 若若 q1, q2, , qk 是递推方程的特征根，则
8、是递推方程的特征根，则 c1q1n + c2q2n + + ckqkn 是该递推方程的解，其中是该递推方程的解，其中c1, c2, , ck 是任意常数是任意常数. 10无重根下通解的结构无重根下通解的结构定义定义13.4 若对常系数线性齐次递推方程的每个解若对常系数线性齐次递推方程的每个解 h(n) 都都存在一组常数存在一组常数c1 ,c2 , ck 使得使得 h(n) = c1 q1n+c2 q2n+ck qkn 成立，则称成立，则称 c1q1n + c2q2n + + ckqkn 为该递推方程的为该递推方程的通解通解 定理定理13.3 设设q1, q2, , qk 是是常系数线性齐次常系
9、数线性齐次递推方程不等递推方程不等的特征根，则的特征根，则 H(n)= c1q1n + c2q2n + + ckqkn为该递推方程的通解为该递推方程的通解.11251,251 例例3 Fibonacci 数列：数列： fn=fn 1+fn 2 ，特征根为，特征根为 nnnccf 25125121 通解为通解为 125125112121cccc代入初值代入初值 f0 =1, f1=1, 得得 25151,2515121 cc解得解得 112515125151 nnnf解是解是实例实例12有重根下求解中的问题有重根下求解中的问题 1)1(, 0)0(0)2(41)(4)(HHnHnHnH例例4 4
10、解解 特征方程特征方程 x2 4x+4 = 0 通解通解 H(n) = c12n + c22n = c2n 代入初值得：代入初值得： c 无解无解. 问题：两个解线性相关问题：两个解线性相关 120cc13有重根下的通解结构有重根下的通解结构neiiiiiiieqncnccnH).()(121 定理定理13.4 设设 q1, q2, , qt 是递推方程的不相等的特征根，是递推方程的不相等的特征根，且且 qi 的重数为的重数为 ei，i=1, 2, , t，令，令 tiinHnH1)()(那么通解那么通解 14例例5 求解以下递推方程求解以下递推方程 2(3)1(2)0,(1)1(0)0)4(
11、2)3(5)2(31)()(,HH,HHnHnHnHnHnH其中待定常数满足以下方程组其中待定常数满足以下方程组 92, 0,31,9728931442021432143214321432141 ccccccccccccccccccnnnnnH292)1(31)1(97)( 原方程的原方程的解为解为 解解 特征方程特征方程 x4+x3 3x2 5x 2 = 0 , 特征根特征根 1, 1, 1,2nncncnccnH2)1)()(42321 通解为通解为求解实例求解实例15l 递推方程的标准型递推方程的标准型l 通解结构通解结构l 特解的求法特解的求法 多项式函数多项式函数 指数函数指数函数
12、组合形式组合形式常系数线性非齐次递推方程求解常系数线性非齐次递推方程求解160)(*)(.)1(*)1()(*)()()(*.)1(*)(*)()(.)1()(111 knHknhanHnhanHnhnfknHanHanHnfknhanhanhkkk证证 代入验证代入验证, H(n)是解是解. 下面证明任意解下面证明任意解 h(n) 为某个齐次为某个齐次解与特解解与特解H*(n)之和之和. 设设 h(n)为递推方程的解，则为递推方程的解，则h(n) H*(n)是齐次解，即是齐次解，即 h(n) 是一个齐次解与是一个齐次解与H*(n)之和之和. 0)(, 0,),()(.)1()(1 nfakn
13、nfknHanHanHkk定理定理13.5 设设)(nH是对应齐次方程的通解，是对应齐次方程的通解，H*(n)是一个特解，则是一个特解，则 )(*)()(nHnHnH 是递推方程的通解是递推方程的通解. . 递推方程的标准型及通解递推方程的标准型及通解17解解 设设 an* = P1n2 + P2n + P3 , 代入递推方程得代入递推方程得 P1n2 + P2n + P3 2P1(n 1)2 + P2(n 1) + P3 = 2n2 整理得整理得 P1n2+(4P1 P2)n+( 2P1+2P2 P3) = 2n2 022042321211PPPPPP解得解得 P1= 2, P2 = 8,
14、P3= 12，原方程的通解为原方程的通解为 an = c2n 2(n2+4n+6) 例例6 找出递推方程找出递推方程 an 2an 1 = 2n2 的通解的通解如果如果 f(n)为为n次多项式，则特解一般也是次多项式，则特解一般也是 n 次多项式次多项式特解的形式：多项式特解的形式：多项式18例例7 Hanoi塔塔 T(n) = 2T(n 1)+1 T(1)=1 实例实例解解 令令 T*(n) = P代入方程代入方程 P = 2P + 1解得解得 P = 1 T(n) = c 2n1, 代入初值得代入初值得 c=1, 解为解为 T(n) = 2n 1.19例例8 求解关于顺序插入排序算法的递推
15、方程求解关于顺序插入排序算法的递推方程 0)1( 1)1()(WnnWnW解解 设特解为设特解为W*(n)=P1n+P2，代入递推方程，得，代入递推方程，得 P1n+P2 ( P1(n 1)+P2) = n 1无解无解. 设特解设特解W*(n) = P1n2+P2n, 代入递推方程得代入递推方程得 (P1n2+P2n) (P1(n 1)2+P2(n 1)= n 1 解得解得 P1=1/2, P2= 1/2. 通解为通解为 W(n) = c 1n + n(n 1)/2 = c + n(n 1)/2代入初值代入初值W(1)=0，得到，得到W(n)= n(n 1)/2=O(n2). 实实 例例( (
16、续续) )20特解的形式特解的形式: :指数指数f(n)为指数函数为指数函数 n，若若 是是 e 重特征根重特征根(e可以等于可以等于0)，则特，则特解为解为Pne n , 其中其中P为待定常数为待定常数. 例例9 通信编码问题通信编码问题 解解 an = 6an 1 + 8n 1, a1=7 设设 a*n = P 8n 1 , 代入得代入得 P = 4 通解通解 an = c 6n + 4 8n 1 代入初值得代入初值得 an = (6n+8n)/2 例例10 H(n)5H(n1)+6H(n2) = 2n， 解解 令令 H*(n)=Pn2n 代入得代入得 Pn2n 5P(n1)2n1 + 6
17、P(n2)2n2 = 2n 解得解得 P = 2, 特解特解 H*(n) = n2n+1 21l 换元法换元法l 迭代归纳法迭代归纳法l 应用实例应用实例 13.3 递推方程的其他解法递推方程的其他解法22思想：通过换元转化成常系数线性递推方程思想：通过换元转化成常系数线性递推方程 ,2nnab 解解 令令125125 nnnnab代入得代入得 bn = 2 bn1 + 1， b0 = 4解得解得 例例11 2120212aaannan0换元法换元法23解解 H(k) = 2 H(k1) + 2k1 H(1) = 1 令令 H*(k) = P1k2k + P2 , 解得解得 P1=P2=1 H
18、*(k) = k2k + 1通解通解 H(k) = c 2k + k2k + 1 代入初值得代入初值得 c = 1 H(k) = 2k + k2k +1 W(n) = n log n n + 1 0 (1)2 , 1 ) /2 (2 )(WnnnWnWk例例12 归并排序归并排序换元法换元法:实例实例24迭代归纳法：归并排序迭代归纳法：归并排序 0 (1)2 , 1 ) /2 (2 )(WnnnWnWk例例131log122)12.22(2(1)2.122222)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkWWW
19、WWWnWkkkkkkkkkkkkkkkkkkkkkk解解25迭代归纳法：错位排列迭代归纳法：错位排列例例14 Dn = (n1)(Dn1 + Dn2) 0,)1()1(2)1(.)1(112122211 DnDDDDDnDnDDnnnnnnnnn解：解：!1)1(.! 21! 111 !)1()1(.)1(4).1()1(3).1(2).1(.)1()1()1)(1()2)(1()1()1(13211232nnnnnnnDnnnnnDnnnnDnnDnnnnnnnnnn 26快速排序算法快速排序算法算法算法 Quicksort (A,p,r) / p 和和 r 分别表示分别表示A首和末元素下
20、标首和末元素下标 1. if p r 2. then qPartition(A, p, r) / 划分为划分为Ap.q 1和和Aq+1.r 3. ApAq 4. Quicksort(A,p,q 1) 5. Quicksort(A,q+1,r)27划分过程划分过程算法算法 Partition(A,p,r) 1. x Ap /选首元素作为划分标准选首元素作为划分标准x2. i p 1 3. j r+14. while true 5. do repeat j j 1 6. until A j x /Ai是从前找的第一个比是从前找的第一个比x大的元素大的元素9. if i j / 继续搜索继续搜索Ai
21、到到Aj之间的范围之间的范围10 then A i A j / A i 与与A j 交换，回到行交换，回到行411. else return j /结束结束While循环循环28实例实例 27 99 0 8 13 64 86 16 7 10 88 25 90 i j 27 25 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90 j i 16 25 0 8 13 10 7 27 86 64 88 99 90 29平均情况时间复杂
22、度分析平均情况时间复杂度分析 0)1(2),()(2)(11TnnOiTnnTni为某个常数为某个常数cnciTnTncniTnnTnini 2122111)()(21)()1()(2)(递推方程递推方程差消法化简差消法化简)()1()1()(nOnTnnnT 1)1(1)( ncnnTnnT30迭代求解迭代求解 31.1112)1(31.1111)(nncTnncnnT)(log2ln)1ln(ln131.1111212nOnxdxxnnnn )log()(nnOnT 31递归树递归树0 (1),2 , 1 ) /2 (2 )( WnnnWnWk12111114141414142121211
23、 knnnnnnnnnnnW(n)= n k (1+2+2k 1) = nk (2k 1) = n log n n + 13213.4 生成函数及其应用生成函数及其应用l 牛顿二项式系数与牛顿二项式定理牛顿二项式系数与牛顿二项式定理l 生成函数的定义生成函数的定义l 生成函数的应用生成函数的应用33牛顿二项式系数牛顿二项式系数 0!)1).(1(0100nnnrrrnnnr定义定义13.5 设设 r 为实数，为实数，n为整数，引入形式符号为整数，引入形式符号65!6)5)(4)(3)(2)(52 1285! 42)5)(3(1)1(! 4)321)(221)(121(2142/14 4! 32
24、3434 称为称为牛顿二项式系数牛顿二项式系数. . 实例实例34牛顿二项式定理牛顿二项式定理定理定理13.6 （牛顿二项式定理）（牛顿二项式定理）设设 为实数，则对一切实数为实数，则对一切实数x, y，|x/y|0为常为常数数. 当当 p 上涨时上涨时 q 将减少将减少. 供给关系：供给关系：p=kr，其中，其中p为价格，为价格，r 为供给量，为供给量，k0为常数为常数. 当当p上涨时，上涨时，r 将增加将增加. 假设价格随需求量能做到即时变化，而商品生产和流通需要假设价格随需求量能做到即时变化，而商品生产和流通需要时间，因此供给量随价格的变化需要时间，因此供给量随价格的变化需要1个单位时间
25、的延迟个单位时间的延迟. 假假定每个时间的需求量都和供给量相等，考虑一个时间序列定每个时间的需求量都和供给量相等，考虑一个时间序列0,1,n,，设时间，设时间0的价格是的价格是 p0，求时间，求时间 n 的价格的价格 pn. 练习练习683设第设第 n 时间的价格为时间的价格为 pn, 需求量为需求量为 qn，供给量为，供给量为 rn，那么有，那么有 nnnnnnqrkrpbqap1练习练习6appnkbn 1bkkakbcpnn )(bkkapcbkkacp 00bkkapbkkakbpnn )()(0代入得到代入得到 解得解得847用三个用三个1、两个、两个2、五个、五个3可以组成多少个不
26、同的四位数？可以组成多少个不同的四位数？如果这个四位数是偶数，那么又有多少个？如果这个四位数是偶数，那么又有多少个？ 练习练习7)! 5! 4! 3! 21()! 21)(! 3! 21()(5432232xxxxxxxxxxxAe 其中其中x4的系数为的系数为! 4714x 因此因此 a4=71. 85练习练习8方法一方法一. n 个编号球恰放入个编号球恰放入 k 个相同盒子且不允许相邻编号个相同盒子且不允许相邻编号在同一盒的方法数在同一盒的方法数. 选定球选定球a1, 进行变换：如果进行变换：如果a1自己在一自己在一个盒子，将盒子拿走，得到个盒子，将盒子拿走，得到 n 1个不同球恰放入个不
27、同球恰放入k 1个相同个相同盒且相邻编号不落入同一盒子的方法盒且相邻编号不落入同一盒子的方法. 如果与如果与a1在同一盒子的球有在同一盒子的球有 将球将球 放入放入 所在的盒子，所在的盒子， 然后拿走含然后拿走含a1的盒子，从而得到的盒子，从而得到n 1个不同球个不同球恰好放到恰好放到 k 1个盒子且至少两个相邻标号球落入同一盒的个盒子且至少两个相邻标号球落入同一盒的方法方法. 所求方法数等于所求方法数等于n 1个不同球恰好放入个不同球恰好放入k 1个相同盒子个相同盒子的方法数，即的方法数，即 . 再考虑盒子编号为再考虑盒子编号为 8用恰好用恰好k 种可能的颜色做旗子，使得每面旗子由种可能的颜
28、色做旗子，使得每面旗子由 n 条彩条彩带构成（带构成（n k），且相邻两彩带的颜色都不相同，证明不同），且相邻两彩带的颜色都不相同，证明不同的旗子数是的旗子数是 11!knk.,.,21liiiaaajia1 jia 11kn 11!knk86方法二方法二数学归纳法数学归纳法. 当当 n=1, 必有必有 k=1, 这时有这时有 ，命题为真，命题为真. 假设对一切假设对一切 n, k 命题为真，考虑命题为真，考虑 n+1条使用条使用 k 种颜色的涂色种颜色的涂色方案方案. 若用若用 k 种颜色涂色前种颜色涂色前 n 条，最后一条有条，最后一条有 k 1 种选择，种选择，方法数为方法数为 . 若用
29、若用 k 1 种颜色涂色前种颜色涂色前 n 条，选择条，选择颜色的方式数为颜色的方式数为 k, 涂色方法数为涂色方法数为 因此由乘法法则得因此由乘法法则得 . 再根据加法法则，总方再根据加法法则，总方法数为法数为根据归纳法命题成立根据归纳法命题成立. 1! 11111 )1(11! kknk 21)!1(knk 21!knk 1!21!)1(11!knkknkkknk87方法三方法三令令n+1个球恰落入个球恰落入k+1相同盒子且球编号不相邻方法数为相同盒子且球编号不相邻方法数为 将这些方法分成两类：其中第将这些方法分成两类：其中第 n+1个球独占一盒的方法数个球独占一盒的方法数为为 ；第；第 n+1个球不独占一个盒子的方法数为个球不独占一个盒子的方法数为 与第二类与第二类Stirling数递推方程初值一样，因此数递推方程初值一样，因此考虑盒子编号，于是得到考虑盒子编号，于是得到 n+1个球恰好落入个球恰好落入k+1个不同的盒个不同的盒子，且球的编号不相邻的方法数为子，且球的编号不相邻的方法数为 111111SkSSSknknkn knSkn knkSkkn)!1()!1( 11!knkNknS11 knSknkS1
