解析组合/亚纯函数

介绍

本文解释如何估计亚纯生成函数的系数。

定理

由 Sedgewick提出的定理。

• 如果$h(z)={\frac {f(z)}{g(z)}}$ 是一个亚纯函数
• 并且$a$ 是其极点 最靠近原点的，阶数为$m$
• 那么你可以使用公式估计其$n$阶系数

${\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)}}\left({\frac {1}{a}}\right)^{n}n^{m-1}$

证明

由 Sedgewick 和 Wilf提出的证明。

• $h(z)$ 作为亚纯，可以在$a$ 附近进行洛朗展开

$h(z)={\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}+h_{0}+h_{1}(z-a)+\cdots$

• 这个洛朗展开可以用其主部分估计

${\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}$

• ${\frac {h_{-m}}{(z-a)^{m}}}$ 贡献了最大系数。它的$n$阶系数可以计算为

${\frac {(-1)^{m}h_{-m}}{a^{m}}}{\binom {n+m-1}{n}}\left({\frac {1}{a}}\right)^{n}$

• $h_{-m}$ 可以 计算 为

$\lim _{z\to a}(z-a)^{m}h(z)={\frac {m!f(a)}{g^{(m)}(a)}}$

• ${\binom {n+m-1}{n}}\sim {\frac {n^{m-1}}{(m-1)!}}$ 作为 $n\to \infty$ （证明）
• 因此，将所有内容整合在一起

$[z^{n}]h(z)\sim {\frac {(-1)^{m}h_{-m}}{a^{m}}}{\binom {n+m-1}{n}}\left({\frac {1}{a}}\right)^{n}\sim {\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)}}\left({\frac {1}{a}}\right)^{n}n^{m-1}$ 作为 $n\to \infty$.

渐近相等

我们将使用渐近相等

$f(z)\sim g(z)$ 作为 $z\to \zeta$

这意味着

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

这让我们可以使用 $g(z)$ 作为 $f(z)$ 的估计，当 $z$ 越来越接近 $\zeta$。

例如，我们经常给出以下形式的结果

$a_{n}\sim g(n)$ 当 $n\to \infty$

这意味着，当 $n$ 足够大时，$g(n)$ 将成为 $a_{n}$ 的一个很好的估计。

亚纯函数

上述定理只适用于一类称为亚纯函数的生成函数。这包括所有有理函数（两个多项式的比率），例如 ${\frac {1}{(1-z)^{2}}}$ 和 ${\frac {z}{1-z-z^{2}}}$。

亚纯函数是两个解析函数的比率。解析函数是复导数存在的函数。

亚纯函数的一个特性是它们可以用洛朗级数展开式表示，这一事实将在 证明 中使用。

可以估计非亚纯函数的系数（例如 $ln(z)$ 或 $e^{z}$）。这些将在以后的章节中介绍。

洛朗级数

当我们想要一个函数 $f(z)$ 在奇点 $c$ 附近的级数展开式时，我们不能使用泰勒级数展开式。相反，我们使用洛朗级数展开式

$\cdots +{\frac {a_{-2}}{(z-c)^{2}}}+{\frac {a_{-1}}{z-c}}+a_{0}+a_{1}(z-c)+a_{2}(z-c)^{2}+\cdots$

其中 $a_{n}={\frac {1}{2\pi i}}\int _{\gamma }{\frac {f(z)}{(z-c)^{n+1}}}dz$ 并且 $\gamma$ 是 $f(z)$ 是解析的环形区域中的一个轮廓，如下所示。

极点

极点是一种奇点。

$h(z)$ 的奇点是 $z$ 的值，其中 $h(z)=\infty$

如果 $\lim _{z\to a}(z-a)^{m}h(z)=L\neq 0$ 并且 $L$ 是定义的，则 $a$ 被称为 $h(z)$ 的 **极点**，**阶数** 为 $m$。

当我们 计算 $h_{-m}$ 时，我们将利用这一事实。

