摘要: 生成函數是利用冪級數中變數的係數來表達數列，在組合數學上有廣泛的應用。 本文中將介紹一般生成函數重要的性質並透過大量的例子說明他們在組合數學上的應用。

關鍵詞: 一般生成函數、 二項式定理、二項係數、遞迴、遞迴關係、冪級數、恆等式、 等比級數、數學歸納法、計數問題、整數分割、費伯那西、分項分式、 摺積。

一. 前言

在數學的領域中常常遇到艱難的數列問題， 若能利用生成函數則會使得問題變為輕而易舉。 生成函數 是一種常被運用在離散數學上的進階計算技巧。在數學中有很廣泛的應用， 常見的有計數問題、整數的分割、解遞迴關係、求數列和與 恆等式的證明。

西元十三世紀初， 義大利數學家費伯那西(Fibonacci, 1175$\sim$1250)研究費伯那西 數列 $0,1,1,2,3,5,8,13,21,\ldots$，得到遞迴關係為 $$F_{n+2}=F_{n+1}+F_n, \quad n\geq 0 \quad F_0=0, \quad F_1=1$$ 直到西元1843年，法國數學家棣美弗(Jacques-Philippe-Marie Binet, 1786$\sim$1856)利用一般生成函數才得到$F_n$一般解的式子， $$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n -\left(\frac{1-\sqrt{5}}{2}\right)^n\right],\quad n\geq 0 $$

在西元1748時，尤拉(Euler, 1707$\sim$1783)利用一般生成函數的技巧，深入研究整數的分割。 利用 $$P(x)=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3} \cdots=\prod_{i=1}^\infty \frac{1}{1-x^i},$$ 我們得到$p(0),p(1),p(2),\ldots$ 的生成函數，其中 $p(n)$ 代表正 整數 $n$ 的不同分割數, $p(0)$定義為1。

Wilf (1994)介紹了生成函數的基本定義、應用和離散數學上相關的例子。 Stanley (1999)兩冊的書總共用了八百多頁詳細的介紹生成函數的性質及在計數組合學上 各方面的應用。 Grimaldi (2004)討論到生成函數的運算技巧和提到生成函數的相關歷史。 黃子嘉(2001)收錄許多台灣地區關於生成函數的研究所入學考題。 讀者若對生成函數有深入瞭解，可參考上述書目。本文取材參考了上述文獻。

關於著名整數數列的生成函數及其相關性質，請參閱網路整數數列百科全書 "The On-Line Encyclopedia of Integer Sequences"(Sloane, 2007)。 在2007年5月27號共蒐集 了$130017$ 個數列，每個數列包含: 1. 數列的名稱; 2. 數列前幾十項; 3. 數列的別名; 4. 參考文獻; 5. 相關連結; 6. 生成函數; 7. Mathematica, Maple及一般程式的程式碼; 8.相關數列; 9.關鍵字; 10.作者。

生成函數可分為一般生成函數與指數生成函數，指數生成函數主要是用於 計算與排列有關的計數問題，限於篇幅大小，這裡只討論一般生成函數。

本文的主要目的是要介紹單變數的一般生成函數的基本性質，並透過大量的例子說明他們在 計數、整數分割、遞迴關係式、數列和與恆等式上廣泛的應用。一般生成函數更深入的應用， 如解數列的漸近公式與證明數列的單一性、凸性和同餘性等， 有興趣的讀者若想更進一步了解可參閱Wilf (1994)。

二. 基本性質

生成函數(generating function)是藉由冪級數中的係數來呈現數列，是研究數列性質非常有用的工具。 他能用於解很多不同類型的計數(組合)問題，像是選擇或分配不同種類物件的方法數， 這些計數問題受制於各種限制。 應用於解遞迴關係中，藉由轉換遞迴關係項成數列的項到生成函數的方程式中。 這方程式能由找到生成函數的解得到答案， 從這個解，能找到生成函數的冪級數係數，解出原來的遞迴關係式。 他也能應用於計算數列和與證明恆等式，藉由相關地簡單關係函數的優點， 此函數能轉換到包含數列的等式。

在生成函數的冪次的運算中使用到下面兩個重要的觀念:

1. 藉由$x^n$乘以 $x^m$後能得到$x^{m+n}$, 這呈現了個數相加與多項式相乘之間的關係。
2. 多項式或冪級數中的係數提供了生成函數中所要包含的資訊。 這說明利用生程函數來解問題的動機。

可由下面幾節的例子看見上述兩個理由是生成函數可以解多種應用問題的主要原因。

首先介紹一般生成函數的定義如下:

定義 2.1: 設 $\{a_k\}_0^\infty=\{a_0,a_{1},a_2,\ldots\}$ 是一數列， 則函數 \begin{align} f(x) = a_0 + a_1x+a_2x^2+\cdots = \sum_{k=0}^\infty a_k x^k \end{align} 稱為 $\{a_k\}_0^\infty$ 的一般生成函數 (ordinary generating function)。

換言之，一般生成函數是以 $\{a_k\}_0^\infty$ 為係數之 $x$ 的冪級數。

如果只有有限個 $a_k\neq 0$, 則 $\{a_k\}_0^\infty$ 的生成函數是一個多項式。 我們能定義有限項實數數列的生成函數藉由令 $a_{n+1}=0,a_{n+2}=0,\ldots$ 來擴充有限的數列 $a_0,a_1,\ldots,a_n$ 成為無窮的數列。 下面計算幾個常見數列的生成函數。

例 2.1: (常數數列的生成函數) 常數數列 $\{1\}_0^\infty$ 的生成函數是 $$f(x)=1+x+x^2+x^3+\cdots=\sum_{k=0}^\infty x^k $$ 此為公比是 $x$ 的等比級數，若 $|x|\lt 1$, 則此等比級數會收斂，其和為 $\frac{1}{(1-x)}$。$\Box$

例 2.2: (等比數列的生成函數) 等比數列 $\{r^k\}_{k=0}^\infty$ 的生成函數是 $$f(x)=1+rx+r^2 x^2+r^3 x^3+\cdots=\sum_{k=0}^\infty r^k x^k $$ 此為公比是 $rx$ 的等比級數，若 $|rx|\lt 1$, 則此等比級數會收斂，其和為 $\frac{1}{(1-rx)}$。$\Box$

等比級數的生成函數在生成函數的應用中具有無比重要的地位， 例如利用它的生成函數可以很容易的得到下列生成函數的冪級數 $$\frac{x^2}{3+2x}=\frac{x^2}{3} \left(\frac{1}{1-\left(-\frac{2}{3}x\right)}\right) =\frac{1}{3}\left(x^2-\frac{2}{3}x^3+\left(\frac{2}{3}\right)^2 x^4+\cdots\right)$$

例 2.3: (二項係數的生成函數) 令 $n$ 為任意正整數，二項係數 ${n\choose 0}$, ${n\choose 1}$, ${n\choose 2},\ldots,{n\choose n}$ 的生成函數是 $$f(x)={n\choose 0}+{n\choose 1}x+{n\choose 2}x^2+\cdots+{n\choose n}x^n=\sum_{k=0}^n {n\choose k} x^k$$ 根據二項式定理可知 $f(x)=(1+x)^n$。$\Box$

後面章節可以看見二項係數的生成函數可用於求許多與二項係數相關的級數和。 接著討論一些非常有用生成函數的基本性質。

定理 2.2: (一般生成函數的性質) 設 $f(x)=\sum_{n=0}^\infty a_nx^n$ 和 $g(x)=\sum_{n=0}^\infty b_nx^n$ 分別是數列 $\{a_n\}_0^\infty$ 和數 列 $\{b_n\}_0^\infty$ 的生成函數，則

