生成函數模型 (Generating Function Model)

2025/03/29    最後更新: 2025/09/28

生成函數

組合數學中，處理 $r$ 物件分配給 $n$ 個物件的問題可以用生成函數 (generating function) 方法處理，設 $a_r$ 為在某個流程中選擇 $r$ 個物件的方法數，並以多項式 $g$ 表達：

$$ \begin{align*} g (x) = a_0 x^0 + a_1 x^1 + \cdots + a_n x^n \end{align*} $$

如計算 $(1 + x)^3$ 中的 $x^2$ 係數，可以理解為每次乘法都選擇 $1$ 或 $x$，並計算 $1$ 被選擇 $1$ 次與 $x$ 被選擇 $2$ 次的數量

$$ \begin{align*} (1 + x)^3 & = (1 + x)(1 + x)(1 + x) \\ & = 111 + 11x + 1x1 + x11 + 1xx + x1x + xx1 + xxx \\ & = \binom{3}{0} + \binom{3}{1} x^1 + \binom{3}{2} x^2+ \binom{3}{3} x^3 \end{align*} $$

其等價的問題可以描述為，依次選取 3 顆蘋果或香蕉，選出 2 個香蕉有幾種方式？選取 $1$ 視為選蘋果，選取 $x$ 視為選香蕉，因此答案即為 $x^2$ 的對應係數，即 $\binom{3}{2} = 3$。

因此生成函數的概念為考慮帶有限制的整數選取問題，如下列式子有幾種可能的選取方式

$$ \begin{align*} & e_1 + e_2 = r, \\ & e_1 \in \{ 0, 1, 2, 3 \}, \\ & e_2 \in \{ 0, 1, 2 \}, \\ \end{align*} $$

等價於

$$ \begin{align*} & x^{e_1} x^{e_2} = x^{e_1 + e_2} = x^r, \\ & e_1 \in \{ 0, 1, 2, 3 \}, \\ & e_2 \in \{ 0, 1, 2 \}, \\ \end{align*} $$

接著用

• $(x^0 + x_1 + x^2 + x^3)$ 表示 $e_1$ 有 $\{ 0, 1, 2, 3 \}$ 的可能
• $(x^0 + x_1 + x^2)$ 表示 $e_2$ 有 $\{ 0, 1, 2 \}$ 的可能

例如 $x^0 x^2$ 表示 $e_1$ 選取 $0$ 且 $e_2$ 選擇 $2$ 的例子，其生成函數即為全部相乘

$$ \begin{align*} (x^0 + x_1 + x^2 + x^3) (x^0 + x_1 + x^2) \end{align*} $$

接著決定 $x^r$ 係數的問題，如此一來，選取問題就能被轉換成簡單的多項式乘法計算問題而已。

選取問題的方法數

在 2 顆紅球、2 顆黃球、3 顆藍球、3 顆綠球中選擇 $r$ 顆球的方式有幾種？以 $e_1, e_2, e_3, e_4$ 分別表示紅黃藍綠 4 種球的選取數量，如

$$ \begin{align*} & e_1 + e_2 + e_3 + e_4 = r \\ & 0 \leq e_1, e_2 \leq 2 \\ & 0 \leq e_3, e_4 \leq 3 \end{align*} $$

直覺來說這問題不容易處理，但用生成函數則能輕鬆的將問題轉換

• $(x^0 + x^1 + x^2)$ 表達紅球有 $\{0, 1, 2\}$ 能被選取的數量
• $(x^0 + x^1 + x^2)$ 表達黃球有 $\{0, 1, 2\}$ 能被選取的數量
• $(x^0 + x^1 + x^2 + x^3)$ 表達藍球有 $\{0, 1, 2, 3\}$ 能被選取的數量
• $(x^0 + x^1 + x^2 + x^3)$ 表達綠球有 $\{0, 1, 2, 3\}$ 能被選取的數量

