【卡塔兰数】假定有A,B,C,D依次进栈，进栈过程中允许出栈，写

母题：N个数依次入栈，出栈顺序有多少种？

答案：Catalan number 卡塔兰数

Catalan number

常规分析

1. 首先，我们设f(n)代表序列个数为n的出栈序列种数。

f(1) = 1     //即 1
f(2) = 2     //即 12、21
f(3) = 5     //即 123、132、213、321、231

2. 第一个出栈的序数k将1~n的序列分成两个序列：其中一个是1 ~ k-1，序列个数为k-1；另外一个是k+1~n，序列个数是n-k。

1 2 3 4 5   6   7 8 9
1 2 3 4 5  //其中一个是1 ~ k-1，序列个数为k-1；   6-1=5
7 8 9        //另外一个是k+1~n，序列个数是n-k。   9-6=3

3. 此时，我们若把k视为一个确定的序数，那么根据乘法原理，f(n)的问题就等价于序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的出栈组合为f(k-1)×f(n-k)。

f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)  //f(0)=1, f(1)=1

4. 而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)  //f(0)=1, f(1)=1