生成函数在递推关系问题上的应用

熊传霞

摘 要：该文论述了生成函数的概念及相关理论，生成函数方法作为一种特殊的辅助计算方法，能简单而有效的解决组合数学和计算数学中的递推关系、排列组合等问题。文章介绍了如何使用生成函数方法解决递推关系问题，并且结合实例中进行了应用。

关键词：递推关系 生成函数 应用 计算

中图分类号：O174 文献标识码：A 文章编号：1674-098X（2016）04（a）-0154-02

递推关系是数学中特有的思维方法，探求某一事物、现象所遵循的一般规律，并用数学语言表达出来，在数学学科的所有分支中都有着重要的应用。比如：求解排列组合问题、归纳数列递推关系问题都需要用到递推思维方法。但是，递推思维方法比较抽象，递推关系的求解一般也比较困难。而生成函数正是解决这一难题最好的数学工具，经过长期的理论实践研究，生成函数方法已经发展成为了解决递推关系问题的重要工具之一。

1 生成函数的相关知识

1.1 生成函数的定义

生成函数又称为做母函数。生成函数方法是离散数学的一个重要分支，生成函数方法把离散数学和连续数学串联沟通在一起。在分析组合数学问题中，在组合计数方面生成函数具有天生的优越性，成为了解决组合计数问题的强大工具。

生成函数的中心思想是：首先使用多项式或幂级数把需要研究的数列合为一个整体，通过研究多项式或幂级数的性质以及使用合并同类项的方法，来研究数列的性质，从而得到相关的结论。

1.2 生成函数的基本性质

1.3 生成函数的计算

计算生成函数系数的方法是把比较复杂的生成函数化简为简单的二次式类型，或若干个二项式类型的生成函数的积，这样就比较容易得出所需的的系数。需要用到牛顿二项式定理及其生成函数的性质。

2 数学中的递推关系问题

递推关系几乎在所有的数学领域中都占据着重要的比例和广泛应用。通常情况下递推关系的求解比较困难，仅局限于使用递推关系的一些定义很多问题是不能解决的，并且所涉及的领域也很广。递推关系的研究还可以追溯到斐波纳契关系：≥0，F0=0，F1=1，它是比萨的数学家Leonardo最先给出的。

线性递推关系可定义为，数列必须有连续个k项满足，满足此式的数列叫它为数列的一个递推关系式。

由递推关系式及满足k个初始值可以确定的一个数列叫做递推数列。因此，无论是牵涉到递推数列的证明题，解析题，还是需要建立递推关系式的综合题，那么解决递推数列的核心是求通项公式，也是最基本的步骤。

3 生成函数法应用于递推关系的求解

数学中很多求排列组合计算问题时通常都会归结为求某个数列的通项公式，而直接求某些数列的通项公式常常比较艰难，但可以求所满足的递推关系，那么生成函数是首选的方法，并且生成函数是求递推数列关系的一种重要的思维和常用的方法。

3.1 生成函数法在常系数线性齐次递推关系上的应用

在上述例中使用了错位相加减的方法，大家发现，使用生成函数的方法来求解比传统的方法容易得多。

3.2 生成函数法在常系数线性非齐次递推关系上的应用

4 结语

该文将生成函数分为普通型生成函数和指数则型生成函数通过问题引入、问题分析、问题解决、问题延伸的步骤介绍了应用生成函数法求解常系数线性非齐次递推关系和常系数线性齐次递推关系。通过例子可以看出，在递推关系问题的求解上，生成函数方法是比较有效，已经得到了普遍广泛的应用。

参考文献

[1]罗建林，张艳红.利用生成函数求解递推关系[J].科技信息，2009（28）：386.

[2]肖启明.利用母函数法求解一类递推关系[J].宜春学院学报，2006（4）：1-3.

[3]程晓生.浅谈生成函数的应用[J].科技风，2013（20）：183.

[4]安永红，张春霞.生成函数的若干应用[J].呼伦贝尔学院学报，2010（3）：78-80.