卡特兰数 Catalan number 是一个数列，可以用在计算 n 个元素进出栈的情况数目。例如一个序列以 1 2 3 4 的顺序入栈，有多少种出栈情况？

理论

推导过程如下，主要使用了分治思想。

一个序列的入栈顺序确定，那么出栈顺序就有了限制

某元素出栈必须在入栈之后
某元素出栈必须在栈顶

将出入栈顺序放在一起，可以划分为多种情况，每种情况都是分为两个部分，分界线为栈空。下面以带圈为入栈，不带圈为出栈说明，入栈顺序确定 $\textcircled{1}\textcircled{2}\textcircled{3}\textcircled{4}$ ，出入栈顺序可以是 $\textcircled{1}1|\textcircled{2}2\textcircled{3}3\textcircled{4}4$ 、 $\textcircled{1}\textcircled{2}21|\textcircled{3}3\textcircled{4}4$ 、 $\textcircled{1}\textcircled{2}2\textcircled{3}31|\textcircled{4}4$ 等。

在竖线 | 处第一次出现栈空，将出入栈顺序划分为两部分，这两部分是两个更小的本类子问题。由于要求栈空，第一个入栈元素必须最后一个出栈，实际第一个子问题是一个元素个数-1 的子问题。根据乘法法则和加法法则，可以得到本类问题的递推公式：设 $n$ 个元素以确定顺序入栈有 $f(n)$ 种出栈情况，则

$$f(n)=f(0)f(n-1)+\dots+f(n-1)f(0)=\sum\limits_{i=0}^{n-1}f(i)f(n-i)$$

规定 $f(0)=1$ 且 $n\ge1$，接下来是数学问题，推导过程日后研究。

摘抄网上的递推公式和通项公式：

$$f(n+1)=\dfrac{4n+2}{n+2}f(n)$$ $$f(n)=\dfrac{1}{n+1}C_{2n}^{n}=\dfrac{1}{n+1}\dfrac{(2n)!}{(n!)^2}$$

编程

Julia 计算卡特兰数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
f(n)=reduce(div,[factorial(big(2n)),factorial(big(n))^2,n+1])
f.(0:10:100)
                                                         1
                                                     16796
                                                6564120420
                                          3814986502092304
                                    2622127042276492108820
                              1978261657756160653623774456
                        1583850964596120042686772779038896
                  1321422108420282270489942177190229544600
            1136359577947336271931632877004667456667613940
      1000134600800354781929399250536541864362461089950800
 896519947090131496687170070074100632420837521538745909320

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import math
def catalan(n: int) -> int:
	return math.comb(2*n, n) // (n+1)
for i in range(0, 101, 10):
	print(catalan(i))
1
16796
6564120420
3814986502092304
2622127042276492108820
1978261657756160653623774456
1583850964596120042686772779038896
1321422108420282270489942177190229544600
1136359577947336271931632877004667456667613940
1000134600800354781929399250536541864362461089950800
896519947090131496687170070074100632420837521538745909320

测试 Julia 和 Python 程序，毫无意外 Julia 性能更好。同时计算第 1_000_000 个卡特兰数，Julia 秒出，Python 宕机。

sympy 有一个 catalan 函数，比原生 Python 速度快，但相较于 Julia 还是乌龟慢。😀