解析組合/亞純函式

介紹

本文解釋如何估計亞純生成函式的係數。

定理

由 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.