卡特蘭數生成器

歡迎使用卡特蘭數生成器，這是一個用於計算和探索卡特蘭數（數學中最迷人的序列之一）的全面工具。無論您是在學習組合數學、準備競賽程式設計，還是研究代數結構，此計算機都能提供 C_n 的精確值，以及逐步推導、互動式 Dyck 路徑視覺化、平衡括號列舉和深入的組合解釋。

什麼是卡特蘭數？

卡特蘭數（Catalan numbers）是一個自然數序列，出現在組合數學中極其多樣的計數問題中。序列如下開始：

C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, C₆=132, C₇=429, ...

這些數字以比利時數學家歐仁·查理·卡特蘭（Eugène Charles Catalan, 1814–1894）的名字命名，但實際上是由萊昂哈德·歐拉在 1750 年代首先發現的，當時他用這些數字來計算凸多邊形的三角剖分數。該序列在 OEIS（整數序列線上百科全書）中被編號為 A000108。

閉式公式

遞迴關係

生成函數

卡特蘭數的普通生成函數為：

組合解釋

卡特蘭數可以回答極其大量的計數問題。數學家 Richard Stanley 目錄化了超過 200 種不同的組合解釋。以下是最重要的一些：

1. 平衡括號

C_n 計算正確匹配 n 對括號的方法數。例如，C₃ = 5，因為 3 對括號恰好有 5 種有效排列：((()))、(()())、(())()、()(()) 和 ()()()。

2. Dyck 路徑

C_n 是 Dyck 路徑 的數量 —— 即從 (0,0) 到 (2n,0) 的單調格點路徑，使用步長 U=(1,1) 和 D=(1,−1)，且永遠不會跌至 x 軸以下。等效地，這些是在 n×n 網格中從左下角到右上角、保持在對角線上或下方的路徑。

3. 多邊形三角剖分

C_n 計算通過繪製不相交的對角線，將具有 n+2 條邊的凸多邊形進行三角剖分的方法數。這是歐拉最初導致發現該序列的問題。

4. 滿二元樹

C_n 計算具有 n+1 個葉節點（等效於 n 個內部節點）的滿二元樹（每個節點有 0 或 2 個子節點）的數量。這與具有 n 個鍵的不同二元搜尋樹的數量密切相關。

5. 山脈形狀

C_n 是可以用 n 個上坡和 n 個下坡繪製的山脈輪廓數量。這些在視覺上與 Dyck 路徑相同，但被解釋為景觀剪影。

6. 非交叉劃分

C_n 等於集合 {1, 2, ..., n} 的非交叉劃分數量。這些劃分具有如下性質：當在圓上繪製時，沒有兩個塊會彼此「交叉」。

如何使用此計算機

1. 輸入 n： 在輸入欄位中輸入 0 到 500 之間的非負整數。可以使用快速範例按鈕選取常用值。
2. 點擊生成： 按下「生成卡特蘭數」按鈕以計算 C_n。
3. 查看結果： 查看 C_n 的確切值、其位數、逐步公式推導以及遞迴關係驗證。
4. 探索視覺化： 對於較小的 n (≤ 4)，瀏覽所有平衡括號。對於 n ≤ 5，查看互動式 Dyck 路徑圖。
5. 瀏覽序列： 滾動查看卡特蘭數表，其中高亮顯示了您計算的數值。

漸近增長

卡特蘭數呈指數級增長。漸近公式為：

這意味著 C_n 大致以 4ⁿ 的速度增長，但帶有多項式修正因子。隨著 n 變大，比率 C_n/C_n-1 趨近於 4。

在電腦科學中的應用

其他領域中的卡特蘭數

• 代數幾何： 出現在格拉斯曼流形（Grassmannians）和舒伯特演算（Schubert calculus）的研究中。
• 機率論： 與選票問題（ballot problem）和隨機遊走理論相關。
• 數學物理： 與量子場論中的平面圖相關。
• 語言學： 計算給定長度句子的語法解析樹數量。

常見問題解答

什麼是卡特蘭數？

卡特蘭數是一個自然數序列（1, 1, 2, 5, 14, 42, 132, ...），出現在組合數學的許多計數問題中。第 n 個卡特蘭數由公式 C_n = (2n)! / ((n+1)! × n!) = C(2n,n) / (n+1) 給出。它們計算平衡括號、二元樹、多邊形三角剖分和 Dyck 路徑等結構。

如何計算第 n 個卡特蘭數？

可以使用直接公式 C_n = C(2n,n)/(n+1) 來計算第 n 個卡特蘭數，其中 C(2n,n) 是中心二項式係數。或者，您可以使用遞迴關係 C_n = 2(2n−1)/(n+1) × C_n−1，其中 C₀ = 1。對於較大的 n，漸近近似公式 C_n ≈ 4ⁿ / (√(πn) × (n+1)) 可以提供良好的估計。

卡特蘭數計算的是什麼？

卡特蘭數計算了極其廣泛的組合結構：正確匹配 n 對括號的方法數、具有 n 個內部節點的滿二元樹數量、長度為 2n 的 Dyck 路徑數量、將具有 n+2 條邊的凸多邊形進行三角剖分的方法數、集合的非交叉劃分數量，以及超過 200 種其他已知的解釋。

卡特蘭數增長有多快？

卡特蘭數呈指數級增長。其漸近公式為 C_n ~ 4ⁿ / (n^3/2 × √π)，這意味著它們大致以 4 的冪次方增長。例如，C₁₀ = 16,796，C₂₀ = 6,564,120,420，而 C₁₀₀ 則有 58 位數。隨著 n 的增加，比率 C_n/C_n−1 趨近於 4。

卡特蘭數在電腦科學中應用於何處？

在電腦科學中，卡特蘭數出現在：計算具有 n 個鍵的不同二元搜尋樹的數量、解析具有 n 個運算子的表達式的方法數、堆疊可排序排列、相乘 n+1 個矩陣鏈的方法數（與矩陣鏈乘法相關），以及競賽程式設計中的各種動態規劃問題。

其他資源

• 卡特蘭數 - 維基百科
• A000108 - OEIS (卡特蘭數)