卡特兰数(笔记)

满足条件的01序列

思路：

由于前缀的0不能比1小也就说明了，前缀中$sum(0)>sum(1)$。实际生活中有很多这种问题，通常都是某个操作A是另一个操作B的前提，如果操作B的数目提前超过了操作A那么就不合法。

对于这个问题其实是很有名的问题，它的解题思路非常清奇。

把01序列看成两种操作，0表示向右走，1表示向上走(这里以n=3为例左下角为(1,1)右上角为(3,3)) 那么最终这个01序列可以看做从左下角走到右上角的的路径数目 现在要求求合法的路径数目也就是说所有的路径不能触碰红线，比如黄线的路径就是合法的

一旦有不合法的路径，比如说下面这个： 那么就可以把超过红线以后的部分进行做，以红线为轴的轴对称即： 那么就可以发现，它的终点从原来的(3,3)变成了(2,4)可以接着画图，就会发现，只要触碰红线，折叠后它的终点都会变到(2,4)

于是可以得出结论，所有的序列情况等于从(1,1)走到(3,3)的路径的个数，所有不合法的个数为从(1,1) 走到(2,4)的个数

根据排列组合就可以得到，这个问题的答案为$C_6^3-C_6^2$。

因为所有路径的情况等于从6个操作中选3个向上走，即$C_6^3$第二个组合数也同理

推广就可以得到$ans=C_{2n}^n-C_{2n}^{n-1}=\frac{(2n)!}{(n!)\ast (n!)}-\frac{(2n)!}{(n-1)!\ast (n+1)!}=\frac{(2n)!\ast (n+1)}{(n!)\ast (n+1)!}-\frac{(2n)!\ast n}{(n)!\ast (n+1)!}=\frac{(2n)!}{(n!)(n+1)!}=\frac{C_{2n}^n}{n+1}$

最后我们得到了这道题的答案：$\frac{C_{2n}^n}{n+1}$ 这也就是卡特兰数的表达式 可以证明它还满足这样的一个递推式:$F(n+1)=\frac{2(2n+1)}{n+2}F(n)$其中$F(n)$ 表示卡特兰数的第n项

那么这道题就很好解决了，只需要算一个组合数即可

其它的例子：

火车进栈 火车进栈问题 鸡蛋饼 书屋阶梯