第2章组合5-7.ppt

1、2.5 递推关系,一. 递推关系的定义与建立,定义1 设（a0, a1,）是一个序列，把该序列中 an 与 它前面几个ai (0in) 关联起来的方程称为递推关系。 序列中的一些已知项称为初始值。,例如 an = an-1 + nan-2， an-3an-1 = n+1 （5.1）,均为递推关系，其中 （5.1）式中的a1 =1，a2 =2 为初始值。,例1（河内塔问题） n 个大小不同的圆盘依其半径大小依次套在桩A上，大的在下，小的在上，如图2-10。现要将此 n 个盘从桩 A 移到空桩 B 或 C 上，但要求每次只能移动一个盘且移动过程中始终保持大盘在下，小盘在上。移动过程中桩A也可利用。

2、设移动 n 个盘的最少次数为 an，试建立关于 an 的递推关系。,解 先将 A 上的前 n1 个盘按题设要求移到 C 上，这需移动 an-1 次；再将 A 上最大的盘移到 B 上，这需移动一次；最后将C上的 n-1 个盘移到B上，这又需移动 an-1 次。于是得递推关系：,例2 （Fibonacci兔子问题） 有雌雄各一的一对小兔，假定两个月后长成成兔，并同时（即第三个月）开始每月产雌雄各一的一对小兔，新增小兔也按此规律繁殖。设第n月末共有Fn 对兔子。试建立关于Fn的递推关系。,解 因第 n 月末的兔子包括两部分，一部分为上 月留下的，有Fn-1 对，另一部分为当月新生的，而 由题设当月生

3、的小兔数应是前月末的兔子数，所以,例3 在一个平面上有 n 个圆两两相交，但任意三个圆无公共点。设此n个圆将平面分为 an个区域，试建立关于 an 的递推关系。,解 前n1个圆分平面为 an-1个区域，第 n 个圆与 前n1 个圆两两相交，共交 2(n1) 个不同点，这些 交点又将第 n 个圆恰好分为 2(n1) 条弧，而每条弧 又将原来所在的区域一分为二。故加入第 n 个圆后新 增 2(n1) 个区域，于是得,二递推关系的求解,1迭代法,例4 试解例1的递推关系,2n-1 + 2n-2 + + 2 + 1 = 2n -1,解 由式（5.2） an = 2an-1 +1 = 2 (2an-2+

4、1) +1 =22an-2+2 +1 = 22 (2an-3+1) +2 +1 =23an-3 +22 +2 +1 = = 2n-1a1 +2n-2 +2n-3 + + 2 +1,2母函数法,例5 试解例2 的递推关系,解 由原关系可推得F0=0。令 g(x) = = （5.6）,= +,= +,（1- x1 x）(1- x2 x) = 1- ( x1+ x2)x + x1 x2x2 = 1- x - x2, -F1x = x +,由式（5.5）和式（5.6）得 g (x) x = xg (x) + x2 g (x),解得 g (x) =,设 x1= , x2= , 易知 x1x2 1， x1

5、 x2 = 1，x1x2= 。又, g (x) =,=,=,=,说明：满足上例中的递推关系的数列 Fn 称为Fibonacci数列，即 Fn = 1, 1, 2, 3, 5, 8,。数列中的每一项被称为Fibonacci数。由于 这与最优化计算方法中黄金分割法的参数 0.618 相吻合，故 Fn 可用于求解优化问题。,例6 试解错排数 Dn 满足的递推关系,解 令 G (x) = =, G(x)-1- xG(x) = e - x -1, G(x ) = (1- x + ), = 1-1 +, Dn = n! 1- + ,例7 求图2-11所示的n级网络的等效电阻Rn，其中每个电阻器的电阻均为R

6、。 图2-11,所以有,解得 Rn,若取R=1（单位电阻），则上式,Rn 且 R1 = 1,令 Rn ，n 1,2,。,因R1 1，,故可令a1 = b1 = 1，于是得,=,可令,由 (5.10) B(x)-xxA(x)+3xB(x) （5.12） 联立（5.11）和（5.12）解得,令 A(x) , B(x),由 (5.9) = +, A(x)-x=xA(x)+2xB(x) （5.11）,A(x) , B(x) （5.13）,由 (5.13)式，A(x)(1- x) B(x) ， 所以得,将B(x) 展开得 B(x) , bn =,an =,=,2.6 常系数线性递推关系,一 常系数线性齐

