【数论】求凸多边形的三角划分
问题
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。[6]
分析
如果纯粹从f（4）=2，f（5）=5，f（6）=14，……，f（n）=n慢慢去归纳，恐怕很难找到问题的递推式，我们必须从一般情况出发去找规律。
因为凸多边形的任意一条边必定属于某一个三角形，所以我们以某一条边为基准，以这条边的两个顶点为起点P1和终点Pn（P即Point），将该凸多边形的顶点依序标记为P1、P2、……、Pn，再在该凸多边形中找任意一个不属于这两个点的顶点Pk（2<=k<=n-1），来构成一个三角形，用这个三角形把一个凸多边形划分成两个凸多边形，其中一个凸多边形，是由P1，P2，……，Pk构成的凸k边形（顶点数即是边数），另一个凸多边形，是由Pk，Pk+1，……，Pn构成的凸n-k+1边形。
此时，我们若把Pk视为确定一点，那么根据乘法原理，f（n）的问题就等价于——凸k多边形的划分方案数乘以凸n-k+1多边形的划分方案数，即选择Pk这个顶点的f（n）=f（k）×f（n-k+1）。而k可以选2到n-1，所以再根据加法原理，将k取不同值的划分方案相加，得到的总方案数为：f（n）=f（2）f（n-2+1）+f（3）f（n-3+1）+……+f（n-1）f（2）。看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n-2） （n=2，3，4，……）。
最后，令f（2）=1，f（3）=1。
此处f（2）=1和f（3）=1的具体缘由须参考详尽的“卡特兰数”，也许可从凸四边形f（4）=f（2）f（3）+ f（3）f（2）=2×f（2）f（3）倒推，四边形的划分方案不用规律推导都可以知道是2，那么2×f（2）f（3）=2，则f（2）f（3）=1，又f（2）和f（3）若存在的话一定是整数，则f（2）=1，f（3）=1。
几个常用的卡特兰数公式：
令h(0)=1,h(1)=1，catalan数满足递推式[1]：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
另类递推式[2]：
h(n)=h(n-1)*(4*n-2)/(n+1);
递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
递推关系的另类解为：
h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)
代码
#include<cstdio>#include<iostream>#define mo 100000000using namespace std;struct node{ long long aa[50];}c[201][201];void jia(long long cc1,long long cc2){for (long long i=1;i<=50;i++) { c[cc1][cc2].aa[i]+=c[cc1-1][cc2].aa[i]+c[cc1-1][cc2-1].aa[i]; if (c[cc1][cc2].aa[i]>=100000000) { c[cc1][cc2].aa[i+1]+=c[cc1][cc2].aa[i]/100000000; c[cc1][cc2].aa[i]%=100000000; } }}void zuhe(int c1,int c2){ for (int i=1;i<=c1;i++) c[i][0].aa[1]=1;c[1][0].aa[1]=1;c[1][1].aa[1]=1; for (int i=2;i<=c1;i++) for (int j=1;j<=i;j++) jia(i,j); }int main(){ long long n; cin>>n; n-=2; zuhe(n*2,n+1); for (int i=1;i<=n;i++) { c[2*n][n].aa[i]-=c[2*n][n+1].aa[i]; if (c[2*n][n].aa[i]<0) { c[2*n][n].aa[i]+=mo; c[2*n][n].aa[i+1]--; } } int ji=49; while (c[2*n][n].aa[ji]==0) ji--; cout<<c[2*n][n].aa[ji]; for (int i=ji-1;i>=1;i--) printf("%08d",c[2*n][n].aa[i]); cout<<"Tas"; return 0; }//h(n)=c(2n,n)-c(2n,n+1)