解析組合學/鞍點法

定理

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}}}}$ .