浅谈 Catalan 数

引言#

$Catalan$ 的精髓是推递推式，很多问题的递推式形式上与 $Catalan$ 的递推式相同，这说明他们有着共同之处，可以使用 $Catalan$ 数的思考方法，这对我们解决问题来说算是打开了一个新的窗口。

分治：左 + 自己 + 右

我们有如下定义

H_n=\begin{cases} 1, n=0,1\\ \sum_{i=1}^nH_{n-i}\cdot H_{i-1}, n\geq 2 \end{cases}

$n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2, \cdots ,a_{2n}$ ，其部分和满足 $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ 对与 $n$ 该数列为？

乍一看好像很难，但是我们仔细分析一下

好像不方便直接得到结果，那就容斥原理

我们用总量减去不合法量

把 $n$ 个 $+1$ 放在长 $2n$ 数列里面，其他的都是 $-1$ ，故总量为 $\binom{2n}{n}$

首先我们考虑不合法的情况
而只有一种情况会导致不合法
那就是在某个前缀和的过程中，部分和首次小于零。

设 $A$ 是一组合法解， $B$ 是任意序列 (同时满足 $B$ 中缺少且仅缺少一个 $-1$ 且有 $|B|=n-1$ )
即 $|A|+|B|=2n-1$

显然此时有 $H=(A, -1, B)$ ，这是一组不合法解

Warning

此时虽然是不合法解，但是此时 $H$ 中 $+1$ 和 $-1$ 的数量都为 $n$

怎么区分合法解和不合法解呢？
我们设 (取反 $B$ 序列)

\hat{B_i}=\begin{cases} +1, B_i=-1\\ -1, B_i=+1 \end{cases}

那么现在 $\hat{B}$ 就是一个多了且仅多了一个 $-1$ 的序列 (从少一个到多一个了呢)

那么现在 $\hat{H}=(A, -1, \hat{B})$ 就是一组有 $n+1$ 个 $-1$ 和 $n-1$ 个 $+1$ 的序列

好像区分开了，来验证一下可行性
考虑是否能做到不重不漏

仔细思考 $\hat{B}$ 和 $B$ 是一个双射集合
也就是说所有的不合法解都对应一个如此这般的 $\hat{H}$

那么如何统计呢？
枚举 $+1$ 或 $-1$ 的数量都可以

那就是 $\binom{2n}{n-1}$ 或 $\binom{2n}{n+1}$

$H_n=\binom{2n}{n}-\binom{2n}{n-1}$