1. (加法) $rf(x)+sg(x)$ 為 $\{ ra_n+sb_n\}_0^\infty$ 的生成函數。
2. (向後平移) 對於正整數 $h$, $x^h f(x)$ 為 $\underbrace{0,0,\ldots,0}_{h\mbox{個}},a_0,a_1,\ldots$ 的生成函數。
3. (向前平移) 對於正整數 $h$, $\frac{f(x)-a_0-\cdots-a_{h-1}x^{h-1}}{x^h}$ 為 $a_h,a_{h+1},\ldots$ 的生成函數。
4. (乘法、摺積) $f(x)g(x)$ 為 $\{\sum_{r=0}^n a_rb_{n-r}\}_0^\infty$ 的生成函數。
5. (轉換) $f(cx)$ 為 $\{c^n a_n\}_0^\infty$ 的生成函數。
6. (微分) $f'(x)$ 為 $\{(n+1)a_{n+1}\}_0^\infty $ 的生成函數。
7. (積分) $\int_0^x f(t) dt$ 為 $\{\frac{a_{n-1}}{n}\}_1^\infty $ 的生成函數。
8. (部分和) $\frac{f(x)}{(1-x)}$ 為 $\{\sum_{j=0}^n a_j\}_0^\infty $ 的生成函數， 一般稱 ${1\over 1-x}$ 為數列 $\{a_n\}_0^\infty$ 的求和算子。

證明:

1. 直接計算得 $rf(x)+sg(x)=r\sum_{n=0}^\infty a_n x^n+s\sum_{n=0}^\infty b_n x^n=\sum_{n=0}^\infty (ra_n+ sb_n) x^n$, 所以 $rf+sg$ 為 $\{ra_n+sb_n\}_0^\infty $ 的生成函數。
2. $x^h f(x)=x^h \sum_{n=0}^\infty a_n x^n=\sum_{n=h}^\infty a_{n-h} x^n$, $x^h f(x)$ 為 $0,0,\ldots,0,a_0,a_1,\ldots$ 的生成函數。
3. $\sum_{n\geq 0}a_{n+1} x^n =\frac{1}{x} \sum_{m\geq 1}a_m x^m=\frac{f(x)-f(0)}{x}=\frac{f(x)-a_0}{x}$, 所以 $\frac{f(x)-a_0}{x}$ 為 $\{a_{n+1}\}_0^\infty$ 的生成函數。 $\sum_{n\geq 0}a_{n+2} x^n =\frac{1}{x} \sum_{n+1\geq 1}a_{n+1} x^n=\frac{[(f(x)-a_0)/x]-a_1}{x}=\frac{f(x)-a_0-a_1x}{x^2}$, 因此 $\frac{f(x)-a_0-a_1x}{x^2}$ 為 $\{a_{n+2}\}_0^\infty$ 的生成函數。 同理，$\frac{f(x)-a_0-a_1x-\cdots-a_{h-1}x^{h-1}}{x^h}$ 為 $\{a_{n+h}\}_0^\infty$ 的生成函數。
4. 由冪級數的乘法規則得 \begin{align*} f(x)g(x)&=(a_0+a_1x+a_2x^2+\cdots)(b_0+b_1x+b_2x^2+\cdots)\\ &=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\cdots\\ &=\sum_{n=0}^\infty (a_0b_n+a_1b_{n-1}+\cdots+a_{n-1}b_1+a_nb_0)x^n \end{align*} 所以 $f(x)g(x)$ 為 $\{\sum_{r=0}^n a_rb_{n-r}\}_0^\infty$ 的生成函數。
5. $f(x)=\sum_{n=0}^\infty a_n x^n$, 則 $f(cx)=\sum_{n=0}^\infty a_n (cx)^n$。 因此, $f(cx)$ 為 $a_0,ca_1,c^2a_2\ldots=\{c^n a_n\}_0^\infty$ 的生成函數。
6. $f(x)=\sum_{n=0}^\infty a_n x^n$, 兩邊對 $x$ 微分得 $f'(x)=\sum_{n=1}^\infty n a_n x^{n-1}$, 則 $f'(x)$ 是 $a_1, 2a_2$, $3a_3, \ldots =\{(n+1)a_{n+1}\}_0^\infty $ 的生成函數。
7. 直接計算得 $\int_0^x f(t) dt= \int_0^x \sum_{n=0}^\infty a_n t^n dt =\sum_{n=0}^\infty a_n \left( \int_0^x t^n dt\right) =\sum_{n=1}^\infty \frac{a_{n-1}}{n}x^n =\{\frac{a_{n-1}}{n}\}_1^\infty$。
8. 直接計算得 \begin{align*} \frac{f(x)}{1-x}&=(a_0+a_1x+a_2x^2+\cdots)(1+x+x^2+\cdots)\\ &=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots\\ &=\sum_{n=0}^\infty \left(\sum_{j=0}^n a_j\right)x^n \end{align*} 所以 $\frac{f(x)}{1-x}$ 為 $\{\sum_{j=0}^n a_j\}_{n\geq 0}$ 的一般生成函數。 $\Box$

定理 2.2 是後面幾節生成函數應用的主要工具。

表 1 為常見數列的一般生成函數。若能熟悉表 1 對於我們解生成函數的問題有莫大的幫助。

表 1. 常見數列的一般生成函數

數列	一般生成函數
$1,1,1,1,1,\ldots$	$\frac{1}{1-x}$
$1,1,\ldots,1,0,0,\ldots (n \mbox{個1})$	$\frac{1-x^n}{1-x}$
${n\choose 0},{n\choose 1},\ldots,{n\choose n},0,0,\ldots$	$(1+x)^n$
$1,-1,1,-1,1,-1,\ldots$	$\frac{1}{1+x}$
$1,0,1,0,1,\ldots$	$\frac{1}{1-x^2}$
$1,2,3,4,5,\ldots$	$\frac{1}{(1-x)^2}$
$1,4,9,16,25,\ldots$	$\frac{1+x}{(1-x)^3}$
$1,r,r^2,r^3,r^4,\ldots$	$\frac{1}{1-rx}$
$0,r,2r^2,3r^3,4r^4,\ldots$	$\frac{rx}{(1-rx)^2}$

接著介紹如何利用基本性質求得常見數列的一般生成函數。

例 2.4: 求下列數列的生成函數:

1. $1,2,3,4,\ldots$
2. $0,1,2,3,4,\ldots$
3. $1^2,2^2,3^2,4^2,\ldots$
4. $0^2,1^2,2^2,3^2,4^2,\ldots$

解:

1. 考慮等比級數 $$1=(1-x)(1+x+x^2+x^3+x^4+\cdots)$$ 所以 $$\frac{1}{1-x}=1+x+x^2+x^3+x^4+\cdots=\sum_{k=0}^\infty x^k, \quad |x|\lt 1$$ 兩邊對 $x$ 微分 \begin{align*} \frac{d}{dx}\frac{1}{1-x} &=\frac{d}{dx}(1+x+x^2+x^3+x^4+\cdots+x^n+\cdots) \end{align*} 因此得 \begin{align*} \frac{1}{(1-x)^2} &=1+2x+3x^2+4x^3+\cdots+nx^{n-1}+\cdots\\ &=\sum_{i=1}^\infty ix^{i-1} =\sum_{j=0}^\infty (j+1)x^j, \quad |x|\lt \end{align*} 所以 $\frac{1}{(1-x)^2}$ 為數列 $1,2,3,4,\ldots$ 的生成函數。
2. 兩邊同乘 $x$ 得 $$\frac{x}{(1-x)^2}=0+x+2x^2+3x^3+4x^4+\cdots+nx^n+\cdots=\sum_{k=1}^\infty kx^k =\sum_{k=0}^\infty kx^k $$ 所以 $\frac{x}{(1-x)^2}$ 為數列 $0,1,2,3,4,\ldots$ 的生成函數。
3. 兩邊再對 $x$ 微分 $$\frac{d}{dx}\frac{x}{(1-x)^2}=\frac{d}{dx}(0+x+2x^2+3x^3+\cdots)$$ 所以 $$\frac{x+1}{(1-x)^3}=1^2+2^2x +3^2x^2+4^2x^3+ \cdots=\sum_{i=1}^\infty i^2x^{i-1}$$ 所以 $\frac{(1+x)x}{(1-x)^3}$ 為數列 $1^2,2^2,3^2,4^2,\ldots$ 的生成函數。
4. 兩邊再同乘 $x$ $$\frac{(1+x)x}{(1-x)^3}=\sum_{i=1}^\infty i^2 x^i =\sum_{i=0}^\infty i^2x^i$$ 所以 $\frac{(1+x)x}{(1-x)^3}$ 為數列 $0^2,1^2,2^2,3^2,4^2,\ldots$ 的生成函數。$\Box$