7、次递推关系,定义1 若序列 (a0, a1,) 满足 an+b1an-1+b2an-2+bkan-k=0 (6.1) 则称序列 an 为 k 阶常系数线性齐次递推关系。其中 b1, b2, , bk为常数，bk0。,xk+b1xk-1+bk= 0 (6.2) 称为递推关系（6.1）的特征方程，其根称为式（6.1） 的特征根。,例 ， an+ 3an1 +4an3 = 0 均为常系数线性齐次递推关系，前者为二阶，后者为三阶。,递推关系式（6.1）的解法,1. 方程（6.2）有k个相异根 x1, x2, , xk。此时递推关系 式（6.1）有通解 an=c1x1n+c2x2n+ckxkn （6.3

8、） 其中c1, c2, , ck为任意常数。,进一步, 若对（6.1）再给出一组 k 个初始值，还可由 通解求出满足初始条件的唯一解。,例1 求解 (6.4),解 式 (6.4) 的特征方程为 x2 x 1 = 0，其特征根为,x1 = , x2 =,得通解 Fn = c1x1n+ c2x2n = +,由（6.4）式可推得F0 = 0。将F0 = 0，F1=1代入Fn 得, c1= , c2=, Fn=,说明: 若特征根出现一对共扼复根 x1 = a+bi， x2 = abi 时，通解还可表为,an =,其中,理由为：,=,=,=,其中c1 ，c2 为任意常数。,（ 为任意常数）,例2 计算n

9、 阶行列式,解 将an 按第一列展开有,-,其中 第一个行列式是与an类型相同的（n-1）阶行列式。对第二个行列再按第一行展开又得一个与an类型相同的（n-2）阶行列式，故可得,此关系的特征方程为 x2-x+1=0 ， 解得特征根,x1= ， x2=, =1，, = =, an =,由a1=1，a2= 0 得,c1=1， c2=,最终得 an=,2方程（6.2）有重根,设 x1, x2, xt 分别是特征方程 (6.2) 的相异的 m1, m2, mt 重根，且 , 则递推关系 (6.1) 的通解为,其中 c1 j , ct j 为任意常数。,解得 c1= c2=1, 最终得 an=1+ n,

10、例3 求解,解 此关系的特征方程为 x2-2x+1=0 ，解得 二重特征根 x1, x2 =1。所以,an= c11n + c2n1n = c1+ c2n,由初始值得,一非齐次的解法,定义2 形如 an+b1an-1+ b2an-2 + bkan-k= f(n) (6.5) 的递推关系称为序列（a0, a1, a2,）的 k 阶常系数线性非齐次递推关系。其中 bi (i =1,2, ) 是常数，且 bk0, f (n) 0， nk。 而递推关系 an+b1an-1+bkan-k= 0 （6.6） 称为 (6.5) 诱导的齐次递推关系。,定理17 递推关系(6.5)的通解为 an +,其中 是

11、(6.5) 式的一个特解， 是 (6.6) 式的通解。,对两类 f (n)， 的形式,1f (n) 是n 的 t 次多项式。 A. 1 不是 (6.6) 的特征方程的根，(6.5) 有特解形式： A0nt + A1n t-1 + At 其中 A0, A1, At 为待定常数。,B. 1 是 (6.6) 的特征方程的 m 重特征根，(6.5) 有特解 形式： = (A0nt + A1n t-1 + At ) nm,例4 试解2.5 的例 3 所建立的递推关系,解 原关系诱导的齐次递推关系为 an-an-1= 0 其特征方程为 x-1= 0，解得特征根 x = 1。,所以齐关系的通解为 = c1n

