解析組合學/奇點分析

簡介

本文解釋如何估計涉及對數和根的生成函式的係數。

您可能首先需要熟悉

• 在笛卡爾座標和極座標之間轉換
• 曲線引數化

定理

標準函式尺度

來自 Flajolet 和 Odlyzko 的定理。

如果

$f(z)=(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }$

其中$\alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}$ 然後

$[z^{n}]f(z)\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\quad ({\text{as }}n\to \infty )$

奇點分析

來自 Flajolet 和 Sedgewick 的定理。

如果 $f(z)$ 在$\zeta$處有一個奇點並且

$f(z)\sim \left(1-{\frac {z}{\zeta }}\right)^{\alpha }\left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)^{\gamma }\left({\frac {1}{\frac {z}{\zeta }}}\log \left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)\right)^{\delta }\quad ({\text{as }}z\to \zeta )$

其中$\alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}$ 然後

$[z^{n}]f(z)\sim \zeta ^{-n}{\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\quad ({\text{as }}n\to \infty )$

後一個定理的意義在於我們只需要一個$f(z)$的近似值。

分支點

在進入證明之前，我將解釋關於根和對數的哪些方面意味著我們必須對它們進行與亞純函式不同的處理。

極座標

edit | edit source]

複數可以用兩種形式表示：笛卡爾座標 ($x+iy$) 或極座標 $re^{i\theta }$，其中 $r$ 是到原點的距離或模，而 $\theta$ 是相對於正 $x$ 軸的角度或輻角。

對於復變數 $z$ 的複函式 $f(z)$，我們可以繪製一個三維圖形，其中 $x$ 和 $y$ 軸分別是 $z$ 變數的實部和虛部，而 $z$ 軸是函式 $f(z)$ 的模或輻角。

對於根和對數，如果我們使用函式的輻角作為 $z$ 軸，我們會看到一個間斷，這限制了我們在想要積分該函式時可以繪製輪廓的位置。

你可以在負 $x$ 軸上看到的間隙就是間斷。

根函式和對數函式沒有我們可以進行洛朗展開的極點。相反，我們需要繪製輪廓以避免這些間隙或間斷。這就是為什麼在接下來的內容中，我們使用從輪廓中取出狹縫或楔形的輪廓。

標準函式尺度的證明

由塞奇威克、弗拉若萊和奧德萊茲科證明

第一項係數估計的證明。

根據柯西係數公式

$[z^{n}](1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }={\frac {1}{2\pi i}}\int _{C}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}$

其中$C$ 是以原點為中心的圓。

我們可以在不改變上述輪廓積分值的情況下變形$C$。

我們將透過在實軸上從 1 到 $+\infty$ 沿其切開$C$ 。

我們將圓的半徑增大到 $\infty$，這將使它對被積函式的貢獻降為 0。

因此，上述圍繞 $C$ 的輪廓積分等效於圍繞從 $Re(+\infty )$ 開始，繞 1 旋轉，並在 $Re(+\infty )$ 結束的輪廓積分，我們將稱之為${H_{\frac {1}{n}}}$ 。

雖然我們對圍繞輪廓 ${H_{\frac {1}{n}}}$ 的積分行為了解不多，但我們確實瞭解類似的輪廓 $H_{1}$（漢克爾輪廓）的行為，它繞著距離為 1 的原點旋轉。

我們可以透過將其轉換為圍繞 $H_{1}$ 的積分來計算圍繞 ${H_{\frac {1}{n}}}$ 的積分。形式上

$\int _{H_{\frac {1}{n}}}f(z)dz=\int _{\psi ^{-1}\circ H_{\frac {1}{n}}}f(\psi (\zeta ))\psi '(\zeta )d\zeta .$

使得 $\psi ^{-1}\circ H_{\frac {1}{n}}=H_{1}$.

非正式地說，這意味著我們想找到一個函式 $\psi ^{-1}(t)$，它將輪廓 ${H_{\frac {1}{n}}}$ 變成 $H_{1}$。從幾何上講，我們將輪廓向左移動 1 並乘以 $n$

$\psi ^{-1}(t)=n(t-1)$

但是，我們仍然希望 $H_{1}$ 周圍的被積函式等價於 ${H_{\frac {1}{n}}}$ 周圍的被積函式。我們透過將變數除以 $n$ 並加 1 來做到這一點

