出栈次序

X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。
路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。
X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？
为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。

现在足足有16辆车啊，亲！需要你计算出可能次序的数目。


の，图形看起来就很像栈哦，就联想到了出栈进栈，一个车进胡同必须要出胡同，等同于栈的用法。

改题大意是求进出栈的总的方法数。


catalan数：

百度给出的公式：

h(n)=h(0)*h(n-1)+h(1)*h(n-2)+.....+h(n-1)*h(0)  (n>=2,h(0)=h(1)=1)

通项：C(2n,n)/(n+1)   其实会了这个答案秒秒钟

还是通过例题来真正认识一下catalan数吧，具体定义去百度

① 括号的匹配方式

有n对括号，即2n个符号，则h(n)=f(2n)

故第0个符号一定是左括号，右括号一定是2i+1个字符（一定是奇数字符，这样中间的字符方可成功匹配）

则第0个字符与第1个字符匹配的次数是f(0)*f(2n-2)

第0个字符与第3个字符匹配的次数是f(2)*f(2n-4)  =>将所有括号分成了两部分，一部分是两个符合，另一部分是2n-4个符号

②出栈序列

顺序进栈，进栈相当于是左括号，出栈相当于是右括号，n个数字，依次进栈构成了有2n个数字的序列

有 f(2n)=f(0)*f(2n-2)+f(2)*f(2n-4)+...+f(2n-2)*f(0)

其中当n=0时，h(0)=f(2*0)=0;

当n=1时，h(1)=f(2*1)=1;

n=2,h(2)=f(2*2)=2;

n=3,h(3)=f(2*3)=f(0)*f(4)+f(2)*f(2)+f(4)*f(0)=5;

.

则h(16)=C(16*2,16)/17=35357670

③圆连接点

一个圆周长等分n个点，每两个点之间连线，使得各线之间不相交的情况总共有多少种。

同样可类比成出栈进栈，取任意一个点为0点，则0点必须与2n+1个点相连，必须成对同时满足，与括号匹配类同

类似的还有二叉树。

还有哦，如果你看到有这样n个序列，发现有1 1 2 5 的规律，你可以试着继续往下算一算，说不定真成了