离散第7讲 递归关系

1、 计算机专业基础课程计算机专业基础课程-2-第第7讲讲 递归关系递归关系v回顾回顾定义定义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讲讲 递归关系递归关系v回顾回顾 (1) Dn = (n-1)(Dn-2+Dn-1) (2) Dn = nDn-1+(-1)n a1=i ai=1 证.(1) 设设1，2，3，n的一个错置是的一个错置是

2、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-第

3、第7讲讲 递归关系递归关系vPowerPoint Template_Sub 1计数基本原理计数基本原理2排列与组合排列与组合3重集的排列与组合重集的排列与组合4递归关系递归关系v递归关系递归关系Textbook Page 44 to 54离散数学离散数学第第7 7讲讲-6-第第7讲讲 递归关系递归关系v内容提要内容提要递归关系递归关系递归关系的定义和实例递归关系的定义和实例用递归关系构造模型用递归关系构造模型用递归关系为实际问题建模用递归关系为实际问题建模递归关系的迭代求解递归关系的迭代求解常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解 什么是常系数线性齐次递归关系什么是常系数线性齐

4、次递归关系常系数线性齐次递归关系的特征根求解方法常系数线性齐次递归关系的特征根求解方法-7-第第7讲讲 递归关系递归关系v前言前言有多少个有多少个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位二进制串加上位

5、二进制串加上10组成的，有组成的，有an-2个个对以对以1结尾的情况：结尾的情况：是任何不含是任何不含2个连续个连续0的的n1位二进制串加上位二进制串加上1组成的，有组成的，有an-1个个 an = an-1 + an-2这个等式叫做这个等式叫做递归关系递归关系，和初始条件一起唯一地确定了序列，和初始条件一起唯一地确定了序列an。递归关系是求解组合数学问题的重要递归关系是求解组合数学问题的重要工具，几乎在所有的数学分支中都有工具，几乎在所有的数学分支中都有重要应用重要应用.许多计数问题用上一章讨论的方法不许多计数问题用上一章讨论的方法不易求解，但可以通过找到易求解，但可以通过找到序列的项之序列

6、的项之间的关系间的关系间接求解间接求解.-8-第第7讲讲 递归关系递归关系v递归关系递归关系(recurrence relation)(recurrence relation)定义定义1：关于序列关于序列an的的递归关系递归关系是一个等式，它把是一个等式，它把an用序列中排在用序列中排在an前面的一项或多项来表示。如果前面的一项或多项来表示。如果一个序列的项满足某个递归关系，这个序列就叫做一个序列的项满足某个递归关系，这个序列就叫做该递归关系的该递归关系的解解(或或通项通项,通项公式通项公式)。-9-第第7讲讲 递归关系递归关系v递归关系举例递归关系举例确定序列确定序列an是否为递归关系是否为

7、递归关系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)假设对每一个非负整数假设对每一个

8、非负整数n，an=5。对对n2，有，有2an-1an-2 = 25-5 = 5 = an，因此因此an=5是该递归关系的解是该递归关系的解-10-第第7讲讲 递归关系递归关系v说明说明序列的初始条件说明了在递归关系起作用的首序列的初始条件说明了在递归关系起作用的首项之前的那些项项之前的那些项递归关系和初始条件唯一地确定一个序列递归关系和初始条件唯一地确定一个序列，这，这是因为一个递归关系和初始条件一起提供了这是因为一个递归关系和初始条件一起提供了这个序列的递归定义个序列的递归定义只要使用足够多次，序列的任意一项都可以从只要使用足够多次，序列的任意一项都可以从初始条件开始通过递归关系求出初始条件

9、开始通过递归关系求出但对于某些但对于某些特定类型特定类型的序列，可以有的序列，可以有更好的办更好的办法法通过它的递归关系和初始条件来通过它的递归关系和初始条件来计算它的通计算它的通项项-11-第第7讲讲 递归关系递归关系v用递归关系构造模型用递归关系构造模型例例3.14 平面上平面上n条直线两两相交，且没有任何三条条直线两两相交，且没有任何三条直线交于一点，求共有多少个交点？直线交于一点，求共有多少个交点？解：解：设设n(n2)条直线的交点数目条直线的交点数目为为h(n)。如果增加第如果增加第n+1条直线，它将与条直线，它将与前前n条直线相交产生条直线相交产生n个交点个交点h(n+1)=h(n

10、)+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归纳完成，结论成立。归纳完成，结论成立。-1

