递推关系和生成函数.doc

第7章 递推关系和生成函数
讨论内容：本章讨论涉及一个整数参数（n）的某些计数问题的代数求解方法。
简言之，用代数方法求解计数问题。
方 法：递推关系（线性齐次/非齐次递推关系）和生成函数（&指数生成函数）；
简言之，计数问题的代数表示方法。

7.1某些数列
数列：按一定次序排列的一列数称为数列。第1项（首项），第2项，…，第n项。
如：

第一节：算术序列和几何序列
1、常见的序列有两种：
算术序列：例如等差数列，
几何序列：例如等比数列，
联系：算术级数、几何级数（以表示成a*x^y，即x的y次方的形式增长。通常情况下，x=2，也就是常说的翻几（这个值为y）番）。
如图：

序列求和：

算术序列的部分和（等差）：

几何序列的部分和（等比）：

例：确定平面一般位置上的n个互相交叠的圆所形成的区域数。
互相交叠&一般位置：n个圆彼此两两相较于两个不同的点，且这些点互不重叠。

解：

初值：

推导递推关系：
l n-1个圆，形成区域hn-1。
l 放入第n个圆，与其余 n-1 个圆，互相交叠（与每个圆交于两个不同点，且这些点不重叠），则一共产生了2*（n-1）个交点；则产生弧线段2*（n-1）条：p1p2、p2p3、……p2（n-1）-1p2（n-1）、p2（n-1）p1（将空白平面一分为2），每个弧线段将原来的区域一分为2；则导致新增加了2*（n-1）个区域。

所以（累加消元）：
得：

第二节：斐波那契数列与Pascal三角形
1、斐波那契序列：
0，1，1，2，3，5，8，13，21，34，55，89，144，233……
即：
例：兔子繁殖问题：
一月：
（小兔）
二月：
（大兔）
三月：

四月：

五月：

解：
l 找初值：主要用于方便运算，在某些实际的例子中可能没有意义。

l 找递推关系：
l 累加消元：

由（1-2）、（1-3）联立求解，得到：

同理：当 n+1时，可得：（证略）

2、例：斐波那契数是偶数当且仅当n内被3整除；
0，1，1，2，3，5，8，13，21，34，55，89，144，233……

偶、奇、奇、偶、奇、奇、偶、奇、奇、偶……

定理7.1.1：斐波那契数列满足公式：

证明：
l 设初值：；
l 由斐波那契数列的递推关系：

设。 ——————问题：为什么不设？
注：符合常微分方程的格式：
例如：

则，原式变为：

得：
得通解：
代入初值：
得
现有斐波那契的初值：代入，满足公式：
得到：
例，证明同上。

斐波那契数列的实际应用：
例1：确定2*n的棋盘用多米诺骨牌完美覆盖的方法数
解：需要n块牌，
如果最后1块牌竖排（即固定住第n块牌摆放，排放其余n-1块牌），与前面n-1块牌的排法有关系，这种排法有：

如果最后1块牌横排，与前面n-2块牌的排法有关系，这种排法有：

所以
符合 斐波那契数列，在根据实际情况，求出

例2：无101、也没有010的长度为n的0、1序列有多少？
解：
末位为0，
…………110
………… 00

末位为1，
………… 11
…………000

所以

满足斐波那契数列，初值求解

例3、爬楼梯问题：每次可以爬1个台阶或者两个台阶，求。
经过推导，会发现，符合斐波那契数列。略，
2、Pascal三角形：
由图，可以很容易看出，斜对角线上的元素累加和符合 斐波那契 数列。

K的取值 ，其实就是对角线上 k的取值。

定理7.1.2：
沿Pascal三角形左边向上对角线的二项式系数的和是斐波那契数。第n个数满足：

其中是n/2的若取整。（或者写成，更容易看出就是对角线上 k的取值。）

更具二项式系数的性质，很容易证出：

证略。7.2 线性齐次递推关系
已知数列和系数
满足：

关于齐次与非齐次：
若，叫 k阶常系数线性齐次递推关系；
若，叫 k阶常系数线性非齐次递推关系；
齐次：
例题：略