例如 4 顆球的選取為 $x^0 x^1 x^2 x^1$ 表示出紅球選 0 顆、黃球選 1 顆、藍球選 2 顆和綠球選 1 顆。因此其生成函數為全部相乘

$$ \begin{align*} (x^0 + x^1 + x^2)^2 (x^0 + x^1 + x^2 + x^3)^2 \end{align*} $$

若考慮在這樣限制下選取 $r = 4$ 顆球的方法數，即為考慮此多項式的 $x^4$ 係數。

一般性選取問題

更一般性的，考慮一個較為複雜的問題「將 5 顆球分給 4 個箱子，其中第 1 個箱子至少要 2 顆，第 2 個箱子要偶數顆，第 3 與 4 個箱子要奇數顆，有幾種選擇法？」

首先令 $e_1$ 至 $e_4$ 為每個箱子的球數，並刻畫出箱子球數的限制

$$ \begin{align*} & e_1 + e_2 + e_3 + e_4 = 5, \\ & e_1 \in \{ 2, 3, 4, 5 \}, \\ & e_2 \in \{ 0, 2, 4 \}, \\ & e_3 \in \{ 1, 3, 5 \}, \\ & e_4 \in \{ 1, 3, 5 \}. \end{align*} $$

透過轉換

• 第 1 箱能被選取的數量為 $(x^2 + x^3 + x^4 + x^5)$
• 第 2 箱能被選取的數量為 $(x^0 + x^2 + x^4)$
• 第 3 箱能被選取的數量為 $(x^1 + x^3 + x^5)$
• 第 4 箱能被選取的數量為 $(x^1 + x^3 + x^5)$

其生成函數即為

$$ \begin{align*} (x^2 + x^3 + x^4 + x^5) (x^0 + x^2 + x^4) (x^1 + x^3 + x^5)^2 \end{align*} $$

因此在此限制下分配 5 顆球到箱子有幾種方法的問題，等價於求生成函數 $x^5$ 係數問題。

冪級數 (Power Series)

考慮 $r$ 個物件分配給 $n$ 個物件的問題，最簡單的描述是

$$ \begin{align*} & e_1 + e_2 + \cdots + e_n = r, \\ & 0 \leq e_i \leq r \end{align*} $$

其生成函數為 $(x^0 + x^1 + \cdots + x^r)^n$ 並考慮其 $x^r$ 係數；但此計算有時並不方便，可以考慮更泛用的冪級數 (Power Series)

$$ \begin{align*} (x^0 + x^1 + x^2 + \cdots)^n \end{align*} $$

並計算 $x^r$ 係數，這兩者所獲取的答案相同，但冪級數有更多方便的性質。

恆等式

