毕业论文-生成函数的理论与应用.docx

《毕业论文-生成函数的理论与应用.docx》由会员分享，可在线阅读，更多相关《毕业论文-生成函数的理论与应用.docx（31页珍藏版）》请在第一文库网上搜索。

1、本文系统的论述了生成函数的理论及其在组合数学和计算数学中的应用.生成函数又称母函数，它是在基级数和多项式理论的基础上建立的.生成函数可分为普通型生成函数和指数型生成函数，他们在计算问题中有各自的应用范围本文首先介绍了生成函数的基本理论，包括基本概念、性质及其系数计算的一些技巧.其次介绍了普通型生成函数和指数型生成函数的基本模型及其应用范围.最后则具体讨论了生成函数法在求解递推关系和整数分拆中的应用.通过本文的总结，可以使人们对生成函数有一个比较清晰的认识，更加系统的掌握生成函数这一数学工具.关键词：生成函数；普通型生成函数；指数型生成函数；递推关系；整数分拆ABSTRACTIn this pa

2、per, the theory of generation function and the application in thecombinatorial mathematics is discussed. The generation function is also known asgenerating function, which is built on the theory of powerseries and polynomial .Generationfunction includes ordinary-sized and exponential type, they have

3、 their own applicationfields in the problem of calculations. Firstly, this paper introduces the basic theory ofgenerating function, including basic concepts, nature and some calculating skills ofgenerating functions coefficients. Secondly, introduces the basic models and applicationfields of ordinar

4、y-sized and exponential type generation function. Finally, discusses themethods of generation function in solving the recursive relations and partition. By thesummary of this paper, forming a more profound understanding on the generation function,and more systematic mastering the mathematical tool -

5、 generating function.Key words： generation function； ordinary-sized generation function； exponential type generationfunction； recursive relations； partition摘要IABSTRACTII1前言12基本知识22.1 基本概念22.2 基本性质32.3 生成函数的计算43普通型生成函数模型63.1 问题的提出63.2 普通型生成函数模型及其应用64指数型生成函数模型94.1 问题的提出94.2 指数型生成函数模型及其应用94.3 指数型生成函数系数

6、的计算技巧115生成函数在递推关系中的应用135.1 生成函数法在常系数线性齐次递推关系上的应用135.2 生成函数法在常系数线性非齐次递推关系上的应用156生成函数在整数分拆中的应用18结论20参考文献21致谢221前言生成函数乂称母函数，是计数问题中既简单乂精巧的数学模型，也是组合数学的一个重要理论和工具.1720年前后De Moivre首先使用了组合生成函数,通过使用生成函数得到斐波那契数的一个公式.1748年欧拉在他的著作中对分拆问题使用了生成函数，而他同时对概率生成函数的工作是18世纪后期发展起了的组合生函数理论的原始动力.最早提出生成函数的人是法国数学家LaplaceP.S在其18

7、12年出版的概率的分析理论中明确提出“生成函数的计算”，书中对生成函数思想奠基人一EulerL在18世纪对自然数的分解与合成的研究做了延伸与发展，生成函数的理论由此基本建立.曹汝成在生成函数中提出了车问题及其解法，Alan Tucker在应用组合数学中提出了生成函数系数的具体解法及一个求和的算法，RichardA.Brualdi具体提出了生成函数与递推函数的关系等.每本著作中作者所提的概念、所引用的符号以及表述方法都有一些共同点和差异.本文主要是系统的总结生成函数的基本理论和应用问题，使人们对生成函数有一个清晰的认识，比较简便的学会生成函数这一数学工具.本文第二部分主要回顾了生成函数的基本概念

8、及其性质，计算生成函数系数的一些技巧.在第三部分和第四部分中主要介绍了普通型生成函数和指数型生成函数的基本模型及其应用范围.第五部分和第六部分则具体讨论了生成函数在递推关系和整数分拆中的应用.2基本知识2.1 基本概念计数问题是组合数学的一个重要内容，而生成函数又是解决计数问题的一个重要的一般性的处理方法.基级数P(X) = % +qx + %2 +是我们所熟悉的多项式，我们定义幻为数列%,4,出，的生成函数，通常记为G4l.生成函数的中心思想是：首先使用多项式或基级数把需要研究的数列合为一个整体，通过研究多项式或基级数的性质以及使用合并同类项的方法，来研究数列的性质,从而得到相关的结论.例如

