离散第07讲 递归关系-2综述

《离散第07讲 递归关系-2综述》由会员分享，可在线阅读，更多相关《离散第07讲 递归关系-2综述（38页珍藏版）》请在金锄头文库上搜索。

1、 计算机专业基础课程 v回顾 定义3.5：集合1，2，3，n的全排列，使得每个数i都不 在第i位上，称这样的排列为1，2，3，n的一个错置。 定理3.15：集合1，2，3，n的错置的总数(记为 Dn)是 约定D0 =1 。 定理3.16 2 第6讲 重集的排列与组合 v回顾 (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) ai=1 。这时取决于其余n-2个数的错置，这些错置的数目是Dn

2、-2 。 2) ai1 。这时取决于其余n-1个数的错置：“1不可放置在第i位，其 它各数j不可放置在第j位”，这些错置的数目是Dn-1 。 因此，由加法原理和乘法原理Dn=(n-1)(Dn-2+Dn-1) 递归关系 3 第6讲 重集的排列与组合 vPowerPoint Template_Sub 1计数基本原理 2排列与组合 3重集的排列与组合 第第3 3章章 组组组组合合论论论论基基础础础础-计计计计数数 4 递归关系 4 第6讲 重集的排列与组合 v递归关系 Textbook Page 44 to 54 离散数学第7讲 v内容提要 递归关系 递归关系的定义和实例 用递归关系构造模型 用递归

3、关系为实际问题建模 递归关系的迭代求解 常系数线性齐次递归关系的求解 什么是常系数线性齐次递归关系 常系数线性齐次递归关系的特征根求解方法 6 第6讲 重集的排列与组合 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位二进制串加上 10组成的，有an-2个a1a2a3an-2(an-1=1)(

4、an=0) 对以1结尾的情况：是任何不含2个连续0的n1位二进制串加上1 组成的，有an-1个a1a2a3an-2(an-1=1或0)(an=1) an = an-1 + an-2 这个等式叫做递归关系，和初始条件一起唯一地确定了序列an 。 递归关系是求解组合数学问题的重要 工具，几乎在所有的数学分支中都有 重要应用. 许多计数问题用上一章讨论的方法不 易求解，但可以通过找到序列的项之 间的关系间接求解. 7 第6讲 重集的排列与组合 v递归关系(recurrence relation) 定义1：关于序列an的递归关系是一个等式，它把 an用序列中排在an前面的一项或多项来表示。如果 一个序

5、列的项满足某个递归关系，这个序列就叫做 该递归关系的解(或通项,通项公式)。 8 第6讲 重集的排列与组合 v递归关系举例 确定序列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 = an an=3n是该递归关系的解 (2)假设对每一个非负整数n，an=2n。 a0=1，a1=2，a2=4，2a1a0 = 22-1 = 3a2 an=2n不是该递归关系的

6、解 (3)假设对每一个非负整数n，an=5。 对n2，有2an-1an-2 = 25-5 = 5 = an， 因此an=5是该递归关系的解 9 第6讲 重集的排列与组合 v说明 序列的初始条件说明了在递归关系起作用的首项 之前的那些项 递归关系和初始条件唯一地确定一个序列，这是 因为一个递归关系和初始条件一起提供了这个序 列的递归定义 只要使用足够多次，序列的任意一项都可以从初 始条件开始通过递归关系求出 但对于某些特定类型的序列，可以有更好的办法 通过它的递归关系和初始条件来计算它的通项 10 第6讲 重集的排列与组合 v用递归关系构造模型 例3.14 平面上n条直线两两相交，且没有任何三条

7、 直线交于一点，求共有多少个交点？ 解：设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

8、 = k(k-1)/2+k = (k(k-1)+2k)/2 = k(k+1)/2 归纳完成，结论成立。 11 第6讲 重集的排列与组合 v用递归关系构造模型 复合利息。假设一个人在银行的账户上存了10000 美元，复合年利息是11%。那么30年后账上将有多 少钱？ 解：令Pn表示n年后账上的钱。 因为n年后的钱等于n-1年后账 上的钱加上第n年的利息，所以 序列Pn满足递归关系 Pn=Pn-1+0.11Pn-1=1.11Pn-1 P0=10000 P1=1.1110000 P2=1.11P1=1.11210000 Pn=1.11Pn-1=1.11n10000 证明：下面用数学归纳法验证 Pn=

9、1.11n10000的正确性 归纳基础：n=0时显然成立 归纳推理： 假设n=k时，Pk=1.11k10000。 那么由递归关系和归纳假设知 P k+1=1.11Pk=1.11k+110000 归纳完成，结论成立 12 第6讲 重集的排列与组合 v用递归关系构造模型 例3.15汉诺塔：游戏由3根柱子和64个大小不等的金盘组成。开 始时，盘子按照大小次序放在第一根柱子上，大盘在下，小盘 在上。游戏的规则是，每次把一个盘子从一根柱子移动到另一 根柱子上，并且不允许放在比它小的盘子上。游戏的目标是把 所有盘子按照大小次序原样搬到第二根柱子上，最大的盘子放 在最下面。 13 第6讲 重集的排列与组合

10、v用递归关系构造模型 解：假设有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)= 2

11、n -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亿年。 因此这个世界的寿命应该比它已有 的寿命还长 14 第6讲 重集的排列与组合 v用递归关系构造模型 兔子和费波那契（Fibonacci）数。一对（一公一母）刚出生 的小兔子放到岛上，每对兔子出生两个月后开始繁殖后代， 每对兔子每个月可以繁殖一对新的小兔子。假定兔

12、子不会死 去，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 15 第6讲 重集的排列与组合 如果最后一位是1，它前面n-1位构成满足上述要求 的串，这样的串有Cn-1个；

13、如果最后一位是0，它前面第n-1位只能是1，剩下的 n-2位构成满足上述要求的串，这样的串有Cn-2个； 根据加法法则，有Cn= Cn-1 +Cn-2 有多少个n位二进制串不包含两个连续的0？ an = an-1 + an-2 16 第6讲 重集的排列与组合 v递归关系的求解 在前面的几个问题中，除费波那契数之外的其它问 题都可以在求出初始值和递归关系式后迭代求解， 找出数列的通项公式。方法是： 首先利用递归关系式对关系式右边的表达式进行迭代， 并推测解的公式 然后用数学归纳法证明得到的公式 费波那契数列不易迭代求解，但它有一种更系统的 求解方法 17 第6讲 重集的排列与组合 v常系数线性齐

14、次递归关系 定义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 第6讲 重集的排列与组合 v特征方程 递归递归 关系式H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k) 求解的基本方法是寻找形如a

15、n=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 第6讲 重集的排列与组合 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(an=b1r1n+b2r2n)是递归关系an=c1an-1+c2an-2的解。 r1、r2是方程r2 c1r c2 =0的根 r12= c1r1 + c2且r22= c1r2 + c2 c1an-1 + c2an-2 = c1(b1r1n-1 + b2r2n-1) + c2(b1r1n-2 + b2r2n-2) = b1r1n-2(