$\psi (t)=1+{\frac {t}{n}}$

因此，我們得到以下替換

${\begin{aligned}{\frac {1}{2\pi i}}\int _{H_{\frac {1}{n}}}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}&={\frac {1}{2\pi i}}\int _{\psi ^{-1}\circ H_{\frac {1}{n}}}(1-(1+{\frac {t}{n}}))^{\alpha }\left({\frac {1}{1+{\frac {t}{n}}}}\log {\frac {1}{1-(1+{\frac {t}{n}})}}\right)^{\gamma }\left({\frac {1}{1+{\frac {t}{n}}}}\log \left({\frac {1}{1+{\frac {t}{n}}}}\log {\frac {1}{1-(1+{\frac {t}{n}})}}\right)\right)^{\delta }{\frac {1}{n}}{\frac {dt}{(1+{\frac {t}{n}})^{n+1}}}\\&={\frac {n^{-a-1}}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }\left(\log -{\frac {n}{t}}\right)^{\gamma }\left(\log \left({\frac {1}{1+{\frac {t}{n}}}}\log -{\frac {n}{t}}\right)\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(1-{\frac {\log(-t)}{\log n}}\right)^{\gamma }\left(\log \left({\frac {1}{1+{\frac {t}{n}}}}\log -{\frac {n}{t}}\right)\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(\log \left({\frac {1}{1+{\frac {t}{n}}}}\log -{\frac {n}{t}}\right)\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(\log {\frac {1}{1+{\frac {t}{n}}}}+\log \log -{\frac {n}{t}}\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(\log \log -{\frac {n}{t}}\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }\left(1-{\frac {\log \log(-t)}{\log \log n}}\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\end{aligned}}$

我們有

$\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}\sim e^{-t}$（當 $n\to \infty$ 時）

以及

${\frac {1}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }e^{-t}dt={\frac {1}{\Gamma (-\alpha )}}$

因此，

${\frac {1}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }\left(1+{\frac {t}{n}}\right)^{-n-1}dt\sim {\frac {1}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }e^{-t}dt={\frac {1}{\Gamma (-\alpha )}}$

將所有內容整合在一起

${\begin{aligned}[z^{n}](1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }&={\frac {1}{2\pi i}}\int _{C}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}\\&={\frac {1}{2\pi i}}\int _{H_{\frac {1}{n}}}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }\left(1+{\frac {t}{n}}\right)^{-n-1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }e^{-t}dt\\&={\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\end{aligned}}$

奇點分析

Flajolet 和 Sedgewick 的解釋和示例。

在下文中

$F(z)=(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }\quad (\alpha \notin \{0,1,2,\ldots \},\gamma ,\delta \notin \{1,2,\ldots \})$

小o記號

我們將使用“小o”記號。

$f(z)=o(g(z))$ 當 $z\to \zeta$

這意味著

$\lim _{z\to \zeta }{\frac {f(z)}{g(z)}}=0$

它還意味著對於每個 $\epsilon >0$ 都存在 $\delta >0$ 使得

$|z-\zeta |\leq \delta \implies f(z)\leq \epsilon g(z)$

這是我們在證明中將要使用的事實。

還需要注意

$f(z)=g(z)+o(g(z))\iff f(z)\sim g(z)$

總結

對於生成函式 $f(z)$

1. 找到 $f(z)$ 的奇點 $\zeta$.
2. 構造在 $\zeta$ 處的 $\Delta$ 區域。
3. 檢查$f(z)$ 在$\Delta$ 域內是否為解析函式。
4. 對$f(z)$ 在$\zeta$ 附近建立一個如下形式的近似：$f(z)=F\left({\frac {z}{\zeta }}\right)+o\left(F\left({\frac {z}{\zeta }}\right)\right)$.
5. 對$[(z/\zeta )^{n}]f(z)\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$ 或等價地$[z^{n}]f(z)\sim \zeta ^{-n}{\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$ 進行估計。

詳細說明

為了找到奇點，我們需要找到$z$ 的值，使得該函式等於$\infty$。

例如，我們將使用$f(z)={\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}$.

它在$z=1$ 處有一個奇點，因為

${\frac {e^{-3/4}}{\sqrt {1-1}}}={\frac {e^{-3/4}}{\sqrt {0}}}={\frac {e^{-3/4}}{0}}=\infty$

在 z = 1 處的 Δ 域是一個以原點為中心的圓，半徑為 R，其中有一個三角形被切除，一個頂點在 1 處，邊角為 φ 和 -φ。見下圖。我們使用這個域，因為它允許我們稍後進行證明。

為了使 f(z) 在 Δ 域中解析

$f(z)=\sum _{n=0}^{\infty }a_{n}(z-z_{0})^{n}$

對於 Δ 域中的所有 $z_{0}$.

我們的例子在 Δ 域中是解析的，因為

• $e^{-z/2-z^{2}/4}$ 是一個整函式（即沒有奇點），這意味著它在任何地方都是解析的。
• ${\frac {1}{\sqrt {1-z}}}$ 是解析的，除了實軸上的一個切口，對於 $z\geq 1$。
• 兩個解析函式的乘積是相同域上的解析函式。因此，${\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}$ 在整個復域上都是解析的，包括 Δ 域，除了實軸 $z\geq 1$。

我們想要一個形式為 $f(z)=F\left({\frac {z}{\zeta }}\right)+o\left(F\left({\frac {z}{\zeta }}\right)\right)\quad (z\to \zeta )$ 的近似值（在我們這個例子中，我們設定 γ, δ = 0 以及 ζ = 1）。

通常，這將採用 泰勒級數展開 的形式。

對於我們的例子，在 1 附近做泰勒展開

$e^{-z/2-z^{2}/4}=e^{-3/4}+e^{-3/4}(1-z)+{\frac {e^{-3/4}}{4}}(1-z)^{2}+\cdots$

${\frac {1}{\sqrt {1-z}}}={\frac {1}{\sqrt {1-z}}}$

${\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}={\frac {e^{-3/4}}{\sqrt {1-z}}}+e^{-3/4}{\sqrt {1-z}}+{\frac {e^{-3/4}}{4}}(1-z)^{\frac {3}{2}}+\cdots$

因此

${\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}={\frac {e^{-3/4}}{\sqrt {1-z}}}+o({\frac {e^{-3/4}}{\sqrt {1-z}}})$

那麼 $[z^{n}]f(z)\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$.

因此，在我們的例子中

$[z^{n}]{\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}\sim {\frac {e^{-3/4}}{\sqrt {\pi n}}}$

該證明來自於以下事實

1. $[z^{n}]f(z)=\zeta ^{-n}[(z/\zeta ^{n}]f(z)$
2. $[(z/\zeta )^{n}]f(z)=[(z/\zeta )^{n}]F(z/\zeta )+[(z/\zeta )^{n}]o(F(z/\zeta ))$
3. 第一項的係數 $[(z/\zeta )^{n}]F(z/\zeta )\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$，我們從 標準函式尺度 中得到。
4. 第二項的係數 $[(z/\zeta )^{n}]o(F(z/\zeta ))=o\left(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta }\right)$，我們在 #誤差項證明 中進行。這也是為什麼我們需要使用 $\Delta$-域的原因。

誤差項證明

來自 Flajolet 和 Odlyzko、Flajolet 和 Sedgewick 以及 Pemantle 和 Wilson 的證明。

我們從 柯西係數公式 中得到第二項係數的估計

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

其中 $\gamma$ 是 $\Delta$-域內的任何閉合 輪廓。參見下圖中的紅線。

我們將 $\gamma$ 分成四部分，使得 $\gamma =\gamma _{1}\cup \gamma _{2}\cup \gamma _{3}\cup \gamma _{4}$.

$\gamma _{1}=\{z\mid |z-1|={\frac {1}{n}},|arg(z-1)|\geq \phi \}$

$\gamma _{2}=\{z\mid |z-1|\geq {\frac {1}{n}},|z|\leq r,|arg(z-1)|=\phi \}$

$\gamma _{3}=\{z\mid |z|=r>1,|arg(z-1)|\geq \phi \}$

$\gamma _{4}=\{z\mid |z-1|\geq {\frac {1}{n}},|z|\leq r,|arg(z-1)|=-\phi \}$

${\frac {1}{2i\pi }}\int _{\gamma }o(F(z)){\frac {dz}{z^{n+1}}}={\frac {1}{2i\pi }}\int _{\gamma _{1}}o(F(z)){\frac {dz}{z^{n+1}}}+{\frac {1}{2i\pi }}\int _{\gamma _{2}}o(F(z)){\frac {dz}{z^{n+1}}}+{\frac {1}{2i\pi }}\int _{\gamma _{3}}o(F(z)){\frac {dz}{z^{n+1}}}+{\frac {1}{2i\pi }}\int _{\gamma _{4}}o(F(z)){\frac {dz}{z^{n+1}}}$

來自 $\gamma _{1}$ 的貢獻

在 $\gamma _{1}$ 上，$F(z)$ 的最大值出現在 $z=1-{\frac {1}{n}}$ 時

$o(F(z))\leq \epsilon n^{-\alpha }(\log n)^{\gamma }(\log {\frac {1}{1-{\frac {1}{n}}}}+\log \log n)^{\delta }{\frac {1}{(1-{\frac {1}{n}})^{\gamma +\delta }}}\sim \epsilon n^{-\alpha }(\log n)^{\gamma }(\log \log n)^{\delta }\quad ({\text{as }}n\to \infty )$

在 $\gamma _{1}$ 上，${\frac {1}{z^{n+1}}}$ 的最大值為

${\frac {1}{(1-{\frac {1}{n}})^{n+1}}}\leq 2e$

在 $\gamma _{1}$ 上，$dz$ 的最大值為 ${\frac {2\pi }{n}}$

${\frac {1}{2i\pi }}\int _{\gamma _{1}}o(F(z)){\frac {dz}{z^{n+1}}}\leq \epsilon 2en^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta }=o(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta })$

來自 $\gamma _{2}$ 和 $\gamma _{4}$ 的貢獻

我們透過將$z$ 轉換為極座標形式，並用$z=1+{\frac {t}{n}}e^{i\phi }$ 來對輪廓 $\gamma _{2}$ 進行引數化，使得 $\gamma _{2}$ 成為 $t$ 的函式，從 $1$ 到 $En$。$E$ 是方程 $|1+Ee^{i\phi }|=r$ 的正解，使得輪廓連線 $\gamma _{3}$

$\int _{\gamma _{2}}o(F(z)){\frac {dz}{z^{n+1}}}\leq \int _{1}^{En}|F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}$