1. $\dps 1 + x + x^2 + \cdots + x^m = (1 - x^{m + 1}) (1 - x)^{-1}$
2. $\dps 1 + x + x^2 + \cdots = (1 - x)^{-1}$
3. $\dps (1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$
4. $\dps (1 - x^m)^n = \sum_{k = 0}^{n} (-1)^k \binom{n}{k} x^{km}$
5. $\dps (1 - x)^{-n} = \sum_{k = 0}^{\infty} \binom{n - 1 + k}{k} x^k$

若 $f (x) = \sum_{k = 0}^{\infty} a_k x^k$ 與 $g (x) = \sum_{k = 0}^{\infty} b_k x^k$，則

$$ \begin{align*} h (x) & = f (x) g(x) \\ & = \sum_{k = 0}^{\infty} \left( \sum_{l = 0}^{k} a_l b_{k - l} \right) x^k \end{align*} $$

範例

例如考慮「將 $r$ 顆球分到 4 個箱子內，且第 1 箱至多 5 顆球，有幾種分法」，其方法數即為生成函數的 $x^r$ 係數，且生成函數為：

$$ \begin{align*} (1 + x + x^2 + \cdots + x^5) (1 + x + x^2 + \cdots)^3 \end{align*} $$

首先將元素數量減少

$$ \begin{align*} & \, (1 + x + x^2 + \cdots + x^5) (1 + x + x^2 + \cdots)^3 \\ = & \, \left( \frac{1 - x^6}{1 - x} \right) \left( \frac{1}{1 - x} \right)^3 \\ = & \, (1 - x^6) (1 - x)^{-4} \end{align*} $$

令 $f (x) = 1 - x^6 = \sum a_i x^i$ 與

$$ \begin{align*} g (x) = (1 - x)^{-4} = \sum_{k = 0}^{\infty} \binom{3 + k}{k} x^k = \sum b_i x^i \end{align*} $$

若考慮 $r = 10$ 的情況，即求取 $x^{10}$ 係數，即可透過 $a_0 b_{10} + a_1 b_9 + \cdots + a_{10} b_{0}$ 得出，其中 $a_i$ 有不少為 0，即可以化簡為

$$ \begin{align*} a_0 b_{10} + a_6 b_{4} = 1 \times \binom{3 + 10}{10} + (-1) \times \binom{3 + 4}{4} = 251 \end{align*} $$■

Partitions

先前考慮 $\contia{e}{n}$ 係數為 $1$ 的情況，並限制 $e_2$ 必須為偶數的情況

$$ \begin{align*} & e_1 + e_2 = r, \\ & e_1 \in \{ 0, 1, 2, \cdots \}, \\ & e_2 \in \{ 0, 2, 4, \cdots \} \end{align*} $$

在原本的方法中的生成函數為

$$ \begin{align*} (x^0 + x^1 + x^2 + \cdots) (x^0 + x^2 + x^4 + \cdots) \end{align*} $$

但其實上述的問題等價於

$$ \begin{align*} & e_1 + 2 e_2 = r, \\ & e_1 \in \{ 0, 1, 2, \cdots \}, \\ & e_2 \in \{ 0, 1, 2, \cdots \} \end{align*} $$

因此 $n e_i$ 並限制 $e_i \{ 0, 1, 3, 5, \cdots \}$ 的對應多項式為

$$ \begin{align*} ((x^0)^5 + (x^1)^5 + (x^3)^5 + (x^5)^5 + \cdots) \end{align*} $$

範例

任意正整數和為 $r$ 的情況有幾種可能？例如當 $r = 5$ 時有 7 種。

$$ \begin{align*} 5 & = 1 + 1 + 1 + 1 + 1 \\ & = 1 + 1 + 1 + 2 \\ & = 1 + 1 + 3 \\ & = 1 + 2 + 2 \\ & = 1 + 4 \\ & = 2 + 3 \\ & = 5 \end{align*} $$

這議題是考慮有幾個 $1$，幾個 $2$，幾個 $3$，$\cdots$ 其和為 $r$，令 $e_i$ 為 $i$ 選取的數量，則求和為 $r$ 的議題則為

$$ \begin{align*} & e_1 + e_2 + e_3 + \cdots = r, \\ & e_1 \in \{ 0, 1, 2, \cdots \}, \\ & e_2 \in \{ 0, 2, 4, \cdots \}, \\ & e_3 \in \{ 0, 3, 6, \cdots \}, \\ & \quad \vdots \end{align*} $$

等價於

$$ \begin{align*} & 1 e_1 + 2 e_2 + 3 e_3 + \cdots = r, \\ & e_i \in \{ 0, 1, 2, \cdots \} \end{align*} $$

其對應的生成函數為

$$ \begin{align*} & (x^0 + x^1 + x^2 + \cdots) \\ & \times (x^0 + x^2 + x^4 + \cdots) \\ & \times (x^0 + x^3 + x^6 + \cdots) \\ & \times \cdots \times (x^0 + x^{k} + x^{2k} + \cdots ) \\ & \times \cdots \end{align*} $$■

指數型生成函數 (Exponential Generating Function)

在前述的議題中僅考慮組合數而不考慮排列，即 $1xx$ 與 $x11$ 視為同一種。但若同時考慮排列數量，則可引進指數型生成函數 (Exponential Generating Function)。

考慮 $a, b, c$ 三個字的排列數並限制 $a$ 至少要兩個，則可以先處理數量限制，再處理排列方式，即 $\{a, a, a, a\}$, $\{a, a, a, b\}$, $\{a, a, a, c\}$, $\{a, a, b, b\}$, $\{a, a, b, c\}$, $\{a, a, c, c\}$ 有 $6$ 可行的數量方式，再考慮排列數量和

$$ \begin{align*} \frac{4!}{4!0!0!} + \frac{4!}{3!1!0!} + \frac{4!}{3!0!1!} + \frac{4!}{2!2!0!} + \frac{4!}{2!1!1!} + \frac{4!}{2!0!2!} = 33 \end{align*} $$

但在原先的生成函數會考慮 $e_1, e_2, e_3$ 分別為 $a, b, c$ 字母數量，並滿足

$$ \begin{align*} x^{e_1 + e_2 + e_3} = x^4, \quad e_1 \geq 2, \quad e_2, e_3 \geq 0 \end{align*} $$

然而其中每個可成立的解僅貢獻 $1$ 次記數，而非 $4! / (e_1! e_2! e_3!)$ 次，因此考慮的問題轉換為

$$ \begin{align*} & \frac{(e_1 + e_2 + e_3)!}{e_1! e_2! e_3!} x^{e_1 + e_2 + e_3}, \quad e_1 \geq 2, \quad e_2, e_3 \geq 0 \end{align*} $$

其中的 $x^r$ 係數為

$$ \begin{align*} & \sum_{\substack{e_1 + e_2 + e_3 = r}} \frac{r!}{e_1! e_2! e_3!}, \quad e_1 \geq 2, \quad e_2, e_3 \geq 0 \end{align*} $$

使用這樣的表達式與原先計算方式相同，然而透過一個巧妙的轉換，給 $x^r$ 除以 $r!$，再考慮 $x^r / r!$ 的係數，如此多此一舉的行為看似沒改變問題，但實際上已經將問題轉換成泰勒展開式 (Taylor expansion)，即指數型生成函數 (Exponential Generating Function) 的形式

$$ \begin{align*} g (x) & = \sum_{r = 0}^{\infty} a_r \frac{x^r}{r!} \\ & = a_0 + a_1 x + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \cdots \end{align*} $$

這樣做會使得計算更加簡便，並擁有許多良好的數學性質。

恆等式

1. $\dps e^x = \sum_{i = 0}^{\infty} \frac{x^i}{i!}$
2. $\dps e^{nx} = \sum_{i = 0}^{\infty} \frac{n^i x^i}{i!}$
3. $\dps \frac{1}{2} (e^x + e^{-x}) = \frac{x^0}{0!} + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots$
4. $\dps \frac{1}{2} (e^x - e^{-x}) = \frac{x^1}{1!} + \frac{x^3}{3!} + \frac{x^5}{5!} + \cdots$

因此原先排字母的的議題就會變成考慮

1. $\sum_{i = 2}^{\infty} \frac{x^i}{i!} = \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$ 表達 $e_1 \geq 2$ 的選取範圍
2. $\sum_{i = 0}^{\infty} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2!} +\cdots$ 表達 $e_2 \geq 0$ 的選取範圍
3. $\sum_{i = 0}^{\infty} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2!} +\cdots$ 表達 $e_3 \geq 0$ 的選取範圍

