浅论生成函数在组合数学中的应用

魏建刚

【摘 要】发生函数是组合数学中许多问题的首要解决方法，他可以将很多数学问题转化为生成函数问题，从而简单明了提供解题思路与方法，使得复杂困难的问题迎刃而解。本文主要研究生成函数在组合计数、整数拆分、递推问题和恒等式证明等问题中的应用，从而体现生成函数在组合数学中的作用。

【关键词】组合函数；数学；应用

引言

所谓生成函数也就是母函数，又被称为发生函数，它是链接离散函数和连续函数的结合点，是组合数学中许多问题的首要解决方法。可以将很多数学问题转化为生成函数问题，从而简单明了的为数学中的许多问题提供解题思路与方法，使得复杂困难的问题迎刃而解。

1.生成函数在组合计数中的应用

生成函数作为在组合计数学习中极其重要的一个工具，在处理某些相关问题时运用生成函数，往往会使问题简单明了。

例1.现有1分2分5分邮票，邮票可重复使用，则能贴出那些面值的邮票？每种面值有多少种贴法？

解：a 把表示为用1分2分5分邮票贴出面值为n的有票的不同贴法，则我们可以得到一个数列{a }的生成函数f（x）=∑n≥0anxn=（1+x+x2+x3+…）（1+x2+x4+…）（1+x5

+x10+…）

=1+x+2x2+2x3+3x4+4x5+…

根据生成函数展开式可知

x表示贴出面值为1分的方案有1种：1分

2x 表示贴出面值为2分的方案有2种：1分+1分，2分

2x 表示贴出面值为3分的方案有2种：1分+1分+1分，2分+1分

3x 表示贴出面值为4分的方案有3种：1分+1分+1分+1分，2分+1分+1分，2分+2分

……

由生成函数就可以看出，可以贴出那些面值的邮票，贴出n面值的邮票有多少种贴法。

通过上述例子我们可以看出，在现实学习生活中，很多问题看似复杂，处理起来毫无头绪，但只要我们合理的运用生成函数处理为，很多难题复杂题迎刃而解，且过程简单明了，容易掌握。

2.生成函数在整数拆分中的应用

在很多数学实际问题中， 往往会整数拆分与组合数学联系在一起，既将组合数学中的很多实际问题看做整数拆分问题。

例2.求方程x +x +x +x =12，满足0≤x ≤5，1≤x ≤4，3≤x ≤7，4≤x ≤6的整数解个数。

解：此类问题可看做是整数拆分问题，将12拆分成满足题干4个条件的整数和的方法问题。

通过分析可以构建如下生成函数g（x）=（1+x+…+x ）（x+x +x +x ）（x +x +…+x ）（x +x +x ）将函数展开，则其展开式中x 的系数a 则为符合条件的整数的放法数。

由上述问题不难看出，在组合数学中，整数拆分占有很重要的位置，用于研究所拆分函数的某些性质和所求结果，而生成函数又是解决整数拆分的重要手段和有效工具。

3.生成函数在线性递推数列通项中的应用

递推关系是数学中运用特别多的一种工具形式关系，很多数学中的关系都可以转化为递推关系，但是对于递推关系的处理上存在着一定的困难。此部分以递推数列通项为例，简要说明生成函数在数学递推关系中的重要作用。

4.生成函数在组合恒等式中的证明

在组合数学中往往会涉及到各种不同类型的组合恒等式的证明，融二项式系数恒等式、整数拆分恒等式等。在这些恒等式证明过程中往往存在计算量大或证明复杂等问题，将生成函数运用进恒等式证明可以使问题一目。以二项式为例，它在数学学习中占有很重要的位置，且在其他组合问题证明中往往也会运用二项式展开式系数。做此类题的一般先观察所正等式两边结构特点，然后构造生成函数，最后进行比较证明。

例3求证

分析：由于恒等式比较复杂运用组合计数公式化简存在一定的困难，但是根据左端式子规律构造二项式展开式的生成函数模型，对模型进行化简处理，从而证明等式成立

解：构造生成函数g（x）=（1+x）+2（1+x） +3（1+x） +…+n（1+x） 由此易发现，g（x）中x 所对应的系数应为恒等式的左端。

则我们对g（x）进行化简求和，利用错位相减法得到g（x）= 由此可得x 所对应的

项的系数为 既左边等于右边，则恒等式成立。

运用二项式的展开式证明组合函数的恒等问题是组合数学恒等式证明的重要方法，而在二项式的展开式处理上，又应用生成函数作为重要工具。关键在于如何适当的选取多个二项式，使其对应项的系数恰为所要证的恒等式，以此为生成函数，进而证明恒等成立。

5.总结

生成函数作为组合数学中的重要工具，在其应用中极为广泛，在此文章中我们住研究生成函数在递推关系中的应用，整数拆分中的应用，在组合计数问题中的应用及生成函数在恒等式证明中的应用，事实上生成函数的应用不仅仅局限于此。

【参考文献】

[1]王中平.生成函数在组合数学中的若干应用[J].贵阳学院学报（自然科学版），2016.01：1-7

[2]唐海军，余跃玉，李合朋.数学专业学生“组合數学”学习探析[J].乐山师范学院学报，2013.12：120-123