论文总字数：5237字

摘 要

生成函数在组合数学中居于重要地位,它能灵活的且广泛的应用于相关的组合问题中，它在证明各种有用的组合恒等式,以及组合计数、递推关系、整数分拆等方面也有巨大作用.本文主要从以上几个方面来研究生成函数在组合数学中的一些应用,从而体现了生成函数对解决相关组合数学问题的必要性.

关键词:生成函数，组合恒等式，组合计数，整数分拆，递推关系

Abstract: Generating function occupies an important position in combinatorial mathematics. It can be flexibly and widely used in related combinatorial problems. It can deduce or prove various useful combinatorial identities. In addition, it also plays an important role in Enumerative combinatorics, recurrence relation, integer splitting, etc. This paper mainly studies some applications of generative function in combinatorial mathematics from the above aspects, thus demonstrating the necessity of generative function in solving related combinatorial mathematics problems.

Key words: generating function, Combined identities, Enumerative combinatorics, Integer splitting, Recursive relation

目录

1 前言 4

2 组合恒等式证明问题 5

2．1 二项式系数恒等式的证明 5

2．2 另一些恒等式的证明 5

3 组合计数以及整数分拆问题 6

3．1 组合计数问题 6

3．2整数分拆问题 7

4 关于递推关系的应用 8

5 总结 11

6 参考文献 12

1 前言

我们常常又把生成函数叫做母函数或者发生函数，它具有广泛的应用性，其主要就是联系离散的序列和相应的幂级数，通过对幂级数之间的运算，来得到相应的离散序列之间的一些性质及其相互关系等.

实际上，生成函数就是一种形式幂级数，所以有必要先来给出形式幂级数的定义:

定义 1.1 形式幂级数是指形如 ……的表达式，其中的是系数序列^[1].

这里的形式幂级数的概念实质上是二项式概念的推广，并且当两个形式幂级数的系数全部对应相等时，就说这两个形式幂级数相等.

下面我们给出生成函数的定义:

定义 1.2 对于给定的实数或复数序列 ，，…，…，我们称形式幂级数 = 为这个序列的生成函数，并且一般把这种形式的生成函数称为普通型生成函数^[2].

定义1.3 对于给定的实数或复数序列， ，，…， ，…，我们称形式幂级数 = 为序列的指数型生成函数^[3].

有时我们也将序列的生成函数记为G，并且上面定义中的序列 通常是由具有某种实际组合意义的正整数构成. 下面我们来介绍生成函数的重要运算性质:

定理 1.4 设，为两个数列，则

(1) G±G= G;

(2) GG= G^[4]．

证明:

(1) 因为 G=，G=．

所以有 GG= = = G ．

( 2)

证毕.

2组合恒等式证明问题

2．1 二项式系数恒等式的证明

我们以二项展开式作为生成函数来推导或证明一些组合恒等式. 其一般思路是，先观察，然后构造，再通过比较，来得到要证的恒等式. 下面我们结合具体例子来说明生成函数在证明二项式恒等式中的应用:

例2.1: 求证:

=^[4] .

析:观察可知恒等式的左边比较复杂，但是，我们发现等式左端的规律性还是比较强，为此设法以二项展开式为生成函数，它以等式左端作为确定项的系数，再对所构造的生成函数进行化简处理，看能否得到右端对应的系数.

证明:我们构造如下生成函数:

=^[5].

容易发现中项对应的系数为

，

此即为欲证恒等式的左端. 现在再对进行化简求和，利用错位相减法可得， =.

由此可得对应的项的系数为

=．

两端是同一生成函数对应项的系数，所以即证得结论，证明完毕.

2．2 另一些恒等式的证明

除了上述常见的组合恒等式，另外还有其他类型的组合恒等式，比如可重集上的组合恒等式，Fibonacci恒等式，这些恒等式的证明也可以借助生成函数这一工具，这一节我们简要介绍生成函数在可重集上的恒等式证明中的应用，先看一个定理:

定理2.2 对于，满足的绝对值小于1，有

^[6].

证明: 由于对于，满足的绝对值小于1，有 ( 1 x)

取 ( n 为正整数) ，由

=.

即证得引理，证毕.

例2.2 证明:从n个不同的物体中允许重复地选k个物体的方式数为

．

证明:这个问题其实可以等价地表述为

重集的 组合数为 ．

如果用来表示能够重复地在n个不相同的物体中选取k个的方法数，经分析，序列的生成函数为

.

由定理2.2 可得，

.

所以得到．证明完毕.

3 组合计数以及整数分拆问题

3．1 组合计数问题

组合计数是学习组合数学不可或缺的一部分，我们从高中开始学习的排列组合数就是用来计算一些具体问题的方法数，并为概率论与数理统计的学习与研究打下基础，两者紧密结合. 因此，很有必要对组合计数进行研究，而生成函数作为一个极其重要的工具，通过它来分析和解决一些组合计数问题，有时会有巧妙的效果.

现在我们先看几个问题:

例3.1 : 一个盒子内装有3支红笔，2支黑笔，4支蓝笔，这些笔除颜色外都相同，现在从盒子中任意取3支笔，问有多少种不同的取法数^[7]?

解答:作形式表达式 .

如果每次在盒子中取出n个的能过重复的组合数用表示，那么这个数列的生成函数可表示如下:

=

所以，生成函数的展开式中的系数9即代表从盒子中任意取3支笔的所有不同方法数.

例3.2: 现有3种砝码，分别重为1克，2克，5克，则用这些砝码能称多重的物体，每个物体能有几种称法？

剩余内容已隐藏，请支付后下载全文，论文总字数：5237字