生成函數 (I)

最近在閱讀 Flajolet 與 Sedgewick 的 解析組合學 Analytic Combinatorics。由於這裡面提到的技巧實在太威了，決定將讀書心得以 Blog 的形式紀錄下來。

• 什麼是解析組合學
• 交錯排列
  • 定義：《交錯排列》
  • 解法：$E_5$
  • 通解：André’s theorem
• 生成函數
  • 定義：《生成函數》
  • 例子：二項式係數
  • 例子：取球問題
    • 解法
  • 取出某一項的係數還是很難
• 動差生成函數

---

什麼是解析組合學

解析組合學這個名詞乍聽之下略帶違和感，因為分析（解析）和組合這兩個學問好像不太有交集。我們來看看這兩個數學中的分支：

• 分析學，如同我們學的微積分，主要是探討可微函數、解析函數、連續與極限等問題。
• 組合學，如同中學的排列組合，包含圖論等，是離散數學的領域。

換句話說，我們竟然可以用微積分這種連續的手段來解決離散數學問題，這便是 Analytic Combinatorics 讓人著迷之處。

---

交錯排列

在序章中，作者介紹了中學見過的波浪數問題，或者是交錯排列問題

定義：《交錯排列》

所謂 $n$ 階交錯排列（Alternating Permutation）是指：將 $1, 2, ..., n$ 等數字排列，排列的方式必須依照

• 第二個數大於第一個數
• 第三個數小於第二個數
• 第四個數大於第三個數
• …（以此類推）

而 $n$ 階交錯排列的方法數記為（$E_n$）。

我們在這裡的問題就是：

給定 $n$ ，請問 $E_n$ 為多少？

解法：$E_5$

階數不大時解法也不會太困難，用中學的手法分情況討論即可得出答案。以 $E_5$ 為例：

第二、四項可能為較大的 5 或 4，而剩下的第一、三、五項則為 1, 2, 3，有 $2!\times 3! = 12$ 種可能

也有可能 4 在首或尾處並緊鄰 5，則剩下三個數只要 3 在 1, 2 中間即可，有 $2 \times 2! = 4$ 種可能，前面的 2 是選擇 (4, 5, _ , _ , _ ) 或 ( _ , _ , _ , 5, 4)，後面的 $2!$ 是討論剩下的三個位置可能是 (1, 3, 2) 或 (2, 3, 1)。

故 $E_5 = 2!\times 3! + 2 \times 2! = 16$

但是當 $n$ 過大時，我們便缺乏適當的手段來處理這個問題了。在此，這本書的作者指出了一個極為巧妙的事實：

通解：André’s theorem

有一位數學家 André 證明了這件事：

將 $tan(z) + sec(z)$ 表達為冪級數形式： $$tan(z) + sec(z) = 1 + \frac{1}{1!}z + \frac1{2!}z^2 + \frac{2}{3!}z^3 + \frac5{4!}x^4 + \frac{16}{5!}z^5 + ...$$ 其中每一個 $z^n$ 項係數的分子即為交錯排列方法數¹。

這個公式的確頗為驚人，且不論 $tan(z) + sec(z)$ 乃是和排列組合八竿子打不著邊的函數，我們竟然可以將一個解析函數展開來解決離散數學的問題！

像這樣展開函數來解決方法數問題的方法，我們就稱為生成函數，也是本書所討論的重點。不過這篇文不會探討如何推導 André’s theorem，以後可能會再寫。

---

生成函數

定義：《生成函數》

一個數列 $\mathcal{A} = \{A_0, A_1, A_2, ...\}$ 的生成函數（Generating Function），是一個形式如下的冪級數： $\mathcal{A}[x] = \sum_{i=0}^{\infty} A_ix^i = A_0 + A_1x + A_2x^2 ...$ 。通常 $\mathcal{A}$ 可能含有能夠解決某個特定問題² 的訊息。

沒錯，與一般的冪級數沒有兩樣，看起來就像是擁有無限（或有限）多項的多項式，但它的係數卻是某個問題的答案。我們來看一個各位不陌生例子：

例子：二項式係數

從 $n$ 個不同顏色的球中取出 $r$ 個，不計順序，請問有幾種可能？

顯然答案就是組合數 $C^{n}_{r}$（或者記為 $\mathbf{\binom{n}{r}}$），二項式定理告訴我們，這會等同於 $(1+x)^n$ 展開後第 $r$ 項的係數：

