母函数

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

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

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

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

注意母函数本身并不是一个从某个定义域射到某个上域的函数，名字中的“函数”只是出于历史原因而保留。

历史

母函数于1730年由法国数学家亚伯拉罕·棣莫弗 (Abraham de Moivre) 首次提出，以解决一般线性重复问题。^[1]

数学家乔治·波利亚 (George Pólya) 在《数学与猜想》（Mathematics and plausible reasoning）中写道：

“母函数”这个名称是由拉普拉斯命名的。然而，欧拉却早在拉普拉斯[...]之前就使用了母函数这个工具，却没有为它命名。他将这个数学工具应用在《组合分析》和《数论》中的几个问题上。

瑞士数学家雅各布·伯努利在考虑“当投掷n粒骰子时，加起来点数总和等于m的可能方式的数目”这个问题时首先使用了母函数方法，并得出可能的数目是${\displaystyle (x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{n}}$的展开式中${\displaystyle x^{m}}$项的系数。之后欧拉在研究自然数的分解时也使用了母函数方法并奠定了母函数方法的基础。1812年，法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论。

定义

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

普通母函数

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

${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$

如果${\displaystyle a_{n}}$ 是某个离散随机变量的概率质量函数，那么它的母函数被称为一个概率母函数。

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

${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}}$。

指数母函数

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的指数母函数是：

${\displaystyle EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$

泊松母函数

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的泊松母函数是：

${\displaystyle PG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}e^{-x}{\frac {x^{n}}{n!}}}$

L级数

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的L级数是：

${\displaystyle LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}}$

注意这里的下标 n 从1 而不是0 开始。

贝尔级数

关于算术函数 :${\displaystyle f(n)}$ 和 ${\displaystyle p}$ 的贝尔级数是：

${\displaystyle f_{p}(x)=\sum _{n=0}^{\infty }f(p^{n})x^{n}}$

狄利克雷级数母函数

狄利克雷级数经常被用作母函数，尽管实际上狄利克雷级数并不是严格意义上的形式幂级数。序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的狄利克雷级数母函数是：

${\displaystyle DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}}$

当 ${\displaystyle a_{n}}$ 是积性函数时狄利克雷级数比较有用，因为这时的母函数可以写成一系列贝尔级数的欧拉积：

${\displaystyle DG(a_{n};s)=\prod _{p}f_{p}(p^{-s})\,}$

如果 ${\displaystyle a_{n}}$是狄利克雷特征，那么它对应的狄利克雷级数母函数被称为狄利克雷L函数。

一般母函数

求和

${\displaystyle \displaystyle \sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}}$用于等比数列求和或推导级数${\displaystyle \displaystyle \sum _{n=0}^{\infty }n^{m}x^{n}}$。

不定方程的解数

${\displaystyle \displaystyle \sum _{n=0}^{\infty }{\binom {n+k}{k}}x^{n}={\frac {1}{(1-x)^{k+1}}}}$用于求解一次不定方程的解数，类似隔板法。

对于非负整数${\displaystyle x_{1},x_{2},...,x_{k}}$，${\displaystyle x_{1}+x_{2}+...+x_{k}=n}$有${\displaystyle {\binom {n+k-1}{k-1}}}$个解：

${\displaystyle \displaystyle {\frac {1}{(1-x)^{k}}}=\sum _{n=0}^{\infty }{\binom {n+k-1}{k-1}}x^{n}}$

对于非负整数${\displaystyle x_{1},x_{2},...,x_{k}}$，${\displaystyle x_{1}+2x_{2}+2x_{3}=m}$有${\displaystyle {\binom {[{\frac {m}{2}}]+2}{2}}}$个解：

${\displaystyle \displaystyle {\frac {1}{(1-x)(1-x^{2})^{2}}}={\frac {1+x}{(1-x^{2})^{3}}}=(1+x)\sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{2n}=\sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{2n}+{\binom {n+2}{2}}x^{2n+1}}$^[3]

参见

• 矩生成函数
• 概率母函数
• 动差母函数
• 其他处理数列的组合技巧，如：
  • 递归关系
• Z转换
• 整数分拆

参考来源

1. Knuth, Donald E. §1.2.9 Generating Functions. Fundamental Algorithms. The Art of Computer Programming 1 3rd. Addison-Wesley. 1997. ISBN 0-201-89683-4.
2. 赫伯特·维尔夫（Herbert S. Wilf）. 母函数理论. Academic Press. 1994 [2009-11-26]. （原始内容存档于2013-02-11）.
3. 王迪吉 高福康 段芳. 关于不定方程的整数解及其解数的讨论. 新疆师范大学学报(自然科学版). 2008, (3) [2015-09-20]. （原始内容存档于2019-06-03）.