卡塔蘭數

明安圖《割圜密率捷法》卷三 「卡塔蘭數」書影

卡塔蘭數

卡塔蘭數（英語：Catalan number）是組合數學中一個常在各種計數問題中出現的數列，以比利時數學家歐仁·夏爾·卡塔蘭命名。歷史上，清朝數學家明安圖在其《割圜密率捷法》中最先發明這種計數方式，早於卡塔蘭。有中國學者建議將此數命名為「明安圖數」或「明安圖-卡塔蘭數」。

卡塔蘭數的一般項公式為

$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 {1-{\sqrt {1-4z}}}{2z}}$

應用

組合數學中有非常多的組合結構可以用卡塔蘭數來計數。在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, ..., 2n}的不交叉劃分的個數，其中每個段落的長度為2。綜合這兩個結論，可以用數學歸納法證明：在 魏格納半圓分佈定律 中度數大於2的情形下，所有 自由的 累積量s 為零。 該定律在自由概率論和隨機矩陣理論中非常重要。

• C_n表示用n個長方形填充一個高度為n的階梯狀圖形的方法個數。下圖為n = 4的情況：

• C_n表示表為2×n的矩陣的標準楊氏矩陣的數量。 也就是說，它是數字 1, 2, ..., 2n 被放置在一個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$。

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