令 ${\mathbb R}=\{x|-\infty\lt x\lt \infty\}$ 表示實數的集合，而 ${\mathbb N}_0=\{0,1,2,\ldots\} $ 表示非負整數的集合。

例 2.5: (廣義二項係數) 設 $a\in {\mathbb R},k\in {\mathbb N}_0,{a\choose k}=\frac{a(a-1)(a-2)\cdots(a-k+1)}{k!},{a\choose 0}=1$, 求 ${a\choose 0},{a\choose 1},{a\choose 2},\ldots$ 的生成函數。

解: 考慮 $(1+x)^{a}$ 的馬克勞林展開 \begin{align*} (1+x)^{a}&=1+ax+a(a-1)x^2/2! +a(a-1)(a-2)x^3/3!+\cdots\\ &=1+\sum_{k=1}^\infty \frac{a(a-1)(a-2)\cdots(a-k+1)}{k!}x^k, \quad |x|\lt 1 \end{align*} 所以 $(1+x)^{a}={a\choose 0}+{a\choose 1}x+{a\choose 2}x^2+\cdots=\sum_{k=0}^\infty {a\choose k}x^k$。因此， $(1+x)^{a}$ 為 ${a\choose 0},{a\choose 1},{a\choose 2},\ldots$ 的生成函數。$\Box$

$(1+x)^{a}=\sum_{k=0}^\infty {a\choose k}x^k$稱為廣義二項式定理，此為二項式定理的推廣，後面章節中將利用二項 係數的生成函數求冪級數的係數，對於求數列和、計數、整數的分割 及解遞迴關係等應用有很大的幫助。

註: 設 ${\mathbb N}=\{1,2,\ldots\}$ 表示自然數的集合，當 $a=-m,m\in{\mathbb N}$ 時 \begin{align*} {-m\choose k}&=\frac{(-m)(-m-1)(-m-2)\cdots(-m-k+1)}{k!}\\ &=\frac{(-1)^k(m)(m+1)(m+2)\cdots(m+k-1)}{k!}\\ &=\frac{(-1)^k(m+k-1)!}{(m-1)!k!}\\ &=(-1)^k{m+k-1\choose k} \end{align*}

接著我們來看兩個廣義二項式定理的應用。

例 2.6: 求 $f(x)=(1-3x)^{-8}$ 的馬克勞林展開中 $x^4$ 的係數。

解: 令 $y=-3x$, 利用 $(1+y)^{a}=\sum_{n=0}^\infty {a\choose n}y^n$, 所以 $$(1-3x)^{-8}=(1+y)^{-8}=\sum_{n=0}^\infty {-8\choose n }y^n=\sum_{n=0}^\infty {-8\choose n}(-3x)^n$$因此在 $f(x)$ 中 $x^4$ 的係數為 ${-8\choose 4}(-3)^4=(-1)^4{8+4-1\choose 4}(81)={11\choose 4}(81)=26,730$。$\Box$

例 2.7: 求 $f(x)=\sqrt{1+x}$ 生成何種數列?

解: \begin{align*} \sqrt{1+x}&=(1+x)^{1/2}\\ &={1/2\choose 0}1+{1/2\choose 1}x+{1/2\choose 2}x^2+\cdots\\ &=1+\frac{1}{2}x+\frac{\frac{1}{2}\cdot\frac{-1}{2}}{2!}x^2 +\frac{\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}}{3!}x^3 +\frac{\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2} \cdot\frac{-5}{2}}{4!}x^4+\cdots\\ &=1+\frac{1}{2}x-\frac{1}{8}x^2+\frac{1}{16}x^3-\frac{5}{128}x^4+\cdots \end{align*} 所以 $\sqrt{1+x}$ 是數列 $\{{1/2\choose n}\}_{n=0}^\infty =\{1,\frac{1}{2},-\frac{1}{8}, \frac{1}{16},-\frac{5}{128},\ldots\}$ 的一般生成函數。$\Box$

接著是摺積性質的應用。

例 2.8: 試求數列 $\{{n\choose k}+2{n\choose k-1}\}_1^\infty$ 的生成函數。

解: 設 $a_k={n\choose k}$, 數列 $\{a_k\}_0^\infty$ 的生成函數為 $$f(x)=\sum_{k=0}^n a_k x^k =\sum_{k=0}^n {n\choose k} x^k=(1+x)^n$$ 考慮 $b_k={n\choose k}+2{n\choose k-1}=a_k+2a_{k-1}$, 且設 $g(x)$ 為 $\{b_k\}_0^\infty$ 的生成函數，則 \begin{align*} g(x) &=\sum_{k=1}^n b_k x^k =\sum_{k=1}^n (a_k+2a_{k-1}) x^k=(1+2x)(a_0+a_1x+\cdots +a_n x^n)-a_0\\ &=(a_0+b_1x+\cdots+b_n x^n)-a_0=(1+2x)(1+x)^n -1 \tag*{$\Box$} \end{align*}

三. 計數

對於利用一般生成函數去解計數問題時，可使用形式冪級數，將忽略級數是否收斂。

定義: 3.1: 形式冪級數為 $$\sum_{k=0}^\infty a_k x^k=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots$$ 其中常數 $a_0,a_1,a_2,\ldots$ 叫做冪級數的係數。

我們先說明如何利用生成函數來解相異物組合的問題: 設有三種相異物 $a,b,c$ 其中這三個相異物是可以重複選取， $a$ 最多可選三次， $b$ 最多選二次, $c$ 最多選一次。因為 $a$ 最多可選取三次， 表示可選取 $0,1,2$ 或 $3$ 次，所以可以用 $(1+ax+a^2x^2+a^3x^3)$ 來表示，同理 $(1+bx+b^2x^2)$ 表示 $b$ 可選取 $0,1$ 或 $2$ 次， $(1+cx)$ 表示 $c$ 可選取 $0$ 次或 $1$ 次。當全部放在一起得 \begin{align*} &(1+ax+a^2x^2+a^3x^3)(1+bx+b^2x^2)(1+cx)\\ &=1+(a+b+c)x+(a^2+b^2+ab+ac+bc)x^2\\ &\quad +(a^3+a^2b+ab^2+a^2c+b^2c+abc)x^3 +(a^3b+a^2b^2+a^3c+a^2bc+ab^2c)x^4\\ &\quad +(a^3bc+a^3b^2+a^2b^2c)x^5+(a^3b^2c)x^6 \end{align*}

