前言

今天打个人排位赛被打自闭了。大佬们都会HDU 4828 (opens new window)，我却连卡特兰数是啥都不知道。

例题引入洛谷P1044 (opens new window)

题意： 给定$n$个元素$[1, n]$，从大到小入栈，求有多少种出栈方式。

解：考虑最后一个出栈的元素为$k$，那么比$k$小的元素出栈的方式有$ans(k-1)$种，比$k$大的元素出栈方式有$ans(n-k)$种，此时的答案为$ans(k-1)*ans(n-k)$，又因为最后出栈的元素有$n$种可能，因此答案为

$ans(n)=\sum_{i=1}^{n}[ans(i-1)*ans(n-i)]$

ans[0] = ans[1] = 1;
for(int i=2; i<=n; i++){
    ans[i] = 0;
    for(int j=1; j<=i; j++){
        ans[i] += ans[j-1]*ans[i-j];
    }
}

$ans$即为卡特兰数

卡特兰数

由引入得卡特兰数满足以下递推式

$h_0=h_1=1$

$h_n=h_0h_{n-1}+h_1h_{n-2}+...+h_{n-1}h_0$

卡特兰数的一般项公式为:

$h_n=\frac{1}{n+1}C_{2n}^n=\frac{(2n)!}{(n+1)!n!}$

$h_n=C_{2n}^{n}-C_{2n}^{n+1}$

递推公式:

$h_n=\frac{h_{n-1}(4n-2)}{n+1}$

$h_n=C_{2n}^{n}-C_{2n}^{n+1}$的证明

参考博客 (opens new window)

设操作1使得y值+1，操作2使得y值-1，两操作均能使x值加1。

从2n步中任取n步为操作1，则共有$C_{2n}^{n}$中走法

下面讨论不合法的情况：

设跨越y=0的操作序列不合法，那么不合法的情况肯定存在一点k与y=-1相交

我们将k+1到2n的所有操作翻转(1变2,2变1)。那么该该序列最终会到达点(2n, -2)

由于翻转操作是对称的，因此不合法的情况相当于(n-1个操作1，n+1个操作2)的不同序列数

例题

HDU 4828 (opens new window)

考虑1到2n，若放在上面一排则为0，否则为1，那么方案可以表示为01序列

显然是一道卡特兰数的模板题

HDU 1133

应用

引自OI-Wiki (opens new window)

以下问题属于 Catalan 数列：

1. 有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
2. 一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3. 在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
5. 一个栈（无穷大）的进栈序列为 1, 2, 3, ..., n 有多少个不同的出栈序列？
6. n 个结点可够造多少个不同形态的二叉树（注：结点两两不可分）？
7. n 个不同的数依次进栈，求不同的出栈结果的种数？
8. n 个 +1 和 n 个 -1 构成 a1, a2, a3, ... an 项 ，其部分和满足 a1 + a2 + ... + a_k >=0 对与 n 该数列为？