栈混洗：$n$ 个对象依次入栈，但允许在满足栈的规则下随时出栈，其所有可能的出栈顺序。
合式（well-formed）序列：$n$ 对括号组成的序列，满足从左到右扫描这个序列时，右括号出现的数目始终不大于左括号出现的数目。
显见栈混洗和合式序列是一一对应的。
Catalan数：$Cat(n)=C(2n,n)-C(2n,n-1)=\frac{(2n)!}{(n-1)!(n+1)!}$。
栈混洗数目 = 合式序列数目 = Catalan数。
证明：非合式序列和 $(n-1)$ 个左括号和 $(n+1)$ 个右括号构成的所有序列一一对应（将非合式序列自第一个多出的右括号开始全部括号变方向）。
参考资料：
清华大学电子系吴及老师课件