卡特蘭數用于解決一些特定的排列問題，一般是求解有多少種排列。

　　Catalan數的定義：

　　（1）當n=1時，C(1)=1。

　　（2）當n>1時，C(n) = C(1)*C(n-1) + C(2)*C(n-2) + ... + C(n-1)*C(1)

　　（3）當然，還能這樣算：　　

　　（4）更厲害的，是可以這樣算，但可能不精確：　　　　（ps：這些都是經過證明的公式）

　　注：所有的奇卡塔蘭數（即n為奇數）C_n都滿足。

　　一般來說，求卡特蘭數有個基本問題，而其他問題一般可以轉成這個問題。這個基本問題是這樣的：一個n個bit的二進制數，如果其任意前綴都是1的個數>=0的個數，求這樣的二進制有多少個？可以根據catellan數的性質直接求C_n即可。

經典題（1）：有n對括號，請問n對括號能組成多少個合法序列？比如"(())"就是合法。

　　思路：考慮前i個pre[i]，可以這樣認為，其中的左括號為1，右括號為0，那么就成功轉成了卡特蘭數的一般問題了。這里有個問題，編程之美中提到，f(2*n)=[1/(n+1)]*C(2*n,m)，其實右式完全等于求C_n，也可以直接按C_n來求。但是為什么書里這么寫呢？因為書中考慮的是枚舉k為每個可能與首個左括號匹配的右括號的位置，假如規定括號序列的下標是從0開始的，由于k必須是奇數位置才合法，所以列出來的公式為 f(2n)=f(0)*f(2n-2)+f(2)*f(2n-4)+...f(2n-4)*f(2)+f(2n-2)*f(0)，觀察到式子中沒有出現求奇數的f，因此直接將0～2n-1中的偶數映射過來就是1～n啦。

經典題（2）：12個高矮不同的人，排成兩排，每排必須是從矮到高排列，而且第二排比對應列的第一排的人高,問排列方式有多少種?

　　思路：先將12個人升序排序，下標分別為1～n。同樣，用0代表首行，用1代表第二行。那么每個后綴back[i]中1的個數就必須大于等于0的個數了，否則肯定存在一個j>=i，首行[j]>次行[j]，即第一行有個人比第二行高了，不合法。答案也是求C_n。

經典題（3）：將一個具有n個頂點的凸多邊形切成多個三角形的方法有多少種？注意只能某一頂點切往另一頂點。

　　思路：凸多邊形的每條邊必須對應一個三角形，那么現在的問題只是求這條邊對應的另一個頂點在哪里。同樣，這個頂點的位置也是枚舉，那么就將問題分成了兩個小問題，其實就是區間DP題。答案依然是C_n。

經典題（4）：有3個人要借書，3個人要還書。要使得3個人都能借到書，那么這6人進館的序列有多少種？

　　思路：將還書的人看成0，借書的人看成1。只能在有人還了之后才能有人借得到。那么每個前綴pre[i]中1的個數必須>=0的個數，又轉成了一般問題。

　　同樣的問題還有：”合法的入棧出棧序列有多少種？“和”合法的找錢給錢序列有多少種“等等。

經典題（5）：將一個具有n個頂點的凸多邊形切成多個三角形的方法有多少種？注意只能某一頂點切往另一頂點。

　　思路：凸多邊形的每條邊必須對應一個三角形，那么現在的問題只是求這條邊對應的另一個頂點在哪里。同樣，這個頂點的位置也是枚舉，那么就將問題分成了兩個小問題，其實就是區間DP題。答案依然是C_n。

經典題（6）：一個n*n的網格，要從左下角的格子走到右上角的格子，在不踏入對角線的情況下，且第一步必須往右走，有多少種方案到達終點？

　　思路：要不碰到對角線，那么往右走的次數要時刻多于等于往上走的次數。又是可以轉成一般問題。

經典題（7）：一個由n個節點組成的二叉樹，不同構的有多少棵？

　　思路： 考慮第n個點為根，那么左邊可能有0～n-1個點，右邊就是剩下的點，枚舉左邊有多少個點即可。求C_n。

經典題（8）：矩陣連乘問題，n個矩陣相乘，要求為他們加括號改變乘法的順序，有多少種方法？

　　思路： 仍然是”合法的括號序列“的那道題。

總結：通過上面的題觀察到，一共有兩種類型，一種是”括號匹配“類型，一種是”基本問題“。如果需要匹配的，一般就是第一種類型，否則就是第二種。它們對應的模型都差不多。

總結

以上是生活随笔為你收集整理的Catalan数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。