但是，請記住，小 o 關係只在 $1$ 的某個特定 $\delta$ 內成立。我們知道，當 $n$ 增大時，${\frac {\log ^{2}n}{n}}$ 趨於零，因此，對於任何 $\epsilon$，我們選擇一個足夠大的 $n$ 使得 ${\frac {\log ^{2}n}{n}}\leq \delta$。我們將上面的積分在 $\log ^{2}n$ 處分成兩個部分，使得 ${\frac {t}{n}}e^{i\phi }\leq \delta$

$\int _{1}^{En}|F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}=\int _{1}^{\log ^{2}n}\epsilon |F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}+\int _{\log ^{2}n}^{En}F(1+{\frac {t}{n}}e^{i\phi }){\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}$

和式中的第一項

${\begin{aligned}\int _{1}^{\log ^{2}n}\epsilon |F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}&\leq {\frac {1}{2i\pi }}\int _{1}^{\infty }\epsilon |{\frac {t}{n}}e^{i\phi }|^{\alpha }|\log {\frac {n}{te^{i\phi }}}|^{\gamma }|\log({\frac {1}{1+{\frac {t}{n}}e^{i\phi }}}\log {\frac {n}{te^{i\phi }}})|^{\delta }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}{\frac {e^{i\phi }dt}{n}}\\&\leq {\frac {1}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\int _{1}^{\infty }|t|^{\alpha }|\log({\frac {1}{1+{\frac {t}{n}}e^{i\phi }}}\log {\frac {n}{e^{i\phi }}})|^{\delta }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\\&\sim {\frac {1}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{1}^{\infty }|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\\\end{aligned}}$

$|1+{\frac {e^{i\phi }t}{n}}|\geq 1+Re({\frac {e^{i\phi }t}{n}})=1+{\frac {t\cos \phi }{n}}$ （其中 $Re(x)$ 是 x 的 實部）。

$\int _{1}^{\log ^{2}n}|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\leq \int _{1}^{\infty }|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\leq \int _{1}^{\infty }|t|^{\alpha }\left(1+{\frac {t\cos \phi }{n}}\right)^{-n-\gamma -\delta -1}dt\leq \int _{1}^{\infty }t^{a}e^{-t\cos \phi }dt\quad ({\text{as }}n\to \infty )$

這個收斂到一個常數 $L$。因此

${\frac {1}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{1}^{\infty }|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt={\frac {L}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }=o(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta })\quad (n\to \infty )$

和式中的第二項

${\begin{aligned}\int _{\log ^{2}n}^{En}F(1+{\frac {t}{n}}e^{i\phi }){\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}&\leq {\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{\log ^{2}n}^{En}|t|^{\alpha }\left(1+{\frac {\log ^{2}n\cos \phi }{n}}\right)^{-n-\gamma -\delta -1}dt\\&\leq {\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{\log ^{2}n}^{En}|t|^{\alpha }e^{-\log ^{2}n\cos \phi }dt\\&\leq {\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }{\frac {|En|^{\alpha }}{n^{\log n\cos \phi }}}En\end{aligned}}$

$n^{\log n\cos \phi }$ 隨著 $n$ 的增長速度快於 $|En|^{\alpha +1}$，因此 ${\frac {|En|^{\alpha +1}}{n^{\log n\cos \phi }}}\to 0$ 當 $n\to \infty$。因此

${\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }{\frac {|En|^{\alpha +1}}{n^{\log n\cos \phi }}}=o(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta })\quad (n\to \infty )$

類似的論證適用於 $\gamma _{4}$.

$\gamma _{3}$ 的貢獻

根據 柯西不等式

${\frac {1}{2i\pi }}\int _{\gamma _{3}}o(F(z)){\frac {dz}{z^{n+1}}}\leq {\frac {\max _{|z|=r}F(z)}{r^{n}}}$

這意味著圍繞 $\gamma _{3}$ 的積分貢獻隨著 $n\to \infty$ 指數衰減，可以忽略不計。

多個奇點的公式

以上假設只有一個奇點 $\zeta$。但是，它可以推廣到具有多個奇點的函式。

在多個奇點的情況下，需要將基本奇點分析過程中給出的每個奇點的單獨貢獻加起來。

—Flajolet 和 Sedgewick 2009，第 398 頁。

Flajolet 和 Sedgewick 的定理。

如果 $f(z)$ 在圓盤 $|z|<\rho$ 上是解析的，在圓周 $|z|=\rho$ 上有有限個奇點，並且 $f(z)$ 在 $\Delta$ 域上是解析的，在每個奇點處都有多個凹陷。

如果對於每個奇點 $\zeta _{i}$（對於 $i=1,2,\cdots ,r$)

$f(z)\sim \left(1-{\frac {z}{\zeta _{i}}}\right)^{\alpha _{i}}\left({\frac {1}{\frac {z}{\zeta _{i}}}}\log {\frac {1}{1-{\frac {z}{\zeta _{i}}}}}\right)^{\gamma _{i}}\left({\frac {1}{\frac {z}{\zeta _{i}}}}\log \left({\frac {1}{\frac {z}{\zeta _{i}}}}\log {\frac {1}{1-{\frac {z}{\zeta _{i}}}}}\right)\right)^{\delta _{i}}\quad ({\text{as }}z\to \zeta _{i})$

那麼

$[z^{n}]f(z)\sim \sum _{i=0}^{r}\zeta _{i}^{n}{\frac {n^{-{\alpha _{i}}-1}}{\Gamma (-{\alpha _{i}})}}(\log n)^{\gamma _{i}}(\log \log n)^{\delta _{i}}\quad ({\text{as }}n\to \infty )$

參考文獻

• Flajolet, Philippe; Odlyzko, Andrew (1990). "生成函式的奇點分析" (PDF). SIAM 離散數學雜誌. 1990 (3).
• Flajolet, Philippe; Sedgewick, Robert (2009). 分析組合學 (PDF). 劍橋大學出版社。
• Lang, Serge (1999). 複變函式 (第 4 版). 施普林格科學+商業媒體有限公司。
• Lorenz, Dirk (2011). "複變函式的替換和分部積分". 檢索於 2022 年 11 月 27 日.
• Pemantle, Robin; Wilson, Mark C. (2013). 多個變數的分析組合學 (PDF). 劍橋大學出版社。
• Sedgewick, Robert. "6. 奇點分析" (PDF). 檢索於 2022 年 11 月 13 日.
• Stroud, K. A. (2003). 高等工程數學 (第 4 版). 帕爾格雷夫·麥克米倫。