组合数学第三讲.ppt

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,Math,母,函数与递推关系,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,母,函数与递推关系,1,母函数,定义,：给定序列,(,a,0,a,1,a,n,),，,记为,a,n,.,函数,f,(,x,)=,a,0,+,a,1,x,+,a,n,x,n,+,称为该序列的普通母函数，简称母函数。,例 常数列,(1,1,),的母函数为,f,(,x,)=1+,x,+,x,n,+=1/(1-,x,),数列,C,(,n,i,),i,=0,1,2,n,的母函数为,这里的母函数只是“形式幂级数”，运算均按收敛,幂级数进行。,母,函数与递推关系,母函数的组合意义：考察,母,函数与递推关系,其中：,x,前的,系数为,a,b,c,的所有可重,1-,组合，,x,2,前的系数为,a,b,c,的所有可重,2-,组合，,一般地：,x,n,前的系数为,a,b,c,的所有可重,n,-,组合，,在前式中取,a,=,b,=,c,=1,则,x,n,前的系数为,a,b,c,的所有可重,n组合数,F,(3,n).,母,函数与递推关系,所以，构造某组合问题的组合数,a,n,的母,函数,f,(,x,),的基本方法为：,用一个乘积因子,(1+,x,+,x,2,+),来代表一个所选元素，若该元素可重复,n,次，则因子中应出现,x,n,。,例 设有,2,个红球，,3,个白球，,1,个黑球和,1,个黄球,.,求从这些球中取出,5,个的不同方案数。,解：设从所给球中取出,i,个的不同方案数为,a,i,则,由题设可得,a,i,的母函数为,母,函数与递推关系,例 求用,1,元和,2,元的钞票支付,n,元的不同方式数。,解：设所求不同方式数为,a,n,则由题设可得,a,n,的,母函数为,母,函数与递推关系,于是,母,函数与递推关系,定义,：给定序列,(,a,0,a,1,a,n,),，,记为,a,n,.,函数,称为该序列的指数型母函数,简称指数母函数。,例 常数列,(1,1,),的母函数为,例 从,n,个不同元素中取,r,个的排列数,P,(,n,，,r,),指数母函数为：,母,函数与递推关系,例,n,个不同元素的可重,r,-,排列数,n,r,(,r,=0,1,2,),的指数母函数为,例 求用,1,2,3,4,5,五个数字组成的,n,位数的个数，要求,1,出现的次数为偶数，,2,出现的次数为奇数，并且,3,至少出现一次。,解：设所求,n,位数的个数为,a,n,，则由题设可得,a,n,的指数母函数为：,母,函数与递推关系,母,函数与递推关系,从而有,所以,母,函数与递推关系,2,递推关系,定义,：设,(,a,0,a,1,a,n,),是一个序列，把该序列中,a,n,与它前面几个,a,i,(0,i,n,),关联起来的方程称为,递推关系,。序列中的一些已知条件称为,初始条件,。,例如,母,函数与递推关系,利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：,例一,.,Hanoi Tower,（河内塔）问题：,N,个圆盘依其半径大小，从下而上套在,A,柱上，如下图示。每次只允许取一个移到柱,B,或,C,上，而且不允许大盘放在小盘上方。若要求把柱,A,上的,n,个盘移到,C,柱上请设计一种方法来，并估计要移动几个盘次。现在只有,A,、,B,、,C,三根柱子可用。,A B C,母,函数与递推关系,Hanoi,问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。,算法：,N=2,时,A B C,第一步先把最上面的一个圆盘套在,B,上,第二步把下面的一个圆盘移到,C,上,最后把,B,上的圆盘移到,C,上,到此转移完毕,母,函数与递推关系,对于一般,n,个圆盘的问题，,假定,n-1,个盘子的转移算法已经确定。,先把上面的,n-1,个圆盘经过,C,转移到,B,。,第二步把,A,下面一个圆盘移到,C,上,最后再把,B,上的,n-1,个圆盘经过,A,转移到,C,上,A B 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,是算法是对的。以此类推。于是有,母,函数与递推关系,算法复杂度为：,H,(,x,),是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系,(*),式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。,母,函数与递推关系,2,递推关系的求解方法,一，迭代法,例如前面的,Hanoi Tower,（河内塔）问题：,我们有,母,函数与递推关系,母,函数与递推关系,二，母函数法,例如前面的,Hanoi Tower,（河内塔）问题：,由递推关系，我们有,我们设,a,n,的母函数为,母,函数与递推关系,由递推关系可得,故有,母,函数与递推关系,解得,所以,母,函数与递推关系,三，常系数线性递关系的解法,定义,：,若序列（,a,1,a,2,）满足,则称序列,a,n,为,k,阶常系数线性递推关系,。,若,f,(,n,)=0,则称序列,a,n,为,k,阶常系数线性,齐次,递推关系。,称：,x,k,+,b,1,x,k,-1,+,.,+,b,k,-1,x,+,b,k,=0,为,k,阶常系数线性递推关系的,特征方程,。,母,函数与递推关系,1,，齐次常系数线性递关系的解法,若递推关系的特征多项式有,k,个相异实根,x,1,x,2,x,k,，则递推关系的通解为：,其中,c,1,c,2,c,k,为任意常数。,若对递推关系再给出一组,k,个初始值，还可以由,通解求出满足初始条件的唯一解。,母,函数与递推关系,例 求解：,解：此递推关系的特征方程为,其特征根为,故其通解为,母,函数与递推关系,由初始条件可得,F,0,=0,，将,F,0,=0,，,F,1,=1,代入得,解得,所以,母,函数与递推关系,若特征根出现一对共轭复根,x,1,=,a,+,b,i,x,2,=,a,-,b,i,时，则递推关系的通解可表示为：,若对递推关系再给出一组,k,个初始值，还可以由,通解求出满足初始条件的唯一解。,其中,母,函数与递推关系,例：求下列,n,阶行列式,d,n,的值。,解：根据行列式性质，有,母,函数与递推关系,此递推关系的特征方程为,其特征根为,故其通解为,母,函数与递推关系,由初始条件,d,1,=1,，,d,2,=0,得,解得,所以,母,函数与递推关系,若特征根出现,k,重根。不妨设,a,1,是,k,的重根。则递推关系的解对应于,a,1,的项为,其中,A,0,A,1,.,A,k,是,k,个待定常数,例：求下列,n,阶行列式,d,n,的值。,母,函数与递推关系,解：,根据行列式性质，有,此递推关系的特征方程为,其特征根为,故其通解为,母,函数与递推关系,由初始条件,d,1,=2,，,d,2,=3,得,解得,所以,母,函数与递推关系,2,，非齐次常系数线性递关系的解法,所对应的,齐次递推关系,。,定义,：,我们称齐次递推关系,母,函数与递推关系,定理,：递增推关系（*）的通解为,f,(,n,),是,n,的,t,次多项式的形式。,若,1,不是,(*),的特征方程的根,则,(*),有特解形式为,母,函数与递推关系,若,1,是,(*),的特征方程的,m,重根，则,(*),有特解形,式为,例 求和式,解：设,从则可得,母,函数与递推关系,其对应的齐次递推关系为,其特征方程为,其对应的齐次递推关系的通解为,因为,1,是特征方程式的,1,重根，,f,(,n,),是,n,的三次多,项式。所以有下列形式的特解：,代入题上的递推关系得,母,函数与递推关系,于是可得方程组,从而解得,所以原递推关系的通解为,母,函数与递推关系,代入初始条件,a,1,=1,得,解得,C,=0,故有,母,函数与递推关系,f,(,n,),是,b,n,的,形式,(,b,为常数,),。,若,b,不是,(*),的特征方程的根，则,(*),有特解形式,为,若,b,是,(*),的特征方程的,m,重根，则,(*),有特解形,式为,母,函数与递推关系,例 求解下列递推关系,其对应的齐次递推关系的通解为,解：其对应的齐次递推关系为,其特征方程为,母,函数与递推关系,因为,2,是特征方程式的,1,重根，所以有下列形式,的特解：,代入题上的递推关系，求解得,所以原递推关系的通解为,代入初始条件,a,0,=0,，,a,1,=1,得,母,函数与递推关系,从而解得,所以原递推关系的解为,