解析组合学/奇点分析

简介

本文解释如何估计涉及对数和根的生成函数的系数。

您可能首先需要熟悉

• 在笛卡尔坐标和极坐标之间转换
• 曲线参数化

定理

标准函数尺度

来自 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 版). 帕尔格雷夫·麦克米伦。