母函数

在数学中，某个无穷序列$(a_{n})_{n\in \mathbb {N} }$ 的母函数（又称生成函数，英語：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。母函数一般用有关原始序列进行操作后得到的封闭形式表示，而非一个序列。

母函数可分为很多种，包括普通母函数、指数母函数、朗伯级数、贝尔级数和狄利克雷级数。对任何序列理论上都可以写出以上每个类型的一个母函数（除了朗伯级数和狄利克雷级数需要序列从$a_{1}$而非$a_{0}$开始），但是选用不同形式来解决问题的难度有显著区别。最有用的母函数类型取决于具体问题和序列本身的性质。

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

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

历史

母函数於1730年由法國數學家亞伯拉罕·棣莫弗 (Abraham de Moivre) 首次提出，以解決一般線性重複問題。

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

“母函数”這個名稱是由拉普拉斯命名的。然而，欧拉卻早在拉普拉斯[...]之前就使用了母函數這個工具，卻沒有為它命名。他將這個數學工具應用在《組合分析》和《數論》中的幾個問題上。

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

定义

母函数具有类似于袋子的功能。我们不必把一些小物件分开携带（这样会很尴尬不便），而是把他们全部放在一个袋子里，这样我们只需要携带一件物品——这个袋子。

——乔治·波利亚，数学与猜想 (1954)

母函数就是一列用来展示一系列数字的挂衣架。

——赫伯特·维尔夫，Generatingfunctionology (1994)

敛散性

不像一个普通序列，形式幂级数不需要收敛：实际上，母函数并不真的是一个“函数”，而且“变量”始终是一个不定元（indeterminate形式变量）。无穷多维数列可以用含有多个不定元的形式幂级数表示，因此母函数不是一般意义下从某个定义域射到某个上域的函数。

这些关于不定元$x$的表达式可包括算数运算、微分运算、与其他母函数的复合运算（比如代入）。这些运算也对函数有定义，因此结果看起来像关于$x$的函数。封闭形式的表达式确实可以理解为对某些（足够小的）具体数值$x$可求值的函数，也有形式级数作为它的级数展开。这解释了“母函数”这一名称。但是不一定需要满足这种解释成立，因为当$x$取非零数时，形式级数并不需要成为收敛数列。

局限性

不是所有作为关于$x$的函数有意义的表达式都作为形式级数有意义。例如，$x$的负数和分数指数幂就是没有对应形式幂级数的函数的例子。

分类

普通母函数（OGF）

没有特别说明时，母函数通常指普通母函数。序列$(a_{n})_{n\in \mathbb {N} }$的普通母函数是：

$$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}$$如果$a_{n}$ 是某个离散随机变量的概率质量函数，那么它的普通母函数称为一个概率母函数。

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

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

指数母函数（EGF）

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

$$\operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}$$对于含有有标号对象的组合计数问题，指数母函数通常来说比普通母函数更方便。 指数母函数的另一个优势是易于把线性递推公式转化为微分方程领域。以斐波那契数列$\{f_{n}\}$为例，它满足线性递推公式$f_{n+2}=f_{n+1}+f_{n}$，它对应的指数母函数有如下形式：$\operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}$，且易证它的导数满足微分方程$\operatorname {EF''} (x)+=\operatorname {EF'} (x)+\operatorname {EF} (x)$，直接对应了前面的递推公式。这样看来，阶乘项$n!$只是为了在对$x^{n}$进行微分时归一化。

泊松母函数

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

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

朗伯级数

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

$$\operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}$$注意在朗伯级数中，下标$n$从1 而不是0 开始，否则第一项会未定义。

幂级数展开$b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)$中的朗伯级数系数（整数$n\geq 1$）与因数之和$b_{n}=\sum _{d|n}a_{d}$有关。

贝尔级数

序列$(a_{n})_{n\in \mathbb {N} }$的贝尔级数是一个同时关于不定数$x$和质数$p$的表达式：

$$\operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.$$

狄利克雷级数母函数（DGF）

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

$$DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}$$当 $a_{n}$ 是积性函数时狄利克雷级数非常有用，因为这时的母函数可以写成一系列贝尔级数的欧拉积：

$$\operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,$$如果 $a_{n}$是狄利克雷特征，那么它对应的狄利克雷级数母函数被称为狄利克雷L函数。我们还可证明如上所写朗伯级数展开的一对系数和它们的狄利克雷级数母函数的关系，即$$[x^{n}]\operatorname {LG} (a_{n};x)=b_{n}$$

当且仅当

$$\operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s)$$，其中$\zeta (s)$是黎曼ζ函数。

狄利克雷级数母函数$\operatorname {DG} (a_{k};s)=\zeta (s)^{m}$生成的数列对应的普通母函数为：

$$\sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots$$

多项式序列母函数

母函数的思想可以延伸到其他方面里。例如，二项式型的多项式序列由如下母函数生成：$$e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}$$其中$p_{n}(x)$是一序列多项式，$f(t)$是特定形式的函数。Sheffer序列就是由类似方法生成的。

更复杂的母函数生成的多项式序列如：

• 阿佩尔多项式
• 切比雪夫多项式
• 差分多项式
• 广义阿佩尔多项式
• q-查分多项式

其他母函数

其他通过更复杂母函数生成的序列包括：

• 双重指数母函数，如贝尔数
• 母函数和对角母函数的阿达玛乘积，及他们对应的积分变换

一般母函数

求和

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

不定方程的解数

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

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

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

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

$\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}$

參見

• 矩生成函數
• 概率母函数
• 動差母函數
• 其他處理數列的組合技巧，如：
  • 遞歸關係
• Z轉換
• 整數分拆