离散第7讲递归关系.ppt

,计算机专业基础课程,授课人：张桂芸,-2-,第7讲 递归关系,回顾,定义3.5：集合1，2，3，n的全排列，使得每个数i都不在第i位上，称这样的排列为1，2，3，n的一个错置。定理3.15：集合1，2，3，n的错置的总数(记为 Dn)是 约定D0=1。定理3.16,-3-,第7讲 递归关系,回顾,(1)Dn=(n-1)(Dn-2+Dn-1)(2)Dn=nDn-1+(-1)n a1=i ai=1证.(1)设1，2，3，n的一个错置是a1a2akan，因为a11，所以a1有n-1种取法。设a1=i(2in)，分两种情况讨论：(1.1)ai=1。这时取决于其余n-2个数的错置，这些错置的数目是Dn-2。(1.2)ai1。这时取决于其余n-1个数的错置：“1不可放置在第i位，其它各数j不可放置在第j位”，这些错置的数目是Dn-1。因此，由加法原理和乘法原理Dn=(n-1)(Dn-2+Dn-1),递归关系,-4-,第7讲 递归关系,PowerPoint Template_Sub,计数基本原理,排列与组合,重集的排列与组合,第3章 组合论基础-计数,递归关系,递归关系,Textbook Page 44 to 54,离散数学第7讲,-6-,第7讲 递归关系,内容提要,递归关系递归关系的定义和实例用递归关系构造模型用递归关系为实际问题建模递归关系的迭代求解常系数线性齐次递归关系的求解 什么是常系数线性齐次递归关系常系数线性齐次递归关系的特征根求解方法,-7-,第7讲 递归关系,前言,有多少个n位二进制串不包含两个连续的0？,解：令an表示这样的n位二进制串数，a1=2(0,1)a2=3(00,01,10,11)a3=5(000,001,010,011,100,101,110,111)(010,110,011,101,111)an分为以0和以1结尾两种情况对以0结尾的情况：是任何不含2个连续0的n2位二进制串加上10组成的，有an-2个对以1结尾的情况：是任何不含2个连续0的n1位二进制串加上1组成的，有an-1个 an=an-1+an-2这个等式叫做递归关系，和初始条件一起唯一地确定了序列an。,递归关系是求解组合数学问题的重要工具，几乎在所有的数学分支中都有重要应用.许多计数问题用上一章讨论的方法不易求解，但可以通过找到序列的项之间的关系间接求解.,-8-,第7讲 递归关系,递归关系(recurrence relation),定义1：关于序列an的递归关系是一个等式，它把an用序列中排在an前面的一项或多项来表示。如果一个序列的项满足某个递归关系，这个序列就叫做该递归关系的解(或通项,通项公式)。,-9-,第7讲 递归关系,递归关系举例,确定序列an是否为递归关系an=2an-1an-2(n=2,3,4,)的解，这里an=3n，n是非负整数。若an=2n或an=5呢？,解：(1)假设对每一个非负整数n，an=3n。对n2，可看出2an-1an-2=23(n-1)-3(n-2)=6n-6-3n+6=3n=anan=3n是该递归关系的解(2)假设对每一个非负整数n，an=2n。a0=1，a1=2，a2=4，2a1a0=22-1=3a2an=2n不是该递归关系的解(3)假设对每一个非负整数n，an=5。对n2，有2an-1an-2=25-5=5=an，因此an=5是该递归关系的解,-10-,第7讲 递归关系,说明,序列的初始条件说明了在递归关系起作用的首项之前的那些项递归关系和初始条件唯一地确定一个序列，这是因为一个递归关系和初始条件一起提供了这个序列的递归定义只要使用足够多次，序列的任意一项都可以从初始条件开始通过递归关系求出但对于某些特定类型的序列，可以有更好的办法通过它的递归关系和初始条件来计算它的通项,-11-,第7讲 递归关系,用递归关系构造模型,例3.14 平面上n条直线两两相交，且没有任何三条直线交于一点，求共有多少个交点？,解：设n(n2)条直线的交点数目为h(n)。如果增加第n+1条直线，它将与前n条直线相交产生n个交点h(n+1)=h(n)+n，且已知h(2)=1。h(n)=h(n-1)+n-1=h(n-2)+n-2+n-1=h(n-3)+n-3+n-2+n-1=h(2)+2+3+n-1=1+2+3+n-1=n(n-1)/2,证明：用数学归纳法证明h(n)=n(n-1)/2(n2)归纳基础：n=2时，h(2)=2(2-1)/2=1，成立归纳推理：假设n=k(k2)时，h(k)=k(k-1)/2。则h(k+1)=h(k)+k=k(k-1)/2+k=(k(k-1)+2k)/2=k(k+1)/2归纳完成，结论成立。,-12-,第7讲 递归关系,用递归关系构造模型,复合利息。假设一个人在银行的账户上存了10000美元，复合年利息是11%。那么30年后账上将有多少钱？,解：令Pn表示n年后账上的钱。因为n年后的钱等于n-1年后账上的钱加上第n年的利息，所以序列Pn满足递归关系Pn=Pn-1+0.11Pn-1=1.11Pn-1P0=10000P1=1.1110000P2=1.11P1=1.11210000Pn=1.11Pn-1=1.11n10000,证明：下面用数学归纳法验证Pn=1.11n10000的正确性归纳基础：n=0时显然成立归纳推理：假设n=k时，Pk=1.11k10000。那么由递归关系和归纳假设知P k+1=1.11Pk=1.11k+110000归纳完成，结论成立,-13-,第7讲 递归关系,用递归关系构造模型,例3.15汉诺塔：游戏由3根柱子和64个大小不等的金盘组成。开始时，盘子按照大小次序放在第一根柱子上，大盘在下，小盘在上。游戏的规则是，每次把一个盘子从一根柱子移动到另一根柱子上，并且不允许放在比它小的盘子上。游戏的目标是把所有盘子按照大小次序原样搬到第二根柱子上，最大的盘子放在最下面。,-14-,第7讲 递归关系,用递归关系构造模型,解：假设有n个盘子，H(n)表示解n个盘子的汉诺塔问题需要移动的次数。开始时，n个盘子在柱1(1)H(n-1)次移动将柱1的n-1个盘子移到柱3(2)一次移动把最大的盘子移到柱2；(3)H(n-1)次移动把柱3的n-1个盘子移到柱2。H(n)=2H(n-1)+1，初始条件是H(1)=1。H(n)=2H(n-1)+1=2(2H(n-2)+1)+1=22H(n-2)+2+1=23H(n-3)+22+2+1=2n-1H(n-(n-1)+2n-2+22+2+1=2n-1+2n-2+1=2n-1,证明：用数学归纳法证明H(n)=2n-1归纳基础：n=1时，H(1)=21-1=1，成立归纳推理：假设n=k(k1)时,H(k)=2k-1则H(k+1)=2H(k)+1=2(2k-1)+1=2k+1-1,每秒移动一次，用n=64代入，得H(64)=264-1=18,446,744,073,709,551,615 秒=75000亿年。因此这个世界的寿命应该比它已有的寿命还长,-15-,第7讲 递归关系,用递归关系构造模型,兔子和费波那契（Fibonacci）数。一对（一公一母）刚出生的小兔子放到岛上，每对兔子出生两个月后开始繁殖后代，每对兔子每个月可以繁殖一对新的小兔子。假定兔子不会死去，n个月后岛上共有多少对兔子？,解：用F(n)表示n个月后岛上的兔子对数，规定F(0)=0，且已知F(1)=1，F(2)=1。n个月后岛上的兔子对数为前一个月岛上的兔子对数F(n-1)加上第n个月新出生的兔子对数，而这个数等于F(n-2)，因为每对两个月大的兔子都生出一对新兔子。有递归关系F(n)=F(n-1)+F(n-2)(n2)。加上初始条件得该数列即称为费波纳契数列,有多少个n位二进制串不包含两个连续的0？an=an-1+an-2,-16-,第7讲 递归关系,递归关系的求解,在前面的几个问题中，除费波那契数之外的其它问题都可以在求出初始值和递归关系式后迭代求解，找出数列的通项公式。方法是：首先利用递归关系式对关系式右边的表达式进行迭代，并推测解的公式然后用数学归纳法证明得到的公式费波那契数列不易迭代求解，但它有一种更系统的求解方法,-17-,第7讲 递归关系,常系数线性齐次递归关系,定义2（定义3.7）：形如H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k)的递归关系式叫做常系数线性齐次递归关系式。其中c1,c2,ck为常数，ck 0，kn常系数系数c1,c2,ck为不依赖于n的常数线性等式右边为序列项的倍数之和齐次所出现的各项都是H(i)的倍数,H(n)=nH(n-1)不是常系数的 H(n)=H(n-1)+H(n-2)2不是线性的H(n)=2H(n-1)+1不是齐次的,-18-,第7讲 递归关系,特征方程,递归关系式H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k)求解的基本方法是寻找形如an=rn的解，其中r是常数得到 rn-c1rn-1-c2rn-2-ckrn-k=0 rk-c1rk-1-c2rk-2-ck=0定义3（P48）：xk c1xk-1 c2xk-2 ck=0称为递归关系式H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k)的特征方程，其根为该递归关系式的特征根an=rn是递归关系的解，当且仅当r是其特征方程的根,-19-,第7讲 递归关系,常系数线性齐次递归关系的求解,定理1：设c1和c2是实数，方程r2c1rc2=0有两个不等的根r1和r2，那么序列an是递归关系an=c1an-1+c2an-2的解，当且仅当an=b1r1n+b2 r2n，n=0,1,2,，其中b1，b2是常数,证明：（充分性）如果r1和r2是特征方程的根，且b1，b2是常数，那么序列an(an=b1r1n+b2r2n)是递归关系的解。r1、r2是方程r2 c1r c2=0的根 r12=c1r1+c2且r22=c1r2+c2c1an-1+c2an-2=c1(b1r1n-1+b2r2n-1)+c2(b1r1n-2+b2r2n-2)=b1r1n-2(c1r1+c2)+b2r2n-2(c1r2+c2)=b1r1n-2r12+b2r2n-2r22=b1r1n+b2r2n=an 即an(an=b1r1n+b2r2n)是递归关系的解,-20-,第7讲 递归关系,常系数线性齐次递归关系的求解,定理1：设c1和c2是实数，方程r2c1rc2=0有两个不等的根r1和r2，那么序列an是递归关系an=c1an-1+c2an-2的解，当且仅当an=b1r1n+b2 r2n，n=0,1,2,，其中b1，b2是常数,证明：（必要性）如果r1和r2是特征方程的根，且an是满足递归关系an=c1an-1+c2an-2的任一解。那么an都具有an=b1r1n+b2r2n的形式，n=0,1,，b1、b2是常数。数学归纳法证明。(1)归纳基础：对n=0、1，有：a0=G0=b1+b2，a1=G1=b1r1+b2r2。得到(2)归纳推理an=c1an-1+c2an-2=c1(b1r1n-1+b2r2n-1)+c2(b1r1n-2+b2r2n-2)=b1r1n-2(c1r1+c2)+b2r2n-2(c1r2+c2)=b1r1n-2r12+b2r2n-2r22=b1r1n+b2r2n,1、r1r22、特征根是复数仍旧适用,-21-,第7讲 递归关系,常系数线性齐次递归关系的求解,求解费波那契数列的通项公式,解：费波那契数列的递归关系式为F(n)=F(n-1)+F(n-2)(n2)，其特征方程x2-x-1=0有两个不等的特征根q1=，q2=。根据定理，该递归关系式有通解F(n)=c1+c2，c1,c2为常数。F(0)=0，F(1)=1 解得c1=，c2=费波那契数列的通项公式为F(n)=,-22-,第7讲 递归关系,常系数线性齐次递归关系的求解,例3.17 某人有n(n1)元钱，他每天买一次物品，或者买一元钱的甲物品，或者买两元钱的乙物品或丙物品。问此人有多少种方式花完这n元钱？,解：设花完这n元钱有H(n)种方式。可分三种情况：（1）第一天买甲物品，共有H(n-1)种方式花完剩余的钱；（2）第一天买乙物品，有H(n-2)种方式花完剩余的钱；（3）第一天买丙物品，有H(n-2)种方式花完剩余的钱。根据加法原理，有H(n)=H(n-1)+2 H(n-2)(n3)该递归关系的特征方程为x2-x-2=0，有两个不等的特征根q1=2，q2=1，所以其通解为H(n)=c12n+c2(1)n又H(1)=1，H(2)=3 解得c1=2/3，c2=1/3H(n)=2/32n+1/3(1)n,-23-,第7讲 递归关系,常系数线性齐次递归关系的求解,例3.18 求解递归关系式H(0)=1H(1)=3H(n)=4H(n-1)4H(n-2)(n2),解：递归关系式的特征方程是 x2-4x+4=0 解之，得到两个重根x1=2,x2=2,于是递归关系式的通解 将初始值H(0)=1，H(1)=3代入得一个矛盾的方程组求解失败，显然，必须改进上述方法。,-24-,第7讲 递归关系,常系数线性齐次递归关系的求解,定理2：设c1和c2是实数，方程r2c1rc2=0只有一个根r0，那么序列an是递归关系an=c1an-1+c2an-2的解，当且仅当an=b1r0n+b2 nr0n，n=0,1,2,，其中b1，b2是常数,求：具有初始条件a0=1和a1=6的递推关系an=6an-1-9an-2,解：r2-6r+9=0唯一的根是r3 递推关系的解是：an=b13n+b2n3n，其中b1和b2是常数使用初始条件得到a0=1=b1a1=6=b1*3+b2*1*3得到b1=1,b2=1得到：an=3n+n3n,-25-,第7讲 递归关系,常系数线性齐次递归关系的求解,例3.19(例3.18续)求解递归关系式H(0)=1H(1)=3H(n)=4H(n-1)4H(n-2)(n2),解：由于特征方程有两个重根2，所以根据上面定理，其通解为 H(n)=(c1+c2n)2n 由H(0)=1，H(1)=3代入得 解得c1=1，c2=0.5 通解为H(n)=(1+n/2)2n,-26-,第7讲 递归关系,常系数线性齐次递归关系的求解,定理3.18 设q是一个非零的实数或复数，那么，是递归关系式 的解当且仅当q是它的一个特征根。证:若 是递归关系式的解，那么由于 因此，也就是说q是它的特征方程 的一个特征根。另一方面，上述推理过程是可逆的，故定理得证。,-27-,第7讲 递归关系,常系数线性齐次递归关系的求解,定理3.19 设 是非零实数或复数，那么，是递归关系式的解当且仅当 是它的k个不同的特征根。,-28-,第7讲 递归关系,常系数线性齐次递归关系的求解,定理3.20 设 是非零实数或复数，它们是递归关系式 的特征方程的t个不同的特征根，各有 重。那么该递归关系式的一般解是 其中,注意系数的变化,需要加多少项，视根qi的重数而定,-29-,第7讲 递归关系,常系数线性齐次递归关系的求解,例3.20 求解递归关系式H(0)=1H(1)=0H(2)=1H(3)=2H(n)=H(n-1)+3H(n-2)+5H(n-3)+2H(n-4)(n4),-30-,第7讲 递归关系,常系数线性齐次递归关系的求解,解：递归关系式的特征方程为x4+x3-3x2-5x-2=0，其根为x1=1，x2=1，x3=1，x4=2。递归关系式通解为H(n)=(c1+c2n+c3n2)(1)n+c42n代入初始条件，得 解得c1=7/9，c2=-1/3，c3=0，c4=2/9通解为H(n)=(7/9 n/3)(1)n+2n+1/9,H(0)=1H(1)=0H(2)=1H(3)=2,-31-,第7讲 递归关系,本讲小结,主要内容递归关系的定义用递归关系构造模型的技术常系数线性齐次递归关系的求解方法重点掌握递归关系和常系数线性齐次递归关系的求解方法能够针对要求解的问题建立递归关系式，学会利用递归关系式解决一些重要的计数问题作业P54-55.1（1）、（3），3选做9，10,