卡特兰数

约 714 个字预计阅读时间 2 分钟

经典题：进出栈序列¶

n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列

我们将进栈表示为 +1，出栈表示为 -1

出栈序列的所有前缀和必然大于等于 0，并且序列 +1 的数量等于 -1 的数量

接下来让我们观察一下 n = 3 的一种出栈序列：+1 -1 -1 +1 -1 +1。序列前三项和小于 0，显然这是个非法的序列。

如果将第一个前缀和小于 0 的前缀，即前三项元素都进行取反，就会得到：-1 +1 +1 +1 -1 +1。此时有 3 + 1 个 +1 以及 3 - 1 个 -1。

因为这个小于 0 的前缀和必然是 -1，且 -1 比 +1 多一个，取反后，-1 比 +1 少一个，则 +1 变为 n + 1 个，且 -1 变为 n - 1 个。进一步推广，对于 n 元素的每种非法出栈序列，都会对应一个含有 n + 1 个 +1 以及 n - 1 个 -1 的序列。

如何证明这两种序列是一一对应的？

假设非法序列为 A，对应的序列为 B。每个 A 只有一个"第一个前缀和小于 0 的前缀"，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到"第一个前缀和大于 0 的前缀"，显然 B 也只能产生一个 A。

每个 B 都有 n + 1 个 +1 以及 n - 1 个 -1，因此 B 的数量为 $\dbinom {2n}{n+1}$ ，相当于在长度为 2n 的序列中找到 n + 1 个位置存放 +1。相应的，非法序列的数量也就等于 $\dbinom {2n}{n+1}$ 。

出栈序列的总数量共有 $\dbinom {2n}{n}$ ，因此，合法的出栈序列的数量为 $\dbinom {2n}{n}-\dbinom {2n}{n+1}$ 。

此时我们就得到了卡特兰数的通项 $\dbinom {2n}{n}-\dbinom {2n}{n+1}=\dbinom{2n}{n}/(n+1)$

n 对括号，则有多少种 “括号匹配” 的括号序列

左括号+1，有括号-1

n + 1 个叶子节点能够构成多少种形状不同的满二叉树

如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。

非叶节点，左子树+1，右子树-1

电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。则有多少种排队方式，可以让每个人都买到电影票。

50+1，100-1

公式不同， $\dbinom {n+m}n-\dbinom{n+m}{m+1}$

节点数为 $i$ 时二叉树构造的方案数

写题就是寻找满足下列公式的特点

$C_n=\dbinom{2n}{n}/(n+1)$

$C_1=1,C_n=C_{n-1}\times\frac{4n-2}{n+1}$

$C_n=\begin{cases}1&n=0,1\\\sum\limits_{i=1}^n C_{i-1}*C_{n-i}&2\le n\end{cases}$

$C_n=\dbinom {2n}{n}-\dbinom {2n}{n+1}$