卡特兰数整理笔记

一、卡特兰数基础定义

卡特兰数是组合数学中一类经典的数列，其前几项的数值序列为： $$1, 1, 2, 5, 14, 42, 132, 429, 1430...$$

核心递推关系

卡特兰数的递推定义可以通过组合场景推导得出，最基础的递推形式为： $f(n) = \sum_{i=0}^{n-1} f(i) \times f(n-1-i)$ 其中边界条件为 $f(0)=1$，$f(1)=1$。

二、卡特兰数通项公式

通过组合数学推导，可以得到卡特兰数的通项表达式： $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{C_{2n}^n}{n+1}$ 进一步展开可以写作： $C_n = \binom{2n}{n} - \binom{2n}{n-1}$

三、卡特兰数的经典应用场景

卡特兰数可以解决大量具有“合法前缀约束”的组合计数问题，典型场景包括： 1. ‌括号匹配问题‌：n对括号的合法匹配方案数，对应卡特兰数第n项。 2. ‌出栈序列计数‌：1~n依次入栈，不同的合法出栈序列总数为卡特兰数第n项。 3. ‌二叉树形态计数‌：n个节点构成的不同结构二叉树的总数为卡特兰数第n项。 4. ‌路径不相交问题‌：在网格中从原点走到(n,n)，仅向右/向上走，且路径始终不越过对角线y=x的合法路径总数，对应卡特兰数第n项。

四、网格路径的几何直观推导

以2×2的网格路径为例，所有从(0,0)到(n,n)的路径总数为 $\binom{2n}{n}$，其中越过对角线的非法路径可以通过“反射法”映射到另一个等价的路径集合，非法路径总数为 $\binom{2n}{n-1}$，二者相减即可直接推导出卡特兰数的通项公式，和前文给出的 $C_n = \binom{2n}{n} - \binom{2n}{n-1}$ 完全吻合。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com