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

1、第七章（Chapter 7）,递推关系和生成函数 (Recurrence Relations and Generating Functions),许多组合数学计数问题依赖于一个整数参数n，这个整数参数n常常表示问题中某个基本集（笛卡尔集）或多重集的大小、组合的大小、排列中的位置数等等。因此一个计数问题常常不是一个孤立的问题，而是一系列单个问题的综合。本章中，我们将讨论涉及一个整数参数的某些计数问题的代数求解方法。这些方法类似于上一章所介绍的棋盘多项式方法一样，通过引入一个函数（称为生成函数，它实质上是一个幂级数，其各项系数对应于相应计数问题的解）结合递推关系来求解相应的计数问题。,7.1 生成

2、函数（母函数）的引入,组合数学研究的主要内容之一是计数，生成函数（母函数）是计数的一种重要工具。 一、引例： 例7.1.1：观察幂级数 的各项系数与组合数序列之间的内在关系。 分析：,从上例分析可见，函数 及其幂级数展开式对于研究组合数序列 非常有价值，对其他序列也有类似作用。 于是我们引入生成函数（母函数）的概念： 二、生成函数（母函数） 定义7.1.1：对于无穷序列： ，定义无穷级数（幂级数）： = (7.1.6) 为该序列的生成函数（也叫母函数）。,例如： 为序列 的生成函数； 为序列1，1，1，的生成函数； （因为： = ） 是序列 的生成函数； （因为： = ， 其证明见书P145页

3、）,注：由定义可见： 给定一个无穷序列，如果它是收敛的，则可借助幂级数求和的方法求得该序列的生成函数。 若已知某一无穷序列对应的生成函数，则可由该生成函数的幂级数展开式中各项的系数得到该序列的内容。,三、生成函数在实际的组合计数问题中的简单应用 例7.1.2：有红球两只（无区别）、白球、黄球各一只，试求有多少种不同的组合方案？ 解： 例7.1.3：某单位有8位男士，5位女士，现要组成一个由偶数个男士和数目不少于2个的女士的小组，试求有多少种不同的组成方式？ 解：,四、生成函数的性质 假设序列 和 的生成函数分别为： 和 。则有： 性质：若 ，则 = ； 性质：若 ，则 = ； 性质：若 ，则

4、= ；,性质：若 收敛， ，则 = ； 性质：若 ，则 = ； 性质：若 ，则 = ； 性质：若 ，则序列 的生成函数满足： = 证明,7.2整数的拆分,一、整数的拆分 定义7.2.1：所谓的整数的拆分是指将给定的正整数n分解成若干个正整数之和。 它相当于将n个无区别的球放进n个无区别的盒子，每个盒子中允许放一个以上的球，也允许为空的情形。一个整数拆分成若干整数之和的拆分方案往往有多个，不同拆分方案的数目称为该整数的拆分数。一般地，整数n的拆分数记为： .,例如，整数5共有7种不同的拆分方案分别为： 5，4+1，3+2，3+1+1，2+2+1， 2+1+1+1，1+1+1+1+1 所以， =7

5、。 下面我们应用生成函数对整数的拆分进行研究：（著名的费勒斯(Ferrers)图像也是一种研究整数拆分的有效工具，有兴趣的同学可查阅相关资料了解）,二、若干拆分数的例子和计算方法 例7.2.1：若有1克、2克、3克和4克的砝码各一枚，问能称出几种可能的重量？ 解： 思考题： 1、若有1克的砝码3枚，2克的砝码4枚，4克的砝码2枚，问能称出那些重量？各有几种方案？ 2、若有1克，2克，4克，8克，16克，32克的砝码各一枚，试问能称出那些重量？各有多少种方案？,例7.2.2：求1角、2角、3角的邮票可贴出不同数值邮资的方案数的生成函数并解释其意义。 解： 例7.2.3：n个完全相同的球放到m（m

6、n）个有标志的盒子，不允许空盒，问共有多少种不同的方案？ 解： 例7.2.4：求整数n拆分成1，2，m(mn)之和并允许重复的拆分数的生成函数。如若要求其中m至少出现一次，试求其方案数的生成函数并解释其组合意义。 解：,三、有关整数拆分数的几个定理 定理7.2.1：整数n拆分成不同整数之和的拆分数等于拆分成奇整数的拆分数。 证明： 定理7.2.2：整数n拆分成重复数不超过2的整数之和的拆分数等于它拆分成不被3整除的整数之和的拆分数。 证明： 定理7.2.3：整数n拆分成重复数不超过k的整数之和的拆分数等于它拆分成不被k+1整除的整数之和的拆分数。 证明略,注：由以上例题可以归结得到如下的一个重