其生成函數為

$$ \begin{align*} & \left( \sum_{i = 2}^{\infty} \frac{x^i}{i!} \right) \left( \sum_{i = 0}^{\infty} \frac{x^i}{i!} \right)^2 \\ = \, & (e^x - 1 - x) (e^x)^2 \\ = \, & e^{3x} - e^{2x} - x e^{2x} \\ = \, & \sum_{i = 0}^{\infty} \frac{3^i x^i}{i!} - \sum_{i = 0}^{\infty} \frac{2^i x^i}{i!} - \sum_{i = 0}^{\infty} \frac{2^i x^{i + 1}}{i!} \\ = \, & \sum_{i = 0}^{\infty} \left( 3^i - 2^i - i 2^{i - 1} \right) \frac{x^i}{i!} \end{align*} $$

若回到 $r = 4$ 的例子，就會發現 $3^4 - 2^4 - 4 \cdot 2^{4 - 1} = 33$，與原先的答案相同。

求和法

在前面的生成函數問題中，我們先建構了生成函數 $g (x)$，再找出其 $x^r$ 次方對應係數 $a_r$。在本段落我們要討論，如果給定 $a_r$，與另一係數 $b_r$ 與 $a_r$ 的關係，那該如何反推出 $b_r$ 對應的生成函數。首先令 $A (x) = \sum_{r = 0}^{\infty} a_r x^r$、$B (x) = \sum_{r = 0}^{\infty} b_r x^r$ 與 $C (x) = \sum_{r = 0}^{\infty} c_r x^r$，則關係的推論滿足