常數項1表示 $a,b,c$ 都不選, $x$ 的係數 $a+b+c$ 表示選1個物品時可選 $a,b$ 或 $c$。 $x^2$ 的係數 $ab+ac+bc+a^2+a^2c+b^2$ 表示選兩個物品: $ab$ 表 $a,b$ 各選一次， $ac$ 表 $a,c$ 各選一次, $bc$ 表 $b,c$ 各選一次, $a^2$ 表 $a$ 選二次, $b^2$ 表 $b$ 選二次。 $x^3$ 的係數 $a^3+a^2b+ab^2+a^2c+b^2c+abc$ 表示選三個的物品, $a^3$ 表 $a$ 選三次， $a^2b$ 表 $a$ 選二次且 $b$ 選一次, $ab^2$ 表 $b$ 選二次且 $a$ 選一次， $a^2c$ 表 $a$ 選二次且 $c$ 選一次, $b^2c$ 表 $b$ 選二次且 $c$ 選一次, $abc$ 表 $a,b,c$ 各選一次。 同理 $x^4$ 的係數 $a^3b+a^2b^2+a^3c+a^2bc+ab^2c$ 表示選四個物品所有組合方式。 $x^5$ 的係數 $a^3bc+a^3b^2+a^2b^2c$ 表示選五個物品所有組合方式。 $x^6$ 的係數 $a^3b^2c$ 表示選六個物品所有組合方式。

當只關心事件發生可能之個數，而不在乎選取那些物品時，我們令 $a=b=c=1$ 代入得 $(1+x+x^2+x^3)(1+x+x^2)(1+x)=1+3x+5x^2+6x^3+5x^4+3x^5+x^6$。 多項式中 $x$ 的次方表示物品的個數，而係數則為其相對應的方法數。 表示三個物品都不選時方法數有1種，選一個物品時方法數有3種， 選二個物品時方法數有5種，選三個物品時方法數有6種， 選四個物品時方法數有5種， 選五個物品時方法數有3種，選六個物品時方法數有1種。 此為計數問題的生成函數，該問題的答案已具見於函數當中。

例 3.1: 將20顆相同的球分配到五個相異的箱子中，

1. 每個箱子至少有兩顆球，
2. 每個箱子至少有兩顆球但不超過7個，

求有幾種分配數。

解:

1. 每個箱子分配的可能性可利用生成函數 $\left(x^2+x^3+x^4+\cdots\right)$ 來表示， 因為有五個箱子，所以可看成 $$f(x)=\left(x^2+x^3+x^4+\cdots\right)^5=x^{10}\left(1+x+x^2+\cdots\right)^5 =\frac{x^{10}}{(1-x)^5}$$

   有20顆球要分配到五個箱子，所以在 $f(x)$ 中 $x^{20}$ 的係數可看成在 $(1-x)^{-5}$ 中 $x^{10}$ 的係數，設 $[x^n]f(x)$ 表示 $f(x)$ 的冪級數中 $x^n$ 的係數。 \begin{align*} \left[x^{20}\right]f(x)&=\left[x^{10}\right](1-x)^{-5}\\ &=\left[x^{10}\right]\left(1-{-5\choose 1}x+{-5\choose 2}x^2-{-5\choose 2}x^3+\cdots\right)\\ &={-5\choose 10} \end{align*} 因為 ${-5\choose 10}=(-1)^{10}{5+10-1\choose 10}={14\choose 10 }=1,001$, 所以總共有1,001種分配數。

2. 每個箱子分配的可能性可利用生成函數 $\left(x^2+x^3+x^4+\cdots+x^7\right)$ 來表示， 因為有五個箱子，所以可看成 \begin{align*} g(x)&=\left(x^2+x^3+x^4+\cdots+x^7\right)^5\\ &=x^{10}\left(1+x+x^2+x^3+x^4+x^5\right)^5\\ &=x^{10}\left(\frac{1-x^6}{1-x}\right)^5 \end{align*} 有20顆球要分配到五個箱子，所以在 $g(x)$ 中 $x^{20}$ 的係數可 看成在 $(1-x^6)^5(1-x)^{-5}$ 中 $x^{10}$ 的係數， \begin{align*} \left[x^{20}\right]g(x) &=\left[x^{10}\right]\left(\frac{1-x^6}{1-x}\right)^5\\ &=\left[x^{10}\right](1-x^6)^5(1-x)^{-5}\\ &=\left[{-5\choose 10}(-1)^{10}-{5\choose 1}{-5\choose 4}(-1)^4\right]\\ &={14\choose 10}-{5\choose 1}{8\choose 4}\\ &=651 \end{align*} 所以總共有651種分配數。$\Box$

例 3.2: [重複組合] 利用生成函數求 $n$ 個相異物允許重複取 $r$ 件組合的方法數有幾種?

解: 設 $P(x)$ 為數列 $\{a_r\}$ 的生成函數，其中 $a_r$ 代表 $n$ 個 物件中允許重複取 $r$ 件組合的方法數。因此, $P(x)=\sum_{r=0}^\infty a_r x^r$。因為我們能選擇任何 $n$ 個物件的特別的元素，當允許重複取 $r$ 件組合， 其對應的生成函數為 $(1+x+x^2+x^3+\cdots)$。 每一個物件對應到這個因子，因為每一個的選擇有可能是0次，1次，2次，3次以上。 因為在這個集合中有 $n$ 個物件，每個都是有相同因子，所以 $$P(x)=(1+x+x^2+\cdots )^n$$ 只要$|x|\lt 1$, 可以得到$1+x+x^2+\cdots =1/(1-x)$, 所以 $$P(x)=1/(1-x)^n=(1-x)^{-n}$$ 利用廣義的二項式定理, $$(1-x)^{-n}=(1+(-x))^{-n}=\sum_{r=0}^\infty {-n\choose r}(-x)^r $$ $n$ 個物件允許重複取 $r$ 件組合的方法數是在加總中 $x^r$ 的係數 $a_r$, 其中 $r$ 為正整數。 我們得到$a_r$等於 $${-n\choose r }(-1)^r={n+r-1\choose r}{\Box} $$

例 3.3: 請問函數 $\frac{1}{(1-x-x^2-\cdots-x^6)}$ 為何種數列的生成函數?

解: 由等比級數可知 \begin{align} \frac{1}{(1-x-x^2-\cdots-x^6)}=\sum_{k=0}^\infty (x+x^2+x^3+x^4+x^5+x^6)^k \label{eqnC:23487} \end{align} 由於投擲一個公平骰子的生成函數為 $(x+x^2+x^3+x^4+x^5+x^6)$, 因此 $\sum_{k=0}^\infty (x+x^2+x^3+x^4+x^5+x^6)^k$ 為不論投擲幾次骰子其點數和的次數的生成函數， 點數和剛好為 $n$ 的次數即為 $x^n$ 的係數。 $\Box$

例 3.4: 對於所有的整數 $n$, 證明 $n$ 都能由 $$1, 3, 3^2, 3^3, 3^4, \ldots$$ 經由唯一的子序列作加或減運算得到。例如: $10=1+3^2,73=3^4-3^2+1$。

證明: 令 $f_m(x)=\prod_{k=0}^m (1+x^{3^k}+x^{-3^k})$, 則 $(1+x^{3^k}+x^{-3^k})$ 其中 $1$ 代表 $3^k$ 沒有使用, $x^{3^k}$ 代表加 $3^k$, $x^{-3^k}$ 代表減$3^{k}$。 因此, $f_m(x)$ 展開後 $x^n$ 的係數代表是用 $1, 3, 3^2, 3^3, 3^4, \ldots$, $3^m$ 的子序列作加減所組合出來等於 $n$ 的方法數， 特別是 $x^0$ 的係數代表都不取時的方法數，在此狀況下只有一種。 當 $m=1$ 時， \begin{align*} f_1(x)&=(1+x+x^{-1})(1+x^3+x^{-3})\\ &=x^{-4}+x^{-3}+x^{-2}+x^{-1}+1+x+x^2+x^3+x^{4} \end{align*} 包含 $x^{-4}= x^{-1}\cdot x^{-3},x^{-3}=1\cdot x^{-3},\ldots , x^3=1\cdot x^3, x^4=x\cdot x^3 $, 且每一項的係數都為1，所以從 $-4$ 到4都有唯一的表示方法。

