递归与母函数ppt课件.ppt

《递归与母函数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学---母函数与递推长沙市雅礼中学朱全民母函数与递推关系递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如母函数x2项的系数a1a2+a1a3+…+an-1an中所有的项包括n个元素a1,a2,…,an中取两个组合的全体；同理项系数包含了从n个元素a1,a2,…,an中取3个元素组合的全体。以此类推。若令a1=a2=…=an=1，在x2项系数a1a2+a1a3+…+an-1an中每一个组合有1个贡献，其他各项以此类推。故有：母函数比较等号两端项对

2、应系数，可得一等式相关公式令r=n，则，对原方程等号的两端对x求导可得：若已知序列则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。例如是序列的母函数。母函数称函数G(x)是序列的母函数定义：对于序列构造一函数：序列可记为递推关系利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种

3、方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。ABC递推关系对于一般n个圆盘的问题，假定n-1个盘子的转移算法已经确定。先把上面的n-1个圆盘经过C转移到B。第二步把A下面一个圆盘移到C上最后再把B上的n-1个圆盘经过A转移到C上ABC递推关系算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有例2.求n位十进制数中出现偶数个5的数的个数。先从分析n位十进制数出现偶数个5的数

4、的结构入手是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）不出现某特定元素设为，其组合数为，相当于排除后从中取r个做允许重复的组合。2）至少出现一个，取组合

5、数为相当于从中取r-1个做允许重复的组合，然后再加上一个得从n个元素中取r个允许重复的组合。递推关系依据加法原理，有整数的拆分所谓整数拆分即把整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。问题举例例1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？问题举例从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有项，即称出5克的方案有2同样，故称出6克的方案有2，称出10克的方案有1问题举例例2：求用1分、

6、2分、3分的邮票贴出不同数值的方案数。因邮票允许重复，故母函数为以其中为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即问题举例例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？问题举例从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数n，可表示为而且是唯一的。如果，则是一般的排列问题。设有n个元素，其中元素a1重复了n1次，元素a2重复了n2次，…，ak重复了nk次，从中取r个排列，求不同的排列数.指数型母函数现在由于出现重复，故不同的排列计

7、数便比较复杂。先考虑n个元素的全排列，若n个元素没有完全一样的元素，则应有n!种排列。若考虑ni个元素ai的全排列数为ni!，则真正不同的排列数为解的分析先讨论一个具体问题：若有8个元素，其中设a1重复3次，a2重复2次，a3重复3次。从中取r个组合，其组合数为cr，则序列c1,c2,c3,c4,c5,c6,c7,c8的母函数为:解的分析从x4的系数可知，这8个元素中取4个组合，其组合数为10。这10个组合可从下面展开式中得到解的分析其中4次方项有表达了从8个元素(a1a3各3个,a22个)中取4个的组合。例如x1x33为一个a1，3个a3的组合，x12x3

8、2两个a1，两个a3的组合，以此类推。解的分析若研究