先看2个问题：
1.n个元素进栈（栈无穷大），进栈顺序为1,2,3，....n，那么有多少种出栈顺序？
先从简单的入手：
n=1，当然只有1种；
n=2，可以是1,2  也可以是2，1；那么有2种；
n=3，可以是1,2,3或1,3,2或2,1,3或2,3,1或3，2,1；一共5种；
容易联想到可能有一个通项公式可以求；
(扯一点，以前学栈的时候做过判断一个序列是否为合法的出栈顺序的题目，只要依次检查序列，对于一个元素i，在i后面出来的且序号比i小的肯定是从大到小出来的，比如 4 2 1 3，如果4都出来了，那么栈里从上到下只能是3 2 1)
通项公式的推导：
起先设F【i】表示i个元素进出栈（入栈的编号从小到大）的方案数；F【0】=1；F【1】=1；F【2】=2；F【3】=5； 
对于F【n】；假设编号为1的元素先入栈，在出栈，那么剩下n-1个元素，方案数就是F【1】*F【n-1】；
假设编号为1和2的元素入栈出栈，有F【2】种方案，剩下n-2个元素，根据乘法原理方案数就是F【2】*F【n-2】；
。。。。
1,2,3，。。。n-1先入栈出栈。。。。
相加就是总方案数
但是带入发现不对：其实这样枚举会漏解，因为这样枚举元素n永远都是最后一个出栈；
思路二：
假设元素1第一个出栈，剩下n-1个； 方案数就是F【1】*F【n-1】；
假设元素1第二个出栈，剩下n-2个；1前面的1个元素出栈有F【1】种方案，后n-2个有F【n-2】种，根据乘法原理 方案数就是F【2】*F【n-2】；
假设元素1第三个出栈，剩下n-3个；1前面的2个元素出栈有F【2】种方案，后n-3个有F【n-3】种，根据乘法原理 方案数就是F【3】*F【n-3】； 
。。。。。
假设元素1第n个出栈。。。。。。
相加就是总方案数；
公式的话F【n】=F【k-1】*F【n-k】(1<=K<=n);

问题2；n个1和n个0组成一个2n位的二进制数；要求从左到右的1的累计数不少于0的累计数，求方案数；
假设有一个2n位的二进制数，从左到右某一位开始不满足条件，那么这一位前面的1和0一样多，所以这一位必定是奇数位；
设第2k+1位开始不满足条件，那么第2k+1位是0；前面2k+1位有k个1和k+1个0，剩下后面的（2n-2k-1）位有n-k个1和
n-k-1个0；如果把后面的（2n-2k-1）位中的n-k个1换成0，把n-k-1个0换成1；那么这个二进制数就变成了由n+1个0和n-1个1组成的二进制数；因此可知任意一个不符合要求的数都可以转化成一个由n+1个0和n-1个1组成的二进制数；
同理反过来 任意一个由n+1个0和n-1个1组成的二进制数都可以转化成一个不符合要求的数；证明：由于0比1多2个，必定在从某一个偶数位开始，0的个数比1多2个；同理把后面部分的01互换，就变成一个由n+1个0和n-1个1组成的二进制数；
所以总方案就等于 n个1和n个0组成一个2n位的二进制数的个数减去由n+1个0和n-1个1组成的二进制数的个数；
F【n】=C（2n，n）-C(2n，n-1)=C（2n，n）/（n+1）；

由问题二 再来看 问题一：进栈的累计次数必定不少于出栈的累计次数，故
 F【n】=C（2n，n）-C(2n，n-1)=C（2n，n）/（n+1）；
也等于 F【k-1】*F【n-k】(1<=K<=n);这就是Catalan数（数学家Catalan在研究乘法结合律的时候提出，即求一个式子a1*a2*a3*a4*a5*。。。an一共有多少种添加括号的方法）；

总结：像这种某两个元素的总个数相等，但其中一个的累计数不小于另一个的题目都可以用Catalan数的公式来解决； 
 
相关练习：
1.2n个人排成一行买票，n个人只有10元整，n个人只有5元整，票价5元一张，问有多少种排队的方法，使得只要有带着10元的人买票，就有零钱可以找给他；
2.过河卒改编版，（图不好画，，结合过河卒的图吧）就是从左到右，n行n列，第一列只有从下到上1个 格子，第2列从下到上有2个，第n列有n个格子，从最左下角走到最右上角有多少种方案；