對任意的自然數 $m$, 則 \begin{align*} f_m(x)&=\prod_{k=0}^m (1+x^{3^k}+x^{-3^k})\\ &=(1+x+x^{-1})(1+x^3+x^{-3})(1+x^{3^2}+x^{-3^2})\cdots(1+x^{3^m}+x^{-3^m})\\ &=\left(\frac{x^2+x+1}{x}\right)\left(\frac{x^6+x^3+1}{x^3}\right) \left(\frac{x^{18}+x^9+1}{x^9}\right)\cdots\left(\frac{x^{2\cdot 3^m}+x^{3^m}+1}{x^{3^m}}\right)\\ &=\frac{1}{x x^3 x^9 \cdots x^{3^{m}}}\left(\frac{x^3-1}{x-1}\right)\left(\frac{x^9-1}{x^3-1}\right) \left(\frac{x^{27}-1}{x^9-1}\right)\cdots\left(\frac{x^{3^{m+1}}-1}{x^{3^m}-1}\right)\\ &=\frac{1}{x^{\frac{3^{m+1}-1}{2}}}\left(\frac{x^{3^{m+1}}-1}{x-1}\right)\\ &=\frac{x^{3^{m+1}-1}+\cdots+x+1}{x^{\frac{3^{m+1}-1}{2}}}\\ &=x^{\frac{3^{m+1}-1}{2}}+\cdots+x^{1}+1+x^{-1}+x^{-2}+\cdots+x^{-\frac{3^{m+1}-1}{2}} \end{align*} 則 $f_m(x)$ 的冪次包含了從$-\frac{3^{m+1}-1}{2}$到$\frac{3^{m+1}-1}{2}$ 的整數。 因此，當 $m\rightarrow \infty$ 時，就可以得到下面這個很漂亮的等式 $$\prod_{k=0}^\infty (1+x^{3^k}+x^{-3^k})=\sum_{k=-\infty}^\infty x^k$$ 因為 $k$ 是任意的整數，且 $x^k$ 的係數皆為1，因此得證。 $\Box$

對於在計數組合學上各方面的應用可參考 Stanley (1999)兩冊的書。

四. 整數分割

在整數的分割問題中可分為整數(有序)分割問題和整數(無序)分割兩種問題， 它們分別對應著「分配」問題和「組合」問題。

整數的分割是指把正整數 $n$分割為若干個正整數，各個正整數相加之和為 $n$, 問有多少種不同分割法? 由於各部分無次序之分，因此在列出某個正整數的各部分時，把它們按遞增序排列。 整數的有序分割可以加上限制條件，例如: 各個部分大小的限制條件、部分個數的限制條件。

在處理整數的分割中常常利用排容原理，但在這裡是利用生成函數法來解決這類型的問題。 對於某些計算處理上有困難，若利用生成函數會變得較為容易。先定義$p(n)$ 代表對正整數 $n$分割成各項皆不同的方法數， $P(x)$ 為 $p(n)$ 的生成函數。表 2 為自然數 $1,2,3,4,5$ 的整數分割:

表 2. 整數分割

$n$	分割的情況	分割方法數	$p(n)$
1	1	1	$p(1)$
2	2, 1+1	2	$p(2)$
3	3, 2+1, 1+1+1	3	$p(3)$
4	4, 3+1, 2+2, 2+1+1, 1+1+1+1	5	$p(4)$
5	5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1	7	$p(5)$

表 2 只要透過簡單的數學即可得到答案，如果延伸到較大的的整數時就需要一項工具記錄， 即生成函數中次方係數，例如: \begin{align*} & 1+x+x^2+x^3+x^4+\cdots & &\mbox{$x^i$ 項中的 $i$ 代表有 $i$ 個1}\\ &1+x^2+x^4+x^6+\cdots & &\mbox{$x^{2i}$ 項中的 $i$ 代表有 $i$ 個2}\\ &1+x^3+x^6+x^9+\cdots & &\mbox{$x^{3i}$ 項中的 $i$ 代表有 $i$ 個3}\\ & \quad\vdots & &\quad\vdots \\ &1+x^n+x^{2n}+x^{3n}+\cdots & &\mbox{$x^{ni}$ 項中的 $i$ 代表有 $i$ 個 $n$}\\ & \quad\vdots & &\quad\vdots \end{align*}

把上式表示成生成函數，可以寫成 $$P(x)=\frac{1}{(1-x)}\frac{1}{(1-x^2)}\frac{1}{(1-x^3)} \cdots\frac{1}{(1-x^n)}\cdots=\prod_{i=1}^\infty \frac{1}{(1-x^i)}$$ $p(n)$相當於 $P(x)$ 中 $x^n$ 的係數，也等於 $$\prod_{i=1}^n \frac{1}{(1-x^i)}$$ 中 $x^n$ 的係數，因為 $\prod_{i=n+1}^\infty \frac{1}{(1-x^i)}$ 的冪級數中除了常數1以外，其餘皆高於 $n$次。 此外，在問題討論中，如無特別註明， 整數分割都是各部分下限為1，且定義$p(0)=1$。

例 4.1: 試求5的「分割」方法總數。

解: 其對應的生成函數為 \begin{align} P(x)=\sum_{n=0}^\infty p(n) x^n=\prod_{i=1}^\infty \frac{1}{(1-x^i)} \label{eqnC:44903}的 \end{align} $p(5)$即上式展開式中 $x^5$ 項的係數。 根據觀察，從(\ref{eqnC:44903}) 前5個括弧中取以下數值時，相乘會得到$x^5$ 項: $$1\cdot 1\cdot 1\cdot 1\cdot x^5+ 1\cdot x^2\cdot x^3\cdot 1\cdot 1+ x\cdot 1\cdot 1\cdot x^4\cdot 1+ x\cdot x^4\cdot 1\cdot 1\cdot 1+ x^2\cdot 1\cdot x^3\cdot 1\cdot 1+ x^3\cdot x^2\cdot 1\cdot 1\cdot 1+ x^5\cdot 1\cdot 1\cdot 1\cdot 1$$ 由於以上7組數值的相乘結果均為 $x^5$, 所以上式展開式中 $x^5$ 項的係數是7，即 $p(5) = 7$, 5的分割方法數有7種。$\Box$

例 4.2: 證明將正整數分割成每一項不超過兩次以上的生成函數與正整數不被3整除的生成函數是相同的。

證明: 表因每一項不超過兩次以上的分項，因此令 $f(x)=\prod _{i=1}^\infty (1+x^i+x^{2i})$。若不被3整除則其生成函數可令 $g(x)=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^4} \frac{1}{1-x^5}\frac{1}{1-x^7}\cdots$。可以發現 \begin{align*} f(x)&=(1+x+x^2)(1+x^2+x^4)(1+x^3+x^6)(1+x^4+x^8)\cdots\\ &=\frac{1-x^3}{1-x}\frac{1-x^6}{1-x^2}\frac{1-x^9}{1-x^3} \frac{1-x^{12}}{1-x^4}\frac{1-x^{15}}{1-x^5}\frac{1-x^{18}}{1-x^6}\cdots\\ &=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^4} \frac{1}{1-x^5}\frac{1}{1-x^7}\cdots=g(x) \end{align*} 得證。$\Box$

