[高瞻自然科學教育資源平台] 計數問題(counting)

國立高雄大學應用數學系游森棚副教授責任編輯

高中的排列組合主要是「計數(counting, enumeration)」，延伸到高等數學上就是稱為「計數組合(enuemrative combinatorics)」的數學分支。在這篇文章中我們介紹什麼是計數問題。

什麼是計數問題

計數問題說穿了就是「數數看有幾個」，如此而已。所有的理論，所有的公式，都只是要幫助我們算得比較快一點。

用數學的語言來說，一個計數問題就是要數一個有限集合的元素個數。例如：「平面上一般位置的四條直線(一般位置即任三線不共點) 把平面分成幾塊?」亦即， $S_4$ 表示平面上四條直線把平面分成的區域所成的集合，我們要數 $|S_4|$。高中的排列組合大概都停在這個層次，即給一個特殊的情境，我們要算滿足這個情境下的集合的元素個數，這個問題的答案是 $11$ 塊。

但是以數學的觀點來看，我們通常想要一勞永逸， 一次解決一整類問題：我們希望可以有一個函數 $|S_1|,|S_2|,\dots$ 都算出來。換句話說我們想要知道 $f(n)=|S_n|$ 的公式，即平面上一般位置的 $n$ 條直線可以把平面分成幾塊。

更抽象一點來說，設有由一堆集合 $S_n$ 所構成的集合族，其中足碼 $n$ 跑遍某個集合 $I$ (通常是非負整數 $\mathbb N_0$)，所謂的計數問題就是要找出計數函數 $f:I\to\mathbb N_0$ 其中 $f(n)=|S_n|$ ，在這個例子中為

$\displaystyle f(n)=\frac{n^2+n+2}2\quad\text{for}~n\in\mathbb N_0$.

什麼是答案

什麼是一個計數問題的答案？這個問題乍看之下很好笑—不就是數出來就好了嗎？非也，什麼樣的結果可以稱為「計數問題的答案」是值得討論的。

1. 封閉型式的公式(closed form).
一個計數問題，能得到 $f(n)$ 的封閉形式毫無疑問當然是答案。
比如上例，平面上一般位置的 $n$ 條直線可以把平面分成 $\displaystyle f(n)=\frac{n^2+n+2}2$ 塊。
2. 含有求和符號的公式.
但是計數問題並不總有封閉形式。比如，將 $n$ 封不同的信裝入 $n$ 個已寫好住址的信封，全部都裝錯的方法有幾種？這是錯列(derangement)問題，答案是

$\displaystyle f(n)=n\left(1−\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots+(−1)n\frac1{n!}\right).$

這個式子不能再化簡了，我們也接受這是答案。
3. 遞迴公式.
在錯列問題中，$f(n)$ 事實上滿足遞迴關係式

$f(n)=(n−1)(f(n−1)+f(n−2))$, $f(0)=1$, $f(1)=0$,

讀者覺得這個算不算答案？說實在，要求 $f(20)$，用遞迴式會比用求和式快，而且快許多！
4. 生成函數.
從這裡已經跨入高等數學了。我們一樣以錯列為例，錯列數列

$f(0),f(1),f(2),f(3),f(4),\dots.=1,0,1,2,9,44,\dots.$

的指數形生成函數(exponential generating function) 定義為

$\displaystyle1+0\cdot\frac x{1!}+1\cdot\frac{x^2}{2!}+2\cdot\frac{x^3}{3!}+9\cdot\frac{x^4}{4!}+44\cdot\frac{x^5}{5!}+\cdots+f(n)\frac{x^n}{n!}+\cdots$

透過高等數學的技巧，可以得到這個無窮級數恰好是 $\displaystyle\frac1{e^x(1−x)}$ 的泰勒展開式。因此 $f(n)$ 就是把 $\displaystyle\frac1{e^x(1−x)}$ 作泰勒展開式後，求出 $x^n$ 的係數再乘上 $n!$

在高階的計數組合中，數學家事實上是先想辦法求出計數問題的生成函數。神奇的是，只要有生成函數，則要得到遞迴公式(或是求和符號的公式, 或是封閉型式的公式) 都有一套公式化的方法！所以求生成函數變成計數組合的核心問題。在計數組合的研究中， 通常求得生成函數表示這個問題已經被解決了。按這個觀點來看，生成函數也是答案。

5. 漸近公式.
顧名思義，漸近公式只是近似值，所以它不是答案—畢竟計數問題我們感興趣的是正確值。但是，有時近似值傳達的訊息也許更直接也更多。在錯列問題中，顯然有

$\displaystyle f(n)\sim\frac{n!}e$.

這個式子非常清楚地告訴我們 $f(n)$ 的大小。以這個角度來看，漸近公式反而最直接。研究並尋找漸近公式也是組合學的一個研究分支，稱為分析組合學(analytic combinatorics)。

附帶一提，追根究底的讀者會問，那 $n!$ 到底多大？這也可以從漸近公式 $\displaystyle n!\sim\sqrt{2πn}\left(\frac ne\right)^n$ 看出來(這稱為Stirling 公式)。

綜上所述，相信讀者會對組合問題和其答案有一點初步的概念。下一篇文章中我們開始談計數組合的幾個基本原理。

※依科教中心的政策，在清楚標示作者與出處的前提下，以不營利的方式轉載分享。