卡特蘭數：組合數學中的神奇數列與算法應用

什麼是卡特蘭數

卡特蘭數（Catalan Number）是組合數學中一個極其重要的數列，由比利時數學家歐仁·查理·卡特蘭在研究凸多邊形三角剖分問題時發現。該數列在計算機科學、圖論、代數幾何等領域廣泛出現，Richard Stanley曾收集超過200種等價的組合解釋。

數學定義與前幾項

遞推公式：

C₀ = 1
Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ × Cₙ₋₁₋ᵢ  (n ≥ 1)

通項公式：

Cₙ = (1/(n+1)) × C(2n, n) = (2n)! / ((n+1)! n!)

前16項：

經典組合模型（任一模型計數均為卡特蘭數）

1. 凸多邊形三角剖分：凸 (n+2) 邊形用 n-1 條不相交對角線分割為三角形的方案數
2. 合法括號序列：n對括號構成的合法匹配序列數（如 n=3: ((())), (()()), (())(), ()(()), ()()()）
3. 棧排列：1..n 入棧，出棧序列的合法排列數
4. 二叉樹形態：n個節點的不同二叉樹結構數
5. 不超過對角線的路徑：n×n網格中從(0,0)到(n,n)不超過對角線y=x的路徑數
6. 洗碗堆碗問題：n個碗洗完疊入櫃，姐姐洗、妹妹疊，可能的疊放順序數

算法競賽經典題目：POJ 1095 - 二叉樹構造

問題描述

給定編號 n，構造第 n 棵二叉樹（按特定順序編號），輸出其結構表示。

解題思路：三步遞歸定位

1. 確定節點總數：依次減去 C₁, C₂, C₃... 直到無法減，剩餘即為節點數 k，總節點 = k+1（含根）
2. 確定左右子樹節點數：對於 k 個非根節點，枚舉左子樹節點數 i (0≤i≤k)，右子樹 k-i。依次減去 Cᵢ × Cₖ₋ᵢ 直到無法減，確定左子樹節點數 = j+1
3. 確定左右子樹編號：左子樹為具有 j+1 節點的第 x 棵，右子樹為具有 k-j-1 節點的第 y 棵。n 除以 Cₖ₋ⱼ₋₁，商為 x，餘數為 y

核心代碼框架

// 預計算卡特蘭數 C[0..19] (C[19] < 2^31)
long long C[20];
void initCatalan() {
    C[0] = 1;
    for (int i = 1; i < 20; i++) {
        C[i] = 0;
        for (int j = 0; j < i; j++)
            C[i] += C[j] * C[i-1-j];
    }
}

// 遞歸構造二叉樹
void buildTree(int n) {  // n: 當前子樹的編號
    if (n == 0) return;  // 空樹
    
    // 1. 找節點數
    int nodes = 1;
    while (n > C[nodes]) n -= C[nodes++];
    // 當前子樹共 nodes 個節點（含根）
    
    // 2. 找左子樹節點數
    int leftNodes = 0;
    while (n > C[leftNodes] * C[nodes-1-leftNodes]) {
        n -= C[leftNodes] * C[nodes-1-leftNodes];
        leftNodes++;
    }
    int rightNodes = nodes - 1 - leftNodes;
    
    // 3. 找左右子樹編號
    int leftIdx = (n - 1) / C[rightNodes] + 1;
    int rightIdx = (n - 1) % C[rightNodes] + 1;
    
    // 輸出當前根，遞歸處理左右子樹
    printf("X");  // 或根據題目要求輸出具體表示
    if (leftNodes > 0) buildTree(leftIdx);
    if (rightNodes > 0) buildTree(rightIdx);
}

計算卡特蘭數的高效方法

動態規劃 O(n²)

C[0] = 1;
for (int i = 1; i <= N; i++) {
    C[i] = 0;
    for (int j = 0; j < i; j++)
        C[i] += C[j] * C[i-1-j];
}

遞推公式 O(n) - 利用 Cₙ = Cₙ₋₁ × (2(2n-1))/(n+1)

C[0] = 1;
for (int i = 1; i <= N; i++)
    C[i] = C[i-1] * 2 * (2*i - 1) / (i + 1);  // 整除無餘數

大數處理

n > 19 時超過 64 位整數範圍，需使用高精度庫（Java BigInteger、Python 原生大整數、C++ 自定義大數類或 GMP）。

總結

卡特蘭數是連接組合數學與計算機科學的橋樑。掌握其遞推定義、通項公式、經典模型、動態規劃計算，能靈活解決二叉樹計數、括號匹配、棧排列、路徑計數等大類問題。在算法競賽中，識別「卡特蘭數模型」往往是破題關鍵。