問題
《編程之美》中提到了“買票找零”問題，查閱了下資料，此問題和卡特蘭數(shù) Cn有關(guān)，其定義如下：
卡特蘭數(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)。