主要内容递推方程的定义及实例递推方程的公式解法递推方程课件.ppt

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=fn1+fn2 初值 f0=1，f1=1 阶乘计算数列：1，2，6，24，5！，,记作 F(n)递推方程 F(n)=nF(n1)初值 F(1)=1,3,例1 从A柱将这些圆盘移到C柱上去.如果把一个圆盘从一个柱子移到另一个柱子称作一次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小圆盘的上面.问把所有的圆盘的从A移到C总计需要多少次移动？,初值是 T(1)=1 可证明解是 T(n)=2n1,移动n个盘子的总次数为T(n).因此得到递推方程 T(n)=2T(n1)+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)/归并排好序数组Ap.q与Aq+1.r,插入排序算法 INSERTION-SORT(A,n)1.for j 2 to n key Aj i j14 while i 0 and Ai key5.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),6,13.2 递推方程的公式解法,特征方程、特征根递推方程的解与特征根的关系无重根下通解的结构求解实例有重根下通解的结构求解实例,7,其中 a1,a2,ak为常数，ak 0 称为 k 阶常系数线性齐次递推方程 b0,b1,bk1 为 k 个初值,定义13.2 常系数线性齐次递推方程的标准形：,常系数线性齐次递推方程,实例：Fibonacci 数列的递推方程,8,特征方程与特征根,9,递推方程解与特征根的关系,定理13.1 设 q 是非零复数，则 qn 是递推方程的解当且仅当q 是它的特征根.,qn是递推方程的解 qn a1qn1 a2qn2 akqnk=0 qnk(qk a1qk1 a2qk2 ak)=0 qk a1qk1 a2qk2 ak=0（因为q0）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)=c1q1n+c2q2n+ckqkn 成立，则称 c1q1n+c2q2n+ckqkn 为该递推方程的通解,定理13.3 设q1,q2,qk 是常系数线性齐次递推方程不等的特征根，则 H(n)=c1q1n+c2q2n+ckqkn为该递推方程的通解.,11,例3 Fibonacci 数列：fn=fn1+fn2，特征根为,通解为,代入初值 f0=1,f1=1,得,解得,解是,实例,12,有重根下求解中的问题,例4,解 特征方程 x24x+4=0 通解 H(n)=c12n+c22n=c2n 代入初值得：c 无解.问题：两个解线性相关,13,有重根下的通解结构,定理13.4 设 q1,q2,qt 是递推方程的不相等的特征根，且 qi 的重数为 ei，i=1,2,t，令,那么通解,14,例5 求解以下递推方程,其中待定常数满足以下方程组,原方程的解为,解 特征方程 x4+x33x25x2=0,特征根1,1,1,2,通解为,求解实例,15,递推方程的标准型通解结构特解的求法 多项式函数 指数函数 组合形式,常系数线性非齐次递推方程求解,16,递推方程的标准型及通解,17,例6 找出递推方程 an 2an1=2n2 的通解,如果 f(n)为n次多项式，则特解一般也是 n 次多项式,特解的形式：多项式,18,例7 Hanoi塔 T(n)=2T(n1)+1 T(1)=1,实例,解 令 T*(n)=P代入方程 P=2P+1解得 P=1 T(n)=c 2n1,代入初值得 c=1,解为 T(n)=2n 1.,19,例8 求解关于顺序插入排序算法的递推方程,解 设特解为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)=c 1n+n(n1)/2=c+n(n1)/2代入初值W(1)=0，得到W(n)=n(n1)/2=O(n2).,实 例(续),20,特解的形式:指数,f(n)为指数函数 n，若 是 e 重特征根(e可以等于0)，则特解为Pne n,其中P为待定常数.,例9 通信编码问题 解 an=6an1+8n1,a1=7 设 a*n=P 8n1,代入得 P=4 通解 an=c6n+48n1 代入初值得 an=(6n+8n)/2,例10 H(n)5H(n1)+6H(n2)=2n，解 令 H*(n)=Pn2n 代入得 Pn2n 5P(n1)2n1+6P(n2)2n2=2n 解得 P=2,特解 H*(n)=n2n+1,21,换元法迭代归纳法应用实例,13.3 递推方程的其他解法,22,思想：通过换元转化成常系数线性递推方程,解 令,代入得 bn=2 bn1+1，b0=4解得,例11,an0,换元法,23,解 H(k)=2 H(k1)+2k1 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=(n1)(Dn1+Dn2),解：,26,快速排序算法,算法 Quicksort(A,p,r)/p 和 r 分别表示A首和末元素下标 1.if p r 2.then qPartition(A,p,r)/划分为Ap.q1和Aq+1.r 3.ApAq 4.Quicksort(A,p,q1)5.Quicksort(A,q+1,r),27,划分过程,算法 Partition(A,p,r)1.x Ap/选首元素作为划分标准x2.i p1 3.j r+14.while true 5.do repeat j j 1 6.until A j x/Ai是从前找的第一个比x大的元素9.if i j/继续搜索Ai到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,平均情况时间复杂度分析,递推方程,差消法化简,30,迭代求解,31,递归树,W(n)=n k(1+2+2k1)=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 5an1+6an2=0，a0=1,a1=2,41,例17,解：设 hn 的生成函数为,求解递推方程,42,求解递推方程,43,多重集的 r 组合数,S=n1a1,n2a2,nkak 的 r 组合数就是不定方程 x1+x2+xk=r xi ni i=1,2,k的非负整数解的个数,的展开式中 yr 的系数,生成函数,44,实例,例18 S=3a,4b,5c 的10 组合数解：生成函数G(y)=(1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5)=(1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5)=(1+3y10+2y10+y10+)N=6 组合方案 a,a,a,b,b,b,b,c,c,c,a,a,a,b,b,b,c,c,c,c,a,a,a,b,b,c,c,c,c,c,a,a,b,b,b,b,c,c,c,c,a,a,b,b,b,c,c,c,c,c,a,b,b,b,b,c,c,c,c,c,45,不定方程解的个数,基本的不定方程 x1+x2+xk=r，xi 为自然数,46,推广的不定方程,带限制条件的不定方程 x1+x2+xk=r，li xi ni,带系数的不定方程 p1x1+p2x2+pkxk=r，xiN生成函数,生成函数,47,实例,例19 1克砝码2个，2克砝码1个，4克砝码2个，问能称出哪些重量，方案有多少？,解：x1+2 x2+4 x3=r 0 x1 2,0 x2 1,0 x3 2 G(y)=(1+y+y2)(1+y2)(1+y4+y8)=1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12,48,拆分的定义：将给定正整数N表示成若干个正整数之和.,正整数拆分,49,无序拆分,基本模型：将N无序拆分成正整数 a1,a2,an a1x1+a2x2+anxn=N 不允许重复,允许重复,50,实例,例20 证明任何正整数都可以唯一表示成 2 进制数.对应于将任何正整数N拆分成 2 的幂，20,21,22,23,且不允许重复.,对于所有的 n,系数是1，这就证明唯一的表法.,生成函数,51,解 N允许重复无序拆分成 k个数（kr）的方案 N允许重复无序拆分成正整数 k（kr）的方案做下述 Ferrers图 将图以 y=x 对角线翻转180度，得到 共轭的Ferrers图.16=6+5+3+2（k 4）对应每个数不超过4的拆分:16=4+4+3+2+2+1 这种拆分数的生成函数为,无序拆分：个数限制,例21 给定r,求N允许重复无序拆分成 k个数(kr)的方法数,52,定理13.7 将N允许重复地有序拆分成 r 个部分的方案数为 C(N1,r1).证 设 N=a1+a2+ar 是满足条件的拆分，则令,r1个Si 取值为1,2,N1，方法数为 C(N1,r1).,不允许重复有序拆分：不允许重复无序拆分+全排列,有序拆分,推论 对N 做任意重复的有序拆分，方案数为,53,指数生成函数的定义与实例指数生成函数的应用,13.5 指数生成函数及其应用,54,例22 给定正整数m,an=P(m,n),an的指数生成函数为,例23 bn=1,则bn的指数生成函数为,定义13.7 设an为序列，称,为an的指数生成函数.,指数生成函数的定义与实例,55,应用：多重集排列计数,定理13.8 设 S=n1a1,n2a2,nkak为多重集，则 S 的 r 排列数的指数生成函数为,56,实例,例24 由1,2,3,4 组成的五位数中，要求1出现不超过2次，但不能不出现，2出现不超过1次，3出现可达3次，4出现偶数次.求这样的五位数个数.,N=215,解,57,实例,解 设方案数为an,例25 红、白、兰涂色 1n 的方格，要求偶数个为白色，问有多少方案？,58,13.6 Catalan数与Stirling数,Catalan数第一类 Stirling数第二类 Stirling数,59,Catalan数定义,定义13.8 一个凸 n+1边形，通过不相交于n+1 边形内部的对角线把 n+1 边形划分成三角形，划分方案个数记作hn，称为Catalan数.,实例：h4=5,初值 h2=1,60,考虑n+1条边的多边形，端点A1,An+1的边记为a,对于任意的 k=1,2,n1，以Ak+1A1为边，An+1Ak+1为另一边，与a构成三角形T,T 将多边形划分成 R1和 R2两个部分，分别为 k+1 边形和 nk+1边形.,递推方程,Catalan数的递推方程,解：,61,实例：计数堆栈的输出个数,例26 1,2,n放入堆栈后的不同的输出个数,解 在 1 进栈到出栈之间作为一个子问题，1出栈后作为一个子问题.过程如下：,步2：子问题规模 k，步4：子问题规模 nk1,11 进栈；2处理 k个数（2,k+1）的进栈问题；31 出栈；4处理 k+2,n 的进栈问题；,62,求解递推方程,63,第一类Stirling数,将 xr 系数的绝对值 Sr 记作，称为第一类 Stirling数,定义13.9 多项式 x(x1)(x2)(xn+1)的展开式为 Snxn Sn1xn1+Sn2xn2+(1)n1S1x,实例 x(x1)=x2x x(x1)(x2)=x33x2+2x,64,第一类Stirling数的递推方程,65,第一类Stirling数的恒等式,66,第二类Stirling数定义,定义13.10 n 个不同的球恰好放到 r 个相同的盒子里的方法数称为第二类Stirling数，记作实例具体方案如下：a,b,c|d a,c,d|b a,b,d|c b,c,d|a a,b|c,d a,c|b,d a,d|b,c,67,第二类Stirling数递推方程,证明：取球a1，a1单独放一个盒子，a1不单独放一个盒子，先放n1个球到 r 个盒子，插入a1有 r 种方法，,递推方程,68,第二类Stirling数恒等式,69,恒等式证明,1.,a1 先放在一个盒子里，剩下的 n1 个球每个有 2 种选择，但是全落入a1的盒子的方法不符合要求.,n 个球放到 n1个盒子，必有一个盒子含 2 个球，其余每个盒子 1 个球.选择两个球有 C(n,2)种方法.,70,恒等式证明,对应 n 个不同的球恰好放到 m 个不同盒子的方法数（无空盒）,按照含球的盒子数 k 分类，对应了允许存在空盒的方法,至多 n 个不同的球放到 r1 个相同的盒子不存在空盒的方法按照球数分类,71,放球问题的计数,72,第十三章 习题课,主要内容递推方程的求解方法：公式法、换元法、迭代归纳法、生成函数法递推方程与递归算法生成函数的应用：计算多重集的 r 组合数、确定不定方程的整数解个数、计算拆分方案数、求解递推方程指数生成函数的应用：计算多重集的 r 排列数常用的计数符号：组合数、排列数、多项式系数、错位排列数、Fibonacci数、Catalan数、两类Stirling数基本计数模型：选取问题、不定方程的解、非降路径、正整数拆分、放球等,73,基本要求,能够使用递推方程求解计数问题能够使用生成函数或指数生成函数求解计数问题掌握 Fibonacci数、Catalan 数、两类 Stirling数的定义、组合意义以及相关的公式.,74,练习1,已知 a0=0,a1=1,a2=4,a3=12 满足递推方程 an+c1an1+c2an2=0，求 c1 和 c2.,解得 c1=4,c2=4.,代入a0,a1,a2,a3的值得到,根据已知条件得到,75,练习2,2求解递推方程,.,用换元法.令bn=nan,代入原递推方程得,用公式法解得,从而得到,76,练习3,3确定序列an的生成函数，其中an=,77,练习3,78,练习4,4已知,是序列an的生成函数，求an.,解得A=1/4,B=3/4,C=1/4,从而得到,79,练习4,80,练习5,5求下列 n 阶行列式的值 dn,.,解得 dn=n+1.,方程,81,设平面上已经有n1条直线.当加入第n条直线时，它与平面上的前n1条直线交于n1个点.这些点将第n条直线分割成n段，每段都增加一个区域，共增加n个区域，因此得到递推方程,练习5,5.平面上有 n 条直线，它们两两相交且没有三线交于一点，问这 n 条直线把平面分成多少个区域？,82,6在经济中，商品价格随需求量增长而上涨，随供给量增长而下降，可以简单地用一个线性方程表示这种依赖关系.需求关系：p=abq，其中p为价格，q 为需求量，a,b0为常数.当 p 上涨时 q 将减少.供给关系：p=kr，其中p为价格，r 为供给量，k0为常数.当p上涨时，r 将增加.假设价格随需求量能做到即时变化，而商品生产和流通需要时间，因此供给量随价格的变化需要1个单位时间的延迟.假定每个时间的需求量都和供给量相等，考虑一个时间序列0,1,n,，设时间0的价格是 p0，求时间 n 的价格 pn.,练习6,83,设第 n 时间的价格为 pn,需求量为 qn，供给量为 rn，那么有,练习6,代入得到,解得,84,7用三个1、两个2、五个3可以组成多少个不同的四位数？如果这个四位数是偶数，那么又有多少个？,练习7,其中x4的系数为,因此 a4=71.,85,练习8,方法一.n 个编号球恰放入 k 个相同盒子且不允许相邻编号在同一盒的方法数.选定球a1,进行变换：如果a1自己在一个盒子，将盒子拿走，得到 n1个不同球恰放入k1个相同盒且相邻编号不落入同一盒子的方法.如果与a1在同一盒子的球有 将球 放入 所在的盒子，然后拿走含a1的盒子，从而得到n1个不同球恰好放到 k1个盒子且至少两个相邻标号球落入同一盒的方法.所求方法数等于n1个不同球恰好放入k1个相同盒子的方法数，即.再考虑盒子编号为,8用恰好k 种可能的颜色做旗子，使得每面旗子由 n 条彩带构成（nk），且相邻两彩带的颜色都不相同，证明不同的旗子数是,86,方法二,数学归纳法.当 n=1,必有 k=1,这时有，命题为真.假设对一切 n,k 命题为真，考虑 n+1条使用 k 种颜色的涂色方案.若用 k 种颜色涂色前 n 条，最后一条有 k1 种选择，方法数为.若用 k1 种颜色涂色前 n 条，选择颜色的方式数为 k,涂色方法数为 因此由乘法法则得.再根据加法法则，总方法数为根据归纳法命题成立.,87,方法三,令n+1个球恰落入k+1相同盒子且球编号不相邻方法数为 将这些方法分成两类：其中第 n+1个球独占一盒的方法数为；第 n+1个球不独占一个盒子的方法数为 与第二类Stirling数递推方程初值一样，因此考虑盒子编号，于是得到 n+1个球恰好落入k+1个不同的盒子，且球的编号不相邻的方法数为,