前言

如果你对这篇文章可感兴趣，可以点击「【访客必读 – 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

卡特兰数

一、基础公式

定义式

• f[n]=∑i=0n−1f[i]∗f[n−1−i]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]=C2nn−C2nn−1f[n]=C_{2n}^n-C_{2n}^{n-1}f[n]=C2nn​−C2nn−1​
• f[n]=C2nnn+1f[n]=\displaystyle\frac{C_{2n}^n}{n+1}f[n]=n+1C2nn​​
• f[n]=4n−2n+1∗f[n−1]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...$
• $1$,$1$,$2$,$5$,$14$,$42$,$132$,$429$,$1430$,$4862$,$16796$,$58786$,$208012...$

二、应用方向

括号匹配问题

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

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

出栈次序问题

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

多边划分为三角形问题

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

二叉树计数问题

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