1、卡特蘭數

卡特蘭通過解決凸n邊形的剖分得到了數列C_n。

凸n＋2邊形用其n－1條對角線把此凸n＋2邊形分割為互不重疊的三角形，這種分法的總數為C_n。

為紀念卡特蘭，人們使用“卡特蘭數”來命名這一數列。

據說有幾十種看上去毫不相干的組合計數問題的最終表達式都是卡特蘭數的形式。

卡特蘭數在數學競賽、信息學競賽、組合數學、計算機編程等都會有其不同側面的介紹。

前幾個卡特蘭數：規定C₀＝1，而

C₁＝1，C₂＝2，C₃＝5，C₄＝14，C₅＝42，

C₆＝132，C₇＝429，C₈＝1430，C₉＝4862，C₁₀＝16796，

C₁₁＝58786，C₁₂＝208012，C₁₃＝742900，C₁₄＝2674440，C₁₅＝9694845。

遞推公式

2、有意思的應用

飯後，姐姐洗碗，妹妹把姐姐洗過的碗一個一個放進碗櫥摞成一摞。一共有n個不同的碗，洗前也是摞成一摞的，也許因為小妹貪玩而使碗拿進碗櫥不及時，姐姐則把洗過的碗摞在旁邊，問：小妹摞起的碗有多少種可能的方式？

答：得數是第n個卡特蘭數C_n。

3、poj 1095

要構造出一顆編號為n的二叉樹,只需要知道左子樹和右子樹的編號,就可以進行遞歸構造:
     1> 計算出編號為n的二叉樹有幾個節點:將n依次減去h[1],h[2],……,h[i],直到不能減為止,則此二叉樹共有(i+1)個節點,除去根節點,則左右子樹共有i個節點.
     2> 計算左右子樹各有幾個節點:將n依次減去h[1]*h[i-1],h[2]*h[i-2],……,h[j]*h[i-j],直到不能減為止,則左子樹有(j+1)個節點,右子樹有i-(j+1)個節點.
     3> 計算左右子樹的編號:計算左子樹是具有(j+1)個節點的二叉樹中的第x棵,右子樹是具有i-(j+1)個節點的二叉樹中的第y棵,將n整除h[i-(j+1)],商即為x,余數即為y.