卡特兰数

卡特兰数 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
f(n) = factorial(big(2n)) ÷ factorial(big(n))^2 ÷ (n+1)
@time f.(0:10:100)

运行结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
  0.000032 seconds (274 allocations: 6.320 KiB)
11-element Vector{BigInt}:
                                                         1
                                                     16796
                                                6564120420
                                          3814986502092304
                                    2622127042276492108820
                              1978261657756160653623774456
                        1583850964596120042686772779038896
                  1321422108420282270489942177190229544600
            1136359577947336271931632877004667456667613940
      1000134600800354781929399250536541864362461089950800
 896519947090131496687170070074100632420837521538745909320