解析生成函数 | Codeboy's Blog

形式陈述

序列 $(a_n)$ 的生成级数在首先由符号方法确定后，若它作为解析幂级数

A(z)=\sum_{n\ge0}a_nz^n

具有正收敛半径 $R>0$ ，便可在圆盘 $|z|<R$ 内视为全纯函数。由 Cauchy–Hadamard 公式，

\frac1R=\limsup_{n\to\infty}|a_n|^{1/n}.

对任意 $0<r<R$ ，Cauchy 公式给出系数提取

a_n=[z^n]A(z) =\frac1{2\pi i}\int_{|z|=r}\frac{A(z)}{z^{n+1}}\,dz,

从而有 Cauchy 上界

|a_n|\le M(r)r^{-n}, \qquad M(r)=\max_{|z|=r}|A(z)|.

OGF直接使用上述系数；若 $A$ 是EGF，则对象数为 $n![z^n]A(z)$ 。解析方法必须在最后把这项阶乘归一化还原。

直觉

形式生成函数把组合分解编码为系数恒等式；解析生成函数再把同一系数表放进复平面。围道积分说明，第 $n$ 个系数是函数沿圆周的加权平均，而因子 $z^{-n}$ 会把靠近原点的轮廓放大。随着 $n$ 增长，把轮廓推向最接近原点的奇点通常能捕捉主要贡献。

“通常”需要证明。收敛圆只告诉我们从零展开能走多远；要把轮廓越过圆周的一部分，还须有解析延拓。奇点的位置提供指数尺度，局部类型提供幂次和常数，同模多个奇点还可能相加或抵消。

例子与边界

Fibonacci 生成函数

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

既是形式递推的解，也是原点附近的有理解析函数。分母零点为

\rho=\frac{\sqrt5-1}{2}=\varphi^{-1}, \qquad -\varphi, \qquad \varphi=\frac{1+\sqrt5}{2}.

最近奇点只有正实数 $\rho$ ，部分分式给出

F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \psi=\frac{1-\sqrt5}{2},

故 $F_n\sim\varphi^n/\sqrt5$ 。指数因子 $\varphi^n=\rho^{-n}$ 来自最近极点，常数 $1/\sqrt5$ 来自留数，而第二极点贡献的 $\psi^n$ 指数更小。

若半径为零，例如 $\sum n!z^n$ ，级数仍是合法形式生成函数，却不能在零点附近定义非平凡解析函数。若函数整全纯，如 $e^z$ ，则没有有限主导奇点，系数常由鞍点而非有限边界奇点分析。即使 $R>0$ ，圆周也可能是自然边界，无法作所需延拓。

另一个边界是表达式相同不等于解析分支相同。代数函数含平方根、对数时，形式展开选定了零点附近的分支；围道变形必须持续使用同一解析分支，不能跨过支割后仍沿用原局部公式。

推论与应用

解析生成函数是精确计数与渐近计数之间的接口。主导奇点确定首要指数尺度，奇点分析把局部幂—对数展开转成系数展开，鞍点法则处理整函数、Euler 乘积或随 $n$ 移动的最大贡献区。

Cauchy 积分还允许选择最有利半径：对非负系数，最小化 $A(r)r^{-n}$ 常导出鞍点方程；对孤立极点，可把轮廓推出并用留数求精确主项。所有这些操作都依赖函数在所经区域内全纯或只有已知奇点，不能仅凭形式方程实施。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapters IV–VIII。
Herbert S. Wilf, generatingfunctionology, 3rd ed., A K Peters, 2006, Chapters 4–5。
Robin Pemantle and Mark C. Wilson, Analytic Combinatorics in Several Variables, Cambridge University Press, 2013, Chapter 1。