关于Catalan数列|Fooage's Blog

卡特兰数列是组合数学中一个经常在各种计数问题中出现的数列。其实最早清朝数学家明安图在其《割圜密率捷法》中就已经发明了这种技术方法。Catalan数列中前几项为1 1 2 5 14 42 132 429 1430 4862 16796等，在解题过程中可以联系一下。它更像是一个由问题总结出来的数列，本身很难发现规律，个人的理解该数列经常和一些二分选择划分和有条件前缀排列问题的计数有关。

公式定义

没什么特别的，就和斐波那契数列一样可以通过某种特殊运算来获得各项，这里有通向、递归和递推的公式。

通项公式

通项公式由于需要算阶乘，所以时间复杂度比较高不经常采用。可以采用杨辉三角的计算方法在 $Ot(n^{2})$ 的时间复杂度内同时算出大量组合数。

\[f_{n}=\frac{C_{2n}^{n}}{n+1}\] \[f_{n}=C_{2n}^{n}-C_{2n}^{n-1}\]

递归公式

递归公式更像是一种划分两组的意义，具体的作用可以见二叉树的构成问题。

\[f_{n}=f_{0}f_{n-1}+f_{1}f_{n-2}+\cdots +f_{n-1}f_{0}\]

代码实现

int Catalan(int n) {
  memset(f, 0, sizeof(f));
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      f[i] = f[i] + f[j] * f[i - j - 1];
    }
  }
  return f[n];
}

递推公式

递推公式也是从组合数角度上的，直接表明了第 $n$ 项和第 $n-1$ 项之间的关系。

\[f_{n}=\frac{4n-2}{n+1}f_{n-1}\]

代码实现

// It is often mod by Fermat’s little theorem.
int Catalan(int n) {
  f[0] = 1;
  // initialize first element
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  }
  return f[n];
}

具体问题

既然卡特兰数列如此的抽象，那么就要结合实际情况看一看它到底解决什么问题。通常是一些计数问题，要满足一定合法条件。

前缀限定问题

前缀限定问题主要是一些对前缀有不过半的限定条件，比如从 $(0,0)$ 向右的次数不少于向上的次数来走到 $(n,n)$ ，可以看到每一次都有两个方向可以选择，为了满足条件不能触及 $y=x+1$ 这一条直线，所以总的方法数有 $C_{2n}^{n}-C_{2n}^{n-1}$ 其符合卡特兰数列。

二进制序列

有 $n$ 个1和同样数量的0组成序列，要求序列的任意一个前缀中1的个数都要大于0的个数，能够组成多少序列？同样的问题还有括号匹配的问题，只不过是将零和一换成了左括号和右括号。

栈重构序列

具体可以看https://www.luogu.com.cn/problem/P1044的描述，简单来讲就是将 $n$ 个数压进栈的进栈序列为 $1,2,3,\ldots ,n$ 有多少个不同的出栈序列。思路主要是如果进出栈的操作合法，那么前缀中出栈的次数就不能超过进栈的次数。又因为进出栈顺序会导致不同的结果序列，所以栈合法操作的序列个数就是序列种类数。由此延伸出312 序列个数，因为这种序列不可能由升序的进栈顺序用栈构造，所以答案显而易见。

划分问题

这个数列的提出就是从清朝数学家研究圆的分割时发现的，所以划分问题有时候也能够通过它解决。

不交弦

在圆上有 $2n$ 个不同的点，想用 $n$ 条线段把这些点连接起来，使所有的线段都不相交，这样的连接方案有多少种？割圆问题有https://www.luogu.com.cn/problem/P1976，要求线段不能相交，所以一条弦两边各有偶数个点才能够让他们不相交的相连。如果继续转换，即在任意前缀中起点的数量不能少于终点的数量，而其种类数又是经典的卡塔兰数列。

如果使用第二个递推公式的时间复杂度是： $O(n^{2})$

二叉树构成

二叉树的构成又是一个每步两选且有限定的问题， $n$ 个节点能够组成多少种不同的二叉树。每一个节点选择子节点的时候都分成两组刚好和递推公式 $f_{n}=f_{0}f_{n-1}+f_{1}f_{n-2}+\cdots +f_{n-1}f_{0}$ 表达的含义一样，又是一个典型的数列题。

fooage