递推关系和生成函数

《递推关系和生成函数》由会员分享，可在线阅读，更多相关《递推关系和生成函数（20页珍藏版）》请在装配图网上搜索。

1、第7章 递推关系和生成函数讨论内容：本章讨论涉及一个整数参数（n）的某些计数问题的代数求解方法。 简言之，用代数方法求解计数问题。方 法：递推关系（线性齐次/非齐次递推关系）和生成函数（&指数生成函数）； 简言之，计数问题的代数表示方法。7.1某些数列数列：按一定次序排列的一列数称为数列。第1项（首项），第2项，第n项。如： 第一节：算术序列和几何序列1、常见的序列有两种：算术序列：例如等差数列，几何序列：例如等比数列，联系：算术级数、几何级数（以表示成a*xy，即x的y次方的形式增长。通常情况下，x=2，也就是常说的翻几（这个值为y）番）。如图：序列求和：算术序列的部分和（等差）：几何序列的

2、部分和（等比）：例：确定平面一般位置上的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、斐波那

3、契序列：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 由斐波那契数列的递推关系：设。 问题：为什么不设？注：符合常微分

4、方程的格式：例如：则，原式变为：得：得通解：代入初值：得 现有斐波那契的初值：代入，满足公式：得到： 例，证明同上。斐波那契数列的实际应用：例1：确定2*n的棋盘用多米诺骨牌完美覆盖的方法数解：需要n块牌，如果最后1块牌竖排（即固定住第n块牌摆放，排放其余n-1块牌），与前面n-1块牌的排法有关系，这种排法有：如果最后1块牌横排，与前面n-2块牌的排法有关系，这种排法有：所以 符合 斐波那契数列，在根据实际情况，求出 例2：无101、也没有010的长度为n的0、1序列有多少？解：末位为0，110 00末位为1， 11000所以 满足斐波那契数列，初值求解例3、爬楼梯问题：每次可以爬1个台阶或者

5、两个台阶，求。经过推导，会发现，符合斐波那契数列。略，2、Pascal三角形：由图，可以很容易看出，斜对角线上的元素累加和符合 斐波那契 数列。K的取值 ，其实就是对角线上 k的取值。定理7.1.2：沿Pascal三角形左边向上对角线的二项式系数的和是斐波那契数。第n个数满足：其中是n/2的若取整。（或者写成，更容易看出就是对角线上 k的取值。）更具二项式系数的性质，很容易证出：证略。7.2 线性齐次递推关系已知数列和系数满足：关于齐次与非齐次：若，叫 k阶常系数线性齐次递推关系；若，叫 k阶常系数线性非齐次递推关系；齐次：例题：略定理7.2.1 令q为一个非零数。则是常系数线性齐次递推关系的

6、解，当且仅当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、7.3 非齐次递推关系汉诺塔问题：（插入视频）借助于B，将盘从A全部移到B，保持每一步操作中，每块盘的下面一块盘都比它大。下面是移动3块盘的示意图：解法详细描述搬第n块，需要：；把剩下的n-1块搬过去，需要：；所以：迭代得出：7.4 生成函数（解决组合问题）生成函数是无限可微分函数的泰勒级数（幂级数展开式）。有无穷数列：它的生成函数定义为无穷级数：若，从第m项开始，均为0则，例：确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个n-组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在0和4之间，而且至少要有一个梨。解：详细解释一下：7.5 递归与生成函数（解决组合问题）使用生成函数求解常系

8、数线性齐次递推关系。生成函数求解步骤：求；分解成部分分式；确定常系数：；展开成泰勒级数；比较常用结论：例：令是满足递推关系的数列，其中。求的一般公式。解：求解4步骤：求；分解成部分分式；累加消元、分解成部分分式得到：确定常系数：；代入初始值：（待定系数法）展开成泰勒级数；所以：定理7.5.1 证明略7.6 一个几何的例子递推关系解决不了的问题，可以用生成函数解凸多边形：内角均 递归必须得有一个明确的中止条件 B 该函数所处理的数据规模必须在递减 C 这个转化必须是可解的 理论上讲所有的循环都可以用递归来解决； 循环与递归 递归 易于理解 速度慢 存储空间大 循环 不易理解 速度快 存储空间小 举例： 1 1+2+3+4+.+100的和 2 求阶乘 f(n-1)*n 3 汉诺塔 4 走迷宫20