生成函数理论及应用论文

《生成函数理论及应用论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科毕业论文第1页共29页1引言组合数学（CombinatorialMathematics），又称为离散数学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面问题。组合数学主要内容有图论、组合计数、组合设计、组合矩阵、组合优化等。有时人们也把组合数学和图论加在一起看作离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析

2、和代数占统治地位的局面。组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。组合数学是现代数学中发展较快的一门学科，当今，组合原理中的许多问题是数学中的精华。组合原理的应用也涉及到自然科学和社会科学的许多领域。例如：它在计算机科学、编码理论、通信网络、电子工程、实验设计、交通运输、社会经济学、管理科[1]学等领域中都有着广泛的应用价值，特别是在计算机科学中有着重要的应用。组合数学的研究方法在其他学科以及生产生活中被广泛应用，常见的有：鸽巢原理、计数

3、技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以[2]及组合结构等等。本文学习研究生成函数理论以及应用,前半部分介绍了生成函数的基本理论，包括基本概念及其性质,接着介绍普通型生成函数和指数型生成函数的基本模型及其应用范围，而后又具体讨论了生成函数法在求解递推关系和整数拆分中的应用。让大家对生成函数基本理论有一个具体的认识。后半部分将介绍生成函数理论在其他学术研究以及生活中的应用，只有将研究的理论应用于实际，我们的研究才会有价值。2生成函数生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。

4、生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多，并被广泛应用。在第一节中，我们首先介绍生成函数的基本概念；在第二节中我们介绍生成函数的性质，在第三、四节中，我们介绍普通型生成函数和指数型生成函数的基本模型，及其应用范围，在第五节中，我们介绍生成函数的基本运算，在第六节中，我们具体讨论了生成函本科毕业论文第2页共29页数法在求解递推关系和整数拆分中的应用。2.1生成函数的基本概念生成函数的中心思想是：对于一个有限或无限实数列，，，…，用幂级数=…，使之成为一个整体，然后通过研究幂

5、级数()，导出实[3]数列，，，…的构造和性质。定义1设是一个抽象符号，(=，，，…)为实数，如果函数()可以表示成=……，则称()为数列(=，，，…)的生成函数。并约定，若某个=(=，，，…)，则项可略去。比如=()是数列，，，…的生成函数。无穷序列，…，，…的生成函数为=……。有了生成函数的概念，就可以讨论它与组合计数的关系了。因此，我们先看一

6、个具体问题。问题把4个相同的球放入5个不同的盒子里，要求第一、二、三每盒最多不超过个，第四、五每盒最多不超过两个。问有多少种放法？用表示个球，现设计符合题意的一个放法：第一、二两盒里各放个，第三盒里放个，第四盒里放个，第五盒里放个。这个放法我们可以用符号表示为。另一方面，我们看多项式()()=，比如，从第一、二个括号中各取，第三个括号取，第四个括号取，第五个括号取，然后相乘，即得到展开式中的一个

7、4项(=4)。值得注意的是，该4项(看形式)恰是前述符合题意的分配球的一种设计方案。因此，通过上面的分析，满足题意的分配球的方案与多项式()()的展开式中的4项正好一一对应，故多项式()()的展开式中4项的系数即为满足题意的分配球的方案数目。生成函数最绝妙的是，某些生成函数可以化简为一个很简单的函数。也就是说，不本科毕业论文第3页共29页一定每个生成函数都是用一长串多项式来表示的。比如，这个函数=（属于自然数），它的生成函数就是

8、=4…（每一项都是1，即使=时也有系数为，所以有常数项）。再仔细一看，这就是一个有无穷多项的等比数列求和。如果-<<，那么()就等于()了。在研究生成函数时，我们都假设级数收敛，因为生成函数的