定理7.2.1 令q为一个非零数。则是常系数线性齐次递推关系

的解，当且仅当q是多项式方程

的一个根。如果多项式方程有k个不同的根
则
是下述定义下（7-20）的一般解：无论给定什么初始值，都存在常数，使得公式（7-22）满足递推关系（7-20）和初始条件的唯一的序列。

证明：
l 证明，存在k个不同根的解：
为公式（7-20）的解，当且仅当：

由于：，所以存在不为0.
则存在通解：推之，

l 证明，无论初值取何值，如果互异，不为0，则总存在常数 ，使得公式（7-22）满足递推关系（7-20）
设初始值：
则：

方程组系数行列式：

范德蒙矩阵。由于，所以方程组有唯一解。
定理得证。

定理7.2.2
联系：常微分方程
证明方法类似7.2.1，这里采用的是特征方程法。

符合常微分方程的格式：
7.3 非齐次递推关系
汉诺塔问题：（插入视频）
借助于B，将盘从A全部移到B，保持每一步操作中，每块盘的下面一块盘都比它大。
下面是移动3块盘的示意图：

解法详细描述

搬第n块，需要：；
把剩下的n-1块搬过去，需要：；
所以：
迭代得出：7.4 生成函数（解决组合问题）
生成函数是无限可微分函数的泰勒级数（幂级数展开式）。

有无穷数列：
它的生成函数定义为无穷级数：

若，从第m项开始，均为0
则，

例：确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个n-组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在0和4之间，而且至少要有一个梨。
解：

详细解释一下：7.5 递归与生成函数（解决组合问题）
使用生成函数求解常系数线性齐次递推关系。

生成函数求解步骤：
①求；
②分解成部分分式；
③确定常系数：；
④展开成泰勒级数；

比较常用结论：

例：令是满足递推关系

的数列，其中。求的一般公式。

解：
求解4步骤：
①求；

②分解成部分分式；

累加消元、分解成部分分式得到：

③确定常系数：；
代入初始值：（待定系数法）

④展开成泰勒级数；

所以：

定理7.5.1
证明略7.6 一个几何的例子
递推关系解决不了的问题，可以用生成函数解
凸多边形：内角均<180°。其内任意两点的连线所形成的线段，线段上的点均在多边形内部。

定理7.6.1 通过画出在区域内部不相交的对角线，令表示具有n+1条边的凸多边形区域分成三角形区域的方法数。定义。则满足递推关系

该递推关系的解为

证明：如左图，假设P点在a1点，讲凸多边形分成了两个区域k1和k2；k1具有k+1≥2条边可以插入种方法插入对角线（两条边+1条对角线才能构成三角形）【这里可推出k≥1】，k2具有n-k+1≥2【这里可推出k≤n-1】条边可以插入种方法插入对角线，则此时分解方法有 ；（k1有k+1条边，是因为多了划分的那条红边）下面两个图是P点在a1点的划分方法示意图：

同理：P点可以在a2，a3等其他点（当然不会在a5，a6，否则红色的部分构成不了三角形。）

所以 ：
【做法类似于求解4步骤：】

非线性递推关系：

偶然发现：

解得：
跳步……
又，所以
所以7.7 指数生成函数（解决排列问题）
定理7.71 令为一多重集，其中
均为非负整数。令是S 的n-排列数。则序列的指数生成函数 由

给定，其中，对于

证明：

汉诺塔
伪算法
{
先把A柱子上的前n-1个盘子从A借助C移到B
将A柱子上的第n个盘子直接移到C
再将B柱子上的n-1个盘子借助A移到C
}
专题： 递归 【用栈实现】
定义：
一个函数自己直接或间接调用自己；

递归要满足的三个条件：
A> 递归必须得有一个明确的中止条件
B> 该函数所处理的数据规模必须在递减
C> 这个转化必须是可解的

理论上讲所有的循环都可以用递归来解决；
循环与递归
递归
易于理解
速度慢
存储空间大
循环
不易理解
速度快
存储空间小

举例：
1> 1+2+3+4+...+100的和
2> 求阶乘
f(n-1)*n
3> 汉诺塔
4> 走迷宫
20