卡塔蘭數(shù)是組合數(shù)學(xué)中一個(gè)常出現(xiàn)在各種計(jì)數(shù)問(wèn)題中出現(xiàn)的數(shù)列。由以比利時(shí)的數(shù)學(xué)家歐仁·查理·卡塔蘭 (1814–1894)命名。

卡塔蘭數(shù)的一般項(xiàng)公式為                       另類遞歸式：  h(n)=((4*n-2)/(n+1))*h(n-1);

前幾項(xiàng)為 （OEIS中的數(shù)列A000108）: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

[編輯]性質(zhì)

C_n的另一個(gè)表達(dá)形式為 所以，C_n是一個(gè)自然數(shù)；這一點(diǎn)在先前的通項(xiàng)公式中并不顯而易見(jiàn)。這個(gè)表達(dá)形式也是André對(duì)前一公式證明的基礎(chǔ)。(見(jiàn)下文的第二個(gè)證明。)

卡塔蘭數(shù)滿足以下遞推關(guān)系

它也滿足

這提供了一個(gè)更快速的方法來(lái)計(jì)算卡塔蘭數(shù)。

卡塔蘭數(shù)的漸近增長(zhǎng)為

它的含義是左式除以右式的商趨向于1當(dāng)n → ∞。（這可以用n!的斯特靈公式來(lái)證明。）

所有的奇卡塔蘭數(shù)C_n都滿足n = 2^k − 1。所有其他的卡塔蘭數(shù)都是偶數(shù)。

[編輯]應(yīng)用

組合數(shù)學(xué)中有非常多.的組合結(jié)構(gòu)可以用卡塔蘭數(shù)來(lái)計(jì)數(shù)。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一書(shū)的習(xí)題中包括了66個(gè)相異的可由卡塔蘭數(shù)表達(dá)的組合結(jié)構(gòu)。以下用C_n=3和C_n=4舉若干例：

• C_n表示長(zhǎng)度2n的dyck word的個(gè)數(shù)。Dyck word是一個(gè)有n個(gè)X和n個(gè)Y組成的字串，且所有的部分字串皆滿足X的個(gè)數(shù)大于等于Y的個(gè)數(shù)。以下為長(zhǎng)度為6的dyck words:

• 將上例的X換成左括號(hào)，Y換成右括號(hào)，C_n表示所有包含n組括號(hào)的合法運(yùn)算式的個(gè)數(shù):

• C_n表示有n+1個(gè)葉子的二叉樹(shù)的個(gè)數(shù)。

• C_n表示所有不同構(gòu)的含n個(gè)分枝結(jié)點(diǎn)的滿二叉樹(shù)的個(gè)數(shù)。（一個(gè)有根二叉樹(shù)是滿的當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)都有兩個(gè)子樹(shù)或沒(méi)有子樹(shù)。）

證明：

令1表示進(jìn)棧，0表示出棧，則可轉(zhuǎn)化為求一個(gè)2n位、含n個(gè)1、n個(gè)0的二進(jìn)制數(shù)，滿足從左往右掃描到任意一位時(shí)，經(jīng)過(guò)的0數(shù)不多于1數(shù)。顯然含n個(gè)1、n個(gè)0的2n位二進(jìn)制數(shù)共有個(gè)，下面考慮不滿足要求的數(shù)目.

考慮一個(gè)含n個(gè)1、n個(gè)0的2n位二進(jìn)制數(shù)，掃描到第2m+1位上時(shí)有m+1個(gè)0和m個(gè)1（容易證明一定存在這樣的情況），則后面的0-1排列中必有n-m個(gè)1和n-m-1個(gè)0。將2m+2及其以后的部分0變成1、1變成0，則對(duì)應(yīng)一個(gè)n+1個(gè)0和n-1個(gè)1的二進(jìn)制數(shù)。反之亦然（相似的思路證明兩者一一對(duì)應(yīng)）。

從而。證畢。

• C_n表示所有在n × n格點(diǎn)中不越過(guò)對(duì)角線的單調(diào)路徑的個(gè)數(shù)。一個(gè)單調(diào)路徑從格點(diǎn)左下角出發(fā)，在格點(diǎn)右上角結(jié)束，每一步均為向上或向右。計(jì)算這種路徑的個(gè)數(shù)等價(jià)于計(jì)算Dyck word的個(gè)數(shù)： X代表“向右”，Y代表“向上”。下圖為n = 4的情況：
•                                                                        

• C_n表示通過(guò)連結(jié)頂點(diǎn)而將n + 2邊的凸多邊形分成三角形的方法個(gè)數(shù)。下圖中為n = 4的情況：

• C_n表示對(duì){1, ..., n}依序進(jìn)出棧的置換個(gè)數(shù)。一個(gè)置換w是依序進(jìn)出棧的當(dāng)S(w) = (1, ..., n), 其中S(w)遞歸定義如下：令w = unv，其中n為w的最大元素，u和v為更短的數(shù)列；再令S(w) =S(u)S(v)n，其中S為所有含一個(gè)元素的數(shù)列的單位元。

• C_n表示集合{1, ..., n}的不交叉劃分的個(gè)數(shù). 那么, C_n 永遠(yuǎn)不大于第n項(xiàng)貝爾數(shù). C_n也表示集合{1, ..., 2n}的不交叉劃分的個(gè)數(shù)，其中每個(gè)段落的長(zhǎng)度為2。綜合這兩個(gè)結(jié)論，可以用數(shù)學(xué)歸納法證明 that all of the free cumulants of degree more than 2 of the Wigner semicircle law are zero. This law is important in free probability theory and the theory of random matrices.

• C_n表示用n個(gè)長(zhǎng)方形填充一個(gè)高度為n的階梯狀圖形的方法個(gè)數(shù)。下圖為 n = 4的情況: