Catalan数

该数列经常出现在计数问题中

特征

递推关系

\[ C_n = \begin{cases} 1, & n = 0, \\ \sum_{i=0}^{n-1} C_{i}C_{n-1-i}, & n > 0. \end{cases} \] 前几项为$1,1,2,5,14,42,132,429,1430,\cdots$

常见表达式

$C_n = = ,~ n. $

$ C_n = - ,~n .$

$ C_n = C_{n-1},~ n > 0,~ C_0 = 1.$

前两个形式将它转换为阶乘和组合数的计算问题，第三个形式则提供了顺次计算的递推公式

应用

规模为$n$的计数问题$C_n$，可以通过枚举分界点，拆分为两个规模分别为$i$和$(n-1-i)$的子问题

因此Catalan数广泛用于各类具有类似递归结构的问题中

路径计数问题

有一个大小为$n\times n$的方格图，左下角为$(0,0)$，右上角为$(n,n)$，从左下角开始，每次向右或向上走一单位，不走到$y=x$上方（但可以触碰）的情况下，到达右上角的路径总数为$C_n$

总的路径数为 $\binom{2n}{n}$。不合法的路径恰好可以与到 $(n,n+1)$ 的路径建立一一对应，从而得到不合法路径数为 $\binom{2n}{n+1}$，所以合法的为二者之差。

圆内不相交弦计数/圆上点配对问题

圆上有$2n$个点，将这些点成对连接起来且使得所得到的$n$条线段两两不相交的方案数是$C_n$

将点按顺序编号，考虑与编号1配对的点k，将圆分成两部分，每部分再独立配对，得到递推

多边形剖分三角计数问题

对角线不相交的情况下，将一个凸$n+2$边形区域分为三角形区域的方法数为$C_n$

固定某个顶点，把与该顶点连成三角形的另一顶点作为切点，分割成左右两个子问题，变为递推形式

二叉树计数问题

含有$n$个结点的形态不同的二叉树数目为$C_n$。等价的，含有$n$个非叶结点的形态不同的满二叉树数目为$C_n$。

含有$n$内部结点的满二叉树个数为$C_n$

选择某个元素作根，左子树大小为 $i$，右子树大小为 $n−1−i$，左右子树独立，乘法得到递推。

括号序列计数问题

由$n$对括号构成的合法括号序列数为$C_n$。

可以映射为路径问题

出栈序列计数问题/避免模式排列问题

一个栈进栈序列为$1,2,3,\cdots,n$，合法出栈序列数目为$C_n$

可以映射为括号序列问题

数列计数问题

由$n$个$+1$与$n$个$-1$组成的数列$a_1,a_2, \ldots ,a_{2n}$，部分和满足$a_1+a_2+ \ldots +a_k \geq 0~(k=1,2,3, \ldots ,2n)$的数列数目为$C_n$