卡特兰数证明

卡特兰数

Catalan Numbers

卡特兰数有很多种应用情景。

  1. 计算机中最常见的是 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}\)

参考资料

https://brilliant.org/wiki/catalan-numbers/

http://blog.sina.cn/dpool/blog/s/blog_6917f47301010cno.html

Leave a Comment