9、数列22,22广.21的生成函数是(x) = 20 +2,x + 22+这个生成函数的值为/( 二一用了非常简洁紧凑的方式显示了上述数列的序列信息.1 -2x下面列举了几个常见的生成函数.1 ?(1) = 1 + X + JC +1 -%1( + 1) 25 + 1)(+ 2) 31 + HX +厂 +JT2!3!(3)= 20 +2,x+22x2 +l-2x(4)- = a() +tzIx + tz2x2 +-ax(5) / = 1 + x + 2/ + + 止 + (1-力业YE?/ +32/ +. + /+(一)32r(7)- = (l2)x + (23) +(34)x3 +(1)xa

10、(I)6x(8) = (12 3)x + (23 4)x2 +(34 5)x3 + + & x (A +1) x (k + 2)xk + (17)(9) ex = l + -x + -x2 + + +1!2! k2.2基本性质首先假定，序列%,%的生成函数分别为P(x) = & alx + a2x2 Q(x) = b。x + 2x2 h因为生成函数与数列之间是一一对应的关系，所以研究两个数列之间的关系可以转化为研究其生成函数的关系，这样就给解题带来了许多便利.线性性质若 bn = can,则 Q(x) = cP(x)(2)若 cn = an + hll,则 C(x) = (x)+ P(x)乘积

11、性质(3)若，则 C() = Q(x)P(x)/=1移位性质0 (k / )(4)若 bli = 4，则 Q(x) = xi P(x)%. (k z)(5)若 bn = ak+i,则 Q(x) = J(P(x)-)xk=o(6)若=Z ai 则。(1)=i=0(7)若bll=Y a”则g(x) = P(1) XP(X),其中生是收敛的i=k1 Xi=k换元性质(8)若 bn = cnan,则 Q(x) = P(cx)求导与积分性质(9)若 btt = nan,则 Q(x) = xP,(x)(10)若 hn =-,贝IQ(x)=-VP(t)dt + lx J。2.3生成函数的计算计算生成函数系数

12、的方法是把比较复杂的生成函数化简为简单的二次式类型，或若干个二项式类型的生成函数的积，这样就比较容易得出所需的P的系数.我们需要用到牛顿二项式定理及其生成函数的性质.牛顿二项式定理，设实数,对一切x,y有(y = . 广=o U)其中二 二(T)(4i + l),V)制当。=时，变成我们所熟悉的二项式定理(l+x)n =1 + C(n,l)x+C(n,2)x2 + +特别的当-时，ook( n + k-y( + =()kho k )n ( h + k I A(5= : /k=o ky例 1 (l + x + x2 + + x10)(l + x + x2 +)5o解(1 + x + x2 + +

13、 x1 )(1 + x + -=1yllY 1 Y、1 Jll-=1)(j)11fl + 6- /2 + 67=(1 -x )(1+x+j1217/C(n, n)xnW1W1)52住+ 6f li 、C +X +)利用牛顿二项式求得生成函数的系数.例2已知A(x) = G伙3,求解AQ)的值.Gk3 = Gk* + 1)(Z + 2) -3Gk2-2Gk6x 3x(1 + x) 2xG伙(Z + l)(Z + 2), G伙2和G在2.1中已注明，本题利用生成函数的加法运算及其性质求得.例372在(/+/+/+)5中的系数，/系数是多少？解(2 +/+/+.)x)(l + x + x )中，的系数是，5-1 + 2J即15,所以的系数是15.同理可得5-1 + /:-10k-W3通型生成函数模型3.1 问题的提出在现实生活中我们经常遇见类似于这样的问题：5个苹果，4个橘子，3个梨，从中选出4个水果的组合数，及其组合方案.当然，通过列举法可以来解决上述问题，但当水果的种类和数量变多时，应用列举法就困难许多.在本节，我们在组合问题中引入了生成函数法，使解题的过程更加简便.3.2 普通型生成函数模型及其应用(1)求C%,6,%，%的女组合数，这是普通集合的组合问题.例1现在有n个不同的球，求从中选出三个球的组合数./ /1解 显然根据以前的学习，我们可以得到