生成函数 · aiwiki.page

生成函数是将数列的各项作为级数的系数，从而表示该数列的数学表达式。最常见的形式是将数列 $a_0,a_1,a_2,\ldots$ 与幂级数 $A(z)=\sum_{n\ge0}a_nz^n$ 对应起来。对这一个表达式进行运算，就相当于对数列进行相应的运算，因此生成函数是组合数学、概率和算法分析中的重要工具。根据具体用途，可以将这类级数视为纯粹的形式代数对象，也可以将其视为收敛的函数。(aofa.cs.princeton.edu)

定义与解释

数列的普通生成函数（OGF）定义为

A(z)=\sum_{n=0}^{\infty}a_nz^n.

记号 $[z^n]A(z)$ 表示“ $A(z)$ 中 $z^n$ 的系数”，因此 $[z^n]A(z)=a_n$ 。对于计数数列，指数记录对象的大小，系数记录具有该大小的对象数量。有限数列对应一个多项式，其后的系数均视为零。(aofa.cs.princeton.edu)

例如，数列 $1,1,1,\ldots$ 的生成函数为

1+z+z^2+\cdots=\frac{1}{1-z},

这里使用了等比级数恒等式。类似地，

\sum_{n\ge0}nz^n=\frac{z}{(1-z)^2}.

这些简洁的表达式保留了原数列的每一个系数。(aofa.cs.princeton.edu)

形式观点与解析观点

形式幂级数由其系数确定，不要求数值上的收敛。两个形式幂级数相等，意味着对应的系数逐项相等。在域（数学）上，形式级数存在乘法逆元，当且仅当其常数项系数非零。因此，无论是否给 $z$ 赋予数值， $1/(1-z)$ 在形式意义下都是有意义的。(math.cmu.edu)

对于增长很快的数列，这一区别尤为重要。级数

\sum_{n\ge0}n!z^n

的收敛半径为零，但它仍是有效的形式生成函数。如果级数在零点附近收敛，就可以使用复分析方法，包括通过围道积分提取系数，以及根据奇点进行估计。(math.cmu.edu)

代数运算

设 $A(z)=\sum a_nz^n$ ， $B(z)=\sum b_nz^n$ 。对它们进行的运算，可以直接从系数的角度解释：

运算	对系数的作用
$A(z)+B(z)$	逐项相加： $a_n+b_n$
$z^rA(z)$ ， $r\ge0$	向后移 $r$ 位，并在开头补零
$A(z)B(z)$	$\displaystyle c_n=\sum_{k=0}^{n}a_kb_{n-k}$
$zA'(z)$	将第 $n$ 项乘以权重 $n$
$\displaystyle A(z)/(1-z)$	求部分和： $\displaystyle s_n=\sum_{k=0}^{n}a_k$

因此，乘法实现了离散卷积，而求导数则实现了与下标有关的加权。这些规则解释了为什么涉及求和与移位的关系，往往能转化为更简单的生成函数方程。(math.cmu.edu)

主要类型

指数生成函数

数列的指数生成函数（EGF）定义为

E(z)=\sum_{n\ge0}a_n\frac{z^n}{n!}, \qquad a_n=n![z^n]E(z),

其中 $n!$ 为阶乘。对于常数数列 $a_n=1$ ，其指数生成函数是指数函数 $e^z$ ，而不是 $1/(1-z)$ 。(aofa.cs.princeton.edu)

指数生成函数特别适合用于计数带有互异标号的结构。两个指数生成函数相乘，所编码的系数为

c_n=\sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k}.

二项式系数表示从全部标号中选出归属于第一个组成部分的 $k$ 个标号的方式数。这使带标号结构的乘积有别于普通乘积，后者不包含这一分配因子。(aofa.cs.princeton.edu)

多元生成函数

一个生成函数可以同时记录多个参数：

A(z,u)=\sum_{n,k\ge0}a_{n,k}z^nu^k.

这里， $z$ 可以标记对象的大小， $u$ 则标记另一个统计量，例如树的叶节点数。只要代入有明确定义， $A(z,1)$ 就只按大小对对象进行计数。对 $u$ 求导，会按对象的这一附加统计量进行加权，从而可以求出平均值和高阶矩。(ac.cs.princeton.edu)

其他生成级数

不同的系数编码方式适用于不同的运算。狄利克雷生成级数

D(s)=\sum_{n\ge1}\frac{a_n}{n^s},

在数论中很有用，因为其乘法通过约数而非加法来组合下标：

c_n=\sum_{d\mid n}a_db_{n/d}.

