栈（stack）是一种线性表，所有的插入和删除都在表的一端进行。其中，插入被称为压栈(push)，删除被称为弹栈(pop)，由于只能对最新被压入的元素进行弹出，栈又被称为后入先出(LIFO)表。
对于栈，给定一个输入序列(1,2...n) ，有两个经常被提及的问题，
- 长度无限的栈可以有多少种输出序列。
- 给定一个输出序列(p_1,p_2...p_n) ，如何判定它是否有效？
比如，对于输入序列(1,2,3)，我们有以下输出序列
- (1,2,3)
- (1,3,2)
- (2,1,3)
- (2,3,1)
- (3,2,1)
序列(3,1,2)是不合法的，因为输出3时，1和2已经被压进栈中，故而输出时2必须在1前面，不可能出现(3,1,2)的输出序列。
问题一
将问题一转化一下，由于输入序列已经确定，在栈上执行的操作将唯一地决定输出的序列，因而可以定义压栈操作为S，弹栈操作为X，使用S和X的序列来表示输出的序列。比如(1,2,3)可以用(SXSXSX)表示。容易看出，对于长度为(n)的输入序列，SX的序列长为(2n)，其中S和X各占n个。可以证明，SX序列和输出序列一一对应。
下面解决问题1，不同的输出序列的数量就是不同的合法SX操作序列的数量。合法的操作数等于n个S与n个X的组合数减去其中非法的组合数。根据SX在栈上的意义，非法的组合可以如下判定：
- 从左向右对S和X计数，若在某一点X的个数超出S的个数，则操作非法
比如(XSSSXX)就是一个非法的组合。
这个数目被称之为卡特兰数，是一个很有用的数学结论，下面给出一个不严谨的推导。
对于长度为n的输入序列，n个S与n个X的组合数为(dbinom{2n}{n})，对于每个非法的组合，从左向右记到第一个非法的X，将包括这个X在内的左边全部S和X反转，即将
转化为
这样，由于在第一个非法的X左边，S和X的数目相等，右边S的数目要比X的数目多1。进行反转后，总体上S的数目要比X的数目多2，即变为由(n+1)个S与(n-1)个X的组合。每个不合法的SX序列都可以唯一转化为一个这样的组合，每个这样的组合也可以唯一转化为不合法的SX序列。易证对于不同的非法序列不会映射为相同的结果，同理两个不同的(n+1)S与(n-1)X的组合也不会映射为相同的非法序列。故卡特兰数的结果为
问题二
命题：对于序列(p_1p_2...p_n)，其使用栈得到输出序列(S)的充要条件为序列中不存在(p_i...p_j...p_k)，在(T)中的输出顺序为(p_k...p_i...p_j)。
证明：
在输出的任意时刻，我们有还未入栈的剩余序列(p_m...p_n)，栈内元素(栈底为左)(s_1...s_k)，以及顺序合法的已输出元素(t_1t_2...t_a)，对于下一个将出现在输出序列中的元素(t_{a+1})，有两种情况
- 存在于未入栈序列(p_m...p_n)中
- 是栈顶元素(s_k)
- 存在于栈中且不为栈顶元素
对于情况一，我们只需不停地入栈直到(t_{a+1})成为栈顶元素，此时化归为情况二
对于情况二，我们只需弹栈即可
对于情况三，我们证明在充分条件下其不存在。
使用反证法假设其存在。由于(t_{a+1})不为栈顶元素，设从(t_{a+1})到栈顶选取一个元素(o_{temp})，由于已经存在的序列是合法的，则(t_{a+1}) 的输出顺序应先于(o_{temp})。即(t{a})先于(t{a+1})先于(o_{temp})。由于现有输出序列均是由栈弹出获得，根据栈的性质可知入栈顺序(t{a+1})先于(o_{temp})先于(t_a)，即在序列中，(t{a+1})先于(o_{temp})先于(t_a)。令
则与条件矛盾，故可证。
必要性略。
总结
卡特兰数为抽签问题的特殊形式。除卡特兰数之外，还有一种扩展是在规定了栈长度m以后求可能的输出序列数，这个问题比较困难，笔者目前还没有头绪。