毕业论文-生成函数的理论与应用.doc
《毕业论文-生成函数的理论与应用.doc》由会员分享,可在线阅读,更多相关《毕业论文-生成函数的理论与应用.doc(23页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、xx大学毕业论文摘 要本文系统的论述了生成函数的理论及其在组合数学和计算数学中的应用.生成函数又称母函数,它是在幂级数和多项式理论的基础上建立的.生成函数可分为普通型生成函数和指数型生成函数,他们在计算问题中有各自的应用范围.本文首先介绍了生成函数的基本理论,包括基本概念、性质及其系数计算的一些技巧.其次介绍了普通型生成函数和指数型生成函数的基本模型及其应用范围.最后则具体讨论了生成函数法在求解递推关系和整数分拆中的应用.通过本文的总结,可以使人们对生成函数有一个比较清晰的认识,更加系统的掌握生成函数这一数学工具.关键词: 生成函数;普通型生成函数;指数型生成函数;递推关系;整数分拆ABSTR
2、ACTIn this paper, the theory of generation function and the application in the combinatorialmathematics is discussed. The generation function is also known as generating function, which is built on the theory of powerseries and polynomial.Generation function includes ordinary-sized and exponential t
3、ype, they have their own application fields in the problem of calculations. Firstly, this paper introduces the basic theory of generating function, including basic concepts, nature and some calculating skills of generating functions coefficients. Secondly, introduces the basic models and application
4、 fields of ordinary-sized and exponential type generation function. Finally, discusses the methods of generation function in solving the recursive relations and partition. By the summary of this paper, forming a more profound understanding on the generation function. and more systematic mastering th
5、e mathematical tool - generating function.Key words:generation function;ordinary-sized generation function;exponential type generation function;recursive relations;partition 目 录摘要IABSTRACT.II1前言.12基本知识.22.1基本概念.22.2基本性质32.3生成函数的计算.43普通型生成函数模型.63.1问题的提出.63.2普通型生成函数模型及其应用.64指数型生成函数模型.94.1问题的提出94.2指数型生
6、成函数模型及其应用.94.3指数型生成函数系数的计算技巧.115生成函数在递推关系中的应用.135.1生成函数法在常系数线性齐次递推关系上的应用135.2生成函数法在常系数线性非齐次递推关系上的应用.156生成函数在整数分拆中的应用.18结论.20参考文献.21致谢.22- 20 -1 前言 生成函数又称母函数,是计数问题中既简单又精巧的数学模型,也是组合数学的一个重要理论和工具. 1720年前后De Moivre首先使用了组合生成函数,通过使用生成函数得到斐波那契数的一个公式.1748年欧拉在他的著作中对分拆问题使用了生成函数,而他同时对概率生成函数的工作是18世纪后期发展起了的组合生函数理
7、论的原始动力.最早提出生成函数的人是法国数学家LaplaceP.S.在其1812年出版的概率的分析理论中明确提出“生成函数的计算”,书中对生成函数思想奠基人Euler L在18世纪对自然数的分解与合成的研究做了延伸与发展,生成函数的理论由此基本建立.曹汝成在生成函数中提出了车问题及其解法,Alan Tucker在应用组合数学中提出了生成函数系数的具体解法及一个求和的算法,RichardA.Brualdi具体提出了生成函数与递推函数的关系等.每本著作中作者所提的概念、所引用的符号以及表述方法都有一些共同点和差异.本文主要是系统的总结生成函数的基本理论和应用问题,使人们对生成函数有一个清晰的认识,
8、比较简便的学会生成函数这一数学工具.本文第二部分主要回顾了生成函数的基本概念及其性质,计算生成函数系数的一些技巧.在第三部分和第四部分中主要介绍了普通型生成函数和指数型生成函数的基本模型及其应用范围.第五部分和第六部分则具体讨论了生成函数在递推关系和整数分拆中的应用.2 基本知识2.1基本概念 计数问题是组合数学的一个重要内容,而生成函数又是解决计数问题的一个重要的一般性的处理方法. 幂级数是我们所熟悉的多项式,我们定义为数列的生成函数,通常记为1 . 生成函数的中心思想是:首先使用多项式或幂级数把需要研究的数列合为一个整体,通过研究多项式或幂级数的性质以及使用合并同类项的方法,来研究数列的性
9、质,从而得到相关的结论.例如 数列 的生成函数是 这个生成函数的值为用了非常简洁紧凑的方式显示了上述数列的序列信息.下面列举了几个常见的生成函数2.(1)(2)(3)(4)(5)(6)(7)(8)(9)2.2基本性质首先假定,序列,的生成函数分别为因为生成函数与数列之间是一一对应的关系,所以研究两个数列之间的关系可以转化为研究其生成函数的关系,这样就给解题带来了许多便利.线性性质(1) 若 ,则 (2) 若 ,则 乘积性质 (3) 若 =,则 移位性质(4) 若 ,则 (5) 若 ,则 )(6) 若 ,则 =(7) 若 ,则 =,其中是收敛的换元性质(8) 若 ,则 求导与积分性质(9) 若
10、,则 (10) 若 ,则 =2.3生成函数的计算 计算生成函数系数的方法是把比较复杂的生成函数化简为简单的二次式类型,或若干个二项式类型的生成函数的积,这样就比较容易得出所需的的系数.我们需要用到牛顿二项式定理及其生成函数的性质.牛顿二项式定理,设实数,对一切有 其中=,当时,变成我们所熟悉的二项式定理特别的当时, 例1 求解。解 = =利用牛顿二项式求得生成函数的系数.例2 已知,求解的值.解= = ,和在2.1中已注明,本题利用生成函数的加法运算及其性质求得.例3 在中的系数,?解= = 中的系数是即15,所以的系数是15.同理可得 =3 通型生成函数模型3.1问题的提出在现实生活中我们经
11、常遇见类似于这样的问题:5个苹果,4个橘子,3个梨,从中选出4个水果的组合数,及其组合方案.当然,通过列举法可以来解决上述问题,但当水果的种类和数量变多时,应用列举法就困难许多.在本节,我们在组合问题中引入了生成函数法,使解题的过程更加简便.3.2普通型生成函数模型及其应用(1) 求的组合数,这是普通集合的组合问题.例1 现在有n个不同的球,求从中选出三个球的组合数.解 显然根据以前的学习,我们可以得到三个球的组合数为,一般的对于r组合数有,.我们知道是二项式中的系数,所以我们可以用多项式因子的乘积来表示题意信息,因子相乘后拆开的系数就是对应的所选的组合数,即可用生成函数来解决此题.(2)求,
12、的组合数.例2 下面我们来解决3.1中所提出的问题.解 我们可以用方程整数解的方法来对这一组合问题建模,3.1中的问题我们可以表示为= 4的形式,其中分别代表选取苹果,橘子,梨的个数,05, 04, 03.基于多项式,我们想要建立多项式因子的乘积,使得当这些因子乘开时,得到所有的乘积,拆开后所得多项式中的系数就是选出4个水果的组合数,所以我们需要三个因子,每个因子应该包含的可能取值.即 (1+),(1+),(1+)我们所需的生成函数是上述三个因子的乘积,对于组合方案:我们可用代表苹果,代表橘子,代表梨,展开多项式因子的乘积,使得=,即= 5的,的可能的取值是我们所求的组合方案,如当= 1,=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业论文 生成 函数 理论 应用
限制150内