卡特兰数
Catalan Numbers
卡特兰数有很多种应用情景。
- 计算机中最常见的是 n 个数有序入栈的出栈顺序数量。
2. 或描述为从原点出发，每次要不斜 45 度向上走一格，或斜 45 度向下走一格，且要求不跨过 x 轴走到下方，求折线的总数量。
3. 或可抽象描述为一共有 n 个 A 操作，和 n 个 B 操作，要求任意时刻已经做的 A 操作数量不低于 B 操作数量，问合法的序列数量。
总之，可以应用的场景很多。而卡特兰数等于
\begin{align}
\frac{1}{n+1}\dbinom{2n}{n}
\end{align}
折线法证明
来自：http://blog.sina.cn/dpool/blog/s/blog_6917f47301010cno.html
对于情景2，容易计算知道从原点到 (2n,0) 的所有折线总数为 \(\dbinom{2n}{n}\) (选 n 个斜上，剩余斜下)。
之后如果能计算出其中有多少个非法的线条，相减则可以得到卡特兰数。
天才般地观察知，每一个非法的线条一定接触或跨越了 y=-1 这条虚线。于是可以取第一个交点之后的部分，以 y=-1 为轴进行上下翻转。显然，反转过后的终点一定为 (2n,-2)。
且翻转操作是一对一可逆的，即任意一条原点至 (2n,-2) 的折线对应了一条非法的 原点至 (2n,0) 的折线。
而原点至 (2n,-2) 的折线数量为 \(\dbinom{2n}{n-1}\) (选 n-1 个斜上，其他斜下)。
于是得到卡特兰数\(C(n)=\dbinom{2n}{n}-\dbinom{2n}{n-1}=\frac{1}{n+1}\dbinom{2n}{n}\)