Home Catalan Number 卡特兰数
Post
Cancel

Catalan Number 卡特兰数

卡特兰数

卡特兰数是组合数学中的一个常出现在各种计数问题中的数列, ​这个数列的前几项为: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

经典的卡特兰问题有: 进出栈序列、括号序列、满二叉树等.

进出栈序列

题目描述: n 个元素的进栈序列为: 1, 2, 3, 4, …, n, 则有多少种出栈序列?

思路: 我们将进栈表示为 +1, 出栈表示为 -1, 则 1 3 2 的进出栈序列可以表示为: +1 -1 +1 +1 -1 -1.

根据栈本身的特点, 每次出栈的时候, 这个出栈的元素必定在之前已经入栈, 即进出栈序列中的每个 -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 相加得到的, 而且这还是第一个小于 0 的前缀和, 因此这个前缀和一定是由 0 - 1 得到的). 而且我们还可以顺带得到另外一个结论: 在这个前缀和的序列中, -1 的个数比 +1 多 1 个, 并且这个前缀和序列长度必定是奇数.

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

这是因为, 对于一个长为 n 的进栈序列而言, 其进出栈序列长度为 2n, 其中必定有 n 个 1 和 n 个 -1. 现在又对进出栈序列中第一个前缀和小于 0 (前缀和其实等于 -1, 假设长度为 2m + 1) 的子序列取反了, 而这个子序列中有 m 个 +1 和 m + 1 个 -1, 那么反转后就成了 m 个 -1 和 m + 1 个 +1. 剩下的 2n - 2m - 1 个数中又有 n - m 个 +1 和 n - m - 1 个 -1, 所以最后就有了 n - m + m + 1 = n + 1 个 +1 和 n - m - 1 + m = n - 1 个 -1.

而且这两种序列是一一对应的:

  • 假设非法序列为 A, 对应的反转后的序列为 B, 那么每个 A 只有一个“第一个前缀和小于 0 的前缀”, 所以每个 A 只能产生一个 B. 而每个 B 想要还原到 A, 就需要找到“第一个前缀和大于 0 的前缀”, 显然 B 也只能产生一个 A.

每个 B 都有 n + 1 个 +1 以及 n - 1 个 -1, 因此 B 的数量为 $C_{2n}^{n+1}$ , 相当于在长度为 2n 的序列中找到 n + 1 个位置存放 +1. 同理, 非法序列的数量也等于 $C_{2n}^{n+1}$ .

注意, A 是非法序列, 其对应的前缀反转序列 B 并不是合法序列! 这样做只是为了计算出非法序列的数量.

出栈序列的总数量是 $C_{2n}^{n}$ , 因此合法序列的数量为: $C_{2n}^{n}-C_{2n}^{n+1}=\dfrac{C_{2n}^{n}}{n+1}$ .

这就是卡特兰数的通项.

括号序列

题目描述: n 对括号, 有多少种“括号匹配”的括号序列?

思路: 将左括号看成 +1, 右括号看成 -1, 那么就和上题的进出栈一样, 共有 $\dfrac{C_{2n}^{n}}{n+1}$ 种序列.

满二叉树

题目描述: n + 1 个叶子节点能够构成多少种形状不同的满二叉树? (别说你不知道什么是满二叉树)

满二叉树: 一棵二叉树的结点要么是叶子结点, 要么有两个子结点. 在一棵深度为 n 的满二叉树中, 结点的个数为 $2^{n}-1$ , 叶子结点的个数为 $2^{n-1}$ . 因此非叶子结点的个数为 $2^{n-1}-1$ , 即非叶子结点比叶子结点少一个.

思路: DFS 这棵满二叉树, 向左扩展时标记为 +1, 向右扩展时标记为 -1. 由于每个非叶子节点都有两个左右子节点, 所以它必然会先向左扩展, 再向右扩展. 在整个遍历过程中, 左右扩展将形成匹配, 变成进出栈的题型. n + 1 个叶子结点会有 2n 次扩展, 构成 $\dfrac{C_{2n}^{n}}{n+1}$ 种形状不同的满二叉树.

在此题中, 既然已知叶子结点数为 n + 1 了, 那么可以推出非叶子结点数为 n. 而每个非叶子结点必有两个子结点, 所以整棵树遍历完后共有 2n 次扩展.

满二叉树

电影购票

