解析组合学/Darboux 方法

介绍

Darboux 方法是估计包含根的生成函数系数的一种方法。

它比奇点分析更容易，但它适用于更小的一组函数。

大O

我们将使用“大O”符号。

$f(z)=O(g(z))$ 当 $z\to \zeta$

这意味着存在正实数 $M,\delta$ 使得如果 $0<|z-\zeta |<\delta$

$|f(z)|\leq Mg(z)$

或者，我们可以说

$f(z)=O(g(n))$

对于正整数 $n$，这意味着存在正实数 $M$ 和正整数 $N$ 使得

$|f(n)|\leq Mg(n)$ 对于 $n\geq N$

定理

Wilf 证明的定理。

如果我们有一个函数 $(1-z)^{\beta }f(z)$ 其中 $\beta \notin \{0,1,2,\ldots \}$ 其中 $f(z)$ 的收敛半径大于 $1$ 并在 1 附近有一个展开式 $\sum _{j\geq 0}f_{j}(1-z)^{j}$，那么

$[z^{n}](1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}+O(n^{-m-\beta -2})$

示例

该定理有点抽象，所以我会在进行证明之前展示如何使用它的例子。

从 Wilf中取一个例子。

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

$e^{-z/2-z^{2}/4}$ 是一个完全函数，因此它的收敛半径大于 1。

它可以在 1 附近使用泰勒级数展开。

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

因此，对于 $m=0$

$[z^{n}]{\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}=e^{-3/4}{\frac {n^{-{\frac {1}{2}}}}{\Gamma ({\frac {1}{2}})}}+O(n^{-{\frac {3}{2}}})$

或者，如果我们想要更高的精度，我们可以设置 $m=1$

$[z^{n}]{\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}=e^{-3/4}{\frac {n^{-{\frac {1}{2}}}}{\Gamma ({\frac {1}{2}})}}+e^{-3/4}{\frac {n^{-{\frac {3}{2}}}}{\Gamma (-{\frac {1}{2}})}}+O(n^{-{\frac {5}{2}}})$

等等。

证明

Wilf 证明。

我们有

$(1-z)^{\beta }f(z)=\sum _{j\geq 0}f_{j}(1-z)^{\beta +j}$

并且

$\sum _{j\geq 0}f_{j}(1-z)^{\beta +j}=\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}+\sum _{j>m}f_{j}(1-z)^{\beta +j}$

通过从最后一个求和中分解出 $(1-z)^{\beta +m+1}$

$\sum _{j>m}f_{j}(1-z)^{\beta +j}=(1-z)^{\beta +m+1}g(z)$

因此

$(1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}+(1-z)^{\beta +m+1}g(z)$

我们需要证明

1. $[z^{n}]\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}=\sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}$
2. $[z^{n}](1-z)^{\beta +m+1}g(z)=O(n^{-m-\beta -2})$

证明 1

通过应用 #引理 1

$[z^{n}]\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}=\sum _{j=0}^{m}f_{j}[z^{n}](1-z)^{\beta +j}\sim \sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}$

证明 2

$[z^{n}](1-z)^{\beta +m+1}=O(n^{-m-\beta -2})$ （根据 #引理 1）

$[z^{n}]g(z)=O(\theta ^{n})\quad (0<\theta <1)$ （因为，根据 定理 中的假设，收敛半径 $R$ 大于 $1$，并且 柯西不等式 告诉我们 $[z^{n}]g(z)=O\left({\frac {1}{R^{n}}}\right)$ 并且 ${\frac {1}{R^{n}}}<1$）

$\left|\sum _{0\leq k\leq {\frac {n}{2}}}h_{k}g_{n-k}\right|\leq \left\{\max _{0\leq k\leq {\frac {n}{2}}}|h_{k}|\right\}\left\{\sum _{0\leq k\leq {\frac {n}{2}}}A\theta ^{n-k}\right\}=\max\{B,Bn^{-m-\beta -2}\}C\theta ^{\frac {n}{2}}\leq D\theta ^{\frac {n}{2}}=O(\theta ^{\frac {n}{2}})$ （对于 $A,B,C,D$ 常数，并假设 $-m-\beta -2<0$）。

$\left|\sum _{{\frac {n}{2}}\leq k\leq n}h_{k}g_{n-k}\right|\leq \left\{\max _{{\frac {n}{2}}\leq k\leq n}|h_{k}|\right\}\left\{\sum _{{\frac {n}{2}}\leq k\leq n}A\theta ^{n-k}\right\}\leq Bn^{-m-\beta -2}=O(n^{-m-\beta -2})$

因为 $\left\{\sum _{{\frac {n}{2}}\leq k\leq n}A\theta ^{n-k}\right\}\leq C\max _{{\frac {n}{2}}\leq k\leq n}\theta ^{n-k}=C$ 因为 $\theta ^{2}\leq \theta ^{1}\leq \theta ^{0}=1$.

总结起来

$[z^{n}](1-z)^{\beta +m+1}g(z)=O(\theta ^{\frac {n}{2}})+O(n^{-m-\beta -2})=O(n^{-m-\beta -2})$

因为 $C\theta ^{\frac {n}{2}}=o(n^{-m-\beta -2})$ 因为 $\theta <1$.

引理 1

$[z^{n}](1-z)^{\beta }\sim {\frac {n^{-\beta -1}}{\Gamma (-\beta )}}$

证明

$[z^{n}](1-z)^{\beta }={\binom {\beta }{n}}(-1)^{n}={\binom {n-\beta -1}{n}}={\frac {\Gamma (n-\beta )}{\Gamma (-\beta )\Gamma (n+1)}}={\frac {1}{\Gamma (-\beta )(n-\beta )^{(\beta +1)}}}\sim {\frac {n^{-\beta -1}}{\Gamma (-\beta )}}$

其中 $x^{(n)}$ 是上升阶乘.

Szegő 定理

我们可以将类似的定理应用于具有多个奇点的函数。来自 Wilf 和 Szegő.

如果 $f(z)$ 在 $|z|<1$ 内解析，在单位圆 $|z|=1$ 上有有限个奇点 $e^{i\phi _{1}},e^{i\phi _{2}},\cdots ,e^{i\phi _{r}}$，并且在每个奇点附近有展开式

$f(z)=\sum _{v\geq 0}c_{v}^{(k)}(1-ze^{-i\phi k})^{\alpha _{k}+v\beta _{k}}\quad (k=1,2,\cdots ,r{\text{ and }}\beta _{k}>0)$

那么我们有渐近级数

$[z^{n}]f(z)=\sum _{v\geq 0}\sum _{k=1}^{r}c_{v}^{(k)}{\binom {\alpha _{k}+v\beta _{k}}{n}}(-e^{i\phi k})^{n}$

参考文献

• Szegő, Gabor (1975)。正交多项式 (第 4 版)。美国数学学会。
• Wilf, Herbert S. (2006)。生成函数学 (PDF) (第 3 版)。A K Peters, Ltd.