公式1 (通项公式) ：
在上文提到的出栈序列的问题情景中，如果有n
个元素，在平面直角坐标系中用x坐标表示入栈数，y坐标表示出栈数，则坐标(a,b)表示目前已经进行了a次入栈和b次出栈，则再进行一次入栈就是走到(a+1,b)，再进行一次出栈就是走到(a,b+1)。并且，由于入栈数一定小于等于出栈数，所以路径不能跨越直线y=x
因此，题目相当于求从(0,0)走到(n,n)且不跨越直线y=x的方案数
首先，如果不考虑不能跨越直线y=x的要求，相当于从2n次操作中选n次进行入栈，则方案数为Cn2n。
然后，考虑对于一种不合法的方案，一定在若干次操作后有一次出栈数比入栈数多一次，这个点在直线y=x+1 (即下图中红色的线) 上。那么把第一次碰到该直线以后的部分关于该直线对称，则最终到达的点是(n−1,n+1) (如下图) 。
图源：英文维基 (即文首网址)
显然，任何非法方案都可以通过此方式变成一条从(0,0)到(n−1,n+1)的路径，有Cn+12n种。而任何合法方案由于不接触直线y=x+1，无论从哪个点对称都不是一条连续的路径。由于合法方案数就是Catalann
，所以：