12、= c,因 f (n) =2n-2且1是特征根，设原关系的特解为 = (A0n+ A1)n,代入原关系得 (A0n+ A1)n-A0(n-1)+ A1(n-1) = 2n-2,整理得 2A0n+( A1-A0) = 2n-2,通过比较系数可求得 A0=1， A1= -1,所以 an= c+(n-1) n,将a1 = 2代入上式得 c = 2，故 an= n( n-1)+2,2.f (n)是 n 的形式（为常数） A. 不是 (6.6 ) 的特征根，有,(A为待定常数),B. 是 (6.6 ) 的 t 重特征根，有,(A为待定常数),例5 求 an - 4an-1 + 4 an-2 = 2n 的

13、通解。,解 原关系诱导的齐关系的特征方程为 x2 - 4 x+ 4 = 0,解得二重根 x1, 2 = 2，故齐关系的通解为 = c12n+ c2 n 2n,设 = An22n。将 代入原关系得,A n22n - 4A(n-1)22n-1 + 4A( n-2)22n-2 = 2n,解得 , 故得原关系的通解 an = c12n + c2n 2n + n22n-1,有些非齐次关系还可以化为齐次求解，试看下例 例6 求 an -2an-1 =3 的通解。,解 an-2an-1 = 3 an-1-2 an-2 = 3,两式相减得 an-3an-1+2an-2=0 （6.7）,由特征方程 x2 -3x

14、 +2 = 0 解得特征根 x1=1，x2=2， 于是得递推关系（6.7）的通解 an = c1+ c22n,将上式代入原关系解得 c1= -3，故最终得 an = c2 2 n -3,例7 求 1 + 2 + + n = ?,解 令 an = 1 + 2 + + n ，则有 an - an-1 = n （1）,（1）式减去（2）式得 an - 2an-1 + an-2 =1 （3）, an-1 - 2an-2 + an-3 =1 （4）,(3) 式减去(4)式得 an -3an-1 + 3an-2 - an-3 = 0 （5）, an-1 - an-2 = n-1 （2）,齐次递归关系（5）

15、的特征方程 x3 - 3x2 +3x 1 = 0 即 (x -1)3 = 0,有三重特征根x = 1。从而其通解 an = A + Bn + Cn2,由 a0 = 0，a1 = 1，a2 = 3 。可解得 A = 0，B = C =1/2,从而得 an= (n + n2)/2 = n(n +1)/2,定理 设 g(n)是n 的t 次多项式， 为常数。若是常系数线性非齐次递推关系式 an + b1an-1 + + bkan-k = n g(n) 导出的常系数线性齐次递推关系的m 重特征根，则该递归关系的特解具有形式,说明 1. 若不是上述特征根，则取 m = 0。,2. 若 = 1，则 f(n)

16、 = n g(n) = g(n)，此时该定理即为前文所讨论过的 f(n)为n 的 t 次多项式的情况。,= (A0 nt + A1 nt-1 +At)nmn 其中A0 , A1 , At 为待定常数。,3. 当 g(n) 是n 的零次多项式（即g(n)为常数）时，定理即为前面所讨论过的 f(n) =n g(n) = n 的形式。,解 因2是递归关系式导出的线性齐次递归关系的特征根， 且 n 是关于n 的一次多项式，由定理，可设递归关系式的特解为,例 给出下递归关系的特解形式,= ( A0 n + A1)n2n,2.7 Stirling 数与Catalan 数,一Stirling数,定义1 将

17、n 个有区别的球放入 k 无区别的盒子中， 要求盒子不空。设其不同方案数为 S2(n,k)，称 S2(n, k) 为第二类 Stirling 数。,例如，将 3 个球 a, b 和 c 放入两个相同的盒子有三种 放法： a ； b, c，b ；a, c，c ；a, b 所以 S2(3, 2) = 3。,定理18 第二类Stirling数 S2(n, k) 有下列性质： 1S2(n, 1) =1，S2(n, n) = 1，S2(n, k) = 0 ( nk 或 k = 0n ) 2S2(n, 2 ) = 2n-1 1 3S2(n, n-1) =,证明 1 式显然，3式留作习题，只证2式。 先将 n 个有区别的球中某特定球（设为b1）放入两 个相同盒子中的一个，再放其余的球。因其余 n- 1个 球