第七章(Chapter 7)递推关系和生成函数(Recurrence Relations and Generating Functions).ppt

由上式可得： 即： 因为： 所以， 以n=60为例，∵ ∴若以一秒搬动一个盘的速度来进行移盘，则移动60个盘的汉诺依塔所需时间为： [思考题]： 1、求n位十进制正数中出现偶数个5的数的个数。 2、古代有一个国王要奖赏他的一位臣子，问他要什么，臣子说我的要求不高，的棋盘上1个格子放1粒麦子，第2个格子放2粒麦子，第3个格子放，…，第64个格子放粒麦子。国王自认为国家富有，不认为有什么困难，便满口答应。到兑现承诺时，结果却让他大吃一惊。请问为什么？试用生成函数求解所需的麦子总数。若以每秒运来粒麦子，需要多少时间？ （答案：所需麦子总数为： ； 所需时间为： ） 2、斐波那契（Fibonacci）序列问题： Fibonacci序列是递推关系的又一个典型问题，数列的本身有着许多应用。 问题：有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？ ⑴递推关系的建立： 设满n个月时兔子对数为 ，其中当月新生兔数目设为 对。第n-1个月留下的兔子数目设为 对. 则， = + 但， = ， = = （即第n-2个月的所有兔子到第n个月都有繁殖能力了。） 所以， = + ， ……(7.4.2) ⑵问题的求解： 令 = 则由递推关系(7.4.2)有： ： ： ： +) . ∴ = … ∴ 令 = ， = ，则有 ∴ = 二、线性常系数递推关系及其求解的特征根法 1、线性常系数递推关系： 下面一类递推关系称为k阶线性常系数递推关系: 其中 均为常数且 . 2、二阶常系数齐次递推关系及其求解的特征方程法 一般地，二阶常系数齐次递推关系具有如下形式： 其中 为已知常数. 其求解的特征根法类似于高等数学中所介绍的二阶常系数线性齐次微分方程丢解的特征根法，具体如下：假定初始值已知 ⑴建立特征方程： ⑵求解特征方程得特征根： ⑶根据特征根的不同类型求解 ： ①若 且 均为实根，则 利用初始条件即可求得 . ②若 且 为共轭复根(比如 )则先利用欧拉公式 将 转化为 ，于是有： 利用已知的初始条件代入该式即可求得 ， 也就求得了 . ③若 且 均为实根，则， 利用初始条件即可求得 . 应用实例： 例7.4.1：已知 ， 求 . 解： 例7.4.2：已知 ， 求 . 解： 例7.4.3：已知 ， 求 . 解： 第七章（Chapter 7） 递推关系和生成函数 (Recurrence Relations and Generating Functions) 许多组合数学计数问题依赖于一个整数参数n，这个整数参数n常常表示问题中某个基本集（笛卡尔集）或多重集的大小、组合的大小、排列中的位置数等等。因此一个计数问题常常