母题：N个数依次入栈，出栈顺序有多少种？
答案：Catalan number 卡塔兰数
Catalan number
常规分析
- 首先，我们设f(n)代表序列个数为n的出栈序列种数。
f(1) = 1 //即 1
f(2) = 2 //即 12、21
f(3) = 5 //即 123、132、213、321、231
- 第一个出栈的序数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
- 此时，我们若把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
- 而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
