奇点分析 | Codeboy's Blog

形式陈述

标准幂项与转移公式

设 $\rho>0$ 。对实数 $\alpha\notin\{0,-1,-2,\ldots\}$ ，广义二项式公式给出

[z^n]\left(1-\frac z\rho\right)^{-\alpha} =\rho^{-n}\frac{\Gamma(n+\alpha)}{\Gamma(\alpha)\Gamma(n+1)} \sim\rho^{-n}\frac{n^{\alpha-1}}{\Gamma(\alpha)}.

这里 $[z^n]$ 表示提取 $z^n$ 的系数，最后一步使用 Gamma 函数比值的渐近。于是一个标准项被拆成三部分：

局部信息	系数中的对应部分
奇点位置 $\rho$	$\rho^{-n}$
幂指数 $-\alpha$	$n^{\alpha-1}$
局部系数 $c$	$c/\Gamma(\alpha)$

这不只适用于发散的函数。若 $\alpha=-1/2$ ，局部项是趋于零的平方根，但它仍不解析，产生 $n^{-3/2}$ 的系数因子。看见函数在奇点处有有限极限，并不能断定那里对系数没有贡献。

为什么必须有带缺口的复邻域

一个以 $\rho$ 为尖点的 $\Delta$ -域可以写成

\Delta(\rho,\eta,\theta)= \{z:|z|<\rho+\eta,\ z\ne\rho,\ |\arg(z-\rho)|>\theta\}, \qquad \eta>0,\quad0<\theta<\pi/2.

它比收敛圆稍大，同时从 $\rho$ 向外挖去一个楔形。这样，积分路径可以从奇点两侧绕过，而不穿过平方根、对数等函数的支割。

假设 $A$ 可解析延拓到这样的区域，在其中接近 $\rho$ 时满足

A(z)=c\left(1-\frac z\rho\right)^{-\alpha} +o\!\left(\left(1-\frac z\rho\right)^{-\alpha}\right), \qquad c\ne0,

则在上述非例外指数条件下，可把这一局部等价转移为

a_n\sim c\rho^{-n}\frac{n^{\alpha-1}}{\Gamma(\alpha)}.

含多个标准项时可逐项处理；余项也要有相应的 $\Delta$ -域控制。只知道沿实轴 $z\uparrow\rho$ 的数值等价，通常不足以推出这个系数结论。实轴只是一条路径，未排除的其他复方向或其他主导点仍可能改变系数。[1]

对于有局部解析项的展开，可以先减去实际出现的有限多项式，再对奇异项和余项应用转移。不能仅凭一个函数在 $\rho$ 附近“看起来光滑”，就忽略它可能在别处拥有的同模奇点。

直觉

从函数的破口读出系数的增长

一个生成函数 $A(z)=\sum_{n\ge0}a_nz^n$ 把整列计数藏在一个解析表达式里。奇点分析反过来研究：当 $A$ 接近最先遇到的奇点时，它怎样发散、出现分支或失去解析性，这些局部形状如何决定 $a_n$ 的渐近行为。

例如 $1/(1-z)$ 有简单极点，系数恒为 $1$ ； $1/(1-z)^2$ 有二阶极点，系数为 $n+1$ 。两者奇点位置相同，系数的多项式因子却不同。奇点的位置控制指数尺度，局部奇异形状控制幂次与常数。但要把这个观察升级为定理，还需要知道函数在奇点周围的复平面中如何延拓。[1][2]

Gamma 常数从哪里来

Cauchy 系数公式把系数写成

a_n=\frac1{2\pi i}\oint\frac{A(z)}{z^{n+1}}\,dz.

利用 $\Delta$ -解析性，可以把围道向外推，并在 $\rho$ 两侧留下绕行的局部轮廓。远离主导点且模严格大于 $\rho$ 的部分指数级较小；主要贡献来自距离 $\rho$ 为 $1/n$ 量级的区域。