11、2-第第7讲讲 递归关系递归关系v用递归关系构造模型用递归关系构造模型复合利息。假设一个人在银行的账户上存了复合利息。假设一个人在银行的账户上存了10000美元，复合年利息是美元，复合年利息是11%。那么。那么30年后账上将有多年后账上将有多少钱？少钱？解：解：令令Pn表示表示n年后账上的钱。年后账上的钱。因为因为n年后的钱等于年后的钱等于n-1年后账年后账上的钱加上第上的钱加上第n年的利息，所年的利息，所以序列以序列Pn满足递归关系满足递归关系Pn=Pn-1+0.11Pn-1=1.11Pn-1P0=10000P1=1.11 10000P2=1.11P1=1.112 10000Pn=1.11P

12、n-1=1.11n 10000 证明：证明：下面用数学归纳法验证下面用数学归纳法验证Pn=1.11n 10000的正确性的正确性归纳基础：归纳基础：n=0时显然成立时显然成立归纳推理：归纳推理：假设假设n=k时，时，Pk=1.11k 10000。那么由递归关系和归纳假设知那么由递归关系和归纳假设知P k+1=1.11Pk=1.11k+1 10000归纳完成，结论成立归纳完成，结论成立 -13-第第7讲讲 递归关系递归关系v用递归关系构造模型用递归关系构造模型 例例3.15汉诺塔：游戏由汉诺塔：游戏由3根柱子和根柱子和64个大小不等的金盘组成。开个大小不等的金盘组成。开始时，盘子按照大小次序放在

13、第一根柱子上，大盘在下，小盘始时，盘子按照大小次序放在第一根柱子上，大盘在下，小盘在上。游戏的规则是，每次把一个盘子从一根柱子移动到另一在上。游戏的规则是，每次把一个盘子从一根柱子移动到另一根柱子上，并且不允许放在比它小的盘子上。游戏的目标是把根柱子上，并且不允许放在比它小的盘子上。游戏的目标是把所有盘子按照大小次序原样搬到第二根柱子上，最大的盘子放所有盘子按照大小次序原样搬到第二根柱子上，最大的盘子放在最下面。在最下面。-14-第第7讲讲 递归关系递归关系v用递归关系构造模型用递归关系构造模型解：解：假设有假设有n个盘子，个盘子，H(n)表示解表示解n个盘子个盘子的汉诺塔问题需要移动的次数。

14、开始时，的汉诺塔问题需要移动的次数。开始时，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证明：证明：用数学归纳

15、法证明用数学归纳法证明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讲讲 递归关系递归关系v用递归关系构造模型用递归关系构造模型兔子和兔子和费波那契（

16、费波那契（Fibonacci）数）数。一对（一公一母）刚出生。一对（一公一母）刚出生的小兔子放到岛上，每对兔子出生两个月后开始繁殖后代，的小兔子放到岛上，每对兔子出生两个月后开始繁殖后代，每对兔子每个月可以繁殖一对新的小兔子。假定兔子不会死每对兔子每个月可以繁殖一对新的小兔子。假定兔子不会死去，去，n个月后岛上共有多少对兔子？个月后岛上共有多少对兔子？解：解：用用F(n)表示表示n个月后岛上的兔子对数，规个月后岛上的兔子对数，规定定F(0)=0，且已知，且已知F(1)=1，F(2)=1。n个月后岛上的兔子对数为前一个月岛上的个月后岛上的兔子对数为前一个月岛上的兔子对数兔子对数F(n-1)加上第

