問題
《編程之美》中提到了“買票找零”問題，查閱了下資料，此問題和卡特蘭數 Cn有關，其定義如下：
卡特蘭數真是一個神奇的數字，很多組合問題的數量都和它有關系，例如：
一.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 個葉子節點的二叉樹的數量。例如 4個葉子節點的所有二叉樹形態：
五.Cn=n*n的方格地圖中，從一個角到另外一個角，不跨越對角線的路徑數，例如， 4×4方格地圖中的路徑有：
六.Cn= n+2條邊的多邊形，能被分割成三角形的方案數，例如 6邊型的分割方案有：
七.Cn= 圓桌周圍有 2n個人，他們兩兩握手，但沒有交叉的方案數。
在《Enumerative Combinatorics》一書中，竟然提到了多達 66種組合問題和卡特蘭數有關。