引入
有 \(n\) 个元素进栈序列为 \(1,2,3,4\dots n\)。求有多少种出栈序列
我们需要确保最后一次操作后，栈中没有元素。因此，共有 \(2n\) 次操作。（每个元素进栈一次，出栈一次）
对于每次操作，如果我们想出栈，则它一定要有数字可以 pop。如果我们把栈抽象成一条链，若第 \(k\) 次想要出栈，则必须满足 \(sum_k \geq 0\)（\(sum_k\) 表示前 \(k\) 个操作的前缀和）
我们先不考虑不合法的序列，则共有 \(C_{2n}^n\) 种方案。也就是在 \(2n\) 次操作中选 \(n\) 个标记为 \(1\)。\(1,-1\) 一定是一一对应的。
对于不合法的序列呢？
举个例子：对于不合法序列 \(+1,-1,-1,+1,-1,+1\) ， 显然从第 \(3\) 位就不合法。若对前 \(3\) 位进行取反，即序列变成 \(-1,+1,+1,+1,-1,+1\)。容易发现变成了 \(n+1\) 个 \(1\) 。
那么这个性质是否存在普遍性？
我们找的是第一个前缀和小于 \(0\) 的位置，因此它的前缀和一定是 \(-1\)。它前面的 \(-1\) 一定比 \(1\) 多一个。若取反，则 \(1\) 比 \(-1\) 多一个。就会导致 \(1\) 变成 \(n+1\) 个，\(-1\) 变成 \(n-1\) 个。
取反后的序列和取反前的序列一定是一一对应的。也就是从取反后的序列一定能变换成唯一的取反前的序列。
因此，不合法的序列个数等于 \(C_{2n}^{n+1}\)。 这里运用了转换法。因为取反前和取反后的序列一一对应，所以找取反后的序列个数即为不合法的方案个数。
所以，合法的出栈数量应为：
其中 \(\frac{C_{2n}^n}{n+1}\) 即为卡特兰数的通项公式。
md后面的就不会了。。。
待更