1. 若 $c_r = \alpha a_r$，則 $C (x) = \alpha A (x)$
2. 若 $c_r = a_r + b_r$，則 $C (x) = A (x) + B (x)$
3. 若 $c_r = \sum_{i = 0}^{r} a_i b_{r - i}$，則 $C (x) = A (x) B (x)$
4. 若 $c_r = a_{r - k}$ 且 $c_r = 0$ 對 $r < k$，則 $C (x) = x^k A (x)$
5. 若 $c_r = r a_r$，則 $C (x) = x (\frac{d}{dx} A (x))$
6. 若 $c_r = \sum_{i = 0}^{\infty} a_i$，則 $C (x) = (1 - x)^{-1} A (x)$

這分別對應上多項式的加法與乘法，其中第 4 項表達的是將多項式係數向右移動，而第 5 項目則是一個在多項式中常用的工具，證明如下：

$$ \begin{align*} x \left[ \frac{d}{dx} A (x) \right] = x \left[ \sum_{r = 0}^{\infty} r a_r x^{r - 1} \right] = \sum_{r = 0}^{\infty} r a_r x^r \end{align*} $$

第 6 項則是討論 $c_r$ 是 $\contia{a}{r}$ 的和，其應用上 $B (x) = (1 - x)^{-1}$ 對應係數全是 $1$ 的性質，這是第 3 項性質的直接推導。

範例

接著討論多項式中 $a_r = 1$ 對任意 $r$ 的例子，其對應的多項式就是 $(1 - x)^{-1}$

$$ \begin{align*} (1 - x)^{-1} = \sum_{r = 0}^{\infty} x^{r} \end{align*} $$

而 $b_r = r$ 的例子則是從 $(1 - x)^{-1}$ 與微分關係得出，已知 $b_r = r a_r = r \times 1 $，則 $b_r$ 對應多項式的則為 $x (\frac{d}{dx} (1 - x)^{-1})$

$$ \begin{align*} \sum_{r = 0}^{\infty} r x^r = x \left( \frac{d}{dx} (1 - x)^{-1} \right) = x (1 - x)^{-2} \end{align*} $$

因此 $B (x) = x (1 - x)^{-2}$ ■。

範例

考慮生成函數 $A (x)$ 的對應係數 $a_r = (r + 1) r (r - 1) = r^3 - r$，其生成函數當然能透過對係數為 $b_r = r$ 的生成函數微分的方法往下推論。但也能從 $(1 - x)^{-4}$ 開始，令 $b_r$ 為 $(1 - x)^{-4}$ 的係數，則

$$ \begin{align*} b_r & = \binom{r + 3}{3} = \frac{(r + 3) (r + 2) (r + 1)}{3!} \\ 3! b_r & = (r + 3) (r + 2) (r + 1) = a_{r + 2} \end{align*} $$

因此 $A (x) = x^2 3! (1 - x)^{-4}$。■

遞迴關係

