解析組合學/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.