例如，${\frac {1}{(1-2z)^{2}}}$ 有奇点 ${\frac {1}{2}}$，因为 ${\frac {1}{(1-2{\frac {1}{2}})^{2}}}={\frac {1}{(1-1)^{2}}}={\frac {1}{0^{2}}}={\frac {1}{0}}=\infty$，并且 ${\frac {1}{2}}$ 是 2 阶极点，因为 $\lim _{z\to {\frac {1}{2}}}(z-{\frac {1}{2}})^{2}{\frac {1}{(1-2z)^{2}}}=\lim _{z\to {\frac {1}{2}}}(z-{\frac {1}{2}})^{2}{\frac {1}{(-2)^{2}(z-{\frac {1}{2}})^{2}}}=\lim _{z\to {\frac {1}{2}}}{\frac {1}{(-2)^{2}}}={\frac {1}{4}}$.

最靠近原点

我们将 $h(z)$ 视为一个复函数，其中输入 $z$ 是一个复数。

复数有两个部分，实部（Re）和虚部（Im）。因此，如果我们要表示一个复数，我们将在二维图上表示它。

如果我们要比较两个复数的“大小”，我们比较它们在二维平面中与原点的距离（即上图中蓝色箭头的长度）。这称为模数，用 $|z|$ 表示。

主要部分

Wilf 的证明。

Laurent 级数展开式的主要部分是带有负指数的项，即

${\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}$

我们将 $h(z)$ 在 $a$ 处的主要部分记为 $PP(h,a)$.

如果 $a$ 是距离原点最近的极点，则收敛半径 $R=|a|$ ，作为 Cauchy-Hadamard 定理 的结果

$\left({\frac {1}{|a|}}-\epsilon \right)^{n}\leq [z^{n}]h(z)\leq \left({\frac {1}{|a|}}+\epsilon \right)^{n}$ （对于某个 $\epsilon >0$ 且对于足够大的 $n$）。

其中 $[z^{n}]h(z)$ 是 $h(z)$ 的 $n$ 次系数。

$h(z)-PP(z)$ 在 $a$处不再存在极点，因为 $\left({\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-}1}{z-a}}+h_{0}+h_{1}(z-a)+\cdots \right)-\left({\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}\right)=h_{0}+h_{1}(z-a)+\cdots$.