現在我們考慮 $a_n$ 具有遞迴關係的情況，並由此建構其通項。例如 $a_n = a_{n - 1} + 1$ 與 $a_0 = 1$，則通項公式則顯然的 $a_n = n$。然而實際的遞迴關係往往更加複雜，如銀行複利，生物群系數量等議題，常見的遞迴關係有：

1. 分而治之 (divide and conquer)

   $$ \begin{align*} a_n = c a_{n / 2} + f (n) \end{align*} $$

2. 齊次 (homogeneous or linear)

   $$ \begin{align*} a_n = c_1 a_{n - 1} + c_2 a_{n - 2} + \cdots + c_r a_{n - r} \end{align*} $$

3. 非齊次 (inhomogeneous)

   $$ \begin{align*} a_n = c a_{n - 1} + f (n) \end{align*} $$

其概念可以理解為 $a_{n}$ 次項無法直接求得，但能從較小的項目，如 $a_{n - 1}$ 求得；若 $a_{n - 1}$ 仍無法求得，就繼續減小至 $a_{n - 2}$ 開始，一直「遞迴」到一個已知狀態，如起始狀態 $a_0$。

分而治之 (Divide and Conquer)

考慮分而治之的遞迴關係

$$ \begin{align*} a_n = c a_{n / 2} + f (n) \end{align*} $$

可以理解為將一個大小為 $n$ 的問題，分解成兩個 $n / 2$ 的子問題。考慮在不同 $c$ 與 $f (n)$ 的設定下，$a_n$ 通式有以下規律，其中 $A$ 可由起始條件解出。

$c$	$f (n)$	$a_n$
$1$	$d$	$d \ceil{\log_2 n} + A$
$2$	$d$	$An - d$
$2$	$dn$	$dn (\ceil{\log_2 n} + A)$
$\geq 2$	$dn$	$An^{\log_2 c} + \left( \frac{2d}{2 - c} \right) n$

齊次 (Homogeneous or Linear) 遞迴

考慮齊次遞迴關係

$$ \begin{align*} a_n = c_1 a_{n - 1} + c_2 a_{n - 2} + \cdots + c_r a_{n - r} \end{align*} $$

其一般解可以從給定 $a_n = \alpha^n$ 開始，因此寫成

$$ \begin{align*} \alpha^n = c_1 \alpha^{n - 1} + c_2 \alpha^{n - 2} + \cdots + c_r \alpha^{n - r} \end{align*} $$

移項且同除 $\alpha^{n - r}$ 後可得 characteristic equation

$$ \begin{align*} \alpha^r - c_1 \alpha^{r - 1} - c_2 \alpha^{r - 2} - \cdots - c_r = 0 \end{align*} $$

這成為了一個 $r$ 次多項式，在沒有重根的前提下有 $r$ 個解 $\contia{\alpha}{r}$，其線性組合也是 $a_n$ 的解，因此 $a_n$ 的解可以寫成

$$ \begin{align*} a_n = A_1 \alpha_1^n + A_2 \alpha_2^n + \cdots + A_r \alpha_r^n \end{align*} $$

其中 $\contia{A}{r}$ 為常數，可由給定的起始條件解出。

費波那契數列 (Fibonacci Sequence)

費波那契數列 (Fibonacci Sequence) 定義相當簡單，給定數列的起始條件 $a_0 = 0$ 與 $a_1 = 1$，與遞迴關係

$$ \begin{align*} a_{n} = a_{n - 1} + a_{n - 2} \end{align*} $$

其 characteristic equation 為

$$ \begin{align*} \alpha^2 = \alpha^1 + 1 \end{align*} $$

得出兩解 $\alpha_1$ 與 $\alpha_2$，值得注意的是，這解正是黃金比例 (golden ratio) 的解

$$ \begin{align*} \alpha_1 & = \frac{1 + \sqrt{5}}{2} = \varphi, \\ \alpha_2 & = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = -\varphi^{-1} \end{align*} $$

因此 $a_n$ 通項為