7、要结论： 若 为拆分为由 个 ， 个 ， 个 组成的集合中元素的和的拆分数，则序列 的生成函数为： = 其中 和 ， ， 以及 ， ， 都是正整数， ， ， 可以是无穷大。 的幂级数展开式中 项的系数即为 。,7.3指数型生成函数,一、问题的提出 设n个元素 互不相同，对它们进行全排列，可得n!个不同的排列。若其中的某一元素，设为 ，重复了 次，则全排列中必有相同的，实际上真正不同的排列数应为： 即重复度为： 同理，若n个元素中 重复了 次， 重复了 次， 重复了次 ， ，则对这样的n个元素进行全排列，可得到真正不同的排列数为：,这类问题如何利用生成函数进行分析呢？我们先看一个例子： 例7.3

8、.1：设有8个元素，其中 重复了3次， 重复了2次， 重复了3次。试分析从这8个元素中任取r（0r8）个进行排列的排列数。 解： 从上利分析可见，后一种函数的分析方法在解决此类计数问题上比前一种函数的分析方法要简单的多。 有鉴于此，为解决有重复的排列以及为了计算方便，我们引入指数型生成函数的概念如下：,二、指数型生成函数 定义7.3.1：对于序列 ，定义函数： = 为该序列的指数型生成函数。 例如， 序列 的指数型生成函数为：,序列 的指数型生成函数为： 序列 的指数型生成函数为： 序列 的指数型生成函数为： (可利用高等数学中所介绍的广义二项式定理证明),三、应用实例 例7.3.2：由a,b

9、,c,d这4个字符取5个进行排列，要求a出现的次数不超过2次，但不能不出现；b出现的次数不超过1次；c出现的次数不超过3次；d出现的次数为偶数。求满足上述条件的排列数。 解： 例7.3.3：求1，3，5，7，9这5个数组成的n位数的个数，要求其中3和7出现的次数为偶数，其它数字出现的次数无限制。 解：,注：由以上例题可以归结得到如下的一个重要结论： 若 为由 个 ， 个 ， 个 组成的多重集 ， ， 取r个进行排列的排列数，则序列 的指数型生成函数为： = 的展开式中 项的系数即为 。,例7.3.4：将 7个有区别的球放进4个有标志的盒子，要求1，2 两个盒子必须含偶数个球，第3个盒子含奇数个

10、球，试问共有多少种不同的放法？ 解： 思考题：r个有标志的球放进n个不同的盒子，要求无一空盒，问有多少种不同的分配方案？ （答案为： ）,7.4递推关系,递推关系是组合数学用以计数的一种强有力工具。 一、组合数学中两个与递推关系有关的著名问题：汉诺（Hanoi）塔问题和斐波那契（Fibonacci）序列问题 1、汉诺（Hanoi）塔问题：n个圆盘依其半径大小，从下而上套在A柱上，如下图7.4.1所示。若要把A柱上的n个盘移到C柱上，要求每次只允许搬动一个移到柱B或C上，而且不允许大盘放在小盘上方。请设计一种方法来，并估计要移动几个盘次。假定只有A、B、C三根柱子可用。,图7.4.1：汉诺（Ha

11、noi）塔问题图,汉诺（Hanoi）塔问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，即估计工作量。 算法： n=2时，先将A柱上面的小盘移到B柱上，再将下面的大盘移到C柱上，最后将B柱上的小盘移到C柱上，至此，问题已经解决，移动次数为3次。 n=3时，先将A柱最上面的两个盘经过C移到B柱上，再将A柱上最下面的大盘移到C柱上，最后将B柱上的两个盘经过A柱移到C柱上，至此，问题已经解决，移动次数为7次。,假定n-1个圆盘时的转移算法已经确定。 对于一般n个圆盘的问题，先把A柱上上面的n-1个圆盘经过C柱转移到B柱上，然后把A柱上最下面一个圆盘移到C柱上，最后再把B柱上的n-1个圆盘经过

12、A柱转移到C柱上，至此转移完毕。 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。n=4，5，依此类推。,算法分析： 令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是正确的，因此，n=3时算法也正确。依此类推，假定n-1时算法正确，则n时算法也正确。于是有，算法复杂度为： (7.4.1),序列 的生成函数为： 给定了序列，对应的生成函数也确定了。反过来也一样，求得了生成

13、函数，对应的序列也就可得而知了。当然，利用递推关系(7.4.1)式也可以依次求得 ( h(n)= )，这样的连锁反应关系，叫做递推关系。,下面介绍如何从(7.4.1)式求得生成函数H(x)的一种形式算法。所谓形式算法是指假定这些幂级数在作四则运算时，一如有限项的代数式一样。 因为 且 +） .,如何从母函数得到序列？下面介绍一种化为部分分数的算法。 令 ,由上式可得： 即：,因为： 所以， 以n=60为例， 若以一秒搬动一个盘的速度来进行移盘，则移动60个盘的汉诺依塔所需时间为： 思考题： 1、求n位十进制正数中出现偶数个5的数的个数。,2、古代有一个国王要奖赏他的一位臣子，问他要什么，臣子说

14、我的要求不高，的棋盘上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、二阶常系数齐次递推关系及其求解的特征方程法 一般地，二阶常系数齐次递推关系具有如下形式： 其中 为已知常数. 其求解的特征根法类似于高等数学中所介绍的二阶常系数线性齐