1、第七章 递推关系和生成函数前言n 数学的一种重要思想 递推思想体现了世界上许多事物现象变化所遵循的一种前因和后果的关系，具有广泛的应用 。 计算机科学中，例如著名的 “梵塔问题 ”，在算法分析中有着广泛的应用。讲授内容7.1 某些数列本章主要讨论涉及一个整数参数的计数问题的代数求解方法。错位排列计数公式的递推关系Dn=n!递 推关系(1) Dn=(n1)( Dn2+Dn1), (n=3,4,)(2) Dn=nDn1+(1)n (n=2,3,)7.1 某些数列（ 1） 算术数列 （等差数列）h0, h0+q, h0+2q, , h0+nq,递 推关系： hn= hn-1+q一般 项 ： hn=
2、h0+nq前 n+1项 和： sn= (n+1)h0+q(n)(n+1)/2（ 2） 几何数列 （等比数列）h0, qh0, q2h0, , qnh0,递 推关系： hn= qhn-1一般 项 ： hn= qnh0前 n+1项 和： sn= h0(1-qn+1)/(1-q) 一些例子例 . 确定平面一般位置上的 n个互相交叠的圆 所形成的区域数。（互相交叠是指每两个 圆 相交在不同的两个点上；一般位置是指没有同心 圆 ）。 用 hn表示 n个交 叠的圆形成的区域数h0=1， h1=2h2=4， h3=8一般递推关 系 (n2)：第 n个圆与前 n-1个圆相交于2(n-1)不同交点， P1, P
3、2, P2(n1)。P1P4P2P5P3P6共形成 2(n1)条弧 P1P2, 弧 P2P3 , P2(n1) 1 P2(n1)和P2(n1) P1，每条弧把穿过的区域一分为二，因此增加了 2(n1)个区域。因此得到递推关系：hn=hn-1+2(n1)h4=14迭代递推关系：hn= hn-1+2(n1)= hn-2+2(n2)+2(n1)= hn-3+2(n3)+2(n2)+2(n1)hn=h1+21+22+2( n2)+2(n1)= h1+21+2+( n2)+(n1)得到 ：hn=2+2n(n1)/2=n2n+2斐波那契（ Fibonacci）序列 n 年初把性 别 相反的一 对 新生兔子放 进围栏，从第二个月开始每月生出一 对 性 别 相反的兔子，每 对 新兔也从第二个月开始每月生出一 对 性 别 相反的兔子， 问 一年后 围栏内共有多少 对 兔子。 表示幼兔表示成兔实线表示成长虚线表示生殖1: 12: 13: 24: 35: 56: 87: 13
