这是Catalan数的定义，现在来证明一下：
所有由n个0和n个1组成2*n个数的个数一共有
那么求出不符合条件的个数，也就是有前缀的1的个数大于0的个数
假设2n个数中有n+1个1与n-1个0
这时一定存在一个位置i=2*k+1，在前i位有k+1个1和k个0
这是i+1~2*n的数中有n-k-1个1和n-k个0
将i+1~2*n中的数全部取反，这时数列中的1和0的个数都为n个，而且保证了这个数列一定不符合条件
所以不符合条件的个数可以看作共有n+1个1和n-1个0组成的数列所有排列数量
共有
于是这道题的答案，也就是catalan数的公式就是
Catalan数的其他式子：
假设需要2*n个数合法，现在知道使2*i个数合法的方案数已经使2*(n-i-1)个数合法的方案数
将一个0填到2*i+1的位置，将一个1填到2*n的位置，构造出来的新数列一定合法
那么有:
这些是catalan数的一些应用
1.将左括号看为0，右括号看为1，问题转化为2*n跟数中所有前缀的0的个数一定大于等于1的个数，同例题
2. 将入栈看作0，出栈看作1，转化为2*n跟数中所有前缀的0的个数一定大于等于1的个数，同例题
3.n个节点的二叉树，左子树有i个，那么右子树就有n-i-1个，那么就有
答案还是
4.假设一定在直线y=x的下方，令向左走为0，向上走为1
那么问题就是2*n个数中任意前缀0的个数大于1的个数(0<前缀长度<2*n)
答案一定不是n的Catala数，考虑构造出来一组答案
现在假设有2*(n-1)个01串满足Catalan数的定义，第一个前缀01个数相等的位置是i
在第i个位置前插入一个0，这样就会使这个串所有的前缀0的个数都大于1的个数
再在串尾加入一个1，使得全串有n个0，n个1
那么在下方的答案总数就是
在上方的个数和在下方一样，那么总方案数为