在这一局部区域令 $z=\rho(1-u/n)$ 。三个因素分别变成

\left(1-\frac z\rho\right)^{-\alpha}=n^\alpha u^{-\alpha}, \qquad z^{-n-1}\sim\rho^{-n-1}e^u, \qquad |dz|\ \text{带来尺度}\ \frac\rho n.

因此整体尺度是 $\rho^{-n}n^{\alpha-1}$ 。按相应取向变换后的 Hankel 围道积分为

\frac1{2\pi i}\int_{\mathcal H} e^u u^{-\alpha}\,du =\frac1{\Gamma(\alpha)}.

这就解释了转移公式中的常数。上述缩放揭示机制；完整证明还需控制局部替换的误差和围道其余部分，而 $\Delta$ -域正是完成这些估计所用的条件。[1]

例子与边界

完整例子：Catalan 数的平方根

Catalan 数的生成函数为

C(z)=\frac{1-\sqrt{1-4z}}{2z}.

取在原点解析、平方根值为 $1$ 的分支； $z=0$ 的表面奇点可去，主导奇点是 $\rho=1/4$ 。令 $X=1-4z$ ，则

C(z)=\frac2{1+\sqrt X} =2-2X^{1/2}+2X+O(X^{3/2}).

多项式 $2+2X$ 对充分大的 $n$ 不贡献系数。首个奇异项为 $-2(1-4z)^{1/2}$ ，对应 $\alpha=-1/2$ 。利用 $\Gamma(-1/2)=-2\sqrt\pi$ ，得到

[z^n]C(z) \sim-2\cdot4^n\frac{n^{-3/2}}{\Gamma(-1/2)} =\frac{4^n}{\sqrt\pi\,n^{3/2}}.

同一展开及余项转移还能给出相对误差 $O(1/n)$ 。这里 $4^n$ 、 $n^{-3/2}$ 和 $1/\sqrt\pi$ 都有明确来源，不是先猜出增长速度再拟合常数。

推论与应用

两类容易失真的使用方式

漏掉同模奇点。 对

A(z)=\frac1{1-z^2} =\frac12\left(\frac1{1-z}+\frac1{1+z}\right),

$1$ 与 $-1$ 都是主导奇点。两处贡献相加才得到

[z^n]A(z)=\frac{1+(-1)^n}{2},

即偶数项为 $1$ 、奇数项为 $0$ 。只处理 $z=1$ 会错误地把系数估计为 $1/2$ 。周期性不是一个可以放进小误差里的扰动，而可能改变整类下标上的主项。

忽略例外指数和奇点类型。 当 $\alpha$ 是非正整数时， $(1-z/\rho)^{-\alpha}$ 是多项式，其尾部系数为零；带对数的 $(1-z/\rho)^m\log(1/(1-z/\rho))$ 却不是同一情况，需要专门的对数转移。具有本性奇点的生成函数，也不能只套一个幂型公式。鞍点法或圆法可能更合适，例如分拆函数的分析。

因此，可靠的流程是定位全部主导奇点，建立所需解析延拓，求局部展开，再逐项转移并控制误差。解析组合的转移定理把这些标准尺度整理成可复用规则；奇点分析则负责把具体生成函数放进规则真正适用的条件中。

参考资料

[1] Philippe Flajolet、Andrew Odlyzko，〈Singularity Analysis of Generating Functions〉，SIAM Journal on Discrete Mathematics 3(2)，1990，216–240，标准尺度、 $\Delta$ -域与误差转移。

[2] Philippe Flajolet、Robert Sedgewick，Analytic Combinatorics，2009，第 VI 章；作者配套章节，尤其 VI.2–VI.5 的标准尺度、转移与多奇点分析。

形式陈述 ​

标准幂项与转移公式 ​

为什么必须有带缺口的复邻域 ​

从函数的破口读出系数的增长 ​

Gamma 常数从哪里来 ​

完整例子：Catalan 数的平方根 ​

两类容易失真的使用方式 ​

反向链接