组合数学第六章递推关系

《组合数学第六章递推关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章递推关系递推关系是一种重要的组合计数方法建立递推关系分析已有递推关系的性质求解递推关系主要内容§6.1递推关系的建立§6.2常系数线性齐次递推关系的求解§6.3常系数线性非齐次递推关系的求解§6.4*用生成函数求解递推关系§6.5*用迭代归纳法求解递推关系及其应用递推关系的定义递推关系的实例常系数线性齐次递推关系及其求解常系数线性非齐次递推关系及其求解（1）等差数列（算术数列）h0,h0+q,h0+2q,…,h0+nq,…递推关系：hn=hn-1+q一般项：hn=h0+nq前n+1项和：sn=(n+1)h0+q(n)(n+1

2、)/2（2）等比数列（几何数列）h0,qh0,q2h0,…,qnh0,…递推关系：hn=qhn-1一般项：hn=qnh0前n+1项和：sn=h0(1-qn+1)/(1-q)定义6.1.1给定一个数的序列H(0),H(1),…,H(n),…若存在正整数n0，使得当n≥n0时，可以用等号(或小于，大于号)把H(n)和前面某些项H(i)，0≤i

3、行研究。利用递推关系和初值在某些情况下可以求出序列的通项表示式H(n)。但是对于大多数递推关系，目前还解不出H(n)的显式来，即使这样，对于给定的n也可以从初值开始，一步一步地计算出H(n)的值或者范围，而H(n)一般代表了某个组合计数问题的解，因此递推关系是组合计数的重要工具，同时也是算法分析的重要手段。求解递推关系的常用方法（1）迭代归纳法；（2）特征根法；（3）生成函数法；例6.1.1（爬楼梯问题）一个小孩要爬上n阶楼梯，每次可上一阶或两阶，问上n阶有多少种上法？解：显然登上1阶台阶有1种方法，登上2台阶有2种方法，f(1）

4、=1，f(2)=2,称为递推关系的初始条件。设有f(n)种方法，要登上这n阶台阶，最后迈上一个台阶或两个台阶完成.（1）若最后是迈上一个台阶完成的，则前面登上了n-1阶台阶，有f(n-1)种方法；（2）若最后是迈上两个台阶完成的，则前面登上了n-2阶台阶，有f(n-2)种方法，根据加法原理有递推关系：f(n)=f(n-1)+f(n-2).例6.1.2Fibonacci数列问题是一个古老的数学问题，是于1202年提出的，问题表述如下:把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由

5、第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。问一年后围栏中有多少对兔子？这是一个数学模型的形象表示，不能真正用来表示兔子的繁殖规律。对于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这是一个带有初值的递推关系。如果规定f(0)=1,则上式

6、变成：f(n)=f(n-1)+f(n-2)(n≥2,n为整数)f(0)=1,f(1)=1称满足这个式子的数列就成为Fibonacci数列，数列中的项叫做Fibonacci数.例6.1.3（Hanoi塔问题）现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.1.1所示，要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上，问至少要搬多少次？解：记f(n)为n个圆盘从A柱搬到C柱所需的最小次数.整个搬运过程可分成三

7、个阶段；（1）将套在A柱上面的n-1个圆盘从A柱按要求搬到B柱，搬动次数为f(n-1);（2）把A柱上最下面的那个圆盘搬到C柱上，搬动次数为1;（3）把B柱上的n-1个圆盘按要求搬到C柱上，搬动次数为f(n-1);由加法原则知，f(n)=2f(n-1)+1又显然f(1)=1，所以有如下带有初值的递推关系:f(n)=2f(n-1)+1f(1)=1解：信道上能够传输的长度为n的字符串可分成四类：（1）最左字符为b；（2）最左字符为c；（3）最左两个字符为ab；（4）最左两个字符为ac。前两类字符串分别有f(n-1)个，后两类字符串分别

8、有f(n-2)个，容易求出f(1)=3，f(2)=8，从而得到例6.1.4在信道上传输由a,b,c三个字母组成的长为n的字符串，若字符串有两个a连续出现，则信道就不能传输，令f(n)表示信道可以传输的长为n的字符串的字数，求f(n)满足的递推关系。