卡特兰数和斯特林数

感觉这几个东西挺常用，记录一下吧。

1.卡特兰数

假如我们定义 \(C_n\) 表示第 \(n\) 个卡特兰数。然后我们就有一下几个式子。

1. \(C_n = \dfrac{\dbinom {2n}{n}}{n + 1}\)
2. \(C_n = \begin{cases} \sum^n_{i = 1}H_{i - 1}H_{n - i} \ \ n \ge 2 \\ 1 \end{cases}\)
3. \(C_n = \dbinom {2n}{n} - \dbinom{2n}{n - 1}\)

例题1 UVA11379

抽象的同学找的题。

首先我们发现这个题目就类似于小奥中的洗盘子问题，这是一个经典的模型，需要用到卡特兰数。假如说有 \(n\) 个碟子，那么总共满足条件的方案数就有 \(C_n\) 种。然后我们考虑第 \(x\) 个圆弧在第 \(j\) 个圆弧后面这个条件怎么考虑。

我们定义 \(dp_{i,j}\) 为有 \(i\) 个圆弧，然后我们已经确定第 \(j\) 个圆弧的最后一个点的位置。那么答案就是 \(\sum^j_{k = 1} C_{i - k} \times C_{k - 1}\)。

然后我们考虑如何计算答案。假如说现在第 \(x\) 个圆弧已经把第 \(j\) 个圆弧包住，那么答案就是 \(dp_{n - j + x,x} \times C_{j - x}\)。这个式子的原因是显然的，因为我们可以把被 \(x\) 包含住的圆弧和没有被 \(x\) 包含住的圆弧分开考虑。所以分别有 \(n - j + x\) 和 \(j - x\) 个，但是我们又已经知道 \(x\) 的结尾在 \(j\) 后面，但是起始点在 \(x\) 的结尾的后面的圆弧的情况，那么答案就是 \(dp_{n - j + x,x} \times C_{j - x}\) 。