17、加上第n个月新出生的兔子对个月新出生的兔子对数，而这个数等于数，而这个数等于F(n-2)，因为每对两个月，因为每对两个月大的兔子都生出一对新兔子。大的兔子都生出一对新兔子。有递归关系有递归关系F(n)= F(n-1)+F(n-2) (n2)。加上初始条件得加上初始条件得该数列即称为该数列即称为费波纳契数列费波纳契数列)2() 1()(1) 1 (0)0(nFnFnFFF有多少个有多少个n位二位二进制串不包含两进制串不包含两个连续的个连续的0？ an = an-1 + an-2-16-第第7讲讲 递归关系递归关系v递归关系的求解递归关系的求解在前面的几个问题中，除费波那契数之外的其它问在前面的几

18、个问题中，除费波那契数之外的其它问题都可以在求出初始值和递归关系式后题都可以在求出初始值和递归关系式后迭代求解迭代求解，找出数列的通项公式。方法是：找出数列的通项公式。方法是：首先利用递归关系式对关系式右边的表达式进行迭代，首先利用递归关系式对关系式右边的表达式进行迭代，并推测解的公式并推测解的公式然后用数学归纳法证明得到的公式然后用数学归纳法证明得到的公式费波那契数列不易迭代求解，但它有一种更系统的费波那契数列不易迭代求解，但它有一种更系统的求解方法求解方法-17-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系常系数线性齐次递归关系定义定义2（定义（定义3.7）：形如形如H(n)=c1

19、H(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讲讲 递归关系递归关系v特征方程特征

20、方程递归关系式递归关系式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是递归关系的解，当且仅当是递归

21、关系的解，当且仅当r是其特征方程的根是其特征方程的根-19-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解定理定理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(a

22、n = 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讲讲 递归关系递归关

23、系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解定理定理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

24、的形的形式，式，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 212011rrrGGb211102rrGrGb1、r1

25、r22、特征根是复数仍旧适用、特征根是复数仍旧适用-21-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解求解费波那契数列的通项公式求解费波那契数列的通项公式解：费波那契数列的递归关系式为费波那契数列的递归关系式为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=费波那契数列的通项公式为费波那契数列的通项

26、公式为F(n)= 251 251 n)251(n)251(125125102121cccc515151n)251(51n)251(-22-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解例例3.17 某人有某人有n(n1)元钱，他每天买一次物品，或者买一元元钱，他每天买一次物品，或者买一元钱的甲物品，或者买两元钱的乙物品或丙物品。问此人有多钱的甲物品，或者买两元钱的乙物品或丙物品。问此人有多少种方式花完这少种方式花完这n元钱？元钱？解：解：设花完这设花完这n元钱有元钱有H(n)种方式。可分三种情况：（种方式。可分三种情况：（1）第一天）第一天买甲物品，共有

27、买甲物品，共有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

28、/3H(n) = 2/32n + 1/3(1)n -23-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解例例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代入得一个矛盾的方程组代入得一个矛盾的方程组求解失败，显然，必须改进上述方法求解失败，显然，必须改进

29、上述方法 。nnnncccccnH22)(22)(21211c32 c -24-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解定理定理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

30、= 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讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解例例3.19(例例3.18续续) 求解递归关系式求解递归关系式H(0) = 1H(1) = 3H(n) = 4H(n-1) 4H(n-2) (n2)解：解：由于特征方程有两个重根由于特征方程有两个重根2，所以根据上面定理，其通，所以根据上面定理，

31、其通解为解为 H(n) = (c1 + c2n) 2n 由由H(0) = 1，H(1) = 3代入得代入得 解得解得c1= 1，c2= 0.5 通解为通解为H(n) =(1 + n /2) 2n 3)(21211ccc-26-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解定理定理3.18 设设q是一个非零的实数或复数，那么，是一个非零的实数或复数，那么， 是递归关系式是递归关系式 的解当且仅当的解当且仅当q是它的一个特征根。是它的一个特征根。 证证:若若 是递归关系式的解，那么是递归关系式的解，那么由于由于 因此，因此， ，也就是说，也就是说q是它的特征

32、方程是它的特征方程 的一个的一个特征根。特征根。另一方面，上述推理过程是可逆的，故定理得证。另一方面，上述推理过程是可逆的，故定理得证。nqnH)(0)()2() 1()(21knHbnHbnHbnHk)0,(kbnknqnH)(02211knknnnqbqbqbq0)(2211kkknkknbqbqbqq 0q02211kkkkbqbqbq02211kkkkbxbxbx-27-第第7讲讲 递归关系递归关系v常系数线性齐次递归关系的求解常系数线性齐次递归关系的求解定理定理3.19 设设 是非零实数或复数，那么，是非零实数或复数，那么， 是递归关系式是递归关系式的解当且仅当的解当且仅当 是它的是它的k个个不同不同的特征根。的特征根。 kqqq,21nkknnqcqcqcnH2211)(nkknnqcqcqcnH2211)(),(21为确定的常数kccc0)()2() 1()(21knHbnHbnHbnHk)0,(kbnk 0)()2() 1()(21knHbnHbnHbnHk)0,(kbnk kqqq,21-28-第第7讲讲 递归关系递归关系v常系