卡特兰数与折线法
问题举例：元素1,2,3,4,5,6,7入栈，有多少种出栈的可能性？
要点：卡特兰数，折线法
这个问题分三种类型问，都是一样的处理方法
解法：
整个过程认为是从坐标（0,0）走到（2n，0），入栈记为向右上方移动单位长度，出栈记为向右下方移动单位长度。栈内必须要有元素，不能为负值，所以，曲线不能在X轴下方，这样才是合法的。
那么我们要求的就是：合法步骤 = 全部步骤 - 非法步骤
那么全部步骤必须满足入栈次数等于出栈次数，即曲线能回到X轴上，到达（2n，0）。
如果不限制合法性，即可以跨越X轴，折线种数为C（2n，n）。
那么非法步骤就是跨越了X轴，最终还是到达了（2n，0）。那么我们可以发现，就算你跨过了X轴，如果将K点的折线之后根据y=-1做对称，那么折线必然终点是在（2n，-2）处，那么非法步骤就是到达（2n，-2）的数量。那么它需要满足的条件是出栈次数比入栈次数多2次，即入栈为n-1，那么出栈为n+1，折线种数为C（2n，n-1）。
好了，所有步骤有了，非法步骤有了
合法步骤为C（2n，n）-C（2n，n-1） = C（2n，n）/（n+1）
当n=7时，次数为429次。
顺带补充一下基本知识
排列
排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(Arrangement)。特别地，当m=n时，这个排列被称作全排列(Permutation)。
公式
组合
从m个不同元素中，任取n(n≤m)个元素并成一组，叫做从m个不同元素中取出n个元素的一个组合；从m个不同元素中取出n(n≤m)个元素的所有组合的个数，叫做从m个不同元素中取出n个元素的组合数。
公式