计数问题中的数学

卡特兰数

卡特兰数表示有多少个序列由 $n$ 个 $1$ 和 $n$ 个 $-1$ 构成，且前缀和非负。
卡特兰数的第 $n$ 项等于 $\frac{\binom{2n}{n}}{n+1}$。

证明 1

Raney 引理

如果 $a_1,a_2,\dots,a_n$ 是任何一个和为 $1$ 的整数数列，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。

证明：
考虑前缀和 $\{s_1,\dots,s_n\}$。假设 $x$ 是一个合法的开头。
那么对于 $i<x$，以 $x$ 开头，$i$ 结尾的区间和是 $1-s_{x-1}+s_i$。
对于 $i\ge x$， $x$ 开头，$i$ 结尾的区间和是 $s_i-s_{x-1}$。
由于 $x$ 是一个合法的开头，所以 $\forall i<x,s_i\ge s_{x-1}$，$\forall i\ge x,s_i>s_{x-1}$。
不难发现，满足条件的 $x$ 等价于 $s_{x-1}$ 是前缀和里最靠后的最小值。
当然，如果此时 $x-1=n$，那么合法的开头就是 $1$。

不难发现，卡特兰数等价于：$n+1$ 个 $1$ 和 $n$ 个 $-1$ 构成的，且前缀和严格大于 $0$ 的序列个数。
具体来说，就是在原来条件的基础上，在序列开头加上一个 $1$。

那么根据 Raney 引理，我们就只要求由 $n+1$ 个 $1$ 和 $n$ 个 $-1$ 构成的序列中有多少种循环同构等价类。
很明显就是 $\frac{\binom{2n+1}{n}}{2n+1}=\frac{\binom{2n}{n}}{n+1}$。

证明 2

直接考虑将 $+1$，$-1$ 看作折线，且折线不能碰到 $y=-1$ 这条直线。
不难发现，将一条路径从第一次触碰到 $y=-1$ 以后沿着 $y=-1$ 翻转，可以把一种不合法的方案一一对应到：从 $(0,0)$ 走到 $(2n,-2)$ 的方案数。
所以合法的方案数就是 $\binom{2n}{n}-\binom{2n}{n+1}=\frac{\binom{2n}{n}}{n+1}$。