卡塔兰数

**卡塔蘭數**是組合數學中一個常在各種計數問題中出現的數列。以比利時的數學家歐仁・查理・卡特蘭（1814–1894）命名。歷史上，清朝數學家明安圖（1692 年－1763 年）在其《割圜密率捷法》中最先發明這種計數方式，遠遠早於卡塔蘭。有中國學者建議將此數命名為「**明安圖數**」或「**明安圖 - 卡塔蘭數**」。

卡塔蘭數的一般項公式為

$$
C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!n!}}
$$

第 0 項到第 19 項的卡塔蘭數為：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ...（OEIS 數列 A000108）

## 性質

_C_n 的另一個表達形式為

 $C_{n}={2n \choose n}-{2n \choose n+1}\quad {\mbox{ for }}n\geq 1$ ，

所以，_C_n 是一個自然數；這一點在先前的通項公式中並不顯而易見。這個表達形式也是 André 對前一公式證明的基礎。

遞推關係：

　
: $C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.$

它也滿足

　
: $C_{0}=1\quad {\mbox{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},$

這提供了一個更快速的方法來計算卡塔蘭數。

卡塔蘭數的漸近增長為

　
: $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$

它的含義是當 _n_→ ∞時，左式除以右式的商趨向於 1。（這可以用 _n_! 的斯特靈公式來證明。）

所有的奇卡塔蘭數 _C_n 都滿足 $n=2^{k}-1$ 。所有其他的卡塔蘭數都是偶數。

而且

$$
C_{n}=\int _{0}^{4}x^{n}{\frac {1}{2\pi }}{\sqrt {4/x-1}}\mathrm {d} x
$$

## 母函數

若**卡塔蘭數**的母函數是

$$
M(z)=\sum C_{n}z^{n}
$$

則

$$
M(z)=1+zM(z)^{2}
$$

解是

$$
M(z)={\frac {2}{1-{\sqrt {1-4z}}}}
$$

## 應用

組合數學中有非常多的組合結構可以用卡塔蘭數來計數。在 Richard P. Stanley 的 Enumerative Combinatorics: Volume 2 一書的習題中包括了 66 個相異的可由卡塔蘭數表達的組合結構。以下用 n=3 和 n=4 舉若干例：

* _C_n 表示長度 _2n_ 的 dyck word 的個數。Dyck 詞是一個有 _n_ 個 X 和 _n_ 個 Y 組成的字串，且所有的前綴字串皆滿足 X 的個數大於等於 Y 的個數。以下為長度為 6 的 dyck words:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

* 將上例的 X 換成左括號，Y 換成右括號，_C_n 表示所有包含 _n_ 組括號的合法運算式的個數：

((())) ()(()) ()()() (())() (()())

* _C_n 表示有 _n_ 個節點組成不同構二元樹的方案數。下圖中，_n_ 等於 _3_，圓形表示節點，月牙形表示什麼都沒有。
* _C_n 表示有 _2n+1_ 個節點組成不同構滿二元樹的方案數。下圖中，_n_ 等於 _3_，圓形表示內部節點，月牙形表示外部節點。本質同上。

**證明**_：_令 1 表示進棧，0 表示出棧，則可轉化為求一個 _2n_ 位、含 _n_ 個 1、_n_ 個 0 的二進位數，滿足從左往右掃描到任意一位時，經過的 0 數不多於 1 數。顯然含 _n_ 個 1、_n_ 個 0 的 _2n_ 位二進位數共有 ${2n \choose n}$ 個，下面考慮不滿足要求的數目。

考慮一個含 _n_ 個 1、_n_ 個 0 的 2n 位二進位數，掃描到第 _2m+1_ 位上時有 _m+1_ 個 0 和 _m_ 個 1（容易證明一定存在這樣的情況），則後面的 0-1 排列中必有 _n-m_ 個 1 和 _n-m-1_ 個 0。將 _2m+2_ 及其以後的部分 0 變成 1、1 變成 0，則對應一個 _n+1_ 個 0 和 _n-1_ 個 1 的二進位數。反之亦然（相似的思路證明兩者一一對應）。

從而 $C_{n}={2n \choose n}-{2n \choose n+1}={\frac {1}{n+1}}{2n \choose n}$ 。證畢。

* _C_n 表示所有在 _n_ × _n_ 格點中不越過對角線的**單調路徑**的個數。一個單調路徑從格點左下角出發，在格點右上角結束，每一步均為向上或向右。計算這種路徑的個數等價於計算 Dyck word 的個數：X 代表「向右」，Y 代表「向上」。下圖為 _n_ = 4 的情況：

* _C_n 表示通過連結頂點而將 _n_+ 2 邊的凸多邊形分成三角形的方法個數。下圖中為 _n_ = 4 的情況：

* _C_n 表示對 {1, ..., _n_} 依序進出棧的置換個數。一個置換 _w_ 是依序進出棧的當 _S_(_w_) = (1, ..., _n_), 其中 _S_（_w_）遞歸定義如下：令 _w_ = _unv_，其中 _n_ 為 _w_ 的最大元素，_u_ 和 _v_ 為更短的數列；再令 _S_(_w_) = _S_(_u_)_S_(_v_)_n_，其中 _S_ 為所有含一個元素的數列的單位元。
* _C_n 表示集合 {1, ..., _n_} 的不交叉劃分的個數。那麼， _C_n 永遠不大於第 _n_ 項貝爾數. _C_n 也表示集合 {1, ..., 2_n_} 的不交叉劃分的個數，其中每個段落的長度為 2。綜合這兩個結論，可以用數學歸納法證明：在 魏格納半圓分布定律 中度數大於 2 的情形下，所有 _自由的_ 累積量 s 為零。 該定律在自由概率論和隨機矩陣理論中非常重要。
* _C_n 表示用 _n_ 個長方形填充一個高度為 _n_ 的階梯狀圖形的方法個數。下圖為 _n_= 4 的情況：

* _C_n 表示表為 2×_n_ 的矩陣的標準楊氏矩陣的數量。 也就是說，它是數字 1, 2, ..., 2_n_ 被放置在一個 2×_n_ 的矩形中並保證每行每列的數字升序排列的方案數。同樣的，該式可由勾長公式的一個特殊情形推導得出。
* _C_n 表示 _n_ 個無標號物品的半序的個數。

## 漢克爾矩陣

無論 _n_ 的取值為多少，_n_×_n_ 的漢克爾矩陣: $A_{i,j}=C_{i+j-2}.\ $ 的行列式為 1。例如，_n_ = 4 時我們有

　
: $\det {\begin{bmatrix}1&1&2&5\\1&2&5&14\\2&5&14&42\\5&14&42&132\end{bmatrix}}=1$ 。

進一步，無論 _n_ 的取值為多少，如果矩陣被移動成 $A_{i,j}=C_{i+j-1}.\ $ ，它的行列式仍然為 1。例如，_n_ = 4 時我們有

　
: $\det {\begin{bmatrix}1&2&5&14\\2&5&14&42\\5&14&42&132\\14&42&132&429\end{bmatrix}}=1$ 。

同時，這兩種情形合在一起唯一定義了卡塔蘭數。

## 參考文獻