卡塔兰数（Catalan number）：组合数学中的一列重要整数序列，常记为 \(C_n\)。它计数许多“结构相同但表述不同”的对象，例如：正确匹配的括号序列、不同形状的满二叉树、不过交的弦划分、Dyck 路径等。常用公式： \[ C_n=\frac{1}{n+1}\binom{2n}{n}\quad (n\ge 0) \]
/ˌkætəˈlæn ˈnʌmbər/
The third Catalan number is 5.
第三个卡塔兰数是 5。
Catalan numbers appear when counting the number of valid ways to parenthesize a product of \(n+1\) factors, which is equivalent to counting full binary tree shapes with \(n\) internal nodes.
在计算把 \(n+1\) 个因子的乘积进行合法加括号的方式数时会出现卡塔兰数；这等价于计算具有 \(n\) 个内部节点的满二叉树形状数量。
“Catalan number”得名于比利时数学家欧仁·卡塔兰（Eugène Charles Catalan, 1814–1894）。他在19世纪研究相关计数问题时使这一序列广为人知，后人便以其姓氏命名该数列。
Select Language