close section ▶
1. 數數難嗎?
還沒上小學的孩子也曉得扳著指頭一個一個地數, 數數有何難? 但很多計數問題, 往往叫我們花好幾個鐘頭也數不出來答案, 而且很多時候並沒有一道具體公式作為答案, 讓我先來介紹一個化學上的例子。
飽和碳氫化合物由若干個碳原子和氫原子構成, 每個化學鍵都掛上應有的原子個數(碳的鍵是 4 價, 氫的鍵是1價), 就像第一個是甲烷 $CH_4$、下一個是乙烷 $C_2H_6$、再下一個是丙烷 $C_3H_8$, 餘類推(見圖1)。 化學上這一連串的化合物稱作烷烴序列。
首先, 讓我們探討一下, 如果烷烴有 $N$ 個碳原子, 它應該有多少個氫原子呢? 不妨這樣形象地描述, 碳原子是一位只伸出手4次的``權貴'', 而且``權貴''之間不願意通過握手搞小圈子; 氫原子是只能伸出手 1次的``趨炎附勢之徒''。``權貴''們自相結識, 組成一個集團(見圖2), ``趨炎附勢之徒''便爭相上前握``權貴''伸出的手。
$N$ 個``權貴''共伸出手 $4N$ 次, 其中 $2(N-1)$ 次用於互相之間握手(為什麼? ), 餘下的 $4N-2(N-1)=2N+2$ 次伸出的手, 馬上吸引了 $2N+2$ 個``趨炎附勢之徒''。因此, 烷烴的化學結構式是 $C_NH_{2N+2}$。雖然化學結構式是確定了, 但化合物的性質卻因碳原子的組合方式不相同而有異, 化學上這種現象稱作同分異構, 就像丁烷有兩種(見圖3), 化學結構式都是 $C_4H_{10}$, 性質卻不相同。
一個自然的提問是: $C_NH_{2N+2}$ 有多少個同分異構體? 這個問題在三十年代給解決了, 運用到的數學比較複雜, 不能在這兒敘述(有興趣的讀者可參看: 蕭文強, 「波利亞計數定理」, 湖南教育出版社, 1991), 答案在下面的表可窺一斑(見圖4)。要注意的是, 沒有一條具體公式直接給出 $C_NH_{2N+2}$ 同分異構體的數目 $A(N)$, 卻有方法計算 $A(N)$, 涉及的數學知識可不少呢!
| $N$ | $A(N)$ |
| 1 2 3 4 5 6 7 8 9 10 | 1 1 1 2 3 5 9 18 35 75 |
由此看來, 數數不容易。唯其如此數數極富挑戰, 而且引人入勝, 讓我們從最簡單的情況開始談吧。
公元前8世紀希臘詩人HOMER 留給後世兩首史詩, 其中一首名為 ODYSSEY, 敘述希臘城邦主之一的英雄人物 ULYSSES 經歷特洛戰爭後漂流異域歷盡十年艱辛的經過。 有一次他去到某個島被獨眼巨人擒獲, 終於用計把巨人的唯一眼睛弄瞎了方能脫險。 據說可憐的巨人以後只好靠數小石塊牧羊, 每天早上守在山洞口, 每當一頭羊經過時便執起一塊石, 等到黃昏羊群回來又守在山洞口, 每當一頭羊經過便放下一塊石。如果早上執起的小石塊剛好放完, 他便知道一頭羊也沒有走失了。 這大抵是民間傳說中最早關於數學上稱作一一對應這個概念的記載!
數數的理論根據就是一一對應。於有限集而言, 我們可能不容易體會這個概念的重要, 因為我們已經非常熟悉 1、2、3 $\cdots$ 這些數字了。 (要是想深一層, 1、2、3 $\ldots$ 其實是相當抽象的東西, 沒有一一對應這個概念是解釋不來的! ) 於無限集而言, 一一對應是無限集理論的基石, 由此而得的基數概念, 成為十九世紀後期由德國數學家 CANTOR 發展起來的集合論的中心概念。在這篇文章裡我們只討論有限集, 不過一一對應仍然大有用武之地。讓我舉一個例子來說明, 這個例子用到的技巧, 在後面還要再用到的。
例子(多邊形對角線的交點數目):
在凸多邊形內, 對角線在多邊形內相交多少次呢? (假設沒有三條對角線共點)(見圖5) 不難知道 $N$ 邊形有 $N(N-3)/2$ 條對角線(為什麼? ), 如果任何兩條都相交便好辦。可惜從圖中可以見到它們有時相交於多邊形外面, 有時說不定平行不相交, 那怎辦呢? 注意, 從 $N$ 個端點中任取 4點, 它們是某個凸四邊形的端點(試證明之), 它的兩條對角線相交於四邊形內, 也就是在 $N$ 邊形內。反之, 任何兩條原來 $N$ 邊形的對角線在 $N$ 邊形內的交點, 都可以這樣得來, 而且那是個一一對應。 結論是: 對角線在凸多邊形內交點, 與四個端點組成 的凸四邊形有一一對應。要計算對角線在凸 $N$ 邊形內的交點數目, 只用計算從 $N$ 點中任取4點的組合數目, 記號寫作 ${N\choose 4}=N(N-1)(N-2)(N-3)/24$。
2. 組合數目
上一節結束前用的例子, 涉及一項經常碰上的組合數目, 現在就讓我們看一看從 $N$ 個元中取出 $r$ 個不同元的組合數目。這個問題的答案, 在中國在西方均有悠久歷史, 十三世紀宋元的書本裡載有乘方圖, 說明源於古法 (北宋賈憲的立成釋鎖算法, 時約公元 1020年), 用以解代數方程或開高次方。 十七世紀中葉法國數學家 PASCAL 創立的算術三角形, 用以計算概率問題, 在一百多年前已經有西歐數學家提過, 而且也就是賈憲提出來的乘方圖, 以下我沿用 PASCAL 的記法(見圖6)。圖中第 $N$ 行第 $r$ 列出現的數字記作 $C(N,r)$ 或 ${N\choose r}$, 表示從 $N$ 元中取出 $r$ 不同元的組合數目。這個數字可以用 $N$ 和 $r$ 表出, 就是 $${N(N\!-\!1)\cdots(N\!-\!r\!+\!1)\over r(r-1)\cdots (3)(2)(1)}\!=\!{N!\over r!(N-r)!},$$ 這兒的 $n!$ 是 $n$ 的階乘, 即是 $1\times 2\times \cdots (n-1)\times n$, 並約定 $0!=1$。雖然大家都一定熟悉這道 $C(N,r)$ 的公式, 容許我在這裡重複解釋一遍, 也好藉此介紹兩條數數的基本原理。
\begin{eqnarray*} 0&1\\ 1&1&1\\ 2&1&2&1\\ 3&1&3&3&1\\ 4&1&4&6 &4 &1 \\ 5&1&5&10&10&5 &1&\quad & & & &r\\ 6&1&6&15&20&15&6 &1&\quad& & &\vdots\\ 7&1&7&21&35&35&21&7&1&\quad& &\vdots\\ 8&1&8&28&56&70&56&28&8&1&\quad &\vdots\\ \vdots& & & & & & & & & & &\vdots\\ N&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot& \cdot&\cdot&{N\choose r}\\ \end{eqnarray*}圖 6
(1) 加法原理: 實現一個事件, 如果能分成兩類方式, 彼此互不相同, 並且按第一類方式有 $m$ 種實現該事件的辦法, 按第二類方式有 $n$ 種實現該事件的辦法, 那麼以這兩類方式實現這個事件共有 $m+n$ 種辦法。例如數學營參加者有 50 名學生來自甲校, 100 名 學生來自乙校, 有幾種辦法從當中選出一名學生擔任營長呢? 答案是 $50+100=150$, 因為不會有學生既來自甲校又來自乙校。
(2) 乘法原理: 實現一個事件, 如果能分成兩個階段, 彼此互無相干, 並且知道實現第一階段有 $m$ 種辦法, 實現第二階段有 $n$ 種辦法, 那麼通過這兩個階段實現這個事件共有 $mn$ 種辦法。例如雪糕店售三款雪糕球。有巧克力(C)、 草莓(S)和香草(V), 兩球相疊的雪糕筒共有多少種呢? 答案是 $3\times 3=9$。 注意, 如果你討厭上下兩球都是 $V$, 便只有8種。 乘法原理不適用, 是因為兩個階段變成互有相干了。要得出答案, 可有兩種思路。 其一是先用乘法原理得出9種, 排除兩球俱為 $V$ 的一種, 即是8種。其二是混合使用加法原理及乘法原理, 第一類方式分成以下兩個階段: 先放下面一球, 只能是 $C$ 或 $S$, 再放上面一球, 不加限制; 第二類方式分成以下兩個階段: 先放下面一球, 限定是 $V$, 再放上面一球, 只能是 $C$ 或 $S$。 從乘法原理知道第一類方式有 $2\times 3=6$ 種辦法, 第二類方式有 $1\times 2=2$ 種辦法, 再從加法原理知道合起來有 $6+2=8$ 種辦法。
不難明白加法原理和乘法原理可以擴展至多於兩類方式或多於兩個階段的情況。 運用推廣的乘法原理便計算得到從 $N$ 元中取出 $r$ 不同元的排列數目, 記作 $P(N,r)$, 即是 $N(N-1)\cdots (N-r+1)={N!\over (N-r)!}$。 運用推廣的加法原理知道 $P(r,r)+\cdots +P(r,r)$ (共 $C(N,r)$ 項) $=P(N,r)$, 因此 $$C(N,r)\!=\!{P(N,r)\over P(r,r)}\!=\!{N!\over r!(N-r)!}\hbox{。}$$
3. 球罐模型
很多數數問題都能套進一種球罐模型作考慮, 讓我在這一節簡單地介紹一下。把 $r$ 個球放進 $N$ 個有標號的罐(圖 7), 共有多少種方法呢?
我們必須弄清楚幾種不同的情況。
(甲) 球可辨認(譬如說, 把球也標號), 每個罐頂多只能放一個球。那麼, 放球方法的數目等於從 $N$ 元中取出 $r$ 不同元的排列數目, 即是 $P(N,r)$。 比方 $N=4$, $r=2$, 把標號是1的球放在標號是2的罐、標號是2的球放在標號是4 的罐, 這種方法相當於排列 $(2,4)$ (見圖 7)。
(乙) 球不可辨認(譬如說, 全部塗以紅漆油!), 每個罐頂多只能放一個球。那麼, 放球方法的數目等於從 $N$ 元中取出 $r$ 不同元的組合數目, 即是 $C(N,r)$。比方 $N=4$, $r=2$, 把兩個球分別放在標號是2和4的罐, 這種方法相當於組合 $\{2,4\}$。
(丙) 球可辨認, 每個罐容許放多於一個球。那麼, 放球方法的數目等於從 $N$ 元中取出 $r$ 元(選取可重複)的排列數目。運用乘法原理, 不難知道答案是 $N^r$。比方 $N=4$, $r=2$, 把標號是1和2的球都放在標號是 3的罐, 這種方法相當於排列 $(3,3)$。
(丁) 球不可辨認, 每個罐容許放多於一個球。那麼, 放球方法的數目等於從 $N$ 元中取出 $r$ 元(選取可重複)的組合數目。比方 $N=4$, $r=2$, 把兩個球都放在標號是3的罐, 這種方法相當於組合 $\{3,3\}$。
上面(甲)、(乙)和(丙)的情況, 答案分別是 $P(N,r)$、$C(N,r)$ 和 $N^r$, 但(丁)的情況怎樣數呢? 就拿 $N=4$, $r=2$ 為例, (甲)有12種方法, (乙)有6 種方法, (丙)有16種方法(試臚列每種情況的全部方法), 而(丁)應有10 種方法, 即是: $$\{1,1\},\{1,2\},\{1,3\},\{1,4\},\{2,2\}$$ $$\{2,3\},\{2,4\},\{3,3\},\{3,4\},\{4,4\}\hbox{。}$$ 如何從 $N=4$ 和 $r=2$ 得到答案是10呢? 讓我們用以下的詮釋看看。設標號是 $i$ 的罐有 $r_i$ 個球, 則 $r_1+\cdots+r_N=r$, 我們要計算的是上式有多少個不同的解 $(r_1,\ldots,r_N)$, 其中 $r_i$ 是非負整數。比方 $N=6$, $r=5$, $(1,2,0,2,0,0)$ 是一個解, 表示標號是1的罐有1個球、標號是2和4的罐各有2個球, 其餘罐沒有球(見圖8)。上述的放球方法亦可簡化為點與豎杆的組合, 把5條豎杆插放於5點之間(見圖8)。由於放球方法與插放豎杆方法有一一對應, 我們只用計算插放豎杆方法的數目。 $r$ 個點和 $N-1$ 條豎杆(分隔成 $N$ 個罐)合成 $r+N-1$ 個位置, 從中選取 $r$ 個作為點的位置, 方法數目即是 $C(r+N-1,r)$, 也就是(丁)的情況的答案了。
以上的四種球罐模型運用到物理學上, 有它的物理意義。 把球看作是粒子, 把罐看作是能量級, 則每個放球方法代表一個宏觀狀態。 在近代量子力學猶未發展的時候, 十九世紀末的物理學家以為粒子是可分辨的, 而且以為多於一個粒子可以處於同一能量級, 因此計算宏觀狀態按照(丙) 的情況分佈, 稱作 MAXWELL-BOLTZMANN 統計法則, 但與實驗觀測不符。後來量子力學發展了, 物理學家知道粒子不可分辨, 計算宏觀狀態便按照(丁)的情況分佈, 稱作 BOSE-EINSTEIN 統計法則, 這與光子、 $\pi$ - 介子等的實驗觀測吻合, 卻與某些粒子 (如質子、電子、中子等) 的實驗觀測不符。再後來物理學家發現那一類粒子服從``PAULI 不相容原理'', 即是說不能有多於一個粒子處於同一能量級, 所以計算宏觀狀態應該按照(乙)的情況分佈, 稱作 FERMI-DIRAC 統計法則。
4. 一勞永逸的數數
在這一節我將採用另一種方式解釋上一節(丁)的情況的公式 $C(N+r-1,r)$, 並藉此介紹一種有力的數數工具。讓我先以一個較簡單的例子帶出中心思想: 設有1紅球、2綠球和3白球, 從中取出4個球, 共有多少種選法? 有秩序地臚列全部情況也不難, 就是
$\ WWWR,WWWG,WWRG,WWGG$, $WRGG$,
共有5種選法($R$代表紅球、$G$代表綠球、$W$代表白球)。 但假如繼續問下去: 從中取出3個球, 共有多少種選法? 從中取出5個球, 共有多少種選法? $\cdots$ 每次都重新臚列去數, 你感到厭煩嗎? 有沒有一勞永逸的方法呢?
| $$\square$$ | ${\bigcirc \!\!\!\!\!{_{^R}}}$ | $\square$ | ${\bigcirc \!\!\!\!\!{_{^G}}}$ | ${\bigcirc \!\!\!\!\!{_{^G}}}$ ${\bigcirc \!\!\!\!\!{_{^G}}}$ | $\square$ | ${\bigcirc \!\!\!\!\!{_{^W}}}$ | ${\bigcirc \!\!\!\!\!{_{^W}}}$ ${\bigcirc \!\!\!\!\!{_{^W}}}$ | ${\bigcirc \!\!\!\!\!{_{^W}}}$ ${\bigcirc \!\!\!\!\!{_{^W}}}$ ${\bigcirc \!\!\!\!\!{_{^W}}}$ |
| $-$ | $\surd$ | $\surd$ | $-$ | $-$ | $-$ | $-$ | $-$ | $\surd$ |
| $\surd$ | $-$ | $-$ | $\surd$ | $-$ | $-$ | $-$ | $-$ | $\surd$ |
| $-$ | $\surd$ | $-$ | $\surd$ | $-$ | $-$ | $-$ | $\surd$ | $-$ |
| $\surd$ | $-$ | $-$ | $-$ | $\surd$ | $-$ | $-$ | $\surd$ | $-$ |
| $-$ | $\surd$ | $-$ | $-$ | $\surd$ | $-$ | $\surd$ | $-$ | $-$ |
讓我們重新看看取出4個球的情況, 並且以圖表描繪 (見圖9), 同時我們也以圖表描繪另一個驟看似是無關的情況, 就是 $z^4$ 如何在式子 $$(1+z)(1+z+z^2)(1+z+z^2+z^3)$$ 中出現的情況(見圖10)。這兩種情況的相似, 並非是巧合, 讀者只要玩味一下, 便知道為什麼如此。原來取 $r$ 個球的選法數目即是 $z^r$ 在 $(1+z)(1+z+z^2)(1+z+z^2+z^3)$ 中的系數。 把式展開, 得 $1+3z+5z^2+6z^3+5z^4+3z^5+z^6$, 於是取 $r$ 個球的選法數目全部出現了。即使我們不把式展開, 還是能從中獲取某些資料。 譬如問全部選法數目(不論取多少個球)是多少, 在上式把 $z$ 置作 1 馬上得到答案是 $(1+1)(1+1+1)(1+1+1+1)=2\times 3\times 4=24$ (為什麼要把 $z$ 置作 1 呢?)
| $1\!+\!z$ | $1\!+\!z\!+\!z^2$ | $1\!+\!z\!+\!z^2\!+\!z^3$ |
| $-$$\surd$ | $\surd$$-$$-$ | $-$$-$$-$$\surd$ |
| $\surd$$-$ | $-$$\surd$$-$ | $-$$-$$-$$\surd$ |
| $-$$\surd$ | $-$$\surd$$-$ | $-$$-$$\surd$$-$ |
| $\surd$$-$ | $-$$-$$\surd$ | $-$$-$$\surd$$-$ |
| $-$$\surd$ | $-$$-$$\surd$ | $-$$\surd$$-$$-$ |
上面的式 $(1+z)(1+z+z^2)(1+z+z^2+z^3)=1+3z+5z^2+6z^3+5z^4+3z^5+z^6$ 叫做那一個計數問題的生成函數 (也稱作母函數), 意思是指該問題的答案已具見於函數當中。更一般地, 設有一序列 $(a_0,a_1,a_2,\ldots)$, 另一種記法是寫作形式冪級數 $$f(z)=a_0+a_1z+a_2z^2+\cdots\ \hbox{。}$$
所謂 ``形式'' 就是叫我們不必擔心那個 ``$\cdots$'' 部份, 不妨把 $f(z)$ 看作是一個多項式函數, 只不過它有很多很多項! 懂得高等數學的朋友自然不滿意這種說法, 因為冪級數若是無窮, 便要涉及收歛問題, 否則連定義亦成疑問。 為此緣故我們把這種冪級數稱作形式冪級數, 暫時拋開收歛性討論, 所有四則運算也是形式的。舉一個例子, 因為 \begin{eqnarray*} &&(1-z)(1+z+z^2+z^3+\cdots)\\ \!\!&\!\!=\!\!&\!\! 1+z+z^2+z^3+\cdots \\ &&-z-z^2-z^3-\cdots=1 \end{eqnarray*} 便有 $1/(1-z)=1+z+z^2+z^3+\cdots$。(懂高等數學的朋友也大可放心, 因為他們也知道只要存在某 $z_0$ 使無窮級數 $f(z_0)$ 收歛, 則在任意閉區間 $[-\alpha,\alpha]$ 上, $0\lt \alpha\lt |z_0|$, $f(z)$ 是均勻收歛且絕對收歛的, 隨之而來是不少關於 $f(z)$ 的良好性質了。)我們把 $f(z)$ 稱作序列 $(a_0,a_1,a_2,\ldots)$ 的生成函數。
往往 $a_r$ 是某些涉及 $r$ 的計數問題的答案, 或者是某些與 $r$ 有關的問題的答案, 於是 $f(z)$ 也就稱作那個問題的生成函數。驟看去那似乎於事無補, 例如 $$2z\!+\!3z^2\!+\!5z^3\!+\!7z^4\!+\!11z^5\!+\!13z^6\!+\!17z^7\!+\!\cdots$$ 是第 $r$ 個質數的生成函數, 我們望著它亦束手無策! 不過, 有時生成函數卻幫忙很大, 就像剛才的例子, 在1紅球、2綠球和3白球中取 $r$ 個球的選法, 它的生成函數樣子很簡單, 就是 $f(z)\!=\!(1+z)(1+z+z^2)(1+z+z^2+z^3)$。 按照類似思路, 我們能回到上一節(丁)的情況。設 $a_r$ 是從 $N$ 元中取出 $r$ 元(選取可重複)的組合數目, 也即是把 $r$ 個不可辨認的球放在 $N$ 個有標號的罐的放球方法數目, 那麼 $(a_0,a_1,a_2,\ldots)$ 的生成函數就是 $(1+z+z^2+\cdots)^N$, 或者說 $a_r$ 就是 $z^r$在 $(1+z+z^2+\cdots)^N$ 的係數。怎樣由此計算得 $a_r$ 呢? 注意 $1+z+z^2+\cdots=1/(1-z)$ (形式地! ), 因此該生成函數也可以寫作 $(1-z)^{-N}$。到了這地步我們要引入一條二項定理的推廣(不證明了, 當中涉及高等數學的知識, 這兒只旨在介紹生成函數如何把數數與高等數學分析拉在一起吧), 就是把大家熟悉的 $$(1\!+\!z)^N\!=\!\sum_{r=0}^NC(N,r)z^r\quad (N \hbox{是非負整數)}$$ 寫成 $$(1+z)^N=\sum_{r=0}^NC(N,r)z^r,$$ 這兒的 $N$ 可以是任何實數, $C(N,r)$ 指 $$N(N-1)(N-2)\cdots(N-r+1)/r!\hbox{。}$$ 特別地, 對正數 $N$, \begin{eqnarray*} C(\!-N,r) \!\!&\!\!=\!\!&\!\!(\!-N)(\!-N\!-\!1)(\!-N\!-\!2)\cdots\\ &&\qquad \cdot (-N-r+1)/r!\\ \!\!&\!\!=\!\!&\!\!(\!-1)^rN(N\!+\!1)(N\!+\!2)\cdots\\ &&\qquad\cdot (N+r-1)/r!\\ \!\!&\!\!=\!\!&\!\!(-1)^rC(N+r-1,r)\hbox{。} \end{eqnarray*} 因此, $z^r$ 在 $$(1-z)^{-N}=\sum_{r=0}^\infty (-1)^r C(-N,r)z^r$$ 的係數是 $C(N+r-1,r)$, 這也就是 $a_r$ 了, 與上一節得到的答案相符。
5. 一個例子
讓我再舉一個例子以顯示生成函數的用途, 為了不涉及高等數學知識, 這個例子只能展示冰山的一角而已! 這個例子是大家都熟悉的 FIBONACCI 序列, 不過在這兒我要強調倒不是序列本身, 而是如何借助生成函數計算序列的指定項的值。
大家都曾聽過 FIBONACCI 序列得名由來, 是意大利數學家 FIBONACCI 在十三世紀初提出這樣的問題: 假定一對雌雄兔子每月產下一對雌雄兔子, 每對出世後過一個月便可繁殖, 又假定沒有兔子死掉, 那麼從一對雌雄兔子開始, 一年內繁殖多少對呢? 答案是377, 如果 $a_n$ 是第 $n$ 個月開始時候的兔子對數目, 則 $a_1=1$, $a_2=2$, 對 $n\ge 2$ 有 $a_{n+1}=a_n+a_{n-1}$ (為什麼? )。有時為了方便, 我們添加一項 $a_0=1$, 上述的遞歸關係仍然成立, 蓋 $a_2=a_1+a_0$。 序列 $(a_0,a_1,a_2,\ldots)$ 叫做 FIBONACCI 序列, 它在很多場合都出現, 有時簡直叫人意想不到, 原因 就是遞歸關係 $a_{n+1}=a_n+a_{n-1}$ 是經常出現的關係式。
現在要問的是: $a_{30}$ 是什麼? 固然, 你可以從 $a_0=1$、$a_1=1$ 開始逐個 $a_n$ 算下去, 總能算出 $a_{30}$, 但那是需要花不少工夫和時間的。譬如再問 $a_{1997}$ 是什麼? 那就更花工夫和時間了, 而且即使你有如此 耐心和時間, 你不久即發現隨著 $n$ 增大, $a_n$ 增大的速度是頗驚人的! 有沒有更有效的計算方法呢?
先寫下 FIBONACCI 序列的生成函數
$A(z)=a_0+a_1z+a_2z^2+a_3z^3+\cdots$ 於是有 $zA(z)=\hskip 12pt a_0z+a_1z^2+a_2z^3+\cdots$ 和$z^2A(z)=\hskip 37pt a_0z^2+a_1z^3+\cdots$。
把三者加減起來, 便有 $A(z)-zA(z)-z^2A(z)=a_0+a_1z-a_0z+0+0+\cdots =a_0+a_1z-a_0=1+z-z=1$, 於是得 $A(z)=1/(1-z-z^2)$。如今要設法把這個簡單式子展開成冪級數, 從而計算 $a_n$ 的值。懂得部分分式的讀者自然知道如何辦, 那是一套標準手法; 不懂得部分分式的讀者只好暫時接受下面看來近似弄魔術的手法, 但計算還是屬於初等數學範圍。首先, $1-z-z^2=(1-\alpha_1z)(1-\alpha_2 z)$, 其中 $\alpha_1={1\over 2}(1+\sqrt{5})$、$\alpha_2=(1-\sqrt 5)$。 因此, \begin{eqnarray*} &&{1\over 1-z-z^2}= {1\over (1-\alpha_1z)(1-\alpha_2z)}\\ \!\!&\!\!=\!\!&\!\!{-\Big({\alpha_1\over \alpha_2-\alpha_1}\Big)\over (1-\alpha_1z)} +{\Big({\alpha_2\over \alpha_2-\alpha_1}\Big)\over (1-\alpha_2z)}\\ \!\!&\!\!=\!\!&\!\!-\Big({\alpha_1\over \alpha_2-\alpha_1}\Big)\Big(1+\alpha_1z+\alpha_1^2z^2+\ldots\Big)\\ &&+\Big({\alpha_2\over \alpha_2-\alpha_1}\Big)\Big(1+\alpha_2z+\alpha_2^2z^2+\ldots\Big)\\ \!\!&\!\!=\!\!&\!\!1+\Big({\alpha_2^2\!-\!\alpha_1^2\over \alpha_2\!-\!\alpha_1}\Big)z\!+\!\Big({\alpha_2^3\!-\!\alpha_1^3\over \alpha_2-\alpha_1}\Big)z^2\!+\!\ldots\\ \!\!&\!\!=\!\!&\!\!1+{1\over \sqrt 5}\Big[\Big(\alpha_1^2-\alpha_2^2\Big)z+\Big(\alpha_1^3-\alpha_2^3\Big)z^2\\ &&+\ldots\Big]\hbox{。} \end{eqnarray*} 比較係數即得 $a_0=1,$ $$a_n={1\over \sqrt 5}\Big[\Big({1+\sqrt 5\over 2}\Big)^{n+1}-\Big({1-\sqrt 5\over 2}\Big)^{n+1}\Big]$$ $(n\ge 1)\hbox{。}$ 以上這種答案早在 1765年已由瑞士數學家 EULER 提出來, 但大家忘掉了或者不知道, 到了1843年又由法國數學家 BINET 重新發現。讀者或者會提出疑問, $a_n$ 應該是個整數, 但用計算機計算右邊的式, 往往得到不是一個整數(那是由於 $\sqrt 5$ 是個無理數, 計算過程當中出現捨入誤差的緣故), 如何判定答案是什麼呢? 巧妙的地方就是在這裡, 運用生成函數我們得到一個近似答案, 但我們將要從這個近似答案抽取精確答案來! 置 $\phi=\alpha_1$, 則 $\phi'=-1/\phi=\alpha_2$, 注意 $\phi\gt 1$, $|\phi'|\lt 1$, 所以 $a_n={1\over \sqrt 5}(\phi^{n+1}-{\phi'}^ {n+1})\sim {1\over \sqrt 5}\phi^{n+1}$。其實, 我們能弄得更清楚, 只用注意對 $n\ge 0$, $|{\phi'}^{n+1}/\sqrt 5|\lt {1\over 2}$ (為什麼? ), 便不難明白 $a_n$ 是最接近 ${1\over \sqrt 5}\phi^{n+1}$ 的整數了(試分析誤差 ${1\over \sqrt 5}{\phi'}^{n+1}$ 與主要部份 ${1\over \sqrt 5}\phi^{n+1}$ 的關係, 先討論 $n$ 是偶數的情況, 再討論 $n$ 是奇數的情況)。例如 ${1\over \sqrt 5}\phi^{31}=1346268.9\cdots$, 因此 $a_{30}=1346269$, 這個答案只用花數秒按袖珍計算器的幾隻鍵就得出, 比起從 $a_0$、$a_1$ 逐個 $a_n$ 加 30 次自是輕鬆快捷多了! 至於 $a_{1997}$ 也可依循同樣方法計算, 只不過它的數值太大, 以目前計算機的能耐也不能把全部數字顯示出來, 我們只好滿足於一個近似值, $a_{1997}$ 是最接近 ${1\over \sqrt 5}\phi^{1998}$ 的整數, 約是 $1.61369040729\times 10^{417}$。
6. 結語
面對一個計數問題, 大家各師各法, 並沒有一種或兩種現成的方法即套即用。 不過, 在悠久的奮鬥過程當中, 數學家也發展了一些一般的法寶, 有效地用來對付一大類一大類的計數問題。這篇小文要介紹的只是其中一項, 即是生成函數, 但考慮到有些高中小讀者的準備知識 (原文是為香港教育署輔導視學處數學組舉辦的數學營的講座而寫成, 對象乃中學四年級生), 只能點到即止, 未能進一步討論連續分析與離散計算之間的互動關係。儘管如此, 我希望讀者還是可以在這樣一個初步敘述當中見到數學上各領域之間``和衷共濟''!
---本文作者任教於香港大學數學系---