因此，选择生成级数，在一定程度上也是在选择要把哪些数列运算转化为乘法、求导或其他简单变换。(math.cmu.edu)

求解递推关系

生成函数可以将许多递推关系转化为代数方程或微分方程。通常的步骤是：将递推式乘以 $z^n$ ，对其适用的下标求和，处理初始项，再求解所得方程。(aofa.cs.princeton.edu)

以斐波那契数列为例，设

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge2).

记 $F(z)=\sum_{n\ge0}F_nz^n$ ，可得

F(z)-z=zF(z)+z^2F(z),

因此

F(z)=\frac{z}{1-z-z^2}.

将分母因式分解，再作部分分式分解并展开，就能得到 $F_n$ 的显式表达式。初始条件不可或缺：仅凭递推关系无法确定分子。(math.mit.edu)

组合结构的计数

生成函数可以表达对象的构造方式。互不相交的备选情况对应加法；由两个组成部分构成的有序对，在大小相加的情况下对应乘法。如果 $A(z)$ 对组成部分进行计数，且 $A(0)=0$ ，那么由任意有限个组成部分构成的序列，其生成函数为

1+A(z)+A(z)^2+\cdots=\frac{1}{1-A(z)}.

上述条件排除了大小为零的组成部分，否则固定大小的序列可能有无穷多个。(aofa.cs.princeton.edu)

一个经典例子是卡塔兰数，它按内部节点数对有序满二叉树进行计数。一棵这样的树要么只有一个叶节点，要么由一个内部根节点及其两棵子树构成，因此

C(z)=1+zC(z)^2.

选取常数项系数为 $1$ 的解，得到

C(z)=\frac{1-\sqrt{1-4z}}{2z}, \qquad C_n=\frac{1}{n+1}\binom{2n}{n}.

最初几个系数为 $1,1,2,5,14,\ldots$ 。这一例子展示了如何将递归的结构描述转化为方程，进而得到计数公式。(aofa.cs.princeton.edu)

概率生成函数

对于取非负整数值的随机变量 $X$ ，其概率生成函数为

G_X(z)=\mathbb E[z^X] =\sum_{n\ge0}\Pr(X=n)z^n.

它的系数构成概率质量函数。对于参数为 $m$ 和 $p$ 的二项分布，

G_X(z)=(1-p+pz)^m.

其中 $z^k$ 的系数就是恰好成功 $k$ 次的概率。(math.mit.edu)

求导可以得到阶乘矩：

G_X^{(r)}(1^-) =\mathbb E[X(X-1)\cdots(X-r+1)].

当相应的矩有限时，期望值和方差可由下式求得：

\mathbb E[X]=G_X'(1^-),

\operatorname{Var}(X) =G_X''(1^-)+G_X'(1^-)-\bigl(G_X'(1^-)\bigr)^2.

生成函数表示也可用于某些离散概率模型的精确推断。(math.cmu.edu)

解析方法与局限

解析组合学将结构性的计数方程与其生成函数的解析性质联系起来。奇点既可以决定系数的指数增长，也可以决定其中的多项式修正因子。例如，卡塔兰数生成函数中的平方根型奇点给出

C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}.

这里， $\sim$ 表示两个表达式的比值趋于 $1$ 。一般的奇点转移定理需要适当的解析性条件；仅仅知道收敛半径，并不足以确定完整的渐近公式。(aofa.cs.princeton.edu)

将数列编码为生成函数，并不保证能得到便于使用的闭式表达式。生成函数所满足的方程，可能比原来的递推式更难求解，系数提取也仍可能很困难。形式运算本身并不能保证数值代入或解析论证的合理性：收敛性必须另行证明。这种方法是否有用，取决于所选级数类型及其运算是否与问题的结构相匹配。(math.cmu.edu)

现代生成函数理论融合了形式级数代数、组合构造规则和复分析估计。赫伯特·S. 威尔夫的《生成函数论》（generatingfunctionology）于1990年首次出版，通过数列和计数问题介绍了这些技术；菲利普·弗拉若莱和罗伯特·塞奇威克的《解析组合学》（Analytic Combinatorics）则系统阐述了组合结构描述与渐近分析之间的联系。(www2.math.upenn.edu)

参考来源

Generating Functionsaofa.cs.princeton.edu
Generating Function Notesmath.mit.edu
generatingfunctionologymath.cmu.edu
Generating Functions lecture slidesaofa.cs.princeton.edu
Analytic Combinatoricsaofa.cs.princeton.edu
Analytic Combinatorics — Philippe Flajolet and Robert Sedgewickac.cs.princeton.edu
Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approacharxiv.org
Download generatingfunctionologywww2.math.upenn.edu