学习笔记：卡特兰数相关
chenxi797
·
·
学习·文化课
问题
有 n 个左括号和 n 个右括号，将它们进行匹配，即每个左括号都有对应的右括号。求每个 n 有多少匹配方式。
下表是 n = 1 \sim 5 的排列方式和答案。
| n |
合法组合 |
数量 |
| 0 |
* |
1 |
| 1 |
() |
1 |
| 2 |
(()),()() |
2 |
| 3 |
()()(),()(()),(())(),(()()),((())) |
5 |
| 4 |
14种组合 |
14 |
| 5 |
42种组合 |
42 |
通项公式
记 C_n 为 n 对括号匹配的方案数。
括号串可以表示为：
(A)B
允许 A 或 B 的括号串长度为 0。
$B$ 是右边剩余的平衡子串，包含 $n - k - 1$ 对括号。
由此可以得到递推公式：
$$
C_n = \sum _ {k = 0} ^ {n - 1} C_k \times C_{n - k - 1}
$$
初始化 $C_0 = 1$。
也可以用组合数表示：
$$
C_n = \frac{1}{n + 1} \dbinom{2n}{n}
$$
##
简单证明：
所有长度为 $2n$ 的合法序列，总数为 $\dbinom{2n}{n}$，非法序列总数为 $\dbinom{2n}{n - 1}
\begin{aligned}
C_n &= \dbinom{2n}{n} - \dbinom{2n}{n - 1} \\
&= \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n - 1)!(n + 1)!} \\
&= (2n)! \left(\frac{1}{n!n!} - \frac{1}{(n - 1)!(n + 1)!}\right) \\
&= (2n)! \left(\frac{1}{(n!)^2} - \frac{1}{\frac{n!}{n} (n + 1) n!} \right) \\
&= (2n)! \left(\frac{1}{(n!)^2} - \frac{n}{(n + 1) (n!) ^2} \right) \\
&= (2n)! \frac{1}{(n!)^2} \left(1 - \frac{n}{n + 1} \right)\\
&= (2n)! \frac{1}{(n!)^2} \cdot \frac{1}{n + 1}\\
&= \frac{1}{n + 1} \dbinom{2n}{n}
\end{aligned}
即：
C_n = \frac{1}{n + 1} \dbinom{2n}{n}
证毕。
相关题目
现有一个操作数序列 1,2,\cdots,n，另有一个栈 A 。
现在可以进行两种操作：
对于给定的 n，求由操作数序列 1,2,\cdots,n 经过操作可能得到的输出序列的总数。
卡特兰数解答
C_n = \frac{1}{n + 1} \dbinom{2n}{n}
我们可以推导出 C_n 与 C_{n - 1} 的递推关系：
C_n = \frac{1}{n + 1} \dbinom{2n}{n} = \frac{(2n)!}{(n + 1)n!n!} \\
C_{n - 1} = \frac{1}{n} \dbinom{2(n - 1)}{n - 1} = \frac{(2n-2)!}{n(n - 1)!(n - 1)!}
那么：
\begin{aligned}
\frac{C_n}{C_{n - 1}} &= \frac{\frac{(2n)!}{(n + 1)n!n!}}{\frac{(2n - 2)!}{n(n - 1)!(n - 1)!}} \\
&= \frac{(2n)!}{(2n - 2)!} \cdot \frac{n}{n + 1} \cdot \frac{(n - 1)! ^ 2}{n! ^ 2} \\
&= \frac{(2n)(2n - 1)}{n ^ 2} \cdot \frac{n}{n + 1} \\
&= \frac{2(2n - 1)}{n + 1} \\
\end{aligned}
所以：
C_n = \frac{2(2n - 1)}{n + 1} C_{n - 1}