卡特兰数 卡特兰数是组合数学中一个常见的数列，出现在许多计数问题中。它的定义如下： 第 \( n \) 个卡特兰数 \( C_ n \) 的公式为： \[ C_ n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \, n !} \] 其中 \( \binom{2n}{n} \) 是二项式系数。 1. 基本例子：括号匹配问题 考虑 \( n \) 对括号的合法匹配序列数。例如： \( n=1 \)： () ，只有 1 种。 \( n=2 \)： ()() 和 (()) ，共 2 种。 \( n=3 \)： ()()() 、 (())() 、 ()(()) 、 (()()) 、 ((())) ，共 5 种。 这些数量正好对应卡特兰数 \( C_ n \)。 2. 递推关系 卡特兰数满足递推公式： \[ C_ 0 = 1, \quad C_ {n+1} = \sum_ {i=0}^{n} C_ i C_ {n-i} \] 例如： \[ C_ 3 = C_ 0C_ 2 + C_ 1C_ 1 + C_ 2C_ 0 = 1\cdot 2 + 1\cdot 1 + 2\cdot 1 = 5 \] 递推意义：将问题划分为独立的子问题（如括号序列分割为首对括号内和外的部分）。 3. 其他经典模型 卡特兰数还出现在以下问题中： 二叉树的计数 ：\( n \) 个节点的不同构满二叉树数量为 \( C_ n \)。 网格路径计数 ：从 \( (0,0) \) 到 \( (n,n) \) 的路径，只向右或向上走，且不越过对角线，路径数为 \( C_ n \)。 凸多边形的三角剖分 ：\( n+2 \) 边形的三角剖分方案数为 \( C_ n \)。 4. 通项公式的推导思路 利用“反射原理”计算网格路径： 无限制路径总数为 \( \binom{2n}{n} \)。 减去越过对角线的路径（反射后等价于非法路径），得到 \( \frac{1}{n+1} \binom{2n}{n} \)。 5. 增长趋势 卡特兰数渐近增长为： \[ C_ n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}} \] 当 \( n \) 较大时，约按指数级增长。 通过以上步骤，你可以逐步理解卡特兰数的定义、性质和应用场景。