组合数学幻灯片51

《组合数学幻灯片51》由会员分享，可在线阅读，更多相关《组合数学幻灯片51（21页珍藏版）》请在金锄头文库上搜索。

1、 5.1 递归关系的建立 第五章 递 归 关 系 递归关系是组合数学的一个重要课题它不仅在几乎所有 的数学分支中占有重要的地位，而且在计算机科学，特别是算 法分析中有着广泛的应用。 在这一节，我们首先给出递归关系的定义然后用几个例子 来说明是怎样建立递归关系的。 例如 第三章3.3节中的错排数 Dn=(n-1)(Dn-1+Dn-2)(n=3,4,)和关系式 都是递归关系。 设(a0,a1,ar,)是一个序列，把该序列中的ar和它前面的 几个ai(0ir)关联起来的方程称做一个递归关系 如果递归关系式(5.1)给出了初值D1=0,D2=1, 那么递归关系式(5.1)连同初值一起就唯一地确定了错排

2、数序列 (D1,D2,D3,)=(0,1,2,9,44,265,)。 同样，对于递归关系式(5.2)，若给出初始值 a1=3，我们就 能确定唯一的序列 (3,32,3r,)。 由上面递归关系的例子可见，递归 关系是计算序列中各项的有效工具。但 如何建立递归关系呢?下面用几个实例 来加以说明。 为方便起见，把式(5.1)和(5.2)连同它们的初值一起统 一写成如下形式： 称这种形式为带初值的递归关系。 解：要求解这个问题，首先必须建立递归 关系，然后求解递归关系即可。 在一个平面上有一个圆和n条直线，这些直线中的每一条 在圆内都同其他的直线相交。如果没有三条的直线相交于一点， 试问这些直线将圆分

3、成多少个区域? 设这n条直线将圆分成的区域数为an， 如果有n-1条直线在圆内将圆分成an-1个区域 ，那么，再加入第n条直线与在圆内的其他n- 1条直线相交。 显然，这条直线被n-1条直线在圆内分成n条 线段，而每线段又将第n条直线在圆内经过的 区域分成两个区域。 这样，加入第n条直线后，圆内就增加了n个 区域。而对于n=0，显然有a0=1。于是对于每 个整数n，可以建立如下带初值的递归关系： 求解递归关系式(5.3)(求解方法将在后几节中介绍)得 an=(n2+n+2)/2 这就是问题的解答。 (5.3) “Hanoi塔”问题是指：n个大小不 一的圆盘依半径的大小，从下而上的套在 柱子A上

4、。如图5-1所示。图见书83页 现要求将所有的圆盘从柱子A上全部转 移 到柱子C上，每次只允许从一根柱子上 转移一个圆盘到另一根柱子上， 且在转移过程中不允许出现大圆盘放在 小圆盘上。 试问要转移多少次才能将柱子A上的n个 圆盘全部转移到柱子C上去? 当n3时，要将柱子A上的n个圆盘全部转移到柱子C上，可以这样设 想: 先把柱子A上的n-1个圆盘转移到柱子B上，这需要转移an-1次， 然后把柱子A上的最后一个大圆盘转移到柱子C上，显然这需要转移 一次， 最后再把柱子B上的n-1个圆盘转移到柱子C上，这也需要转移an-1次 。 解：设an表示从一根柱子上的n个圆盘全部转移到另一根柱子 上的转移次

5、数。 显然，a1=1,a2=3。 经过这些步骤后，所有A上的n个圆盘就 全部转移到柱子C上。 由加法规则，这一共转移了2an-1+1次。于 是可以建立如下带初值的递归关系： (5.4) 求解递归关系式(5.4)得 an=2n-1 这就是我们所需要的结果。 “Fibonacci兔子问题”也是组合数 学中著名问题之一。 这个问题是指：从某一年开始时， 把雌雄各一的一对兔子放入养殖场中， 雌兔每月产雌雄各一的一对新兔。 从第二个月开始每对新兔也是每月 产一对雌雄各一的兔子。 试问第n个月后养殖场中共有多少对 兔子? 解：设第n个月开始时，养殖场中兔子 的对数为Fn。并定义F0=1，显然有F1=1。

6、求解式(5.5)就得到我们所需要的答案。 (5.5) 这是因为，在第n-2个月开始就已经有的每对兔子在第n-1个月里 都应生一对新的兔子。因此可以建立如下带初值的递归关系： 由于在第n个月开始时，除了有第n-1个月开始时养殖场中的全部兔 子Fn-1外，还应该有Fn-2对兔子 利用式(5.5)可以推得 (F0,F1,Fn,)=(1,1,2,3,5,8,13,21,34, 55,89,144,233,377,) 常称Fn为Fibonacci数， (F0,F1,Fn ，)为Fibonacci序列。 Fibonacci序列在数学中是一个奇特而又常 见的序列，它在算法分析中起着重要的作 用。 可以证明，

7、Fibonacci数具有以下性质： 1. 2. 3. 4. 在一个平面中，有n个圆两两相 交，但任两个圆不相切，任三个圆无公 共点。求这n个圆把平面分成多少个区域 ? 解：设这n个圆将平面分成an个 区域，由图5-2 易见a1=2,a2=4。 图52见书84页 现假设前n-1个圆将平面分成an-1个区 域当加入第n个圆时，由题设这个圆与前n -1个圆一定相交于2(n-1)个点,这2(n-1) 个点把第n个圆分成2(n-1)条弧,而每条弧 正好将前面的n-1个圆分成的区域中的每 个区域分成两个区域， 故新加入的第n个圆使所成的区域数 增加了2(n-1)。因此可以建立如下的递归 关系： 求解这个递

8、归关系即可得到问题的答案。 设有n个数b1,b2,bn的连乘积为 b1b2bn。试求不同的结合方式数(加 括号的方式)。 例5 解：设不同的结合方式数为an。定义a1=1。显然有a2=1。 由于对乘积b1b2bn的任一结合方式，必有某 一个k(1kn-1)使得最后的运算为积 b1b2bk与积bk+1bk+2bn相乘。 当k固定时，对乘积b1b2bk有ak种不同的结 合方式，而对乘积bk+1bk+2bn有an-k种不同 的结合方式。 由乘法规则知，对某一个k共有akan-k种不同的结 合方式。再由加法规则即得如下的递归关系： 求解这个递归关系即得到问题的答案。 在上面的几个例子中，只建立了几种类型 的递归关系，但未讨论这些类型的递归关 系的求解方法。 事实上，递归关系的类型很多，当前还没有 一般规则可以用来解所有类型的递归关系 。不过，却有一些规则适用于某些类型的 递归关系。 常系数线性齐次递归关系和常系数线性非齐 次递归关系就是其中的两种类型，在下面 的两节中将分别进行讨论。