卡塔兰数
维基百科，自由的百科全书
 |
本條目正在從en:catalan number翻譯成中文。 歡迎您積極參與翻譯與修訂。 |
Catalan number是組合數學中一個常出現在各種計數問題中出現的數列。由以比利時的數學家Eugène Charles Catalan (1814–1894)命名。
Catalan number的一般項公式為 
前幾項為: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
[编辑] 性質
Catalan number的遞迴式為: 
或是: 
上式提供了一個較快速的方法計算catalan number.
Asymptotically, the Catalan numbers grow as
in the sense that the quotient of the nth Catalan number and the expression on the right tends towards 1 for n → ∞. (This can be proved by using Stirling's approximation for n!.)
[编辑] 應用
組合數學中有非常多的組合結構是用catalan number計數的。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一書中的習題中包含了66個相異的組合結構用catalan number計數。以下是一些例子(用C3 = 5舉例：
- 長度2n的dyck word的數量，dyck word是一個有n個X和n個Y組成的字串，且字串的所有prefix皆滿足X的個數
Y的個數。以下是長度6的dyck word:
- 將上例的X換成左括號，Y換成右括號，Cn表示所有包含n組括號的合法運算式的數量:
- Cn表示有n + 1個葉子的二元樹的數量。