$$ \begin{align*} a_n = A_1 \left( \frac{1 + \sqrt{5}}{2} \right)^n + A_2 \left( \frac{1 - \sqrt{5}}{2} \right)^n \end{align*} $$

帶入起始條件

$$ \begin{align*} 0 = a_0 & = A_1 \left( \frac{1 + \sqrt{5}}{2} \right)^0 + A_2 \left( \frac{1 - \sqrt{5}}{2} \right)^0 \\ 1 = a_1 & = A_1 \left( \frac{1 + \sqrt{5}}{2} \right)^1 + A_2 \left( \frac{1 - \sqrt{5}}{2} \right)^1 \\ \end{align*} $$

由此解出 $A_1 = -A_2 = \sqrt{5}^{-1/2}$，反帶回 $a_n$ 整理後可得

$$ \begin{align*} a_n = \frac{\varphi^n - (1 - \varphi)^n}{\varphi - (1 - \varphi)} \end{align*} $$

其中 $\varphi = (1 + \sqrt{5}) / 2$ 為黃金比例。 ■

非齊次 (Inhomogeneous) 遞迴

考慮非齊次遞迴關係

$$ \begin{align*} a_n = a_{n - 1} + n \end{align*} $$

並給定起始條件 $a_0 = 1$。令 $g (x) = \sum_{n = 0}^{\infty} a_n x^n$，則可由多項式關係，先移除起始條件後，再遞迴出解

$$ \begin{align*} g (x) - a_0 & = \sum_{n = 1}^{\infty} a_n x^n \\ & = \sum_{n = 1}^{\infty} (a_{n - 1} + n) x^n \\ & = x \sum_{n = 0}^{\infty} a_n x^n + \sum_{n = 0}^{\infty} \binom{n}{1} x^n \\ & = x g (x) + \frac{x}{(1 - x)^{2}} \end{align*} $$

移項後可得

$$ \begin{align*} g (x) & = (1 - x)^{-1} + x (1 - x)^{-3} \\ & = \sum_{n = 0}^{\infty} \left[ 1 + \binom{n + 1}{2} \right] x^n \end{align*} $$

又因 $g (x) = \sum_{n = 0}^{\infty} a_n x^n$，係數對應得出 $a_n = 1 + \binom{n + 1}{2}$。 ■

複利

稍微複雜一點的情況，如銀行複利考慮每單位時間存入 $c$，利息為 $r$，則遞迴關係寫成

$$ \begin{align*} a_n & = (1 + r) a_{n - 1} + c \end{align*} $$

其通式為

$$ \begin{align*} a_n = a_0 (1 + r)^n + c \left( \frac{(1 + r)^n - 1}{r} \right) \end{align*} $$

更多應用與計算機參考 複利計算機 。

費波那契數列 (Fibonacci Sequence) 2.0

再次考慮費波那契數列，其起始條件為 $a_0 = 0$ 與 $a_1 = 1$，與遞迴關係 $a_n = a_{n - 1} + a_{n - 2}$。若用 $g (x) = \sum_{i = 0}^{\infty} a_n x^n$ 求取 $a_n$ 通項，在移除起始條件時，需移除 $a_0 + a_1 x^1$；在 $a_n$ 拆分時需拆分成兩項 $a_{n - 1}$ 與 $a_{n - 2}$。

$$ \begin{align*} g (x) - a_0 - a_1 x^1 & = \sum_{n = 2}^{\infty} a_n x^n \\ & = \sum_{n = 2}^{\infty} (a_{n - 1} + a_{n - 2}) x^n \\ & = x \left( - a_0 + \sum_{n = 0}^{\infty} a_n x^n \right) + x^2 \left( \sum_{n = 0}^{\infty} a_n x^n \right) \\ & = x g (x) + x^2 g (x) \end{align*} $$

解出

$$ \begin{align*} g (x) = \frac{x}{1 - x - x^2} \end{align*} $$■

參考資料

1. Tucker, A. (2012). Applied combinatorics. John Wiley & Sons.