卡特蘭數(shù)的應(yīng)用：

1. 括號(hào)化問題。
   　　矩陣鏈乘： P=a1×a2×a3×……×an，依據(jù)乘法結(jié)合律疑苔，不改變其順序，只用括號(hào)表示成對(duì)的乘積甸鸟，試問有幾種括號(hào)化的方案惦费？(h(n)種)

2. 出棧次序問題兵迅。
   　　一個(gè)棧(無窮大)的進(jìn)棧序列為1,2,3,..n,有多少個(gè)不同的出棧序列?

3. 將多邊行劃分為三角形問題。
   　　將一個(gè)凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)?
   　　類似：在圓上選擇2n個(gè)點(diǎn),將這些點(diǎn)成對(duì)連接起來使得所得到的n條線段不相交的方法數(shù)?

4. 給頂節(jié)點(diǎn)組成二叉樹的問題薪贫。
   　　給定N個(gè)節(jié)點(diǎn)恍箭，能構(gòu)成多少種不同的二叉樹？（能構(gòu)成h（N）個(gè)）

C++

//卡特蘭數(shù)的大數(shù)算法
//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;  //數(shù)組每一位存放大數(shù)的四位數(shù)字瞧省，相當(dāng)于萬進(jìn)制

//大數(shù)乘
void multiply(int n, int x) {
    int add = 0;   //進(jìn)位
    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;
}

//大數(shù)除
void divide(int n, int x) {
    int re = 0;   //余數(shù)
    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;//去掉前導(dǎo)零
    }
    //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;//大數(shù)反向存放在數(shù)組中
    
    //預(yù)處理
    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時(shí)的答案的數(shù)組長(zhǎng)度扯夭。
    }   

    int n;
    while (scanf("%d", &n) != EOF) {
        int len = ans[n][0];
        printf("%d", ans[n][len]);//輸出最前面的數(shù)
        for (int i = len - 1; i >= 1; --i) {
            printf("%04d", ans[n][i]); //輸出后面的數(shù)，并每位都保持4位長(zhǎng)度!
        }
        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/
（很棒的總結(jié)）