解析组合学/鞍点法

定理

Flajolet 和 Sedgewick 的定理^[1]。

如果 $F(z)$ 是一个容许函数，则

[z^{n}]F(z)\sim {\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}

作为

n\to \infty

其中 $\zeta$ 使得 $F^{'}(\zeta )=0$ 且 ${\frac {F(z)}{z^{n+1}}}=e^{f(z)}$ .

证明

Flajolet 和 Sedgewick 的证明^[2]。

根据柯西系数公式

[z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz

我们可以将其可视化为一个 3D 图，其 $x$ 和 $y$ 轴分别是 $z$ 的实部和虚部， $z$ 轴是 ${\frac {F(z)}{z^{n+1}}}$ 的实部。

对于我们感兴趣的生成函数， ${\frac {F(z)}{z^{n+1}}}$ 在正实轴上有一个鞍点^[3]。这是上面图中绿色路径的最高点。我们称它为 $\zeta$ 。

作为一个解析函数（除了 $z=0$ ），我们可以将轮廓变形以通过鞍点。对积分贡献最大的部分是靠近鞍点的轮廓部分（我们称之为 $C_{0}$ ，这是下图中红色的部分）。轮廓的其余部分（我们称之为 $C_{1}$ ，绿色的部分）贡献相对较小。

{\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz={\frac {1}{2\pi i}}\int _{C_{0}}{\frac {F(z)}{z^{n+1}}}dz+{\frac {1}{2\pi i}}\int _{C_{1}}{\frac {F(z)}{z^{n+1}}}dz

在下文中，我们设置 ${\frac {F(z)}{z^{n+1}}}=e^{f(z)}$

[z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz={\frac {1}{2\pi i}}\int _{C}e^{f(z)}dz

我们可以进一步变形轮廓，使靠近鞍点的轮廓部分成为一条直线（在复平面上）。 $C_{0}$ 变形为一条垂直于实轴的直线，穿过鞍点，从 $-ia$ 到 $ia$ 。 $a$ 的选择使得当 $n\to \infty$ 时， $f^{''}(\zeta )a^{2}\to \infty$ 且 $f^{'''}(\zeta )a^{3}\to 0$ 。这样， $\zeta$ 处的泰勒级数展开

f(z)=f(\zeta )+{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}+{\frac {1}{6}}f^{'''}(\zeta )(z-\zeta )^{3}+\cdots

.

可以简化为 $f(\zeta )+{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}$ .

$f^{''}(\zeta )={\frac {F^{''}(\zeta )}{F(\zeta )}}+{\frac {n+1}{\zeta ^{2}}}$ 是实数，因为 $\zeta$ 是实数，而 $F(z)$ 作为生成函数，具有实系数。 $z=\zeta +ix$ ，所以 $(z-\zeta )^{2}=-x^{2}$ 是实数。因此， ${\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}$ 是实数。

因此， $f(z)$ 的任何虚部可以移到积分符号之外，只留下一个实值被积函数

{\frac {1}{2\pi i}}\int _{C_{0}}{\frac {F(z)}{z^{n+1}}}dz={\frac {1}{2\pi i}}\int _{C_{0}}e^{f(z)}dz\sim {\frac {e^{f(\zeta )}}{2\pi i}}\int _{C_{0}}e^{{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}dz

这也意味着，我们一开始讨论的实值曲面是潜在复值 ${\frac {F(z)}{z^{n+1}}}$ 的有效估计。

$C_{0}:x\in [-a,a]\to ix+\zeta$

我们改变变量以消除区间的虚部，并将其转化为实轴上的实值被积函数。设置 $g^{-1}(x)={\frac {x-\zeta }{i}}$

\int _{C_{0}}e^{{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}dz=\int _{-a}^{a}e^{{\frac {1}{2}}f^{''}(\zeta )(ix+\zeta -\zeta )^{2}}idx=i\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx

\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx=\int _{-\infty }^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx-2\int _{a}^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx

因为 $e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}$ 当 $x$ 很大时非常小

\left|\int _{a}^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\right|\leq Ae^{-{\frac {1}{2}}f^{''}(\zeta )a^{2}}

根据我们之前对 $a$ 的选择，当 $n\to \infty$ 时， $e^{-{\frac {1}{2}}f^{''}(\zeta )a^{2}}\to 0$ .

因此，积分可以由一个我们知道如何计算的高斯积分来估计

\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\sim \int _{-\infty }^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx={\sqrt {\frac {2\pi }{f^{''}(\zeta )}}}

总结

{\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz\sim {\frac {e^{f(\zeta )}}{2\pi i}}\int _{C_{0}}e^{{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}dz={\frac {e^{f(\zeta )}i}{2\pi i}}\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\sim {\frac {e^{f(\zeta )}}{2\pi }}{\sqrt {\frac {2\pi }{f^{''}(\zeta )}}}={\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}

适用性

这正式化了我们可以应用鞍点法的条件。来自 Flajolet 和 Sedgewick^[4] 以及 Wilf^[5] 的定义。也称为 Hayman 可接受性^[6].

函数 $F(z)$ 是可接受的，如果

$F(z)$ 是一个具有收敛半径 $R\quad (0<R\leq \infty )$ 的函数
存在一个 $R_{0}<R$ 使得 $F(r)>0\quad (R_{0}<r<R)$
H₁: $\lim _{r\to R}a(r)=+\infty$ 并且 $\lim _{r\to R}b(r)=+\infty$
H₂: 存在一个定义在 $R_{0}<r<R$ 上的函数 $\delta (r)$ ，使得 $0<\delta (r)<\pi$ ，并且当 $r\to R$ 时

F(re^{i\theta })\sim F(r)e^{i\theta a(r)-{\frac {1}{2}}\theta ^{2}b(r)}

对

|\theta |\leq \delta (r)

一致成立。

H₃: 对 $\delta (r)\leq |\theta |\leq \pi$ 一致成立，并且当 $r\to R$ 时

F(re^{i\theta })=o\left({\frac {F(r)}{\sqrt {b(r)}}}\right)

直观解释

为了求函数的系数，我们可以使用柯西系数公式。这需要我们找到复平面上路径的积分。想象一下，尝试估计这个积分，它被显示在下面的红线和绿线。

积分的最大贡献来自鞍点附近（以红色显示），尾部的贡献（以绿色显示）可以忽略不计（由 H₃ 确定）。

因此，要估计整个路径的积分，您可以估计路径的红色部分的积分。这就是 H₂ 中描述的渐近关系。

例子

来自 Wilf^[7] 和 Flajolet 和 Sedgewick^[8] 的示例。

假设我们想要估计 $e^{z}$ 的系数。

$e^{z}$ 的收敛半径为 $+\infty$ ，并且对所有 $z\geq 0$ 为正。
H₁: $a(z)=z{\frac {(e^{z})'}{e^{z}}}=z{\frac {e^{z}}{e^{z}}}=z$ 。因此， $\lim _{z\to +\infty }z=+\infty$ 。
H₁: $b(z)=z^{2}{\frac {d^{2}}{dz^{2}}}\ln e^{z}+z{\frac {d}{dz}}\ln e^{z}=z^{2}{\frac {d^{2}z}{dz^{2}}}+z{\frac {dz}{dz}}=z$ . 因此， $\lim _{z\to +\infty }z=+\infty$ .
求解方程 $a(\zeta )=\zeta =n$ ，找到鞍点 $\zeta$ 。因此， $\zeta =n$ ，积分路径是半径为 $n$ 以原点为中心的圆。
选择 $\delta (ne^{i\theta })=n^{-{\frac {2}{5}}}$ .
H₃: 当 $n\to +\infty$ ，对于 $n^{-{\frac {2}{5}}}\leq |\theta |\leq \pi$
$|e^{ne^{i\theta }}|=e^{n\cos \theta }\leq e^{n\cos n^{-{\frac {2}{5}}}}=o\left({\frac {e^{n}}{\sqrt {n}}}\right)$ .
H₂: 对于 $n<1\quad e^{ne^{i\theta }}\sim e^{n+i\theta n-{\frac {1}{2}}\theta ^{2}n}=e^{n}e^{i\theta n-{\frac {1}{2}}\theta ^{2}n}$ （由于指数函数的级数展开 $e^{i\theta }$ ）。
应用定理： $[z^{n}]e^{z}\sim {\frac {e^{n}}{n^{n}{\sqrt {2\pi n}}}}$ .