1. 不能得到的序列有什么特征

那就是：当一个大数后出现一个小数，比如5后面接着2（52），那么5前面一定出现过3和4，如若没有，这个序列就是错误的。总结就是大数A后接一个小数B，如果是符合条件的序列，那么A前面一定存在小数使得B到A连续。

例子：5 4 1 2 3

分析：大数5后接小数4，4 5连续没问题；大数4后接小数1，但4之前2和3没有出现，使得1-4不连续，故这个序列不满足条件。

原理：当一个大数出现时，比他小的数一定是入栈了的，比如序列第一个数5，那么12345是入栈了的。当出现一个较小数3，5出栈接着3再出栈，由于4在3之后入栈，所以4一定在3之前出栈，所以5之前一定出现3，否则这个序列不合法。

2.得到的序列有多少种

结论是一个卡特兰数

h(n)=h(0)*h(n-1)+h(1)*h(n-2)+.....+h(n-1)h(0)=C(2n,n)-C(2n,n+1)

思路：分类相加，分步相乘

怎么分类呢？

我们知道，1，2，3，4，....，n中元素1出栈的顺序可以是1-n的任意一种，故按第一个元素出栈的顺序分类。设第一个元素出栈顺序为k，它把序列分为两段，第一段为2~k，出栈方式为h(k-1)；第二段为k+1~n，出栈方式为h(n-k)。

所以总的方法数量为：h(n)=h(0)*h(n-1)+h(1)*h(n-2)+.....+h(n-1)h(0)=C(2n,n)-C(2n,n+1)，其中h(0)=h(1)=1