问题：存在一个数列H，仅包含-1，1两种数字，其中数列长度为2n，存在n个-1，n个1，则其元素求和 = 0,要求生成的数列符合其左子串Sh中元素相加>=0，计算在长度为2n的情况下，存在多少种该数列。
求解：
由排列组合可知，全排列E的情况总数为:|E| = 2n!/n!n!
设目标数列为H，其排列总数为|H|，则目标数列在全集中的补集数量为|M|
可的等式：|H| + |M| = |E|
由于M中的数列不满足要求，则一定存在至少一个子串Sm的元素总和 < 0,设第一不符合条件的子串为
M(k)
M1，M2，M3，......Mk
由于M(k)是第一个不符合条件的子串，则该子串的元素总数一定为奇数，并且前k-1项总和必为0，第k项为-1,子串中包含(k-1)/2 个 +1，(k-1)/2 + 1 个 -1。
现作如下一一映射,该序列前k项元素取反，即-1变为+1，+1变为-1，其他项保持不变。
M1,M2,M3,....Mk，Mk+1，Mk+2......M2n 此时 n个-1，n个+1
-M1,-M2,M3,...-Mk，Mk+1，Mk+2.......M2n 此时 n+1个+1，n-1个-1
现求|M|的总数，转变为n+1个+1和n-1个-1的全排列，即
|M| = 2n!/(n+1)!(n-1)!
依据以上等式，可的
|H|+|M|=|E|
|H| = |E| - |M|
|H| = 2n!/n!n! - 2n!/(n+1)!(n-1)!
卡特兰数：Cn = 2n!/n!n! - 2n!/(n+1)!(n-1)!
卡特兰数的应用场景：
1.二叉搜索树，在有n个元素的场景下，具有多少中可能的拓扑结构。
2.有n个元素进行出栈/入栈操作，有多少种操作序列。
