学习笔记：卡特兰数相关

问题

有

n

个左括号和

n

个右括号，将它们进行匹配，即每个左括号都有对应的右括号。求每个

n

有多少匹配方式。

下表是

n = 1 \sim 5

的排列方式和答案。

记

C_n

为

n

对括号匹配的方案数。

括号串可以表示为：

(A)B

允许

A

或

B

的括号串长度为

0

。

A

是左括号与右括号之间的平衡子串，包含

k

对括号。

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}

证毕。

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}