母函数与递归的关系ppt课件.ppt

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

1、《组合数学》第三讲母函数与递归关系1母函数与递归关系母函数理论引言母函数概念与运算母函数与递归关系GeneratingFunctionsandRecurrenceRelations2一.母函数理论引言母函数就象一根晒衣绳,我们把需要得到的一列数就挂在它上面.假定我们的问题的解是一列数:a0,a1,a2,,an,.我们想知道这个数列是什么,我们期望得到怎样的答案?当然,最好的答案就是关于an的一个简单的公式.比如诸如an=n2+3之类的表达式.即,通项公式.3但是,如果一个未知数列没有简单公式,或者即便存在,但是很复杂,很不容易得到,我们也不知道,该怎么办?

2、如果我们还希望研究这个数列,讨论它的性质,该如何下手?举一个极端的例子,假定这个数列是2,3,5,7,11,13,17,19,23,….,此处an是第n个素数.这样的情况,期望任何简单的公式都是不合理的.4母函数把数列的所有成员用一种非常巧妙的方法联系在一起,虽然这样做并不一定能得到数列的简单公式,可是也许能够给出一个幂级数和的简单公式,展开这个和函数,所得到的幂级数的系数就是我们所要找的数列.比如后面我们将会学习到的Fibonacci数列,它满足一个递归关系Fn+1=Fn+Fn-1(n2;F1=F2=1).5虽然这个数列也有一个准确的公式,也不算太复杂.但

3、是,我们将以它作为例子,说明用母函数的思想方法是如何回答这个问题的,应该是有意义的.这个回答就是:Fn是函数1/(1-x-x2)关于原点的幂级数展开式中xn的系数.也许你会承认这是一种答案,但是不欣赏这个答案,因为我们没有明显的公式.实际上,这是一个相当优美的答案.用这样的结果,我们可以对整个数列做我们想做的许多事情.6我们不可能讲的太深入,但是我还是想列举出数列的母函数能帮助我们所做的事情.找准确公式.找递归关系.证明恒等式求平均值.求渐近公式.证明单峰性质7二.母函数概念及运算1.母函数概念设有a,b,c三个不同的球,从中选取一个,或选a,或选b,或选c,

4、把这些可能的选取形象地表示为a+b+c.类似地,从中选取二个,或选a和b,或选a和c,或选b和c.可形象地表示为ab+ac+bc,同样,从中选取三个,只有一种方法,也可形象地表示为abc.8从多项式(1+ax)(1+bx)(1+cx)(3.1)=1+(a+b+c)x+(ab+ac+bc)x2+(abc)x3中发现,所有这些可能的选取方式正好是x幂的系数.其中xi的系数是从三个球中选取i个的方法之形象表示.因子(1+ax)形象地指出,对球a,有两种选取方法:不选a,或选a.因子(1+ax)中的1表示不选a,而x的系数a表示选a.9既然在上述多项式中,xi的系数表

5、明选取i个球的方法,那么(1+ax)(1+bx)(1+cx)所表明的是:对a,b,c三球,选取的方法是,“选a或不选a”和“选b或不选b”以及“选c或不选c”.多项式中x的幂次表示选取球的个数,而其相应系数表示一切可能的选取方法.10如果我们只关心不同组合方案的数目,不关心各种方案的罗列.可以在(3.1)式中令a=b=c=1,则得到(1+x)3=C(3,0)+C(3,1)x+C(3,2)x2+C(3,3)x3=1+3x+3x2+x3.(3.2)总方案数N=C(3,0)+C(3,1)+C(3,2)+C(3,3)=1+3+3+1=8.11(3.2)就是一个关于形式

6、变量x的幂函数,这个幂函数中不同幂次的系数都是一个组合数.这可以推广到任意n个不同球所有可能组合的方案数情况.这其实就是我们大家熟悉的二项式系数.不过现在我们是用形式级数的观点来看问题.利用这种形式级数不仅仅是一种不同的表达形式,还非常有用.下面熟悉的公式可以用这种方法证明.12通过比较(1+x)m(1+x)n=(1+x)m+n两边xr项的系数可以得到:C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0)通过在(1+x)n中令x=1可以得到:C(n,0)+C(n,1)+…+C(n,n)=2n通过对(1+x)n=

7、C(n,0)+C(n,1)x+C(n,2)x2+…+C(n,n)xn两边对x求导数,然后令x=1就得到C(n,1)+2C(n,2)+…+nC(n,n)=n2n-113说明这种函数表达式可以帮助我们得到它们系数中所反映出来的组合数之间的关系.许多组合恒等式都可以用这种方法来证明.引入母函数的概念绝对不是为这种简单的目的.母函数还有许多更深刻的应用,特别是可以用来解递归关系.这一点后面我们会体会到.142.母函数定义定义3.1利用给定序列a0,a1,a2,所构造的函数F(x)=a0+a1x+a2x2+称为序列a0,a1,a2,的母函数.母函数定义中的级数是形

8、式幂级数,不必关心收敛性,x只是一个形