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