离散递归关系.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机专业基础课程,授课人：张桂芸,dyxy1999,回顾,定义,3.5,：,集合,1,，,2,，,3,，,，,n,的全排列，使得每个数,i,都不在第,i,位上，称这样的排列为,1,，,2,，,3,，,，,n,的一个,错置,。,定理,3.15,：,集合,1,，,2,，,3,，,，,n,的错置的总数,(,记为,D,n,),是,约定,D,0,=,1,。,定理,3.16,2,回顾,(1)D,n,=(n-1)(D,n-2,+D,n-1,),(2)D,n,=nD,n-1,+(-1),n,a,1,=i a,i,1,证,.(1),设,1,，,2,，,3,，,，,n,的一个错置是,a,1,a,2,a,k,a,n,，因为,a,1,1,，所以,a,1,有,n-1,种取法。设,a,1,=i(2in),，分两种情况讨论：,(1.1)a,i,=1,。这时取决于其余,n-2,个数的错置，这些错置的数目是,D,n-2,。,(1.2)a,i,1,。这时取决于其余,n-1,个数的错置：“,1,不可放置在第,i,位，其它各数,j,不可放置在第,j,位”，这些错置的数目是,D,n-1,。,因此，由加法原理和乘法原理,D,n,=(n-1)(D,n-2,+D,n-1,),递归关系,3,PowerPoint Template_Sub,1,计数基本原理,2,排列与组合,3,重集的排列与组合,第,3,章 组合论基础,-,计数,4,递归关系,4,递归关系,Textbook Page 44 to 54,离散数学,第,7,讲,内容提要,递归关系,递归关系的定义和实例,用递归关系构造模型,用递归关系为实际问题建模,递归关系的迭代求解,常系数线性齐次递归关系的求解,什么是常系数线性齐次递归关系,常系数线性齐次递归关系的特征根求解方法,6,前言,有多少个n位二进制串不包含两个连续的0？,解：,令,a,n,表示这样的,n,位二进制串数，,a,1,=2,(0,1),a,2,=3,(,00,01,10,11),a,3,=5 (,000,001,010,011,100,101,110,111)(,010,110,011,101,111,),a,n,分为以,0,和以,1,结尾,两种情况,对以,0,结尾的情况：,是任何不含,2,个连续,0,的,n,2,位二进制串加上,10,组成的，有,a,n-2,个,对以,1,结尾的情况：,是任何不含,2,个连续,0,的,n,1,位二进制串加上,1,组成的，有,a,n-1,个,a,n,=a,n-1,+a,n-2,这个等式叫做,递归关系,，和初始条件一起唯一地确定了序列,a,n,。,递归关系是求解组合数学问题的重要工具，几乎在所有的数学分支中都有重要应用,.,许多计数问题用上一章讨论的方法不易求解，但可以通过找到,序列的项之间的关系,间接求解,.,7,递归关系(recurrence relation),定义,1,：,关于序列,a,n,的,递归关系,是一个等式，它把,a,n,用序列中排在,a,n,前面的一项或多项来表示。如果一个序列的项满足某个递归关系，这个序列就叫做该递归关系的,解,(,或,通项,通项公式,),。,8,递归关系举例,确定序列,a,n,是否为递归关系,a,n,=2a,n-1,a,n-2,(n=2,3,4,),的解，这里,a,n,=3n,，,n,是非负整数。若,a,n,=2,n,或,a,n,=5,呢？,解：,(1),假设对每一个非负整数,n,，,a,n,=3n,。,对,n2,，可看出,2a,n-1,a,n-2,=23(n-1)-3(n-2)=6n-6-3n+6=3n=a,n,a,n,=3n,是该递归关系的解,(2),假设对每一个非负整数,n,，,a,n,=2,n,。,a,0,=1,，,a,1,=2,，,a,2,=4,，,2a,1,a,0,=22-1=3a,2,a,n,=2,n,不是该递归关系的解,(3),假设对每一个非负整数,n,，,a,n,=5,。,对,n2,，有,2a,n-1,a,n-2,=25-5=5=a,n,，,因此,a,n,=5,是该递归关系的解,9,说明,序列的初始条件说明了在递归关系起作用的首项之前的那些项,递归关系和初始条件唯一地确定一个序列,，这是因为一个递归关系和初始条件一起提供了这个序列的递归定义,只要使用足够多次，序列的任意一项都可以从初始条件开始通过递归关系求出,但对于某些,特定类型,的序列，可以有,更好的办法,通过它的递归关系和初始条件来,计算它的通项,10,用递归关系构造模型,例,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)+n3+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,归纳完成，结论成立。,11,用递归关系构造模型,复合利息。假设一个人在银行的账户上存了10000美元，复合年利息是11%。那么30年后账上将有多少钱？,解：,令,P,n,表示,n,年后账上的钱。因为,n,年后的钱等于,n-1,年后账上的钱加上第,n,年的利息，所以序列,P,n,满足递归关系,P,n,=P,n-1,+0.11P,n-1,=1.11P,n-1,P,0,=10000,P,1,=1.11,10000,P,2,=1.11P,1,=1.11,2,10000,P,n,=1.11P,n-1,=1.11,n,10000,证明：,下面用数学归纳法验证,P,n,=1.11,n,10000,的正确性,归纳基础：,n=0,时显然成立,归纳推理：,假设,n=k,时，,P,k,=1.11,k,10000,。,那么由递归关系和归纳假设知,P,k+1,=1.11P,k,=1.11,k+1,10000,归纳完成，结论成立,12,用递归关系构造模型,例,3.15,汉诺塔：游戏由,3,根柱子和,64,个大小不等的金盘组成。开始时，盘子按照大小次序放在第一根柱子上，大盘在下，小盘在上。游戏的规则是，每次把一个盘子从一根柱子移动到另一根柱子上，并且不允许放在比它小的盘子上。游戏的目标是把所有盘子按照大小次序原样搬到第二根柱子上，最大的盘子放在最下面。,13,用递归关系构造模型,解：,假设有,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=2,2,H(n-2)+2+1=2,3,H(n-3)+2,2,+2+1,=2,n-1,H(n-(n-1)+2,n-2,+2,2,+2+1,=2,n-1,+2,n-2,+1,=2,n,-1,证明：,用数学归纳法证明,H(n)=2,n,-1,归纳基础：,n=1,时，,H(1)=2,1,-1=1,，成立,归纳推理：,假设,n=k(k1),时,H(k)=2,k,-1,则,H(k+1)=2H(k)+1=2(2,k,-1)+12,k+1-,1,每秒移动一次，用,n=64,代入，得,H(64)=2,64,-1,=18,446,744,073,709,551,615,秒,=75000,亿年。,因此这个世界的寿命应该比它已有的寿命还长,14,用递归关系构造模型,兔子和,费波那契（,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,？,a,n,=a,n-1,+a,n-2,15,递归关系的求解,在前面的几个问题中，除费波那契数之外的其它问题都可以在求出初始值和递归关系式后,迭代求解,，找出数列的通项公式。方法是：,首先利用递归关系式对关系式右边的表达式进行迭代，并推测解的公式,然后用数学归纳法证明得到的公式,费波那契数列不易迭代求解，但它有一种更系统的求解方法,16,常系数线性齐次递归关系,定义,2,（定义,3.7,）,：,形如,H(n)=c,1,H(n-1)+c,2,H(n-2)+c,k,H(n-k),的递归关系式叫做,常系数,线性,齐次,递归关系式,。其中,c,1,c,2,c,k,为常数，,c,k,0,，,kn,常系数,系数,c,1,c,2,c,k,为不依赖于,n,的常数,线性,等式右边为序列项的倍数之和,齐次,所出现的各项都是,H(i),的倍数,H(n)=nH(n-1),不是常系数的,H(n)=H(n-1)+H(n-2),2,不是线性的,H(n)=2H(n-1)+1,不是齐次的,17,特征方程,递归关系式,H(n)=c,1H(n-1)+c,2,H(n-2)+c,k,H(n-k),求解的基本方法是寻找形如,a,n,=r,n,的解，其中,r,是常数,得到,r,n,-c,1,r,n-1,-c,2,r,n-2,-c,k,r,n-k,=0,r,k,-c,1,r,k-1,-c,2,r,k-2,-c,k,=0,定义,3,（,P48,）,：,x,k,c,1,x,k-1,c,2,x,k-2,c,k,=0,称为递归关系式,H(n)=c,1,H(n-1)+c,2,H(n-2)+c,k,H(n-k),的,特征方程,，,其根为该递归关系式的,特征根,a,n,=r,n,是递归关系的解，当且仅当,r,是其特征方程的根,18,常系数线性齐次递归关系的求解,定理,1,：,设,c,1,和,c,2,是实数，方程,r,2,c,1,rc,2,=0,有两个不等的根,r,1,和,r,2,，那么序列,a,n,是递归关系,a,n,=c,1,a,n-1,+c,2,a,n-2,的解，当且仅当,a,n,=b,1,r,1,n,+b,2,r,2,n,，,n=0,1,2,，其中,b,1,，,b,2,是常数,证明：（充分性）,如果,r,1,和,r,2,是特征方程的根，且,b,1,，,b,2,是常数，那么序列,a,n,(a,n,=b,1,r,1,n,+b,2,r,2,n,),是递归关系的解,。,r,1,、,r,2,是方程,r,2,c,1,r c,2,=0,的根 r,1,2,=c,1,r,1,+c,2,且,r,2,2,=c,1,r,2,+c,2,c,1,a,n-1,+c,2,a,n-2,=c,1,(b,1,r,1,n-1,+b,2,r,2,n-1,)+c,2,(b,1,r,1,n-2,+b,2,r,2,n-2,),=b,1,r,1,n-2,(c,1,r,1,+c,2,)+b,2,r,2,n-2,(c,1,r,2,+c,2,),=b,1,r,1,n-2,r,1,2,+b,2,r,2,n-2,r,2,2,=b,1,r,1,n,+b,2,r,2,n,=a,n,即,a,n,(a,n,=b,1,r,1,n,+b,2,r,2,n,),是递归关系的解,19,常系数线性齐次递归关系的求解,定理,1,：,设,c,1,和,c,2,是实数，方程,r,2,c,1,rc,2,=0,有两个不等的根,r,1,和,r,2,，那么序列,a,n,是递归关系,a,n,=c,1,a,n-1,+c,2,a,n-2,的解，当且仅当,a,n,=b,1,r,1,n,+b,2,r,2,n,，,n=0,1,2,，其中,b,1,，,b,2,是常数,证明：（必要性）,如果,r,1,和,r,2,是特征方程的根，且,a,n,是满足递归关系,a,n,=c,1,a,n-1,+c,2,a,n-2,的任一解。那么,a,n,都具有,a,n,=b,1,r,1,n,+b,2,r,2,n,的形式，,n=0,1,，b,1,、,b,2,是常数。数学归纳法证明。,(1),归纳基础：,对,n=0,、,1,，有：,a,0,=G,0,=b,1,+b,2,，,a,1,=G,1,=b,1,r,1,+b,2,r,2,。,得到,(2),归纳推理,a,n,=c,1,a,n-1,+c,2,a,n-2,=c,1,(b,1,r,1,n-1,+b,2,r,2,n-1,)+c,2,(b,1,r,1,n-2,+b,2,r,2,n-2,),=b,1,r,1,n-2,(c,1,r,1,+c,2,)+b,2,r,2,n-2,(c,1,r,2,+c,2,),=b,1,r,1,n-2,r,1,2,+b,2,r,2,n-2,r,2,2,=b,1r,1,n,+b,2,r,2,n,1,、,r,1,r,2,2,、特征根是复数仍旧适用,20,常系数线性齐次递归关系的求解,求解费波那契数列的通项公式,解：,费波那契数列的递归关系式为,F(n)=F(n-1)+F(n-2)(n2),，其特征方程,x,2,-x-1=0,有两个不等的特征根,q,1,=,，,q,2,=,。,根据定理，该递归关系式有通解,F(n)=c,1,+c,2,，,c,1,c,2,为常数。,F(0)=0,，,F(1)=1,解得,c,1,=,，,c,2,=,费波那契数列的通项公式为,F(n)=,21,常系数线性齐次递归关系的求解,例,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),该递归关系的特征方程为,x,2,-x-2=0,，有两个不等的特征根,q,1,=2,，,q,2,=,1,，所以其通解为,H(n)=c,1,2,n,+c,2,(,1),n,又,H(1)=1,，,H(2)=3,解得,c,1,=2/3,，,c,2,=1/3,H(n)=2/32,n,+1/3(,1),n,22,常系数线性齐次递归关系的求解,例,3.18,求解递归关系式,H(0)=1,H(1)=3,H(n)=4H(n-1)4H(n-2)(n2),解：,递归关系式的特征方程是,x,2,-4x+4=0,解之，得到两个重根,x,1,=2,x,2,=2 ,于是递归关系式的通解,将初始值,H(0)=1,，,H(1)=3,代入得一个矛盾的方程组,求解失败，显然，必须改进上述方法。,23,常系数线性齐次递归关系的求解,定理,2,：,设,c,1,和,c,2,是实数，方程,r,2,c,1,rc,20,只有,一个根,r,0,，那么序列,a,n,是递归关系,a,n,=c,1,a,n-1,+c,2,a,n-2,的解，当且仅当,a,n,=b,1,r,0,n,+b,2,nr,0,n,，,n=0,1,2,，其中,b,1,，,b,2,是常数,求：具有初始条件,a,0,=1,和,a,1,=6,的递推关系,a,n,=6a,n-1,-9a,n-2,解：,r,2,-6r+9=0,唯一的根是,r,3,递推关系的解是：,a,n,=b,1,3,n,+b,2,n3,n,，其中,b,1,和,b,2,是常数,使用初始条件得到,a,0,=1=b,1,a,1,=6=b,1,*3+b,2,*1*3,得到,b,1,=1,b2,=1,得到：,a,n,=3,n,+n3,n,24,常系数线性齐次递归关系的求解,例,3.19(,例,3.18,续,),求解递归关系式,H(0)=1,H(1)=3,H(n)=4H(n-1)4H(n-2)(n2),解：,由于特征方程有两个重根,2,，所以根据上面定理，其通解为,H(n)=(c,1,+c,2,n)2,n,由,H(0)=1,，,H(1)=3,代入得,解得,c,1,=1,，,c,2,=0.5,通解为,H(n)=(1+n/2)2,n,25,常系数线性齐次递归关系的求解,定理,3.18,设,q,是一个非零的实数或复数，那么，是递归关系式,的解当且仅当,q,是它的一个特征根。,证,:,若 是递归关系式的解，那么,由于 因此，也就是说,q,是它的特征方程 的一个特征根。,另一方面，上述推理过程是可逆的，故定理得证。,26,常系数线性齐次递归关系的求解,定理,3.19,设 是非零实数或复数，那么，,是递归关系式,的解当且仅当 是它的,k,个,不同,的特征根。,27,常系数线性齐次递归关系的求解,定理,3.20,设 是非零实数或复数，它们是递归关系式,的特征方程的,t,个,不同,的特征根，各有 重。那么该递归关系式的一般解是,其中,注意系数的变化,需要加多少项，视根,q,i,的重数而定,28,常系数线性齐次递归关系的求解,例,3.20,求解递归关系式,H(0)=1,H(1)=0,H2)=1,H(3)=2,H(n)=H(n-1)+3H(n-2)+5H(n-3)+2H(n-4)(n4),29,常系数线性齐次递归关系的求解,解：,递归关系式的特征方程为,x,4,+x,3,-3x,2,-5x-2=0,，其根为,x,1,=,1,，,x,2,=,1,，,x,3,=,1,，,x,4,=2,。,递归关系式通解为,H(n)=(c,1,+c,2,n+c,3,n,2,)(,1),n,+c,4,2,n,代入初始条件，得,解得,c,1,=7/9,，,c,2,=-1/3,，,c,3,=0,，,c,4,=2/9,通解为,H(n)=(7/9,n/3)(,1),n,+2,n+1,/9,H(0)=1,H(1)=0,H(2)=1,H(3)=2,30,本讲小结,主要内容,递归关系的定义,用递归关系构造模型的技术,常系数线性齐次递归关系的求解方法,重点,掌握递归关系和常系数线性齐次递归关系的求解方法,能够针对要求解的问题建立递归关系式，学会利用递归关系式解决一些重要的计数问题,作业,P54-55.1,（,1,）、（,3,），,3,选做,9,，,10,31,