遞迴關係（五）（Recurrence relation-5）

遞迴關係（五）（Recurrence relation-5）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授責任編輯

連結：遞迴關係（四）

摘要：本篇探討正多邊形三角剖分的方法數，介紹數學上重要的「Catalan 數列」。

接著要介紹一個大數學家歐拉（Euler）考慮過的問題，關於正多邊形三角剖分的方法數。

$$(3)$$  三角剖分與 Catalan 數

歐拉考慮這個問題：

用互不相交的對角線將正 $$n+2$$ 邊形分割成三角形，有幾個方法？
（用 $$n+2$$ 而不用 $$n$$ 是因為要讓數列從 $$n=1$$ 開始。又，旋轉後相同視為不同的方法）

記答案是 $$a_n$$。如果硬把所有情形畫出來，一開始的幾項是 $$a_{1}=1,a_{2}=2,a_{3}=5,a_{4}=14,a_{5}=42$$，如下圖，畫出 $$a_{2},a_{3},a_{4}$$ 的所有情形。為方便起見我們令 $$a_{0}=1$$。

但是一般的 $$a_n$$ 是多少，並不容易猜。這樣思考：以八邊形為例。如下圖，固定 $$AB$$ 為底邊，以此為一邊總是要張出一個三角形，第三個頂點令為 $$P$$ 點。如果 $$P$$ 點在 $$4$$ 則左邊剩下五邊形有 $$a_3$$ 種分割法；右邊剩下四邊形有 $$a_2$$ 種分割法。亦即當 $$P$$ 點在 $$4$$ 時有 $$a_{3}\cdot a_{2}$$ 種分割法。

$$P$$ 點可以是 $$1,2,3,4,5,6$$ 任一點。當 $$P$$ 點在 $$1$$ 時有 $$a_0\cdot a_5$$ 種分割法；當 $$P$$ 點在 $$2$$ 時有 $$a_1\cdot{a_6}$$ 種分割法；以此類推。因此得到遞迴式

$$a_6=a_0a_5+a_1a_4+a_2a_3+a_3a_2+a_4a_1+a_5a_0$$

由這個遞迴式及上述的前幾項，就可以得到 $$a_{6}=132$$，亦即正八邊形的三角剖分有 $$132$$ 種方法。真要硬畫，是很容易畫漏的。

同理，正 $$n$$ 邊形的三角剖分有這樣的遞迴式

$$a_n=a_0a_{n-1}+a_1a_{n-2}+a_2a_{n-3}+\cdots+a_{n-1}a_0$$

從這個式子怎麼解出一般項？利用生成函數（generating function）的技巧可以解決。生成函數的概念也是歐拉提出來的。一個數列 $$a_{0},a_{1},a_{2},…,a_{n},…$$ 的生成函數是一個冪級數

$$A(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n+\cdots$$

它的精神是用一個函數 $$A(x)$$ 來代表整個數列。如果我們可以用一些方法求出 $$A(x)$$，自然整個數列就知道了。

關鍵的一步是：如果把 $$1+x(A(x))^2$$ 乘開，同類項合併，會得到

$$1+x(A(x))^2=1+a_0a_0x+(a_0a_1+a_1a_0)x^2+(a_0a_2+a_1a_1+a_0a_2)x^3+\cdots$$

但是對照遞迴式，恰好這個式子就是 $$A(x)$$（比如 $$a_{2}=a_{0}a_{1}+a_{1}a_{0}$$ 等等）！

所以得到關鍵的函數方程

$$A(x)=1+x(A(x))^2$$

解出來得到

$$A(x)=\displaystyle\frac{1-\sqrt{1-4x}}{2x}$$

別忘了要求的是 $$a_n$$，亦即 $$A(x)$$ 的 $$x^n$$ 係數。所以理論上，把 $$A(x)$$ 做泰勒展開式就得了。手算也是可以的，由這個式子和二項式定理與二項式係數，不難得到

$$\displaystyle a_n=\frac{1}{n+1}C^{2n}_n$$

此即將正 $$n+2$$ 邊形三角剖分的方法數。

$$\{a_n\}_{n\ge 0}=1,1,2,5,14,42,132,429,\cdots$$ 這個數列稱為「Catalan 數列」。

特別介紹這個問題，不僅僅是巧妙的遞迴式或數學史上的緣故。一方面順道介紹生成函數，也因為 Catalan 數列是數學上最重要的數列之一。Catalan  數不止在組合學（離散數學）中頻繁出現，更在資訊科學，代數，拓樸，幾何中都發現它的蹤影。其相關研究幾乎已經成為一個領域，稱為 Catalan 組合學，目前仍然是非常活躍的一個研究領域。

連結：遞迴關係（六）

參考文獻：

1.  Tucker, Applied Combinatorics, 5th edition, Wiley.
2. Brualdi, Introductory Combinatorics, 5th Edition, Pearson.

延伸閱讀：

1. 教育部，高中課程綱要(99)，2010。
2. Stanley, Enumerative Combinatorics, Vol.2.
3. Koshy, Catalan Numbers with Applications, 2008.