递推方程与生成函数

1,主要内容 递推方程的定义及实例 递推方程的公式解法 递推方程的其他解法 生成函数及其应用 指数生成函数及其应用 Catalan数与Stirling数,第十三章 递推方程与生成函数,2,13.1递推方程的定义及实例,定义13.1 设序列 a0, a1, …, an, …, 简记为{ an }. 一个把 an 与 某些个ai (in) 联系起来的等式叫做关于序列 { an } 的递推方 程. 当给定递推方程和适当的初值就唯一确定了序列.,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柱上去. 如果把一个圆盘从 一个柱子移到另一个柱子称作一次移动，在移动和放置 时允许使用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 pr 2. then q(p+r)/2 //q为p到r的中点， 3. Mergesort(A,p,q) 4. Mergesort(A,q+1,r) 5. Merge(A,p,q,r) // 归并排好序数组A[pq]与A[q+1r],插入排序算法 INSERTION-SORT(A,n) 1. for j  2 to n key  A[j] i  j–1 4 while i 0 and A[i] key 5. do A[i+1]  A[i]; i  i –1 7. A[i+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) + n－1 W(1) = 0 解得 W(n) = O(nlogn),6,13.2 递推方程的公式解法,特征方程、特征根 递推方程的解与特征根的关系 无重根下通解的结构 求解实例 有重根下通解的结构 求解实例,7,其中 a1, a2, … , ak为常数，ak  0 称为 k 阶常系数线性齐次递推方程 b0, b1, …, bk1 为 k 个初值,定义13.2 常系数线性齐次递推方程的标准形：,常系数线性齐次递推方程,实例：Fibonacci 数列的递推方程,8,特征方程与特征根,,,9,递推方程解与特征根的关系,定理13.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0）  q 是它的特征根,定理13.2 设 h1(n) 和 h2(n) 是递推方程的解，c1,c2为任意常数, 则 c1h1(n)+c2h2(n) 也是这个递推方程的解. 推论 若 q1, q2, …, qk 是递推方程的特征根，则 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 是常系数线性齐次递推方程不等 的特征根，则 H(n)= c1q1n + c2q2n + … + ckqkn 为该递推方程的通解.,11,例3 Fibonacci 数列： fn=fn1+fn2 ，特征根为,通解为,代入初值 f0 =1, f1=1, 得,解得,,,解是,实例,12,有重根下求解中的问题,,例4,,解 特征方程 x24x+4 = 0 通解 H(n) = c12n + c22n = c2n 代入初值得： c 无解. 问题：两个解线性相关,13,有重根下的通解结构,定理13.4 设 q1, q2, … , qt 是递推方程的不相等的特征根， 且 qi 的重数为 ei，i=1, 2, … , t，令,那么通解,14,例5 求解以下递推方程,其中待定常数满足以下方程组,原方程的解为,,解 特征方程 x4+x33x25x2 = 0 , 特征根1,1,1,2,通解为,求解实例,15,递推方程的标准型 通解结构 特解的求法 多项式函数 指数函数 组合形式,常系数线性非齐次递推方程求解,16,,递推方程的标准型及通解,17,,例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 2n–1, 代入初值得 c=1, 解为 T(n) = 2n –1.,19,例8 求解关于顺序插入排序算法的递推方程,解 设特解为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).,实 例(续),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(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,21,换元法 迭代归纳法 应用实例,13.3 递推方程的其他解法,22,思想：通过换元转化成常系数线性递推方程,解 令,代入得 bn = 2 bn–1 + 1， b0 = 4 解得,例11,an0,换元法,23,解 H(k) = 2 H(k–1) + 2k–1 H(1) = 1 令 H*(k) = P1k2k + P2 , 解得 P1=P2=1 H*(k) = k2k + 1 通解 H(k) = c 2k + k2k + 1 代入初值得 c = –1 H(k) = –2k + k2k +1 W(n) = n log n– n + 1,,例12 归并排序,换元法:实例,24,迭代归纳法：归并排序,,例13,25,迭代归纳法：错位排列,例14 Dn = (n–1)(Dn–1 + Dn–2),解：,,26,快速排序算法,算法 Quicksort (A,p,r) // p 和 r 分别表示A首和末元素下标 1. if p r 2. then qPartition(A, p, r) // 划分为A[pq1]和A[q+1r] 3. A[p]A[q] 4. Quicksort(A,p,q1) 5. Quicksort(A,q+1,r),27,划分过程,算法 Partition(A,p,r) 1. x  A[p] //选首元素作为划分标准x 2. i  p1 3. j  r+1 4. while true 5. do repeat j  j 1 6. until A[ j ] x //A[i]是从前找的第一个比x大的元素 9. if i j // 继续搜索A[i]到A[j]之间的范围 10 then A[ i ]  A[ j ] // A[ i ]与A[ j ]交换，回到行4 11. 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,平均情况时间复杂度分析,,,递推方程,差消法化简,,30,迭代求解,,,,31,递归树,,W(n)= n k –(1+2+…+2k1) = nk – (2k –1) = n log n – n + 1,32,13.4 生成函数及其应用,牛顿二项式系数与牛顿二项式定理 生成函数的定义 生成函数的应用,33,牛顿二项式系数,定义13.5 设 r 为实数，n为整数，引入形式符号,称为牛顿二项式系数.,,实例,34,牛顿二项式定理,定理13.6 （牛顿二项式定理） 设为实数，则对一切实数x, y，|x/y|1，有,若= m，其中m为正整数，那么,35,重要展开式,令x=z，y=1，那么牛顿二项式定理就变成,在上面式子中用z代替 z ，则有,36,生成函数定义,定义13.6 设序列{an}，构造形式幂级数 G(x) = a0 + a1x + a2x2 +… + an xn + … 称G(x)为序列{an}的生成函数.,例如， { C(m,n) }的生成函数为 (1+x)m 给定正整数k, { kn }的生成函数为 G(x) =1+ kx + k2x2 + k3x3 + … =,37,例14 求序列{an}的生成函数 (1) an = 7· 3n (2) an = n(n+1),解,由序列求生成函数,38,由生成函数求序列通项,,.,解,39,生成函数的应用,求解递推方程 计数多重集的 r 组合数 不定方程的解 整数拆分,40,求解递推方程,例16 an– 5an1 + 6an2 = 0，a0 = 1, a1 =  2,41,例17,解：设 { hn} 的生成函数为,求解递推方程,42,,求解递推方程,。