母函数

2015.01.20 14:53 Tue| 5 visits oi_2015| 2015_算法笔记| Text

以下内容摘自 Wiki 百科。

母函数就是一列用来展示一串数字的挂衣架。 —— 赫伯特·维尔夫

概述

在数学中,某个序列 $(a_n)_{n \in \mathbb{N}}$ 的母函数(又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

母函数可分为很多种,包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。

母函数的表示一般使用解析形式,即写成关于某个形式变量 x 的形式幂级数。对幂级数的幂级数|收敛半径中的某一点,可以求母函数在这一点的无穷级数|级数和。但无论如何,由于母函数是形式幂级数的一种,其级数和不一定对每个 x 的值都存在。

母函数方法不仅在概率论的计算中有重要地位,而且已成为组合数学中一种重要方法。此外,母函数在有限差分计算、特殊函数论等数学领域中都有着广泛的应用。

定义

普通母函数就是最常见的母函数。一般来说,序列 $(a_n)_{n \in \mathbb{N}}$ 的母函数是:

多重下标的序列也可以有母函数。例如,序列 $(a_{m,n})_{m \in \mathbb{N},n \in \mathbb{N}}$ 的母函数是

一般母函数

当序列为常数 1 时,不妨令 $|x|<1$ ,得到 $\displaystyle \sum_{n=0}^{\infty} x^n =\frac{1}{1-x}$ 这一性质。

另外对于形如 $a$, $a^2$, $a^3$, $a^4$, ... 的序列,

由此,显然可以推导出

另外,对于形如 1, 0, ..., 0, 1, 0, ..., 0, 1, 0, ... 的序列,

对于序列 1, 2, 3, 4, ...,

将其一般化,得

另外,因为

可以得到对于平方数列 0, 1, 4, 9, ... 母函数为