递归与母函数精选文档.ppt

递归与母函数本讲稿第一页，共五十三页母函数与递推关系母函数与递推关系v递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如本讲稿第二页，共五十三页母函数vx2项的系数项的系数a1a2+a1a3+an-1an 中所有的项包括中所有的项包括n个元素个元素a1,a2,an中取中取两个两个组合的全体；同理项系数包含了从组合的全体；同理项系数包含了从n个元素个元素a1,a2,an 中取中取3个元素组合的全体。以此类推。个元素组合的全体。以此类推。v若令若令a1=a2=an=1 1，在，在 x2项系数项系数a1a2+a1a3+an-1an中中每一个组合有每一个组合有1 1个贡献，其他各项以此类推。故有：个贡献，其他各项以此类推。故有：本讲稿第三页，共五十三页母函数比较等号两端项对应系数，可得一等式比较等号两端项对应系数，可得一等式本讲稿第四页，共五十三页相关公式令令r=n，则，则，对原方程等号的两端对对原方程等号的两端对x求导可得：求导可得：本讲稿第五页，共五十三页若已知序列 则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。例如 是序列 的母函数。母函数母函数称函数G(x)是序列 的母函数 定义：定义：对于序列 构造一函数：序列可记为本讲稿第六页，共五十三页递推关系递推关系v利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：v例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。A B C本讲稿第七页，共五十三页递推关系递推关系v 对于一般n个圆盘的问题，v 假定n-1个盘子的转移算法已经确定。v 先把上面的n-1个圆盘经过C转移到B。v 第二步把A下面一个圆盘移到C上v 最后再把B上的n-1个圆盘经过A转移到C上A B C本讲稿第八页，共五十三页递推关系递推关系算法分析：算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有本讲稿第九页，共五十三页 例例2.求求n位十进制数中出现偶数个位十进制数中出现偶数个5的数的个数。的数的个数。先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数，若含有偶数个5，则 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。本讲稿第十页，共五十三页 解法解法1：令 位十进制数中出现5的数的个数，位十进制数中出现奇数个5的数 的个数。故有：本讲稿第十一页，共五十三页递推关系递推关系 解法二：解法二：n-1位的十进制数的全体共 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：本讲稿第十二页，共五十三页 例三：例三：从n个元素 中取r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。递推关系递推关系 1 1）不出现某特定元素设为）不出现某特定元素设为 ，其组合数为，其组合数为 ，相当于排除，相当于排除 后从后从 中取中取r r个做允许重个做允许重复的组合。复的组合。2）至少出现一个 ，取组合数为 相当于从 中取r-1个做允许重复的组合，然后再加上一个 得从n个元素中取r个允许重复的组合。本讲稿第十三页，共五十三页递推关系递推关系v依据加法原理，有本讲稿第十四页，共五十三页整数的拆分整数的拆分v所谓整数拆分即把整数分解成若干整数的和，所谓整数拆分即把整数分解成若干整数的和，相当于把相当于把n n个无区别的球放到个无区别的球放到n n个无标志的盒个无标志的盒子，盒子允许空着，也允许放多于一个球。整子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。法的总数叫做拆分数。本讲稿第十五页，共五十三页问题举例问题举例 例例1 1：若有：若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝码各一枚，问克的砝码各一枚，问能称出那几种重量？有几种可能方案？能称出那几种重量？有几种可能方案？本讲稿第十六页，共五十三页问题举例问题举例 从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有 项，即称出5克的方案有2同样，故称出6克的方案有2，称出10克的方案有1本讲稿第十七页，共五十三页问题举例问题举例 例例2：求用1分、2分、3分的邮票贴出不同数值的方案数。因邮票允许重复，故母函数为 以其中为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即本讲稿第十八页，共五十三页问题举例问题举例例例3 3：若有：若有1 1克砝码克砝码3 3枚、枚、2 2克砝码克砝码4 4枚、枚、4 4克砝码克砝码2 2枚的砝码各一枚，问能称出枚的砝码各一枚，问能称出那几种重量？各有几种方案？那几种重量？各有几种方案？本讲稿第十九页，共五十三页问题举例问题举例 从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数这问题可以推广到证明任一十进制数n，可，可表示为表示为而且是唯一的。而且是唯一的。本讲稿第二十页，共五十三页 如果如果 ，则是一般的排列问，则是一般的排列问题。题。设有设有n个元素，其中元素个元素，其中元素 a1 重复了重复了n1次，元素次，元素a2 重复了重复了n2次，次，ak 重复了重复了nk 次，次，从中取从中取r个排列，求不同的排列数个排列，求不同的排列数.指数型母函数指数型母函数 现在由于出现重复，故不同的排列计数便比较复杂。先考虑现在由于出现重复，故不同的排列计数便比较复杂。先考虑 n个元素个元素的全排列，若的全排列，若n 个元素没有完全一样的元素，则应有个元素没有完全一样的元素，则应有n!种排列。若考种排列。若考虑虑ni 个元素个元素ai的全排列数为的全排列数为 ni!，则真正不同的排列数为，则真正不同的排列数为本讲稿第二十一页，共五十三页解的分析解的分析v先讨论一个具体问题：若有先讨论一个具体问题：若有8 8个元素，其中设个元素，其中设a a1 1重复重复3 3次，次，a a2 2重复重复2 2次，次，a a3 3重复重复3 3次。从中取次。从中取r r个组合，其组合数为个组合，其组合数为c cr r ，则序列，则序列c c1 1,c,c2 2,c c3 3,c c4 4,c c5 5,c c6 6,c,c7 7,c c8 8的母函数为的母函数为:本讲稿第二十二页，共五十三页解的分析解的分析 从x4的系数可知，这8个元素中取4个组合，其组合数为10。这10个组合可从下面展开式中得到本讲稿第二十三页，共五十三页解的分析解的分析其中4次方项有表达了从8个元素(a1a3各3个,a22个)中取4个的组合。例如x1x33为一个a1，3个a3的组合，x12x32 两个a1，两个a3的组合，以此类推。本讲稿第二十四页，共五十三页解的分析解的分析 若研究从中取4个的不同排列总数，以 对应的两个两个的不同排列为例，其不同排列数为即 六种。同样，1个 3个 的不同排列数为 本讲稿第二十五页，共五十三页解的分析解的分析 即 以此类推。故可得问题的解，其不同的排列数为本讲稿第二十六页，共五十三页指数型母函数指数型母函数 为了便于计算，利用上述特点，形式地引进函数本讲稿第二十七页，共五十三页指数型母函数指数型母函数v式计算结果可以得出：取一个的排列数为式计算结果可以得出：取一个的排列数为3 3，取两，取两个的排列数为个的排列数为2*9/2,2*9/2,取取3 3个的排列数为个的排列数为3!*14/3=28,3!*14/3=28,取取4 4个的排列数个的排列数4!*35/12=704!*35/12=70，如此，如此等等。等等。本讲稿第二十八页，共五十三页指数型母函数指数型母函数 定义：定义：对于序列 ，函数称为是序列 得指数型母函数本讲稿第二十九页，共五十三页指数型母函数指数型母函数v若元素 a1 有 n1 个，元素 a2 有 n2 个，元素 ak 有 nk个，由此；组成的n个元素中取r个排列，设其不同的排列数为Pr 。则序列P0,P1,Pn,的指数型母函数为:本讲稿第三十页，共五十三页应用举例应用举例 例例1 1：由红球两个，白球、黄球各一个，试求：由红球两个，白球、黄球各一个，试求有多少种不同的组合方案。有多少种不同的组合方案。设设r r，w w，y y分别代表红球，白球，黄球。分别代表红球，白球，黄球。本讲稿第三十一页，共五十三页应用举例应用举例由此可见，出一个球也不取的情况外，有：由此可见，出一个球也不取的情况外，有：（a）取一个球的组合数为三，即分别取红，）取一个球的组合数为三，即分别取红，白，黄，三种。白，黄，三种。（b）取两个球的组合数为四，即两个红的，）取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄。一红一黄，一红一白，一白一黄。（c）取三个球的组合数为三，即两红一黄，两）取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白。红一白，一红一黄一白。（d）取四个球的组合数为一，即两红一黄一）取四个球的组合数为一，即两红一黄一白。白。本讲稿第三十二页，共五十三页应用举例应用举例 令取r的组合数为，则序列 的母函数为共有共有1+3+4+3+1=121+3+4+3+1=12种组合方式。种组合方式。本讲稿第三十三页，共五十三页应用举例应用举例 例2：某单位有8个男同志，5个女同志，现要组织一个有数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式。令 为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数，故 。本讲稿第三十四页，共五十三页2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例故数列 对应一母函数类似的方法可得女同志的允许组合数对应的母函数类似的方法可得女同志的允许组合数对应的母函数位位本讲稿第三十五页，共五十三页应用举例应用举例本讲稿第三十六页，共五十三页2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 中 项的系数 为符合要求的 个人组成的小组的数目，总的组成方式数目为本讲稿第三十七页，共五十三页应用举例应用举例 例例3 3：1010个数字（个数字（0 0到到9 9）和）和4 4个四则运算符个四则运算符 组成的组成的1414个元素。求由其中的个元素。求由其中的n n个元素的排列构个元素的排列构成一算术表达式的个数。成一算术表达式的个数。因所求的因所求的n n个元素的排列是算术表达式，故个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字。而第从左向右的最后一个符号必然是数字。而第n-n-1 1位有两种可能，一是数字，一是运算符。如若第位有两种可能，一是数字，一是运算符。如若第n-1n-1位是十个数字之一，则前位是十个数字之一，则前n-1n-1位必然构成一算位必然构成一算术表达式。术表达式。本讲稿第三十八页，共五十三页应用举例应用举例 如若不然，即第 位是4个运算符之一，则前 位必然是算术表达式。根据以上分析，令 表n个元素排列成算术表达式的个数。则指的是从指的是从0到到99的的100个数，以及个数，以及本讲稿第三十九页，共五十三页例例4 4：设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的n条曲线把平面分割成几个部分？设满足条件的n条封闭 曲线所分割成的域的数目为 an，其中n-1条封闭曲线 所分割成的域的数目为an-1应用举例应用举例本讲稿第四十页，共五十三页v第n条封闭曲线和这些曲线相交于2(n-1)个点，这2(n-1)个点把第n条封闭曲线截成2(n-1)条弧，每条弧把2(n-1)个域中的每个域一分为二。故新增加的域数为2(n-1).应用举例应用举例本讲稿第四十一页，共五十三页母函数和递推关系应用举例母函数和递推关系应用举例例例5 5：求n位2进制最后三位出现010图象的数的个数。对于n位2进制数 从左而右进行扫描，一当出现010图象，便从这图象后面一位从头开始扫描，例如对11位2进制数00101001010从左而右的扫描结果应该是2-4，7-9位出现010图象，即本讲稿第四十二页，共五十三页母函数和递推关系应用举例母函数和递推关系应用举例而不是4-6，7-9位出现的010图象，即不是 为了区别于前者起见，我们说4-6，9-11位是010，但不是“出现010图象”，这作为约定。为了找出关于数列 的第推关系，需对满足条件的数的结构进行分析。由于n位中除了最后三位是010已确定，其余 位可取0或1：本讲稿第四十三页，共五十三页2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例故最后3位是010的n位2进制数的个数是 。其中包含最后3位出现010图象的以及在 位到第 位出现010图象，而在最后3位并不出现010图象的两类数，后一种数为本讲稿第四十四页，共五十三页母函数和递推关系应用举例母函数和递推关系应用举例故有本讲稿第四十五页，共五十三页错排问题错排问题 n个有序的元素应有 个不同的排列，如若一个排列使得所有的元素在原来的位置上，则称这个排列为错排；有的叫重排。以1，2，3，4四个数的错排为例，分析其结构，找出规律性的东西来。本讲稿第四十六页，共五十三页错排问题错排问题即 1 2的错排是唯一的，即2 1。1 2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1，2换位而得的。本讲稿第四十七页，共五十三页错排问题错排问题 1 2 3 4的错排有4 3 2 1，4 1 2 3，4 3 1 2，3 4 1 2，3 4 2 1，2 4 1 3，2 1 4 3，3 1 4 2，2 3 4 1。第一列是4分别与1，2，3互换位置，其余两个元素错排，由此生成的。本讲稿第四十八页，共五十三页错排问题错排问题 第2列是4分别与3，1，2（123的一个错排）的每一个数互换而得到的。即本讲稿第四十九页，共五十三页错排问题错排问题 第三列则是由另一个错排231和4换位而得到，即本讲稿第五十页，共五十三页错排问题错排问题 上面的分析结果，实际上是给出一种产生错排的结果。设n个数1，2，n错排的数目为 ，任取其中一数 ，数 分别与其他的n-1个数 之一互换，其余n-2个数进行错排，共得 个错排。另一部分位数 以外的n-1个数进行错排，然后 与其中每个数互换得 个错排。本讲稿第五十一页，共五十三页错排问题错排问题 综合以上分析结果得递推关系本讲稿第五十二页，共五十三页本讲稿第五十三页，共五十三页