Catalan数

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

特征

递推关系

前几项为

常见表达式

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

应用

规模为的计数问题，可以通过枚举分界点，拆分为两个规模分别为和的子问题

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

路径计数问题

有一个大小为的方格图，左下角为，右上角为，从左下角开始，每次向右或向上走一单位，不走到上方（但可以触碰）的情况下，到达右上角的路径总数为

总的路径数为 。不合法的路径恰好可以与到 的路径建立一一对应，从而得到不合法路径数为 ，所以合法的为二者之差。

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

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

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

多边形剖分三角计数问题

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

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

二叉树计数问题

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

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

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

括号序列计数问题

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

可以映射为路径问题

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

一个栈进栈序列为，合法出栈序列数目为

可以映射为括号序列问题

数列计数问题

由个与个组成的数列，部分和满足的数列数目为

可以映射为括号序列问题

e.g. P1044 栈

1
2
3
4
5
6
7
8
9
10
11
12
13

vector<ll> cat(20);
void init(){
  cat[0]=cat[1]=1;
  for (int i = 2;i<20;i++){
    cat[i] = cat[i-1]*(4*i-2)/(i+1);

  }
}
void solve() {
  int n;
  cin >> n;
  cout << cat[n]<<endl;
}