已知n个数的入栈序列，求一共有多少种出栈序列 (卡特兰数)

已知个数的入栈序列，求一共有多少种出栈序列

这个经典问题有两种解法。

解法一

设为个数入栈后，再全部出栈的序列数量

假设我们有个数, 我们来看的出栈顺序.

假如第一个出栈，那么后面还有个数没有出栈，因此方法数是.

假设第二个出栈，那么的前面有个数已经出栈，后面还有个数没有出栈，因此方法数为.

假设第三个出栈，那么的前面有个数已经出栈，后面还有个数没有出栈，因此方法数为.

同理，第四个出栈的方法数为.

那么我们就可以得到$f(4) = f(3) + f(1) f(2) + f(2)f(1) +f(3)$.

对于来推广一下，可以得到：.

不难发现这就是卡特兰数，这里就不在赘述了。

解法二

我们假设表示出栈，表示入栈，这样我们就可以用和组成的序列来表示出入栈操作。

首先来限定一些条件，一个合法的序列和的数量一定是相等的。并且序列的前缀和一定是不小于的。

了解了上面两个条件后，我们知道所有的序列数为,因为和的数量相同。在这个序列中，存在不合法的序列，即前缀和小于的序列，我们想要知道这些不合法的序列有多少。

假设我们有一个序列，这里在第三个下标，我们发现了它的前缀和小于，因此它不合法。再来推广一下，在这所有个序列中，不合法的序列它的前缀和一定在某一处小于.

接下来，我们将序列开头到不合法下标的这一段进行取反。首先拿上面的例子来进行说明，取反后得到：，不难发现，现在得到的序列比多出一个.

现在再来进行推广，我们截取的不合法序列段(从开头到不合法前缀和下标)，这一段中的一定比多一个，那么将这一段取反后所得到的总序列中的一定比多一个。

不难发现，不合法的序列一定对应唯一一个取反后的序列，并且取反后的序列中有个，有个，那么根据这个条件，我们就可以得到所有不合法的序列数量为或者(因为他两相等)。

最后，合法的序列数为：.

这个解法的关键在于，不合法的序列一定唯一对应一个取反后的序列，那么我们可以算出所有取反后的数列有多少种(根据有个，有个的性质)，来对应出不合法的序列数，从而得到答案.

因为感觉这种解法非常的巧妙，因此来总结一下.