Catalan數(shù)的應(yīng)用：
http://www.shnenglu.com/abilitytao/archive/2010/04/12/112371.html卡特蘭數(shù)真是一個(gè)神奇的數(shù)字，很多組合問題的數(shù)量都和它有關(guān)系，例如：
一.Cn= 長(zhǎng)度為 2n的 Dyck words的數(shù)量。 Dyck words是由 n個(gè) X和 n個(gè) Y組成的字符串，并且從左往右數(shù)， Y的數(shù)量不超過 X，例如長(zhǎng)度為 6的 Dyck words為：
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
二.Cn= n對(duì)括號(hào)正確匹配組成的字符串?dāng)?shù)，例如 3對(duì)括號(hào)能夠組成：
((())) ()(()) ()()() (())() (()())
三.Cn= n+1個(gè)數(shù)相乘，所有的括號(hào)方案數(shù)。例如， 4個(gè)數(shù)相乘的括號(hào)方案為：
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
\四.Cn= 擁有 n+1 個(gè)葉子節(jié)點(diǎn)的二叉樹的數(shù)量。例如 4個(gè)葉子節(jié)點(diǎn)的所有二叉樹形態(tài)：
五.Cn=n*n的方格地圖中，從一個(gè)角到另外一個(gè)角，不跨越對(duì)角線的路徑數(shù)，例如， 4×4方格地圖中的路徑有：
六.Cn= n+2條邊的多邊形，能被分割成三角形的方案數(shù)，例如 6邊型的分割方案有：
七.Cn= 圓桌周圍有 2n個(gè)人，他們兩兩握手，但沒有交叉的方案數(shù)。
在《Enumerative Combinatorics》一書中，竟然提到了多達(dá) 66種組合問題和卡特蘭數(shù)有關(guān)。
算法分析中Catalan數(shù)的應(yīng)用研究一、catalan計(jì)數(shù)序列及其遞推公式
（一）catalan數(shù)
catalan數(shù)即序列c0,c1,c2,…,cn,…。其中cn= (n=0,1,2,…)。前幾個(gè)catalan數(shù)為c0=1,c1=1,c2=2,c3=5,c4=14,c5=42,c6=132,c7=429,c8=1430,c9=4862。
（二）遞推公式
公式1：cn=c0cn-1+c1cn-2+…+cn-1c0= (1)
此公式為catalan數(shù)最常見遞推公式。由公式可得出cn= (n=0,1,2,…),其證明過程主要是求此非線性遞推公式的生成函數(shù), 具體證明可參見參考文獻(xiàn)中的組合數(shù)學(xué)。
公式2：cn= cn-1 (n≥1) c0=1,c1=1 (2)
此公式也為catalan數(shù)常見遞推公式之一。由公式也可得出cn= (n=0,1,2,…),其證明過程較為簡(jiǎn)單。只要不斷地遞歸到c0=1即可。
定理1：n個(gè)+1和n個(gè)-1構(gòu)成的2n項(xiàng)a1,a2,…,a2n,其部分和滿足a1+a2+…+ak≥0 (k=1,2,…,2n)的數(shù)列個(gè)數(shù)等于第n個(gè)catalan數(shù)，即cn= 。
證明：此定理的可以直接利用排列組合來證明，具體的證明可參見參考文獻(xiàn)中的組合數(shù)學(xué)。這里給出另一種證明方式。
設(shè)滿足部分和非負(fù)的數(shù)列個(gè)數(shù)為cn，此數(shù)列中的每一個(gè)都可看成是由i個(gè)+1和i個(gè)-1以及n-i個(gè)+1和n-i個(gè)-1這樣兩個(gè)數(shù)列構(gòu)成。 由i個(gè)+1和i個(gè)-1構(gòu)成的數(shù)列個(gè)數(shù)為ci, 由n-i個(gè)+1和n-i個(gè)-1構(gòu)成的數(shù)列個(gè)數(shù)為cn-i，由乘法和加法原理可知cn= 且c0=1即滿足公式1,所以cn= 。