1、* 计算机科学与技术学院 1第六章 递推关系 6.1 递推关系的建立6.2 常系数线性齐次递推关系的求解6.3 常系数线性非齐次递推关系的求解6.4* 用生成函数求解递推关系6.5* 用其他方法求解递推关系* 计算机科学与技术学院 2递推关系的建立构建求解递推关系是组合计数的重要方法；在第三章 Stirling数的性质 3.5.1中给出了递推关系。S2（ n+1,k)=S2(n,k-1)+k*S2(n,k)在第四章讨论错位排列数 Dn时，也可以建立关于 Dn的递推关系：Dn=(n-1)(Dn-1 + Dn-2) n3D1=0， D2=1* 计算机科学与技术学院 3递推关系的建立定义 6.1.1
2、 给定一个数的序列 H(0),H(1), H(n), 若存在正整数 n0，使得当 nn0时，可以用等号 (或小于，大于号 )把H(n)和前面某些项 H(i)， 0 i n，联系起来，这样的式子叫做 递推关系。递推关系也称递归关系，递归方程。从本质上讲，递推关系是研究整变量函数的或者说是研究数列的，与此对应的是连续论域中的微分方程。因此，我们可以类似的方法对它们进行研究 。 * 计算机科学与技术学院 4递推关系的建立利用递推关系和初值在某些情况下可以求出序列的通项表示式 H(n) 。但是对于大多数递推关系，目前还解不出 H(n)的显式来， 即使这样，对于给定的 n也可以从初值开始，一步一步地计算
3、出 H(n)的值或者范围，而 H(n)一般代表了某个组合计数问题的解，因此递推关系是组合计数的重要工具。* 计算机科学与技术学院 5递推关系的建立求解递推关系的常用方法（ 1）特征根法；（ 2）迭代归纳法；（ 3）生成函数法；* 计算机科学与技术学院 6递推关系的建立n 例 6.1.1（爬楼梯问题）一个小孩要爬上 n阶楼梯，每次可上一阶或两阶，问上 n阶有多少种上法？n 解：显然登上 1阶台阶有 1种方法，登上 2台阶有 2种方法， f(1） =1， f(2)=2 ,称为递推关系的初始条件。设有 f(n) 种方法，要登上这 n阶台阶，最后迈上一个台阶或两个台阶完成 .（ 1）若最后是迈上一个台
4、阶完成的，则前面登上了 n-1阶台阶，有 f(n-1) 种方法；（ 2）若最后是迈上两个台阶完成的，则前面登上了 n-2阶台阶，有 f(n-2) 种方法，根据加法原理有递推关系： f(n)=f(n-1)+f(n-2) .* 计算机科学与技术学院 7递推关系的建立例 6.1.2 Fibonacci数列问题是一个古老的数学问题，是于 1202年提出的，问题表述如下 :把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。问一年后围栏中有多少对兔子？这是一个数学模型的形象表示，不能真正用来表示
5、兔子的繁殖规律。* 计算机科学与技术学院 8递推关系的建立对于 n=1,2, 令 f(n)表示第 n个月开始时围栏中的兔子对数，显然有 f(1)=1,f(2)=2。在第 n个月的开始，那些第 n-1个月初已经在围栏中的兔子仍然存在，而且每对在第 n-2个月初就存在的兔子将在第 n-1个月开始将要生出一对新兔来，所以有：f(n)=f(n-1)+f(n-2) (n 3, n为整数 )f(1)=1,f(2)=2这是一个带有初值的递推关系 。* 计算机科学与技术学院 9递推关系的建立如果规定 f(0)=1,则上式变成：f(n)=f(n-1)+f(n-2) (n 2, n为整数 )f(0)=1,f(1)=1称满足这个式子的数列就成为 Fibonacci数列，数列中的项叫做 Fibonacci数 .* 计算机科学与技术学院 10递推关系的建立n 多米诺牌（可以看作是 2*1大小的方格 )完全覆盖一个n*2的棋盘。覆盖的方案数？f(n)=f(n-1)+f(n-2) (n 2, n为整数 )f(1)=1,f(2)=2称满足这个式子的数列就成为 Fibonacci数列，数列中的项叫做 Fibonacci数 .1 2 n-1 n 1 2 n-1 n
