卡塔蘭數
catalan數的表達形式
h(n) = C(2n,n)/(n+1) （n>=0）
h(n) = C(2n-2,n-1)/n (n>=1)
對catalan數的應用(形式類似，關鍵是能否對問題建模了)
1.括號化問題。
矩陣鏈乘： P=A1×A2×A3×……×An，依據乘法結合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？
分析：可以將分割看成構成二叉樹的情形。
2.將多邊行劃分為三角形問題。將一個凸多邊形區域分成三角形區域(劃分線不交叉)的方法數?
類似：在圓上選擇2n個點,將這些點成對連接起來使得所得到的n條線段不相交的方法數?
分析：同矩陣鏈乘。
3.出棧次序問題。一個棧(無窮大)的進棧序列為1,2,3,..n,有多少個不同的出棧序列?
類似：有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？(將持5元者到達視作將5元入棧，持10元者到達視作使棧中某5元出棧)
類似：一位大城市的律師在他住所以北n個街區和以東n個街區處工作。每天她走2n個街區去上班。如果他從不穿越（但可以碰到）從家到辦公室的對角線，那么有多少條可能的道路？
分析：對于每一個數來說，必須進棧一次、出棧一次。我們把進棧設為狀態‘1’，出棧設為狀態‘0’。n個數的所有狀態對應n個1和n個0組成的2n位二進制數。由于等待入棧的操作數按照1‥n的順序排列、入棧的操作數b大于等于出棧的操作數a(a≤b)，因此輸出序列的總數目=由左而右掃描由n個1和n個0組成的2n位二進制數，1的累計數不小于0的累計數的方案種數。 在2n位二進制數中填入n個1的方案數為c(2n,n),不填1的其余n位自動填0。從中減去不符合要求（由左而右掃描，0的累計數大于1的累計數）的方案數即為所求。
不符合要求的數的特征是由左而右掃描時，必然在某一奇數位2m+1位上首先出現m+1個0的累計數和m個1的累計數，此后的2(n-m)-1位上有n-m個 1和n-m-1個0。如若把后面這2(n-m)-1位上的0和1互換，使之成為n-m個0和n-m-1個1，結果得1個由n+1個0和n-1個1組成的2n位數，即一個不合要求的數對應于一個由n+1個0和n-1個1組成的排列。
反過來，任何一個由n+1個0和n-1個1組成的2n位二進制數，由于0的個數多2個，2n為偶數，故必在某一個奇數位上出現0的累計數超過1的累計數。同樣在后面部分0和1互換，使之成為由n個0和n個1組成的2n位數，即n+1個0和n-1個1組成的2n位數必對應一個不符合要求的數。
因而不合要求的2n位數與n＋1個0，n－1個1組成的排列一一對應。
顯然，不符合要求的方案數為c(2n,n+1)。由此得出 輸出序列的總數目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n).（這個公式的下標是從h(0)=1開始的）
4.給定N個節點，能構成多少種形狀不同的二叉樹？
分析：先去一個點作為頂點,然后左邊依次可以取0至N-1個相對應的,右邊是N-1到0個,兩兩配對相乘,就是h(0)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(0)=h(n))
參考：
卡塔蘭數是組合數學中一個常出現在各種計數問題中出現的數列。由以比利時的數學家歐仁·查理·卡塔蘭 (1814–1894)命名。
卡塔蘭數的一般項公式為 
另類遞歸式： h(n)=((4*n-2)/(n+1))*h(n-1);
前幾項為 （OEIS中的數列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, ...
Cn的另一個表達形式為
所以，Cn是一個自然數；這一點在先前的通項公式中并不顯而易見。這個表達形式也是André對前一公式證明的基礎。(見下文的第二個證明。)
卡塔蘭數滿足以下遞推關系
它也滿足
這提供了一個更快速的方法來計算卡塔蘭數。
卡塔蘭數的漸近增長為
它的含義是左式除以右式的商趨向于1當n → ∞。（這可以用n!的斯特靈公式來證明。）
所有的奇卡塔蘭數Cn都滿足n = 2k − 1。所有其他的卡塔蘭數都是偶數。
組合數學中有非常多.的組合結構可以用卡塔蘭數來計數。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一書的習題中包括了66個相異的可由卡塔蘭數表達的組合結構。以下用Cn=3和Cn=4舉若干例：
- Cn表示長度2n的dyck word的個數。Dyck word是一個有n個X和n個Y組成的字串，且所有的部分字串皆滿足X的個數大于等于Y的個數。以下為長度為6的dyck words:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
- 將上例的X換成左括號，Y換成右括號，Cn表示所有包含n組括號的合法運算式的個數:
((())) ()(()) ()()() (())() (()())
- Cn表示所有不同構的含n個分枝結點的滿二叉樹的個數。（一個有根二叉樹是滿的當且僅當每個結點都有兩個子樹或沒有子樹。）
證明：
令1表示進棧，0表示出棧，則可轉化為求一個2n位、含n個1、n個0的二進制數，滿足從左往右掃描到任意一位時，經過的0數不多于1數。顯然含n個1、n個0的2n位二進制數共有
個，下面考慮不滿足要求的數目.
考慮一個含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的二進制數。反之亦然（相似的思路證明兩者一一對應）。
從而
。證畢。
- Cn表示所有在n × n格點中不越過對角線的單調路徑的個數。一個單調路徑從格點左下角出發，在格點右上角結束，每一步均為向上或向右。計算這種路徑的個數等價于計算Dyck word的個數： X代表“向右”，Y代表“向上”。下圖為n = 4的情況：
-
- Cn表示通過連結頂點而將n + 2邊的凸多邊形分成三角形的方法個數。下圖中為n = 4的情況：
- Cn表示對{1, ..., n}依序進出棧的置換個數。一個置換w是依序進出棧的當S(w) = (1, ..., n), 其中S(w)遞歸定義如下：令w = unv，其中n為w的最大元素，u和v為更短的數列；再令S(w) =S(u)S(v)n，其中S為所有含一個元素的數列的單位元。
- Cn表示用n個長方形填充一個高度為n的階梯狀圖形的方法個數。下圖為 n = 4的情況:
百度百科資料:
簡介
中文:卡特蘭數
Catalan數是組合數學中一個常出現在各種計數問題中出現的數列。由以比利時的數學家歐仁·查理·卡塔蘭 (
1814–1894)命名。
原理：
令h(0)=1,h(1)＝1,catalan數滿足遞歸式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + 
+ h(n-1)h(0) (其中n>=2)
該遞推關系的解為：
h(n)=C(2n,n)/(n + 1) (n=1,2,3,)
另類遞歸式： h(n)=((4*n-2)/(n+1))*h(n-1);
前幾項為 （OEIS中的數列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,
應用
我總結了一下，最典型的四類應用：（實質上卻都一樣，無非是遞歸等式的應用，就看你能不能分解問題寫出遞歸式了）
1.括號化問題。
矩陣鏈乘： P=a1×a2×a3×……×an，依據乘法結合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？(h(n)種)
2.出棧次序問題。
一個棧(無窮大)的進棧序列為1,2,3,..n,有多少個不同的出棧序列?
類似：
(1)有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？(將持5元者到達視作將5元入棧，持10元者到達視作使棧中某5元出棧)
(2)在圓上選擇2n個點,將這些點成對連接起來，使得所得到的n條線段不相交的方法數。
3.將多邊行劃分為三角形問題。
將一個凸多邊形區域分成三角形區域的方法數?
類似：一位大城市的律師在她住所以北n個街區和以東n個街區處工作。每天她走2n個街區去上班。如果她
從不穿越（但可以碰到）從家到辦公室的對角線，那么有多少條可能的道路？
類似：在圓上選擇2n個點,將這些點成對連接起來使得所得到的n條線段不相交的方法數?
4.給頂節點組成二叉樹的問題。
給定N個節點，能構成多少種形狀不同的二叉樹？
(一定是二叉樹!
先去一個點作為頂點,然后左邊依次可以取0至N-1個相對應的,右邊是N-1到0個,兩兩配對相乘,就是h(0)*h(n-1) + h(2)*h(n-2) + + h(n-1)h(0)=h(n))
（能構成h（N）個）