卡特兰数的应用：
括号化问题。
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)出栈次序问题。
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?将多边行划分为三角形问题。
将一个凸多边形区域分成三角形区域的方法数?
类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?给顶节点组成二叉树的问题。
给定N个节点，能构成多少种不同的二叉树？（能构成h（N）个）
C++
//卡特兰数的大数算法
//1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796(0--10)
//公式：f(n) = f(n - 1) * (4 * n - 2) / (n + 1);
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 100 + 10;
int ans[105][MAX_N];//ans[n][i]
int id;
int base = 10000; //数组每一位存放大数的四位数字，相当于万进制
//大数乘
void multiply(int n, int x) {
int add = 0; //进位
for (int i = 1; i <= id || add; ++i) {
ans[n][i] = ans[n][i] * x + add;
add = ans[n][i] / base;
ans[n][i] %= base;
if (i > id) id = i;
}
//cout << add << endl;
}
//大数除
void divide(int n, int x) {
int re = 0; //余数
bool flag = true;
for (int i = id; i >= 1; --i) {
ans[n][i] = re * base + ans[n][i];
re = ans[n][i] % x;
ans[n][i] /= x;
if (ans[n][i] != 0) flag = false;
if (flag && ans[n][i] == 0) --id;//去掉前导零
}
//cout << re << endl;
}
int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
ans[0][0] = ans[0][1] = 1;//f(0) = 1
id = 1;//大数反向存放在数组中
//预处理
for (int i = 1; i <= 100; ++i) {
for (int j = 1; j <= id; ++j) ans[i][j] = ans[i - 1][j];
multiply(i, 4 * i - 2);
divide(i, i + 1);
ans[i][0] = id; //ans[i][0]存放n为i时的答案的数组长度。
}
int n;
while (scanf("%d", &n) != EOF) {
int len = ans[n][0];
printf("%d", ans[n][len]);//输出最前面的数
for (int i = len - 1; i >= 1; --i) {
printf("%04d", ans[n][i]); //输出后面的数，并每位都保持4位长度!
}
printf("\n");
}
return 0;
}
//f(100) = 896519947090131496687170070074100632420837521538745909320
Java
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
BigInteger[] ans = new BigInteger[105];
ans[0] = BigInteger.valueOf(1);
for (int i = 1; i <= 100; ++i) {
ans[i] = ans[i - 1].multiply(BigInteger.valueOf(4 * i - 2)).divide(BigInteger.valueOf(i + 1));
}
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
System.out.println(ans[n]);
}
in.close();
}
}
本文参考自博客：http://blog.163.com/lz_666888/blog/static/1147857262009914112922803/
（很棒的总结）
