母函数

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

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

母函数的表示一般使用解析形式，即写成关于某个形式变量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年，法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论。

定义

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

普通母函数

普通母函数就是最常见的母函数。一般来说，序列$(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}$。

指数母函数

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

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

泊松母函数

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

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

L级数

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

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

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

贝尔级数

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

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

狄利克雷级数母函数

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

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

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

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

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

一般母函数

求和

$\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轉換
• 整數分拆