卡特蘭數生成器
生成第 n 個卡特蘭數，包含逐步公式推導、括號化與多邊形三角剖分的互動式視覺化、完整序列對照表，以及針對數學、計算機科學與競賽程式設計的深度組合數學解釋。
偵測到廣告封鎖，導致我們無法顯示廣告
MiniWebtool 依靠廣告收入免費提供服務。如果這個工具幫到你，歡迎升級 Premium（無廣告 + 更快），或將 MiniWebtool.com 加入允許清單後重新整理頁面。
- 或升級 Premium（無廣告）
- 允許 MiniWebtool.com 顯示廣告，然後重新載入
卡特蘭數生成器
歡迎使用卡特蘭數生成器，這是一個用於計算和探索卡特蘭數（數學中最迷人的序列之一）的全面工具。無論您是在學習組合數學、準備競賽程式設計，還是研究代數結構，此計算機都能提供 Cn 的精確值，以及逐步推導、互動式 Dyck 路徑視覺化、平衡括號列舉和深入的組合解釋。
什麼是卡特蘭數？
卡特蘭數（Catalan numbers）是一個自然數序列，出現在組合數學中極其多樣的計數問題中。序列如下開始：
C0=1, C1=1, C2=2, C3=5, C4=14, C5=42, C6=132, C7=429, ...
這些數字以比利時數學家歐仁·查理·卡特蘭（Eugène Charles Catalan, 1814–1894）的名字命名，但實際上是由萊昂哈德·歐拉在 1750 年代首先發現的，當時他用這些數字來計算凸多邊形的三角剖分數。該序列在 OEIS（整數序列線上百科全書）中被編號為 A000108。
閉式公式
遞迴關係
生成函數
卡特蘭數的普通生成函數為：
組合解釋
卡特蘭數可以回答極其大量的計數問題。數學家 Richard Stanley 目錄化了超過 200 種不同的組合解釋。以下是最重要的一些：
1. 平衡括號
Cn 計算正確匹配 n 對括號的方法數。例如，C3 = 5，因為 3 對括號恰好有 5 種有效排列：((()))、(()())、(())()、()(()) 和 ()()()。
2. Dyck 路徑
Cn 是 Dyck 路徑 的數量 —— 即從 (0,0) 到 (2n,0) 的單調格點路徑，使用步長 U=(1,1) 和 D=(1,−1)，且永遠不會跌至 x 軸以下。等效地，這些是在 n×n 網格中從左下角到右上角、保持在對角線上或下方的路徑。
3. 多邊形三角剖分
Cn 計算通過繪製不相交的對角線，將具有 n+2 條邊的凸多邊形進行三角剖分的方法數。這是歐拉最初導致發現該序列的問題。
4. 滿二元樹
Cn 計算具有 n+1 個葉節點（等效於 n 個內部節點）的滿二元樹（每個節點有 0 或 2 個子節點）的數量。這與具有 n 個鍵的不同二元搜尋樹的數量密切相關。
5. 山脈形狀
Cn 是可以用 n 個上坡和 n 個下坡繪製的山脈輪廓數量。這些在視覺上與 Dyck 路徑相同，但被解釋為景觀剪影。
6. 非交叉劃分
Cn 等於集合 {1, 2, ..., n} 的非交叉劃分數量。這些劃分具有如下性質：當在圓上繪製時，沒有兩個塊會彼此「交叉」。
如何使用此計算機
- 輸入 n： 在輸入欄位中輸入 0 到 500 之間的非負整數。可以使用快速範例按鈕選取常用值。
- 點擊生成： 按下「生成卡特蘭數」按鈕以計算 Cn。
- 查看結果： 查看 Cn 的確切值、其位數、逐步公式推導以及遞迴關係驗證。
- 探索視覺化： 對於較小的 n (≤ 4)，瀏覽所有平衡括號。對於 n ≤ 5，查看互動式 Dyck 路徑圖。
- 瀏覽序列： 滾動查看卡特蘭數表，其中高亮顯示了您計算的數值。
漸近增長
卡特蘭數呈指數級增長。漸近公式為：
這意味著 Cn 大致以 4n 的速度增長，但帶有多項式修正因子。隨著 n 變大，比率 Cn/Cn-1 趨近於 4。
在電腦科學中的應用
| 應用領域 | Cn 計算的內容 |
|---|---|
| 二元搜尋樹 | 具有 n 個鍵的不同 BST 數量 |
| 矩陣鏈乘法 | 對 n+1 個矩陣的乘積加括號的方法 |
| 堆疊可排序排列 | 可通過單個堆疊排序的 {1,...,n} 的排列 |
| 表達式解析 | n 個運算子表達式的不同解析樹 |
| 遞迴演算法 | 競賽程式設計中動態規劃問題的基礎 |
其他領域中的卡特蘭數
- 代數幾何： 出現在格拉斯曼流形（Grassmannians）和舒伯特演算（Schubert calculus）的研究中。
- 機率論： 與選票問題（ballot problem）和隨機遊走理論相關。
- 數學物理： 與量子場論中的平面圖相關。
- 語言學： 計算給定長度句子的語法解析樹數量。
常見問題解答
什麼是卡特蘭數？
卡特蘭數是一個自然數序列（1, 1, 2, 5, 14, 42, 132, ...），出現在組合數學的許多計數問題中。第 n 個卡特蘭數由公式 Cn = (2n)! / ((n+1)! × n!) = C(2n,n) / (n+1) 給出。它們計算平衡括號、二元樹、多邊形三角剖分和 Dyck 路徑等結構。
如何計算第 n 個卡特蘭數？
可以使用直接公式 Cn = C(2n,n)/(n+1) 來計算第 n 個卡特蘭數，其中 C(2n,n) 是中心二項式係數。或者，您可以使用遞迴關係 Cn = 2(2n−1)/(n+1) × Cn−1，其中 C0 = 1。對於較大的 n，漸近近似公式 Cn ≈ 4n / (√(πn) × (n+1)) 可以提供良好的估計。
卡特蘭數計算的是什麼？
卡特蘭數計算了極其廣泛的組合結構：正確匹配 n 對括號的方法數、具有 n 個內部節點的滿二元樹數量、長度為 2n 的 Dyck 路徑數量、將具有 n+2 條邊的凸多邊形進行三角剖分的方法數、集合的非交叉劃分數量，以及超過 200 種其他已知的解釋。
卡特蘭數增長有多快？
卡特蘭數呈指數級增長。其漸近公式為 Cn ~ 4n / (n3/2 × √π)，這意味著它們大致以 4 的冪次方增長。例如，C10 = 16,796，C20 = 6,564,120,420，而 C100 則有 58 位數。隨著 n 的增加，比率 Cn/Cn−1 趨近於 4。
卡特蘭數在電腦科學中應用於何處？
在電腦科學中，卡特蘭數出現在：計算具有 n 個鍵的不同二元搜尋樹的數量、解析具有 n 個運算子的表達式的方法數、堆疊可排序排列、相乘 n+1 個矩陣鏈的方法數（與矩陣鏈乘法相關），以及競賽程式設計中的各種動態規劃問題。
其他資源
引用此內容、頁面或工具為：
"卡特蘭數生成器" 於 https://MiniWebtool.com/zh-tw//，來自 MiniWebtool，https://MiniWebtool.com/
由 miniwebtool 團隊製作。更新日期：2026年2月19日
您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。