《递推关系和生成函数》由会员分享，可在线阅读，更多相关《递推关系和生成函数（20页珍藏版）》请在金锄头文库上搜索。
1、1第 7 章 递推关系和生成函数讨论内容：本章讨论涉及一个整数参数（n）的某些计数问题的代数求解方法。简言之，用代数方法求解计数问题。方 法：递推关系（线性齐次 /非齐次递推关系）和生成函数（&指数生成函数） ；简言之，计数问题的代数表示方法。7.1 某些数列数列：按一定次序排列的一列数称为数列。第 1 项（首项） ，第 2 项，第n 项。如： , ,3210 ， nhh第一节：算术序列和几何序列1、常见的序列有两种：算术序列：例如等差数列， nq 3q ,2 ,q ,10 ， hhh几何序列：例如等比数列， n ，联系：算术级数、几何级数（以表示成 a*xy，即 x 的 y 次方的形式增长。
2、通常情况下，x=2，也就是常说的翻几（这个值为 y）番） 。如图：2序列求和： nkn hhhssh02102102100算术序列的部分和（等差）： nk nqhnkqhs0 02)1()1()(几何序列的部分和（等比）： nk nk hqhqs0 010 1)(q )(3例：确定平面一般位置上的 n 个互相交叠的圆所形成的区域数。互相交叠& 一般位置：n 个圆彼此 两两相较于两个 不同的点，且这些点互不重叠。解：初值： 82 1 110 hh 、（ 一 个 空 白 平 面 ） 、推导递推关系： n-1 个圆，形成区域 hn-1。 放入第 n 个圆，与其余 n-1 个圆，互相交叠（与每个圆交于
3、两个不同点，且这些点不重叠） ，则一共产生了 2*（n-1 ）个交点；则产生弧线段 2*（n-1）条：p 1p2、p 2p3、 p2（n-1）-1 p2（n-1） 、p 2（n-1） p1（将空白平面一分为2） ，每个弧线段将原来的区域一分为 2；则导致新增加了 2*（n-1 ）个区域。4所以（累加消元）： 1)-( )2( 124)13()2(1 )0(02332211 nhhnhnnnn得：2)2( )(21nhnn第二节：斐波那契数列与 Pascal 三角形1、斐波那契序列：0，1，1，2，3 ，5 ，8，13 ，21，34，55 ，89 ，144，233即： 3)(n 21nff例：兔
4、子繁殖问题：一月：（小兔）二月：（大兔）三月：四月：5五月：解： 找初值： 主要用于方便运算，在某些实际的例子中可能没有意义。0f21 0321ff 、 找递推关系： 3)(n nf 累加消元：)21( )( 01 212 343 232 121 -nffffffffnnn )31( 012321 -ffffSnnnn 由（1-2） 、 （1-3）联立求解，得到：2nf同理：当 n+1 时，可得： （证略）131nnfS2、例：斐波那契数是偶数当且仅当 n 内被 3 整除；0，1，1，2，3 ，5 ，8，13 ，21，34，55 ，89 ，144，233nnfffff 、 1232 偶、奇、奇
5、、偶、奇、奇、偶、奇、奇、偶定理 7.1.1：斐波那契数列满足公式：60)(n )251()251( nnnf证明： 设初值： ；bfaf10、 由斐波那契数列的递推关系： 2)(n 021 nnnfff设 。 问题：为什么不设 ？qf nqhfn0注：符合常微分方程的格式：例如： 32yyxxxxxeCye321212-0一 般 解 ：设 ： 、 则，原式变为： 0)( 0)1( 221qqffnnn得： 25-251qq、得通解： )2( )(51)(52221 nCCfnn代入初值： bfaf10、得 b)21()2(121、现有斐波那契的初值： 代入，满足公式：0fff、7得到： )0
6、( )(51-)(51-222 nfCnn、例，证明同上。斐波那契数列的实际应用：例 1：确定 2*n 的棋盘用多米诺骨牌完美覆盖的方法数 nh解：需要 n 块牌，如果最后 1 块牌竖排（即固定住第 n 块牌摆放，排放其余 n-1 块牌） ，与前面n-1 块牌的排法有关系，这种排法有 ：1h如果最后 1 块牌横排，与前面 n-2 块牌的排法有关系，这种排法有 ：2nh所以 2)(n 21nh符合 斐波那契数列，在根据实际情况，求出 21h、例 2：无 101、也没有 010 的长度为 n 的 0、1 序列有多少？解：末位为 0， 1,20,1nnhh110 008末位为 1， 0,21,nnh
7、h 11000所以 21 0,21,21,0, ,2,10 )()( nnnnnhhh满足斐波那契数列，初值求解 421、nf例 3、爬楼梯问题：每次可以爬 1 个台阶或者两个台阶，求 。nh经过推导，会发现，符合斐波那契数列。略， 2nfh92、Pascal 三角形：由图，可以很容易看出，斜对角线上的元素累加和符合 斐波那契 数列。K 的取值 ，其实就是对角线上 k 的取值。21nk定理 7.1.2：10沿 Pascal 三角形左边向上对角线的二项式系数的和是斐波那契数。第 n 个数满足：nf 12310knnfn其中 是 n/2 的若取整。 （或者写成 ，更容易看出就是对角线2k 21n上
8、 k 的取值。 ）更具二项式系数的性质，很容易证出： 10 1n0123nk knnf证略。117.2 线性齐次递推关系已知数列 和系数 , ,3210 ， nhh 021 kaa、满足： )( 21 nbhah knnnn 关于齐次与非齐次：若 ，叫 k 阶常系数线性齐次递推关系；0 b若 ，叫 k 阶常系数线性 非齐次递推关系；n齐次：例题：略定理 7.2.1 令 q 为一个非零数。则 是常系数线性齐次递推关系nqh )207,0( 021 knaahah kknnnn的解，当且仅当 q 是多项式方程 )21-7( 21 kkkk xx的一个根。如果多项式方程有 k 个不同的根 kqq、
9、21则 )-(7 21 nknnn qcqch是下述定义下（7-20）的一般解：无论给定什么初始值，都存在常数，使得公式（7-22 ）满足递推关系（7-20 ）和初始条件的唯一的序列。证明： 证明，存在 k 个不同根的解：为公式（7-20）的解，当且仅当：nqh0)( 2121 kkkkn knnn aqaqa由于： ，所以存在 不为 0.0kak、 21则存在通解： 推之，nqh 21 nknnn qcqch 证明，无论初值取何值，如果 互异，不为 0，则总存在常k、 2112数 ，使得公式（ 7-22）满足递推关系（7-20）kcc、 21设初始值： 110 kkbhbh、则： )1( )
10、2(1 )0( 1121 222 110 kkkk kkbqcqckn bqcqcn方程组系数行列式：范德蒙矩阵。由于 ，0)(111212221 kjiijkkk kqqqqq ijq所以方程组有唯一解。定理得证。定理 7.2.2 联系：常微分方程证明方法类似 7.2.1，这里采用的是特征方程法。符合常微分方程的格式： 032yyxxxxxeCyey321212-0一 般 解 ：设 ： 、 137.3 非齐次递推关系汉诺塔问题：（插入视频）借助于 B，将盘从 A 全部移到 B，保持每一步操作中，每块盘的下面一块盘都比它大。下面是移动 3 块盘的示意图：解法详细描述搬第 n 块，需要： ；1n
11、h把剩下的 n-1 块搬过去，需要： ；1nh所以： )( 211 nn迭代得出： 0)( -h147.4生成函数（解决组合问题）生成函数是无限可微分函数的泰勒级数（幂级数展开式） 。有无穷数列： , ,3210 ， nhh它的生成函数定义为无穷级数： )(210 nxxhxg若，从第 m 项开始，均为 0则， , , ,3210 ， mhxxhxg2)(例：确定苹果、香蕉、橘子和梨的 n-组合的个数，其中在每个 n-组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在 0 和 4 之间，而且至少要有一个梨。解： nee4321225252 43243253)1( )( )xxxxxg 详细
12、解释一下：157.5 递归与生成函数（解决组合问题）使用生成函数求解常系数线性齐次递推关系。生成函数求解步骤：求 ；)(xg 分解成部分分式；确定常系数： ；kcc、 21展开成泰勒级数；比较常用结论： 0321nnxxx 13224)( n1232231)(1( nxxx例：令 是满足递推关系 , ,3210 ， nhh3)( 206)( 3nxg的数列，其中 。求 的一般公式。1-10、 nh解：求解 4 步骤：求 ；)(xg 20163nnnhh 分解成部分分式；)(x16 )(2016 )( 4303 2120 13120 nnxhxhxgxhxhxhxg累加消元、分解成部分分式得到：
13、 5x-12)-(x-1 216)( 313 ccx确定常系数： ；kc、 代入初始值： （待定系数法）-021hh、 495749 0410533232cccc 5x-149/2)-(49/7x-1/2 016)( 32 xxg展开成泰勒级数； kkkk kkk xxxxxg )5(492)1(4972- )5()()(49- 5-149/2-49/71/2 06)(0 00032 所以： )0,12(n )()(- nnnh定理 7.5.1 证明略177.6 一个几何的例子递推关系解决不了的问题，可以用生成函数解凸多边形：内角均 递归必须得有一个明确的中止条件B 该函数所处理的数据规模必须在递减C 这个转化必须是可解的理论上讲所有的循环都可以用递归来解决；循环与递归递归易于理解速度慢20存储空间大循环不易理解速度快存储空间小举例：1 1+2+3+4+.+100 的和2 求阶乘f(n-1)*n3 汉诺塔4 走迷宫
