<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Catalan - 卡特蘭數 -------- #### 問題 1. 現在把$$ 12 $$個高矮不同的人排成兩排，要求每排必須從矮到高排列，且第二排的人比第一排對應的人要高。請問有多少種排列方式。這個問題也可以描述為，把$$ 12 $$個不同的正整數排成兩排，要求從小到大，且第二排的數字比第一排對應的數字要大，求出排列方式$$ n $$。如下圖所示：  2. #### 解法 卡特蘭數（又稱卡塔蘭數）是組合數學中常見的數列，在計算凸多邊形面積劃分和棋盤路徑、以及進出棧方法數中具有很多應用。 卡特蘭數$$ C_{n} $$滿足以下遞推關系： $$ f(n) = frac{1}{n + 1}( \begin{cases} 2 \times n \\ n \end{cases} ) 其中（n \ge 0） $$ 卡特蘭數可以解決的問題： 計算n+2條邊的凸多邊形中劃分三角形的個數 在此模型中，選取任意的兩條邊為基點，在剩余的n條邊中，可知是 兩部分的卷積公式 Cn=sum(Ci*C(n-i)) 0<i<n 計算網格中的路徑方案數： 在n*n的網格中，求從左下角到右上角的路徑的方案數， 要求不能穿過對角線 這個問題可以轉換成第三中模型 進出棧的問題： 設有n個1和n個-1隨機組合，在其中添加括號，是的每個括號中的值 都不為負數，也就是一類dyck word數的計算 dyck word數：是一個有n個X和n個Y組成的字串，且所有部分的字串 滿足x的個數不小于y的個數，一下為5中情況(n=3) XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY 將上述X換成左括號，Y換成右括號，Cn表示組合式算法個數C3=5. 求出$$ n $$的卡特蘭數$$ f(n) $$ #### 解法 #include <iostream> #include <stdio.h> #include <cmath> using namespace std; void catalan(int**a,int* b) //求卡特蘭數 { int i,j,len,carry,temp; a[1][0]=b[1]=1; len=1; for(i=2;i<=100;i++) { for(j=0;j<len;j++) //乘法 a[i][j]=a[i-1][j]*(4*(i-1)+2); carry=0; for(j=0;j<len;j++) //處理相乘結果 { temp=a[i][j]+carry; a[i][j]=temp%10; carry=temp/10; } while(carry) //進位處理 { a[i][len++]=carry%10; carry/=10; } carry=0; for(j=len-1;j>=0;j--) //除法 { temp=carry*10+a[i][j]; a[i][j]=temp/(i+1); carry=temp%(i+1); } while(!a[i][len-1]) //高位零處理 len--; b[i]=len; } } -------- #### 源碼 [import, lang:"c_cpp"](../../../src/CombinatorialMathematics/Catalan.h) #### 測試 [import, lang:"c_cpp"](../../../src/CombinatorialMathematics/Catalan.cpp)