题目：给定进栈顺序1，2，……，n，求出栈序列个数。
分析：关键点就是空栈不能出栈。以“1”表示进栈，“0”表示出栈，则n个数总共进栈n次，出栈n次。一个进出栈序列可以唯一表示成110011…01， 此时，进出栈问题变成了排列问题。
如果不考虑合理性（即空栈出栈），此时共有C(2n,n)个序列。
那么不合理的序列有多少种？有C(2n,n-1)种。
所以总的出栈序列个数就是上面两个数相减C(2n,n) - C(2n,n-1) = C(2n,n) /(n+1) ，也就是卡特兰数。
下面解释不合理序列个数C(2n,n-1)怎么来的：
对于一个不合理的进出栈序列比如1101000……10，从左到右，必然在某一奇数位2m+1首先出现m+1个0，和m个1。（为什么不是偶数位，因为这个数之前都是合理的，合理的数必然是0和1个数相等（栈空），或者1比0多。第一种情况下出现0，此时恰好不合理，恰好在奇数位，第二种情况出现0，序列仍然合理） 此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合理的数对应于一个由n+1个0和n-1个1组成的排列，即C(2n,n-1)
为什么能这么算？ 如果我们把原不合理序列称作序列①，由n+1个0和n-1个1组成的的序列称作序列②，可以发现①和②是一一映射的：
每一个序列①都可以唯一地换成序列②。充分性：必然充分。唯一性：①中不同的序列1和2，映射后必然不同，故①->②是单射
任一序列②都可以唯一地换成序列①。充分性：对于任一序列②，由n+1个0和n-1个1组成的2n位序列，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数，当我们找到不合理奇数位时，将其后的0，1互换，即可还原成①。唯一性：对于②中不同序列1和2，如果某两位不同（不会出现只有一位不同的情况），映射后仍然会不同，故②到①只能是单射。
结论：②的个数（由n+1个0和n-1个1组成的2n位序列的排列C(2n,n-1)）也就是①的个数。