接下來這個例子為限制條件時的整數有序分割。

例 4.3: ( 限制條件的整數分割) 求 $x_1+x_2+x_3=100, x_1\geq 0, x_2\geq 3, 0\leq x_3\leq 9$之整數解個數。

解: $x_1$ 可選取的個數為 $0,1,2,\ldots$, 其對應的生成函數為 $(1+x+x^2+\cdots)$; $x_2$ 可選取的個數為 $3,4,5,\ldots$, 其對應的生成函數為 $(x^3+x^4+x^5+\cdots)$; $x_3$ 可選取的個數為 $0,1,2,\ldots ,8,9$, 其對應的生成函數為 $(1+x+x^2+\cdots+x^8+x^9)$。 因此 $x_1+x_2+x_3=100$ 生成函數為 $A(x)=(1+x+x^2+\cdots)(x^3+x^4+x^5+\cdots)(1+x+x^2+\cdots+x^9)$, 欲求之整數解個數即為 $A(x)$ 中 $x^{100}$ 的係數 \begin{align*} A(x)&=\left(\frac{1}{1-x}\right)\left(\frac{x^3}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right) =(x^3-x^{13})\frac{1}{(1-x)^3}\\ &=(x^3-x^{13})\sum_{r=0}^\infty {3+r-1\choose r}x^r =\sum_{r=0}^\infty {r+2\choose r}x^{r+3}-\sum_{r=0}^\infty {r+2\choose r}x^{r+13} \end{align*} $x^{100}$ 的係數為 ${97+2\choose 97}-{87+2\choose 87}=935$。$\Box$

五. 遞迴關係式

解遞迴關係式有多種方法，其中生成函數是一個非常有效且系統化的方法。 生成函數可用來個別或是同時地解遞迴關係，這個技巧和用來解微分方程 的Laplace轉換法是類似的。 欲解一個 $k$ 階常係數的遞迴關係 $C_{k}a_{n+k}+\cdots+C_0 a_n =g(n),n\geq 0$， 可使用以下的步驟︰

1. 在遞迴關係式兩邊同乘上 $x^{n+k}$, 並加總其結果;
2. 得到此新的方程式，利用生成函數 $f(x)=\sum^{\infty}_{n=0}a_nx^n$ 的形式重新寫此方程式，並且解出 $f(x)$, 而當 $g(n)$ 是 $\{n^i\}, \{\lambda^n\},\{n^i \lambda^n\}, i=0,1,2,\ldots$ 的線性組合時， $f(x)$ 的解 為一有理多項式;
3. 利用分項分式展開，將 $f(x)$ 寫成$x$ 的冪級數，即可得到係數 $a_n$。

由下列例子說明如何由一般生成函數解出遞迴關係式的解。

例 5.1: 設遞迴關係式 $a_{n+1}-2a_n=1, n\geq 0 , a_0=0$, 利用生成函數法求 $a_n$。

解: 此遞迴關係式為一無窮多項的方程式集合 ，第$0$ 項為 $a_1-2a_0=1$, 第$1$ 項為 $a_2-2a_1=1$, 第$2$ 項為 $a_3-2a_2=1$, $\cdots$。 在第一式乘上 $x$, 第二式乘上 $x^2$, 以此類推，我們可以得到，第$0$ 項為 $a_1x-2a_0x=x$, 第$1$ 項為 $a_2x^2-2a_1x^2=x^2$, 第$2$ 項為 $a_3x^3-2a_2x^3=x^3$, $\cdots$。把上述的式子加起來可得 $$\sum_{n=1}^\infty a_n x^n -2\sum_{n=1}^\infty a_{n-1}x^n=\sum_{n=1}^\infty x^n$$ 設 $A(x)=\sum_{n=1}^\infty a_n x^n$, 所以遞迴關係式可寫成 $(A(x)-a_0)-2xA(x)=\frac{x}{1-x}$, 將起始條件$a_0=0$ 代入 $(A(x)-0)-2xA(x)=\frac{x}{1-x}$ ，經化簡後得 $A(x)=\frac{x}{(1-2x)(1-x)}$, 利用分項分式可得 \begin{align*} A(x)&=\frac{-1}{1-x}+\frac{1}{1-2x}=-\sum_{n=0}^\infty x^n+\sum_{n=0}^\infty (2x)^n= \sum_{n=0}^\infty (-1+2^n) x^n \end{align*}

即 $a_n=-1+2^n, n\geq 0$。$\Box$

再舉一個例子說明生成函數的用途，這個例子是費伯那西數列，在這要 強調倒不是數列本身，而是如何借助一般生成函數計算數列的指定項的值。

例 5.2: ( 費伯那西數列) 設 $F_n$ 滿足遞迴關係式 $F_{n+1}=F_n+F_{n-1}$, $n\geq 1$, $F_0=0$, $F_1=1$, 求 $F_n$ 的解。

解: 令 $$F(x)=\sum_{n\geq 0}F_n x^n$$ 將 $F_{n+1}=F_n+F_{n-1}$ 乘以 $x^{n+1}$ 且對 $n\geq 1$ 相加，左式得到 $$F_2 x^2+F_3 x^3+F_4 x^4+\cdots=F(x)-x$$ 右式得到 $$\left(F_1x^2+F_2x^3+F_3x^4+\cdots\right) + \left(F_0 x^2+F_1 x^3+F_2 x^4+\cdots\right) =x F(x)+ x^2 F(x)$$ 所以 $$F(x)-x =xF(x)+x^2F(x)$$ 我們可以得知此生成函數為 $$F(x)=\frac{x}{1-x-x^2}$$ 利用部份分式展開 $x/(1-x-x^2)$, 將會得到費伯那西的公式。 在此我們先分解二次因子，我們可以得到 $$1-x-x^2=(1-xr_+)(1-xr_-),\quad r_{\pm} =(1\pm \sqrt{5})/2$$ 所以 \begin{align*} \frac{x}{1-x-x^2}&=\frac{x}{(1-xr_+)(1-xr_-)}\\ &=\frac{1}{(r_+ -r_-)}\left(\frac{1}{1-xr_+}-\frac{1}{1-xr_-}\right)\\ &=\frac{1}{(r_+ - r_-)}\left\{\sum_{n=0}^\infty r^n_+ x^n- \sum_{n=0}^\infty r^n_-x^n \right\} \end{align*} 利用等比級數，我們可以很容易的辨認出 $x^n$ 的係數 $$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n -\left(\frac{1-\sqrt{5}}{2}\right)^n\right],\quad n=0,1,\ldots.{\Box} $$

註: 利用生成函數解常係數的遞迴關係式，會得到一個有理多項式的生成函數 $f(x)$, 要將 $f(x)$ 寫成冪級數時，分項分式(partial fraction)是一個不可或缺的工具。請參閱微積分課本。

六. 數列和與恆等式

利用一般生成函數計算數列和常見的方法可分為下列三種: 考慮

1. 二項式定理: $\{{n\choose k}\}_{k=0}^n$ 的生成函數
2. 生成函數的微分與積分
3. 摺積性質$f(x)g(x)$ 的一般生成函數，特別是求和算子 $g(x)=\frac{1}{1-x}$ (定理 2.2 (h))

例 6.1: ( 二項式定理求和) 設 $n$ 為自然數，計算

1. ${n\choose 0}+{n\choose 1}+{n\choose 2}+{n\choose 3}+\cdots+ {n\choose n}$
2. $\frac{1}{2}{n\choose 1}+\left(\frac{1}{2}\right)^2{n\choose 2}+ \left(\frac{1}{2}\right)^3{n\choose 3}+\left(\frac{1}{2}\right)^4 {n\choose 4}+\cdots+ \left(\frac{1}{2}\right)^n{n\choose n}$
3. ${n\choose 1}-{n\choose 3}+{n\choose 5}-{n\choose 7}+\cdots$
4. ${n\choose 0}-{n\choose 2}+{n\choose 4}-{n\choose 6}+\cdots$

