递归与母函数市赛课一等奖全省微课优质课特等奖PPT课件省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢您,组合数学,-,母函数与递推,长沙市雅礼中学,朱 全 民,1/53,母函数与递推关系,递推关系是计数一个强有力工具，尤其是在做算法分析时是必需。递推关系求解主要是利用母函数。当然母函数还有其它用处，但这主要是介绍解递推关系上应用。比如,2/53,母函数,x,2,项系数,a,1,a,2,+,a,1,a,3,+,+,a,n-1,a,n,中全部项包含,n,个元素,a,1,a,2,a,n,中取,两个,组合全体；同理项系数包含了从,n,个元素,a,1,a,2,a,n,中取,3,个元素组合全体。以这类推。,若令,a,1,=,a,2,=,=a,n,=,1,，在,x,2,项系数,a,1,a,2,+,a,1,a,3,+,+,a,n-1,a,n,中每一个组合有,1,个贡献，其它各项以这类推。故有：,3/53,母函数,比较等号两端项对应系数，可得一等式,4/53,相关公式,令,r=n,，则，,对原方程等号两端对,x,求导可得：,5/53,若已知序列 则对应母函数,G(x),便可依据定义给出。反之，如若以求得序列母函数,G(x),，则该序列也随之确定。,比如 是序列 母函数。,母函数,称函数,G(x),是序列 母函数,定义：,对于序列 结构一函数：,序列,可记为,6/53,递推关系,利用递推关系进行计数这个方法在算法分析中经惯用到，举例说明以下：,例一,.Hanoi,问题：这是个组合数学中著名问题。,N,个圆盘依其半径大小，从下而上套在,A,柱上，以下列图示。每次只允许取一个移到柱,B,或,C,上，而且不允许大盘放在小盘上方。若要求把柱,A,上,n,个盘移到,C,柱上请设计一个方法来，并预计要移动几个盘次。现在只有,A,、,B,、,C,三根柱子可用。,A B C,7/53,递推关系,对于普通,n,个圆盘问题，,假定,n-1,个盘子转移算法已经确定。,先把上面,n-1,个圆盘经过,C,转移到,B,。,第二步把,A,下面一个圆盘移到,C,上,最终再把,B,上,n-1,个圆盘经过,A,转移到,C,上,A B C,8/53,递推关系,算法分析：,令,h(n),表示,n,个圆盘所需要转移盘次。依据算法先把前面,n-1,个盘子转移到,B,上；然后把第,n,个盘子转到,C,上；最终再一次将,B,上,n-1,个盘子转移到,C,上。,n=2,时，算法是正确，所以，,n=3,是算法是正确。以这类推。于是有,9/53,例,2.,求,n,位十进制数中出现偶数个,5,数个数。,先从分析,n,位十进制数出现偶数个,5,数结构入手 是,n-1,位十进制数，若含有偶数个,5,，则 取,5,以外,0,，,1,，,2,，,3,，,4,，,6,，,7,，,8,，,9,九个数中一个，若 只有奇数个,5,，则取 ，使 成为出现偶数个,5,十进制数。,10/53,解法,1,：,令 位十进制数中出现,5,数个数，位十进制数中出现奇数个,5,数,个数。,故有：,11/53,递推关系,解法二：,n-1,位十进制数全体共 从中去掉含有偶数个,5,数，余下便是,n-1,位中含有奇数个,5,数。故有：,12/53,例三：,从,n,个元素 中取,r,个进行允许重复组合。假定允许重复组合数用 表示，其结果可能有以下两种情况。,递推关系,1,）不出现某特定元素设为 ，其组合数为 ，相当于排除 后从 中取,r,个做允许重复组合。,2,）最少出现一个 ，取组合数为 相当于从,中取,r-1,个做允许重复组合，然后再加上一个 得从,n,个元素中取,r,个允许重复组合。,13/53,递推关系,依据加法原理，有,14/53,整数拆分,所谓整数拆分即把整数分解成若干整数和，相当于把,n,个无区分球放到,n,个无标志盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数和，方法不一，不一样拆分法总数叫做拆分数。,15/53,问题举例,例,1,：若有,1,克、,2,克、,3,克、,4,克砝码各一枚，问能称出那几个重量？有几个可能方案？,16/53,问题举例,从右端母函数知可称出从,1,克到,10,克，系数便是方案数。比如右端有 项，即称出,5,克方案有,2,一样，,故称出,6,克方案有,2,，称出,10,克方案有,1,17/53,问题举例,例,2,：,求用,1,分、,2,分、,3,分邮票贴出不一样数值方案数。,因邮票允许重复，故母函数为,以其中为例，其系数为,4,，即,4,拆分成,1,、,2,、,3,之和拆分数为,4,，即,18/53,问题举例,例,3,：若有,1,克砝码,3,枚、,2,克砝码,4,枚、,4,克砝码,2,枚砝码各一枚，问能称出那几个重量？各有几个方案？,19/53,问题举例,从母函数能够得知，用这些砝码能够称出从,1,克到,63,克重量，而且方法都是唯一。,这问题能够推广到证实任一十进制数,n,，可表示为,而且是唯一。,20/53,假如 ，则是普通排列问题。,设有,n,个元素，其中元素,a,1,重复了,n,1,次，元素,a,2,重复了,n,2,次，,，,a,k,重复了,n,k,次，,从中取,r,个排列，求不一样排列数,.,指数型母函数,现在因为出现重复，故不一样排列计数便比较复杂。先考虑,n,个元素全排列，若,n,个元素没有完全一样元素，则应有,n!,种排列。若考虑,n,i,个元素,a,i,全排列数为,n,i,!,，则真正不一样排列数为,21/53,解分析,先讨论一个详细问题：若有,8,个元素，其中设,a,1,重复,3,次，,a,2,重复,2,次，,a,3,重复,3,次。从中取,r,个组合，其组合数为,c,r,，则序列,c,1,c,2,c,3,c,4,c,5,c,6,c,7,c,8,母函数为,:,22/53,解分析,从,x,4,系数可知，这,8,个元素中取,4,个组合，其组合数为,10,。这,10,个组合可从下面展开式中得到,23/53,解分析,其中,4,次方项有,表示了从,8,个元素,(a,1,a,3,各,3,个,a,2,2,个,),中取,4,个组合。比如,x,1,x,3,3,为一个,a,1,，,3,个,a,3,组合，,x,1,2,x,3,2,两个,a,1,，两个,a,3,组合，以这类推。,24/53,解分析,若研究从中取,4,个不一样排列总数，以 对应两个两个不一样排列为例，其不一样排列数为,即,六种。一样，,1,个,3,个 不一样排列数为,25/53,解分析,即 以这类推。故可得问题解，其不一样排列数为,26/53,指数型母函数,为了便于计算，利用上述特点，形式地引进函数,27/53,指数型母函数,式计算结果能够得出：取一个排列数为,3,，取两个排列数为,2*9/2,取,3,个排列数为,3!*14/3=28,取,4,个排列数,4!*35/12=70,，如此等等。,28/53,指数型母函数,定义：,对于序列 ，函数,称为是序列 得指数型母函数,29/53,指数型母函数,若元素,a,1,有,n,1,个，元素,a,2,有,n,2,个，,，元素,a,k,有,n,k,个，由此；组成,n,个元素中取,r,个排列，设其不一样排列数为,P,r,。则序列,P,0,P,1,P,n,指数型母函数为,:,30/53,应用举例,例,1,：由红球两个，白球、黄球各一个，试求有多少种不一样组合方案。,设,r,，,w,，,y,分别代表红球，白球，黄球。,31/53,应用举例,由此可见，出一个球也不取情况外，有：,（,a,）取一个球组合数为三，即分别取红，白，黄，三种。,（,b,）取两个球组合数为四，即两个红，一红一黄，一红一白，一白一黄。,（,c,）取三个球组合数为三，即两红一黄，两红一白，一红一黄一白。,（,d,）取四个球组合数为一，即两红一黄一白。,32/53,应用举例,令取,r,组合数为，则序列 母函数为,共有,1+3+4+3+1=12,种组合方式。,33/53,应用举例,例,2,：某单位有,8,个男同志，,5,个女同志，现要组织一个有数目为偶数男同志和数目不少于,2,女同志组成小组，试求有多少种组成方式。,令 为从,8,位男同志中抽取出,n,个允许组合数。因为要男同志数目必须是偶数，故 。,34/53,2.8,母函数和递推关系应用举例,故数列 对应一母函数,类似方法可得女同志允许组合数对应母函数位,35/53,应用举例,36/53,2.8,母函数和递推关系应用举例,中 项系数 为符合要求 个人组成小组数目，总组成方式数目为,37/53,应用举例,例,3,：,10,个数字（,0,到,9,）和,4,个四则运算符 组成,14,个元素。求由其中,n,个元素排列组成一算术表示式个数。,因所求,n,个元素排列是算术表示式，故从左向右最终一个符号必定是数字。而第,n-1,位有两种可能，一是数字，一是运算符。如若第,n-1,位是十个数字之一，则前,n-1,位必定组成一算术表示式。,38/53,应用举例,如若不然，即第 位是,4,个运算符之一，则前 位必定是算术表示式。依据以上分析，令 表,n,个元素排列成算术表示式个数。则,指是从,0,到,99100,个数，以及,39/53,例,4,：,设有,n,条封闭曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这么,n,条曲线把平面分割成几个部分？,设满足条件,n,条封闭,曲线所分割成域数目为,a,n,，其中,n-1,条封闭曲线,所分割成域数目为,a,n-1,应用举例,40/53,第,n,条封闭曲线和这些曲线相交于,2(n-1),个点，这,2(n-1),个点把第,n,条封闭曲线截成,2(n-1),条弧，每条弧把,2(n-1),个域中每个域一分为二。故新增加域数为,2(n-1).,应用举例,41/53,母函数和递推关系应用举例,例,5,：,求,n,位,2,进制最终三位出现,010,图象数个数。,对于,n,位,2,进制数 从左而右进行扫描，一当出现,010,图象，便从这图象后面一位从头开始扫描，比如对,11,位,2,进制数,00101001010,从左而右扫描结果应该是,2-4,，,7-9,位出现,010,图象，即,42/53,母函数和递推关系应用举例,而不是,4-6,，,7-9,位出现,010,图象，即不是,为了区分于前者起见，我们说,4-6,，,9-11,位是,010,，但不是“出现,010,图象”，这作为约定。,为了找出关于数列 第推关系，需对满足条件数结构进行分析。因为,n,位中除了最终三位是,010,已确定，其余 位可取,0,或,1,：,43/53,2.8,母函数和递推关系应用举例,故最终,3,位是,010,n,位,2,进制数个数是 。,其中包含最终,3,位出现,010,图象以及在 位,到第 位出现,010,图象，而在最终,3,位并不出,现,010,图象两类数，后一个数为,44/53,母函数和递推关系应用举例,故有,45/53,错排问题,n,个有序元素应有 个不一样排列，如若一个排列使得全部元素在原来位置上，则称这个排列为错排；有叫重排。,以,1,，,2,，,3,，,4,四个数错排为例，分析其结构，找出规律性东西来。,46/53,错排问题,即,1,2,错排是唯一，即,2 1,。,1 2 3,错排有,3 1 2,，,2 3 1,。,这二者能够看作是,1 2,错排，,3,分别与,1,，,2,换位而得。,47/53,错排问题,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,交换位置，其余两个元素错排，由此生成。,48/53,错排问题,第,2,列是,4,分别与,3,，,1,，,2,（,123,一个错排）每一个数交换而得到。即,49/53,错排问题,第三列则是由另一个错排,231,和,4,换位而得到，即,50/53,错排问题,上面分析结果，实际上是给出一个产生错排结果。,设,n,个数,1,，,2,，,，,n,错排数目为 ，任取其中一数 ，数 分别与其它,n-1,个数,之一交换，其余,n-2,个数进行错排，共得,个错排。另一部分位数 以外,n-1,个数进行错排，然后 与其中每个数交换得 个错排。,51/53,错排问题,综合以上分析结果得递推关系,52/53,53/53,