$$(1+x)^n = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + ... + \binom{n}{n}x^n$$

注意到右式的係數正是我們要的答案 $C^{n}_{r}$ 。因此我們就可以稱 $(1+x)^n$ 為 $C^{n}_{r}$ 的生成函數。

我們來複習一下：為什麼這個等式會成立呢？因為我們將 $(1+x)^n$ 展開時，必須要從 $$(1+x)(1+x)(1+x) ... (1+x)$$ 這 $n$ 個括號中各取一項（可能是 $1$ 或 $x$）出來相乘，成為一個 $x^r$ 項（$r$ 是多少端看我們總共從這些括號中取了多少個 $x$ 出來）。

由於我們總共有 $\binom{n}{r}$ 種方式可以從 $n$ 個括號中取出 $r$ 個 $x$ 出來相乘，因此 $x^r$ 展開後總共會有 $\binom{n}{r}$ 個，組合數便反映在 $x^r$ 的係數上了。

「把答案表為某個冪級數的係數」，正是生成函數在做的事。我們來解決一個類似的問題：

例子：取球問題

從 4 個紅球、4 個白球、4 個黑球中取出六個，不計順序，請問有幾種可能？

用中學的方法解決這問題，我們需要先算 $H^3_6$ 再扣掉如 (5, 1, 0)、(6, 0, 0) 等可能性。現在我們來試試生成函數：

解法

將 $(1+x+x^2+x^3+x^4)^3$ 展開，取出第六項係數，便可以得到解。

為什麼呢？當我們將這個式子展開時，總共會需要乘開三個括號，從這三個括號中各取出一項（可能是 $x^0$ ~ $x^4$）來相乘，都可以得到展開後的某一項。這動作如同我們從三種顏色的球中取出 0 到 4 顆，例如「3 紅 2 白 1 黑」對應到下列這種展開方式：

$$(...+\mathbf{\underset{take\ 3\ red}{x^3}}+...)(...+\mathbf{\underset{take\ 2\ white}{x^2}}+...)(...+\mathbf{\underset{take\ 1\ black}{x^1}}+...) \Rightarrow x^6$$

。

所以 $x^6$ 的係數為多少，代表我們展開出幾個 $x^6$ 項，也同時代表有幾種方式可以從三種色球中取出共六顆球。

– 這就是生成函數法解決組合學問題。

---

取出某一項的係數還是很難

在大部份的時候，要手動展開一個這樣的多項式或冪級數，可能會與暴力法一樣麻煩。

通常我們可以選擇用泰勒展開式來「抽取」某一項的係數：

$$t(z) = t(0) + \frac{t'(0)}{1!}z + \frac{t''(0)}{2!}z^2 + \frac{t'''(0)}{3!}z^3 + ...$$ $$\Rightarrow n^{th} \mathit{coefficient} = \frac{t^{(n)}(0)}{n!}$$

不過手動來說還是一樣冗，因為可能會需要做好幾次的微分。不過只要把問題表示成多項式，我們就有許多微積分的工具或是軟體可以幫我們處理這類問題。

另外，也是作為本書的另一個重點，就是我們可以用複分析的工具來估計係數成長的漸進複雜度。

往後的文章可能會介紹制式的手法來為各式各樣組合學的問題找出生成函數並估計數量級，這也是為甚麼我們偏向使用生成函數，而非為每個益智問題絞盡腦汁來想一個特殊解法。

---

動差生成函數

許多人可能也曾經在學習機率與統計時學過動差母函數(Moment Generating Function)，也是類似的手段：我們先對機率分佈函數 $f(x)$ 做完 $$\int_{-\infty}^{\infty}e^{tx}f(x)dx$$ 之後，去取它冪級數的一次項、二次項、甚至 $n$ 次項係數，便可以同時得到該 $\mathit{pdf}$ 的期望值、變異數以及所有 $n$ 階動差。動差母函數把這些資訊都反應在它的係數上，只不過機率學用的是 $exp(x)$ 的冪級數性質而已。

---

這篇第一集就簡單介紹到這裡吧，寫了好多啊（攤）。不過這些內容在數學系的離散數學都有含括到，寫起來也不會吃力。有空會開始按照書本的順序介紹 Combinatorial Class。它的概念有點類似排列組合中的所有排法組成的集合，也是這本書主要探討的對象。我們將透過生成函數來為其計數。