解:

1. 考慮二項式定理 \begin{align} \sum_{k=0}^n {n\choose k}x^k=(1+x)^n\label{eqnC:66852} \end{align} 將 $x=1$ 代入得(\ref{eqnC:66852})$$\sum_{k=0}^n {n\choose k}=(1+1)^n=2^n$$
2. 將 $x=\frac{1}{2}$ 代入(\ref{eqnC:66852})得 $$\sum_{k=0}^n \left(\frac{1}{2}\right)^n{n\choose k}=\left(1+\frac{1}{2}\right)^n=\left(\frac{3}{2}\right)^n$$
3. 將 $x=i$ 代入(\ref{eqnC:66852})，右式為 \begin{align*} (1+i)^n &=\left(\sqrt{2}\left(\cos \left(\frac{\pi}{4}\right)+i \sin \left(\frac{\pi}{4}\right)\right)\right)^n\\ &=2^{n/2}\cos \left(\frac{n\pi}{4}\right)+i 2^{n/2}\sin \left(\frac{n\pi}{4}\right) \end{align*} 利用生二項式展開，左式為 \begin{align*} \sum_{k=0}^n {n\choose k}i^k &= \left[{n\choose 0}-{n\choose 2}+{n\choose 4}-{n\choose 6}+\cdots\right]\\ &\qquad +i\left[{n\choose 1}- {n\choose 3}+{n\choose 5}-{n\choose 7}+\cdots\right]\end{align*} 所以 ${n\choose 1}-{n\choose 3}+{n\choose 5}-{n\choose 7}+\cdots=2^{n/2}\sin \left(\frac{n\pi}{4}\right)$。
4. 由(c)小題知 ${n\choose 0}-{n\choose 2}+{n\choose 4}-{n\choose 6}+\cdots=2^{n/2}\cos \left(\frac{n\pi}{4}\right)$。 $\Box$

例 6.2: ( 自然數平方和) 依下列步驟求前 $n$ 個自然數的平方和:

1. 求數列 $0^2,1^2,2^2,\ldots$ 的生成函數。
2. 求數列 $0^2,0^2+1^2,0^2+1^2+2^2,\ldots$ 的生成函數。
3. 求 $0^2+1^2+2^2+\cdots+n^2$ 的公式。

解:

1. 由例 2.4 (d)得數列 $0^2,1^2,2^2,\ldots$ 的生成函數為 $\frac{(1+x)x}{(1-x)^3}$。
2. 因為 $\frac{(1+x)x}{(1-x)^3}$ 為數列 $0^2,1^2,2^2,\ldots$ 的生成函數，則 \begin{align*} \frac{(1+x)x}{(1-x)^3}\cdot\frac{1}{1-x}&= (0^2+1^2 x+2^2x^2+\cdots)(1+x+x^2+\cdots)\\ &=0^2+(0^2+1^2)x+(0^2+1^2+2^2)x^2+\cdots\\ &=\sum_{n=0}^\infty (0^2+1^2+2^2+\cdots+n^2)x^n \end{align*} 所以 $\frac{(1+x)x}{(1-x)^3}\cdot\frac{1}{1-x}$ 為數列 $0^2,0^2+1^2,0^2+1^2+2^2,\ldots$ 的生成函數。
3. $0^2+1^2+2^2+\cdots+n^2$相當於 $\frac{(1+x)x}{(1-x)^3}\cdot\frac{1}{1-x}$ 中 $x^n$ 的係數 \begin{align*} \frac{(1+x)x}{(1-x)^3}\cdot\frac{1}{1-x} &=\frac{x+x^2}{(1-x)^4}\\ &=(x+x^2)\sum_{r=0}^\infty {4+r-1\choose r}x^r\\ &=\sum_{r=0}^\infty {4+r-1\choose r}x^{r+1}+\sum_{r=0}^\infty {4+r-1\choose r}x^{r+2} \end{align*} $x^n$ 的係數為 \begin{align*} &\hskip -10pt {4+(n-1)-1\choose n-1}+{4-(n-2)-1\choose n-2}\\ &={n+2\choose n-1}+{n+1\choose n-2}=\frac{(n+2)!}{3!(n-1)!}+\frac{(n+1)!}{3!(n-2)!}\\ &=\frac{1}{6}[(n+2)(n+1)(n)+(n+1)(n)(n-1)]=\frac{n(n+1)(2n+1)}{6} \tag*{$\Box$} \end{align*}

例 6.3: ( 微分、積分求和) 試求

1. ${n\choose 1}+2{n\choose 2}+3{n\choose 3}+\cdots+n{n\choose n}$
2. $1+\frac{1}{2}{n \choose 1}+\frac{1}{3}{n\choose 2}+\cdots +\frac{1}{n+1}{n\choose n}$

解:

1. 考慮 \begin{align} \sum_{i=0}^n {n\choose i} x^i=(1+x)^n\label{eqnC:12886} \end{align} (\ref{eqnC:12886})兩邊對 $x$ 微分 $$\sum_{i=0}^n i{n\choose i} x^{i-1}=n(1+x)^{n-1}$$ $x=1$ 代入得 $$\sum_{i=0}^n i{n\choose i}=n2^{n-1}$$
2. (\ref{eqnC:12886})兩邊對 $x$ 積分 $$\sum_{i=0}^n {n\choose i} \frac{x^{i+1}}{i+1}=\frac{(1+x)^{n+1}}{n+1}+C$$ 當 $x=0$ 時, $C=\frac{-1}{(n+1)}$, 再將 $x=1$ 代入得 $$\sum_{i=0}^n {n\choose i}\frac{1}{i+1}=\frac{1}{n+1}\left(2^{n+1}-1\right){\Box} $$

例 6.4: 試求 $$\frac{1^2}{0!}+\frac{2^2}{1!}+\frac{3^2}{2!}+\frac{4^2}{3!}+\cdots$$

解: 考慮 $$e^x=\sum_{n=0}^\infty \frac{x^n}{n!}, \quad x\in \mathbb{R}$$ 兩邊同乘 $x$ 得 $$xe^x=\sum_{n=0}^\infty \frac{x^{n+1}}{n!}$$ 兩邊對 $x$ 微分$$(1+x)e^x=\sum_{n=0}^\infty \frac{(n+1)x^{n}}{n!}, \quad x\in \mathbb{R}$$ 兩邊同乘 $x$ 得 $$(x+x^2)e^x=\sum_{n=0}^\infty \frac{(n+1)x^{n+1}}{n!}$$ 兩邊對 $x$ 微分$$(1+3x+x^2)e^x=\sum_{n=0}^\infty \frac{(n+1)^2 x^{n}}{n!}, \quad x\in \mathbb{R}$$ $x=1$ 代入得 $$\sum_{n=0}^\infty \frac{(n+1)^2}{n!}=5e{\Box} $$

例 6.5: (積分求和) 試求無窮級數 $$1-\frac{1}{4}+\frac{1}{7}-\frac{1}{10}+\cdots$$

