卡特兰数 Catalan 数列

引入

有一个无限大的栈，进栈的顺序为 \(1,2,\cdots,n\)，求有多少种不同的出栈序列。

设 \(h[n]\) 为 \(n\) 个数的出栈序列方案数。

可以这样想 \(k\) 是最后一个出栈的数，那么比 \(k\) 早进栈早出栈的有 \(k-1\) 个，方案数也就是 \(h[k-1]\)。同理比 \(k\) 晚进栈早出栈的方案数就是 \(h[n-k]\)，那么 \(k\) 作为最后一个出栈的数贡献的方案数为 \(h[k-1]h[n-k]\)。

由于 \(1\) 到 \(n\) 中任何一个数都可以成为 \(k\)，那么 \(h[n]\) 的方案数就是 \(h[n]=\sum_{i=1}^n h[i-1]h[n-i]\)。

\(h\) 就是卡特兰数列。

应用问题

• 1.有 \(2n\) 个人排队买票，票 \(5\) 元一张。有 \(n\) 个人有 \(5\) 元钞票，另外 \(n\) 个人有 \(10\) 元钞票，售票处没有其它钞票，求有多少种排队顺序不会使售票处无法找零。

  分析：每一个 \(10\) 元的钞票都需要一个 \(5\) 元的钞票，不妨把 \(5\) 元看成进栈 \(10\) 元看成出栈，每一种出栈序列对应一种排队方案，问题变为引入问题，答案为 \(h[n]\)。

• 2.学校在坐标 \((n,n)\) 处，每天彬彬上学会从 \((0,0)\) 出发，向 \(x\) 轴正方向走 \(n\) 步，向 \(y\) 轴正方向走 \(n\) 步，求不穿过（可以碰到）\((n,n)\) 与 \((0,0)\) 对角线（即直线 \(y=x\)）的路径数（只走直线 \(y=x\) 下方）。

  分析：如果想不穿过对角线那么可以移动看做进栈和出栈。如上题，一种出栈序列对应一种路径方案，答案为 \(h[n]\)。

总结：对于一些问题，可以转换成不同出栈序列的问题，那么便可以由卡特兰数得到。

• 3.有一个 \(n\) 条边的凸多边形，用直线连接对角线，使该多边形分为多个三角形，每条直线不相交，问有多少种划分方法。

  分析：我们先将多边形顺序编号 \(p_1,p_2,\cdots,p_n\)，选择基边 \(p_1p_n\)，再任选一个点 \(p_k\ (2\leq k \leq n-1)\)，连接 \(p_1p_k,p_np_k\)，这样（除连接的三角形外）将多边形重新分为了一个 \(k\) 边型和 \(n-k+1\) 边型，那么设 \(f[n]\) 为 \(n\) 边型的答案，有 \(f[n]=\sum_{i=1}^n h[i-1]h[n-i]\)。这正是卡特兰数的递推公式。

• 4.圆环上有 \(2n\) 个点，求点成对连接，线段不相交的方案数。

  分析：和上述一样，选择后点对后会分为两部分，将两部分独立处理即可。

总结：如果一个问题可以通过枚举来分为两部分，通过乘法和加法原理得到相同的递推式，那么也是卡特兰数列。在做题中，我们可以先设 \(dp\) 在推式子，得出 \(dp\) 的递推公式，再来判断卡特兰数；或者先看能否分为两部分，再推式子。

公式

使用应用问题 \(2\) 推导：

先不管不管对角线限制，从 \((0,0)\) 到 \((n,n)\) 的路径数为 \(C_{2n}^n\)。

在减去穿过对角的路径数，即减去触碰到 \(y=x+1\) 的直线的路径数。

把一条路径碰到 \(y=x+1\) 之前的路径以 \(y=x+1\) 为对称轴翻转，发现每次的起点都变成 \((-1,1)\)。

图中黄线为原触碰 \(y=x+1\) 的路径，灰色为关于 \(y=x+1\) 翻折的部分。

那么不合法线段的选择数就是从 \((-1,1)\) 走到 \((n,n)\) 的方案数。（无论怎么走都会触碰红线）

那么合法的方案数就是 \(总方案数-不合法方案数\)，即 \(h[n]=C_{2n}^n-c_{2n}^{n-1}\)。

化简后变得到了 \(h[n]\) 的递推式，\(h[n]=C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}\)。