求入栈序列对应的所有的合法输出序列种数（一）
xhy7599
·
2020-03-24 20:28:16
·
个人记录
求入栈序列对应的所有的合法输出序列种数
（一） 数学模型（卡特兰数理论）
我们在坐标系里对此进行描述。
如果有n个元素，在平面直角坐标系中用x坐标表示入栈数，y坐标表示出栈数，则坐标(a,b)表示目前已经进行了a次入栈和b次出栈，则再进行一次入栈就是走到(a+1,b)，即横坐标加一，再进行一次出栈就是走到(a,b+1)，即纵坐标加一。
利用此方法来描述入栈与出栈的操作，在坐标系中具有一般性的规律。分别为：
在任意一次操作前，入栈次数始终小于等于出栈次数，即y≤x始终成立，所以路径一定始终在直线y=x下方。
在最后一步操作后，入栈次数一定等于出栈次数，所以路径的终点一定在直线y=x上
因此，题目相当于求从(0,0)走到(n,n)且不跨越直线y=x的路径数。
例如： (2,4,3,1,5,7,6)就是入栈序列(1,2,3,4,5,6,7)的合法出栈序列，因为其路径（如下图黄色线条所示）始终在直线y=x（蓝色线条）的下方
其线段对应着：(入,入,出,入,入,出,出,……,出,出)，线段向右延申一格记为一次入栈，线段向上延申一格记为一次出栈。
因此，我们得出了利用坐标系描述入栈出栈操作的方法。下面我们来讨论如何利用此方法求解合法出栈序列种数。
<1>. 出栈和入栈次数均为n次的情况（不考虑出栈次数>入栈次数的可能性）
首先，如果不考虑不能跨越直线y=x的要求，相当于从2n次入栈出栈操作中选n次进行入栈（或者理解为线段向右延申n次），则方案数为\ C_{2n}^{n}。
<2>. 出栈和入栈次数均为n次的情况（只考虑出栈次数>入栈次数的情况）
然后，在入栈n次出栈n次的基础上，考虑不合法的情况。对于不合法的出栈方案，一定有某次操作（即棕色线段）使得总出栈次数比总入栈次数多一次，即在坐标系下与直线y=x+1（即下图中深蓝色的线段）相交。
对于这种不合法情况，我们可以在坐标系上直观地看出其特点，即终点仍然落在直线y=x上，但路径经过了直线y=x+1。这种路径的描述不便于我们找出不合法出栈序列的规律，但我们对路径稍作调整，将路径与直线y=x+1的交点后的线段沿直线y=x+1对称处理（对称后的路径为下图绿色线段），如下图所示。
我们把对称前的黄色线段和对称后的绿色线段组成的路径称为新路径。因此，对于每一种不合法路径，我们都有新的路径与之一一对应，这个新的路径一定以(n-1,n+1)为终点。
在这里要注意得出新路径的逻辑顺序：首先，如果有一条路径经过了直线y=x+1，则这条路径非法；其次，这条非法路径从与直线y=x+1的交点到终点的那一段可以沿直线y=x+1对称；最后，对称后的路径一定以(n-1,n+1)为终点。
与前面 <1> 的计算方法同理，我们可以得出在出栈和入栈次数均为n次的前提下非法路径的种数，即\ C_{2n}^{n+1}。
综上，合法路径种数为\ C_{2n}^{n}-\ C_{2n}^{n+1}。
最后，我们对此式进行整理与化简，得出结果为为
\frac{C_{2n}^{n}}{n+1}
结论：
序列个数为 n的出栈序列种数=C(2n,n)/(n+1)
利用卡特兰数的这个规律，我们可以求解入栈序列元素个数为n时，其出栈共有多少种可能性。而且在求解所有合法出栈序列的算法中，我们也会用到类似的思想。
附上Catalan数前12项数表