計數問題(counting)

計數問題(counting)
國立高雄大學應用數學系游森棚副教授責任編輯

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

什麼是計數問題

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

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

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

更抽象一點來說，設有由一堆集合 $${S_n}$$ 所構成的集合族，其中足碼 $${n}$$ 跑遍某個集合 $${I}$$(通常是非負整數$$\mathbb{N}_0$$)，所謂的計數問題就是要找出計數函數

$${f}:{I} \longrightarrow \mathbb{N}_0$$

其中 $${f(n)} = {|S_n|}$$，在這個例子中，

$$\displaystyle{f(n)} = \frac{n^2+n+2}{2},~~{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(1- \frac{1}{1!}+ \frac{1}{2!}-\frac{1}{3!} +…+(-1)^{n}\frac{1}{n!})$$

這個式子不能再化簡了，我們也接受這是答案。

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),….=1, 0, 1, 2, 9, 44,….$$ 的指數形生成函數(exponential generating function) 定義為

$$\displaystyle 1+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!}+…+f(n)\frac{x^n}{n!}+…$$

透過高等數學的技巧，可以得到這個無窮級數恰好是

$$\displaystyle{\frac{1}{e^{x}(1-x)}}$$

的泰勒展開式。因此 $$f(n)$$ 就是把 $$\frac{1}{e^{x}(1-x)}$$ 作泰勒展開式後，求出 $$x^n$$ 的係數再乘上 $${n!}$$

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

5. 漸近公式.

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

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

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

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

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