解: 已知$$\frac{1}{1+x^3}=1-x^3+x^6-x^9+\cdots, \quad |x|\lt 1$$ 兩邊對 $x$ 積分 \begin{align} \int_0^x\frac{dx}{1+x^3}=x-\frac{x^4}{4}+\frac{x^7}{7}-\frac{x^{10}}{10}+\cdots, \quad |x|\lt 1 \label{eqnC:33502} \end{align} 由交錯級數定理知當 $x=1$ 時 (\ref{eqnC:33502})右式收斂， 且將(\ref{eqnC:33502})左式進行分項分式及利用Abel's的極限定理得 \begin{align*} \int_0^x \frac{dx}{1+x^3} &=\frac{1}{3}\int_0^x \frac{1}{1+x}+\frac{2-x}{1-x+x^2}\,dx\\ &=\frac{1}{3}\int_0^x \frac{1}{1+x}+\frac{-\frac{1}{2}(2x-1)}{1-x+x^2}+\frac{\frac{3}{2}}{1-x+x^2}\,dx\\ &=\frac{1}{3} \left[\log \frac{1+x}{\sqrt{1-x+x^2}}+\sqrt{3} \left(\arctan \frac{2x-1}{\sqrt{3}}-\arctan\frac{-1}{\sqrt{3}}\right)\right] \end{align*} 因此此無窮級數和為 $$\frac{1}{3}\left(\log 2+\frac{\pi}{\sqrt{3}}\right){\Box} $$

例 6.6: ( 求和算子求和) 利用求和算子計算出 $\sum_{i=0}^n i(i-1)$ 的公式。

解: $\sum_{i=0}^n i(i-1)$ 為數列 $\{i(i-1)\}_{i=0}^\infty$ 的部分和， 令其生成函數為 $$f(x)=\sum_{i=0}^\infty i(i-1)x^i, \quad |x|\lt 1$$ 考慮 $\frac{1}{1-x}=\sum_{i=0}^\infty x^i$, 兩邊對 $x$ 微分二次得 $$\frac{2}{(1-x)^3}=\sum_{i=2}^\infty i(i-1)x^{i-2}, \quad |x|\lt 1$$ 兩邊同乘以 $x^2$ 得 $$\frac{2x^2}{(1-x)^3}=\sum_{i=2}^\infty i(i-1)x^i=\sum_{i=0}^\infty i(i-1)x^i, \quad |x|\lt 1$$因此可得 $f(x)=\frac{2x^2}{(1-x)^3}$。 利用求和算子知$\frac{2x^2}{(1-x)^3}\frac{1}{1-x}=\frac{2x^2}{(1-x)^4}$ 為數列 $\{\sum_{i=0}^n i(i-1)\}_{n=1}^\infty$ 的生成函數，利用二項式定理 \begin{align*} \frac{2x^2}{(1-x)^4}&=2x^2\sum_{r=0}^\infty {4+r-1\choose r}x^r\\ &=2\sum_{r=0}^\infty {r+3\choose 3}x^{r+2} \end{align*} 且 $\sum_{i=0}^n i(i-1)$ 為 $x^n$ 的係數，所以 \begin{align*} \sum_{i=0}^n i(i-1) &=\left[x^{n}\right]\frac{2x^2}{(1-x)^4}=2{n-2+3\choose 3} \\ &=2{n+1\choose 3}=\frac{1}{3}n(n+1)(n-1)\tag*{$\Box$} \end{align*}

接下來介紹如何利用生成函數來證明恆等式， 這裡的證明使用到廣義的二項式定理，下面的例子說明如何用生成函數來證明恆等式。

例 6.7: (Vandermonde's convolution) 設 $n,m\in{\mathbb N},r\in {\mathbb N}_0$, 利用生成函數證明下列等式 $$\sum_{i=0}^r{n\choose i}{m\choose r-i}={n+m\choose r}$$

解: $\{{n\choose 0},{n\choose 1},{n\choose 2},\ldots,{n\choose n},0,0,\ldots\}$ 對應的生成函數為 $f(x)\!=\!(1\!+\!x)^n\!=\!\sum_{i\!\geq\! 0}{n\choose i}x^i$。 同理, $\{{m\choose 0},{m\choose 1},{m\choose 2},\ldots,{m\choose m},0,0,\ldots\}$ 對應的生成函數為 $g(x)\!=\!(1\!+\!x)^m\!=\!\sum_{j\!\geq\!0}{m\choose j}x^j$。將 $f(x)$ 和 $g(x)$相乘得到 \begin{align*} f(x)g(x)&={n\choose 0}{m\choose 0}+\left[{n\choose 0}{m\choose 1}+{n\choose 1}{m\choose 0}\right]x \\ & \quad +\left[{n\choose 0}{m\choose 2}+{n\choose 1}{m\choose 1}+{n\choose 2}{m\choose 0}\right]x^2+\cdots\\ &=(1+x)^n(1+x)^m=(1+x)^{n+m} \end{align*} 觀察$x^r$ 的係數 \begin{align*} \sum_{i=0}^r{n\choose i}{m\choose r-i} &=[x^r]f(x)g(x)=[x^r](1+x)^n(1+x)^m\\ &=[x^r](1+x)^{n+m}={n+m\choose r}\tag*{$\Box$} \end{align*}

註: 當 $m=n,r=n$ 時，即可得著名的組合恆等式 $$ \sum_{i=0}^n{n\choose i}^2={2n\choose n}$$

下列是一些不錯的題目，也許讀者有興趣試試，為了方便讀者， 我們也將答案列入。

1. 求下列數列的一般生成函數 (答案: $\frac{x^2}{1-x^3}$) $$0,0,1,0,0,1,0,0,1,0,0,1, \ldots$$
2. 求下列數列的一般生成函數 (答案: $\frac{2x^2}{(1-x)^3}$) $$0,0,2,6,12,\ldots,k(k-1),\ldots$$
3. 求 $(x^7+x^8+x^9+\cdots)^6$ 中 $x^{50}$ 的係數。 (答案: ${13\choose 8}=1,287$)
4. 求 $\frac{1}{(x-3)(x-2)^2}$ 中 $x^8$ 的係數。 (答案: $-\left(\frac{1}{3}\right)^9-7\left(\frac{1}{2}\right)^{10}$)
5. 計算$\sum_{k=1}^n {n-1\choose k-1}{n\choose k}$。 (答案: ${2n-1\choose n-1}$)
6. 利用一般生成函數來解遞迴關係式: (答案: $\frac{1}{2}(10^n)+\frac{1}{2}(8^n)$) $$a_n=8a_{n-1}+10^{n-1},\quad n\ge 2,a_1=9$$
7. 利用一般生成函數解二階遞迴式 (答案: $(-1)\cdot 4^n+4\cdot 2^n$) $$a_n=6a_{n-1}-8a_{n-2},\quad n\ge 2,a_0=3,a_1=4 $$
8. 對於任一自然數 $n$, 令 $$S_n = \sum_{k=0}^n {(-1)^k \over 2k+1} {n\choose k} ={n\choose 0}-{1\over 3}{n\choose 1} +{1\over 5} {n\choose 2} -{1\over 7} {n\choose 3} +\cdots + {(-1)^n \over 2n+1} {n\choose n} $$ 證明: 對於所有自然數 $n$, $S_{n} = {4^n (n!)^2 \over (2n+1)!}$。
9. 證明 $$\sum_{k=0}^\infty \frac{1}{(k+2)k!}=1$$
10. 利用一般生成函數證明 $$\sum_{k=0}^\infty {n+k\choose k}\frac{1}{2^k}=2^{n+1}$$
11. 對任何正整數 $n$, 證明 \begin{eqnarray} \sum_{k=0}^{\left[\frac{n-1}{2}\right]} \left(\left(1-\frac{2k}{n}\right){n\choose k}\right)^2 =\frac{1}{n}{2n-2\choose n-1}\label{eqnC:98538} \end{eqnarray}這裡 $\left[\frac{n-1}{2}\right]$ 表示 $\frac{n-1}{2}$ 的整數部分。

參考文獻

---本文作者任教中山大學應用數學系---