卡特兰数详解

卡特兰数

一、基础公式

定义式

• $f[n]=\sum\limits_{i=0}^{n-1}f[i]*f[n-1-i]$f[n]=i=0∑n−1​f[i]∗f[n−1−i]

组合数公式 (用生成函数推导定义式)

• $f[n]=C_{2n}^n-C_{2n}^{n-1}$f[n]=C2nn​−C2nn−1​
• $f[n]=\displaystyle\frac{C_{2n}^n}{n+1}$f[n]=n+1C2nn​​
• $f[n]=\displaystyle\frac{4n-2}{n+1}*f[n-1]$f[n]=n+14n−2​∗f[n−1]

卡特兰数列

• $f[0]=1,f[1]=1,f[2]=2,f[3]=5...$f[0]=1,f[1]=1,f[2]=2,f[3]=5...
• $1$1,$1$1,$2$2,$5$5,$14$14,$42$42,$132$132,$429$429,$1430$1430,$4862$4862,$16796$16796,$58786$58786,$208012...$208012...

二、应用方向

括号匹配问题

• $n$n 个左括号，$n$n 个右括号，对于每一个位置，左括号数大于等于右括号数的方案总数。
• 等价于 $n$n 个 $1$1，$n$n 个 $-1$−1，每个位置前缀和大于等于 $0$0 的方案总数。
• 两种理解方向：

1. $f[n]=\sum\limits_{i=0}^{n-1}f[i]*f[n-1-i]$f[n]=i=0∑n−1​f[i]∗f[n−1−i]。枚举第一次前缀和为 $0$0 的位置，假如第 $2*x$2∗x 个点为第一次前缀和为 $0$0 的点，则固定第一个数为 $1$1，第 $x$x 个数为 $-1$−1，则对答案贡献为 $f[x-1]*f[n-x]$f[x−1]∗f[n−x]。
2. $f[n]=C_{2n}^n-C_{2n}^{n-1}$f[n]=C2nn​−C2nn−1​。总方案数为 $C_{2n}^n$C2nn​，现需求不符合条件的方案数，将问题转化为网格上的折线问题。第 $i$i 次在 $(i,j)$(i,j) 处，第 $i+1$i+1 次在 $(i+1,j+1)$(i+1,j+1) 或 $(i+1,j-1)$(i+1,j−1) 处，终点为 $(2n,0)$(2n,0)。不符合条件则说明折线上出现了 $(x,-1)$(x,−1) 这个点，$x$x 为第一次到达 $-1$−1 的点，我们将 $x$x 点之后的折线沿 $y=-1$y=−1 对称过来，则终点为 $(2n,-2)$(2n,−2)，则一共有 $n-1$n−1 个 $1$1，$n+1$n+1 个 $-1$−1，即不合法的方案总数为 $C_{2n}^{n-1}$C2nn−1​，因此 $f[n]=C_{2n}^n-C_{2n}^{n-1}$f[n]=C2nn​−C2nn−1​。
   

出栈次序问题

• 一个无穷大的栈，进栈序列为 $1,2,3...n$1,2,3...n，求有多少个不同的出栈序列。

多边划分为三角形问题

• 将一个凸多边形区域分成三角形区域的方案数。
• 在圆上选择 $2*n$2∗n 个点，将这些点对连接起来使得所得到的 $n$n 条线段不想交的方案数。

二叉树计数问题

• 给定 $n$n 个节点，能构成多少种形状不同的二叉树。
• 先取一个点作为顶点，然后左边依次可以取 $0～n-1$0～n−1 个点，右边则可以取 $n-1～0$n−1～0 个点，相乘再累加即可得到答案。