如果 $h(z)$ 相对于原点第二近的极点是 $a'$，则 $a'$ 是 $h(z)-PP(z)$ 的最大极点，根据上述定理，$h(z)-PP(h,a)\leq \left({\frac {1}{|a'|}}+\epsilon \right)^{n}$ （对于足够大的 $n$）。

因此，$PP(h,a)$ 的系数最多与 $h(z)$ 的系数相差 $\left({\frac {1}{|a'|}}+\epsilon \right)^{n}$ （对于足够大的 $n$）。

请注意，如果 $a$ 是唯一的极点，则差值最多为 $\epsilon ^{n}$ （对于足够大的 $n$）。

如果 $a'<a$，那么我们可以在 $PP(h,a)$ 处停止，因为它已经是一个足够好的近似值。

然而，如果 $a'=a$，那么 $PP(h,a)$ 的系数将与 $h(z)$ 相差最多 $\left({\frac {1}{|a|}}+\epsilon \right)^{n}$。这个差值与 $PP(h,a)$ 的系数一样大。这不是一个很好的近似值。所以，如果在与原点相同距离处存在其他极点，最好使用所有这些极点。

最大系数

比较

$[z^{n}]{\frac {h_{-m}}{(z-a)^{m}}}={\frac {h_{-m}}{a^{m}}}{\binom {n+m-1}{n}}\left({\frac {1}{a}}\right)^{n}\sim {\frac {h_{-m}}{a^{m}}}\left({\frac {1}{a}}\right)^{n}n^{m-1}$

其中

$[z^{n}]{\frac {h_{-(m-1)}}{(z-a)^{m-1}}}={\frac {h_{-(m-1)}}{a^{m-1}}}{\binom {n+m-2}{n}}\left({\frac {1}{a}}\right)^{n}\sim {\frac {h_{-(m-1)}}{a^{m-1}}}\left({\frac {1}{a}}\right)^{n}n^{m-2}$

前者的第 $n$ 个系数与后者仅相差 $O({\frac {n^{m-2}}{a^{n}}})$。

第一项系数的计算

${\frac {h_{-m}}{(z-a)^{m}}}={\frac {(-1)^{m}h_{-m}}{a^{m}(1-{\frac {z}{a}})^{m}}}$ 通过提取 $\left({\frac {-1}{a}}\right)^{m}$。

${\frac {(-1)^{m}h_{-m}}{a^{m}(1-{\frac {z}{a}})^{m}}}={\frac {(-1)^{m}h_{-m}}{a^{m}}}\sum _{n\geq 0}{\binom {n+m-1}{n}}\left({\frac {z}{a}}\right)^{n}$ 根据负指数的二项式定理。

计算 h_-m

$h(z)={\frac {h_{-m}}{(z-a)^{m}}}+{\frac {h_{-(m-1)}}{(z-a)^{m-1}}}+\cdots +{\frac {h_{-}1}{z-a}}+h_{0}+h_{1}(z-a)+\cdots$.

所以，$\lim _{z\to a}(z-a)^{m}h(z)=\lim _{z\to a}h_{-m}+h_{-(m-1)}(z-a)+\cdots +h_{-}1(z-a)^{m-1}+h_{0}(z-a)^{m}+h_{1}(z-a)^{m+1}+\cdots =h_{-m}$.

为了计算$\lim _{z\to a}(z-a)^{m}h(z)=\lim _{z\to a}{\frac {(z-a)^{m}f(z)}{g(z)}}$，因为分子和分母在$a$处都为$0$，我们需要使用洛必达法则

$\lim _{z\to a}{\frac {(z-a)^{m}f(z)}{g(z)}}=\lim _{z\to a}{\frac {((z-a)^{m}f(z))'}{g'(z)}}$

事实上，如果$a$是$g(z)$的$m>1$阶根，而$(z-a)^{m}f(z)$也是，那么它也是$g'(z)$和$((z-a)^{m}f(z))'$的根，因此$\lim _{z\to a}{\frac {((z-a)^{m}f(z))'}{g'(z)}}$仍然是不定式。因此，我们需要应用洛必达法则$m$次

$\lim _{z\to a}{\frac {((z-a)^{m}f(z))^{(m)}}{g^{(m)}(z)}}=\lim _{z\to a}{\frac {((z-a)^{m}f'(z)+m(z-a)^{m-1}f(z))^{(m-1)}}{g^{(m)}(z)}}=\lim _{z\to a}{\frac {((z-a)^{m}f''(z)+2m(z-a)^{m-1}f'(z)+m(m-1)(z-a)^{m-2}f(z))^{(m-2)}}{g^{(m)}(z)}}=\cdots ={\frac {m!f(a)}{g^{(m)}(a)}}$

二项式渐近式的证明

${\binom {n+m-1}{n}}={\frac {(n+m-1)!}{n!(m-1)!}}={\frac {(n+1)(n+2)\cdots (n+m-1)}{(m-1)!}}\sim {\frac {n^{m-1}}{(m-1)!}}$ 当 $n\to \infty$ 时。

参考文献

• Biggs, Norman L. (2002). 离散数学 (第 2 版). 牛津大学出版社.
• Flajolet, Philippe; Sedgewick, Robert (2009). 解析组合学 (PDF). 剑桥大学出版社.
• Lang, Serge (1999). 复分析 (第 4 版). 施普林格科学+商业媒体有限责任公司.
• Orloff, Jeremy. "泰勒级数和洛朗级数" (PDF). 检索于 2022年10月3日.
• Sedgewick, Robert. "4. 复变函数，有理函数和亚纯函数的渐近线" (PDF). 检索于 2022年9月16日.
• Sedgewick, Robert. "4. 复变函数，有理函数和亚纯函数的渐近线 (勘误)" (PDF). 检索于 2022年9月16日.
• Stroud, K. A. (2003). 高等工程数学 (第4版). Palgrave Macmillan.
• Stroud, K. A. (2001). 工程数学 (第5版). Palgrave Macmillan.
• Wilf, Herbert S. (2006). 生成函数学 (PDF) (第3版). A K Peters, Ltd.