引入
有 \(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后面的就不会了。。。
待更