生成函数及其应用

《 生成函数及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、生成函数及其应用生成函数及其应用生成函数及其应用生成函数及其应用生成函数及其应用生成函数及其应用生成函数及其应用生成函数及其应用第11卷第19期2011年7月1671—1815(2011,19—4547-04科学技术与工程ScienceTechnologyandEngineeringVo1.11No.19July2011@2011Sci.Tech.Engng.数学生成函数及其应用陈军科(安康职业技术学院信息传媒系,安康725000)摘要研究了递推关系,递归数列及Bell级数的生成函数,使用生成函数的方

2、法和计算技巧并给出了递推公式,为使用生成函数提供了依据.关键词递推关系递归数列Bell级数生成函数应用中图法分类号O157;文献标志码A生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具.最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出.生成函数有普通型生成函数和指数型生成函数两种,其中普通型用的比较多.生成函数的应用简单来说在于研究未知(通项)数列规律,用这种方法在给出递推式的情况下求出数列的通项,生成函数是推导Fibonacci数列

3、的通项公式方法之一.另外生成函数也广泛应用于编程与算法设计,分析上,运用这种数学方法往往对程序效率与速度有很大改进.生成函数作为一类特殊函数在函数论,组合数学,解析数论,数学物理方程等学科的研究领域中,一些恒等式的证明结果及证明方法极为重要uJ.本文以生成函数为工具,讨论了生成函数方法的广泛应用.设{口}(n=0,1,2,3,…)是一待定数列,若能作出一个函数),使得厂()的展开式恰好是厂()=a.+aI+2011年3月11日收到,3月18日修改陕西省自然科学基金(2009JQ1009)资助作者简介:

4、陈军科(1966一),男,陕西凤翔人,副教授,研究方向:解析函数.a2x+…+口+…,则称函数f()是数列{口}(儿=0,1,2,3,…)的生成函数,也称母函数.相应地数列{a}称为)的生成数列.它是形式上的考虑,而不考虑实际上的数值,而其中幂级数则是无穷项的多项式.一般的长相如下:)=∑an.而我们给定数列{口}n=0,=UEClat出的)=∑an则称为数列的生成n=U函数.1幂级数作为生成函数最初应用幂级数作为生成函数的是欧拉,其后拉普拉斯曾广泛采用此方法.该方法主要是通过多项式或幂级数相乘方程中

5、合并同类项,从而得到相关的结论.着名的Bernoulli数B和Bernoulli多项式B()k阶Bernoulli多项式”()分别是由下列●n..函数展开式中按的系数定义的….,正!(t)=亡的幂级数展开式是4548科学技术与工程11卷)==Btn(1)式(1)中B为第n个Bernoulli数,由级数逐项求导理论得:B=()…l:..B()一B(一)=可得B.=1;=一,=,B=一1,B=1,…;2+1=0,(≥1).已经证明得:B=∑c,∑B=0,n≥2.k=0k=0Bernoulli多项式B()被

6、定义为:text=驯tn(n=0,1,2,…)(2)式(2)中=1;B=一号,曰=,=一,B=1,…;日2=0,(≥1).2以递归数列作为生成函数这种把数列放人多项式的系数中,观察多项式的性质而得到数列或者得到系数的新关系的方法,在组合学,机率甚至是编码中有非常重要且广泛的使用.以二阶(常系数线性齐次)递归数列作为生成函数:a+p口+qa一2=0,g≠0;特征多项式:K(x)=++g.则如我们所说的,令数列的生成函数G(x)=口0+a,1x+O,2X+t23.~+….则我们会有下面这个好用的算式:G(

7、x)=n0+a1+02+口3+C$44…(3)pxG(x)=pa0戈+pa1+pa2+pa3…(4)qx2G(x)=qa02+qal+qa24+…(5)式(3),式(4)及式(5)相加得(1++)c(x)=o0+(01+pa0)+(02+pa1+q2)+(口3+pⅡ2+qa1)X….于是(1+p+qx)G(x)=口o+(n1+pao).所㈤=菁.(I++)令分母为D(x)=1++qx;.:二是特征多项式()的两根,则D()=1++qx=(1一F1)(1一F2X).则我们可以将G()做一个分式的改写(暂

8、时假设二根相异).G㈩==+;其中A,B是某两个常数.了一=1++++…于是G(x)=A(1+++…)+B(1+F2X++…)=A∑k+B∑r.所以有G()=∑ak=∑(+Brk2)x;r≠r2.比较系数,得o=Ar+Br;,其中r,r:为特征多项式的两根.例如:满足递推关系式F一,一F一=0,及初始条件Fo=0,F=1费波纳契Fibonacci数列{F},序列满足递推关系式的{F}特征多项式:K(x)=一一1=0,其根为.:L,::L.璃~Fn=A((