题目描述: 电影票一张 50 coin, 且售票厅没有 coin. m 个人各自持有 50 coin, n 个人各自持有 100 coin. 则有多少种排队方式, 可以让每个人都买到电影票?

思路: 持有 50 coin 的人每次购票时不需要找零, 并且可以帮助后面持有 100 coin 的人找零; 而持有 100 coin 的人每次购票时需要找零, 且对后面的找零没有任何作用.

因此, 相当于每个持有 100 coin 的人都需要和一个持有 50 coin 的人进行匹配. 我们将持有 50 coin 的标记为 +1, 持有 100 coin 的标记为 -1, 此时又回到了进出栈问题.

不同的是, m 并一定等于 n, 且排队序列是一种排列, 需要考虑先后顺序, 例如各自持有 50 coin 的甲和乙的前后关系会造成两种不同的排队序列. 所以, 将会有 $(C_{m+n}^{m} - C_{m+n}^{m+1})\cdot A_{m}^{m}\cdot A_{n}^{n}$ 种可能.

这里 +1 有 m 个, -1 有 n 个, 取反后 +1 变成 m + 1 个, -1 变成 n - 1 个, 总和不变, 所以第二项是减去 $C_{m+n}^{m+1}$ .

解题模板

用递推计算: $C_1=1, C_n=C_{n-1}\cdot\dfrac{4n-2}{n+1}$ .

代码实现: 打印前 n 个卡特兰数

1
2
3
4
5
6
7
8
9
10
11
12
import java.math.BigInteger;
int n = 20;
BigInteger ans = BigInteger.valueOf(1);
System.out.println("1:" + ans.toString());
BigInteger four = BigInteger.valueOf(4); 
BigInteger one = BigInteger.valueOf(1);
BigInteger two = BigInteger.valueOf(2);
for (int i = 2; i <= n; i++) {
    BigInteger bi = BigInteger.valueOf(i);
    ans = ans.multiply(four.multiply(bi).subtract(two)).divide(bi.add(one));
    System.out.println(i + ":" + ans.toString());
}
1
2
3
4
5
ans, n = 1, 20
print("1:" + str(ans))
for i in range(2, n + 1):
    ans = ans * (4 * i - 2) // (i + 1)
    print(str(i) + ":" + str(ans))

需要注意的是, 由于卡特兰数增长速度较快, 当 n 等于 17 时, 卡特兰数将会超过 int 最大值, 造成溢出 (Python 除外). 对于 Java 来说, 可以使用 BigInteger 来计算大整数.

如果 +1 的数量不等于 -1 的数量, 如前面提到的电影购票问题, 则不能继续使用原有的递推性质. 直接推导:

\[\begin{eqnarray} \label{eq} C_n&=&C_{m+n}^m-C_{m+n}^{m+1} \nonumber \\ ~&=&\dfrac{(m+n)!}{m!\cdot n!}-\dfrac{(m+n)!}{(m+1)!\cdot (n-1)!} \nonumber \\ ~&=&\dfrac{(m+n)!}{m!\cdot n!}-\dfrac{(m+n)!\cdot\dfrac{1}{m+1}\cdot n}{m!\cdot n!} \nonumber \\ ~&=&\dfrac{(m+n)!}{m!\cdot n!}\cdot(1-\dfrac{1}{m+1}\cdot n) \nonumber \\ ~&=&\dfrac{(m+n)!}{m!\cdot n!}\cdot\dfrac{m+1-n}{m+1} \end{eqnarray}\]

一般而言, 为了降低难度, 题目会要求我们计算排列数量 (即考虑次序), 所以:

\[A_n=C_n\cdot A_m^m\cdot A_n^n=C_n\cdot m!\cdot n!=(m+n)!\cdot\dfrac{m+1-n}{m+1}\]

总结

基本上所有的卡特兰数问题经过一定的转换都可以还原成进出栈问题. 因此, 只要我们能够学会进出栈问题的解法, 无论问题再怎么变化, 本质还是不变的.

卡特兰数问题中都会存在一种匹配关系, 如进出栈匹配、括号匹配等, 一旦计数问题中存在这种关系, 那我们就需要去考虑这是否是卡特兰数问题. 此外, 我们还可以记住序列前四项: 1, 1, 2, 5, 这些将有利于我们联想到卡特兰数.

参考

This post is licensed under CC BY 4.0 by the author.