http://www.cnblogs.com/wuyuegb2312/p/3016878.html
问题（《编程之美》4.3买票找零）：2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至于使售票处找不开钱？
分析1：队伍的序号标为0,1,...,2n-1,并把50元看作左括号，100元看作右括号，合法序列即括号能完成配对的序列。对于一个合法的序列，第0个一定是左括号，它必然与某个右括号配对，记其位置为k。那么从1到k-1、k+1到2n-1也分别是两个合法序列。那么，k必然是奇数（1到k-1一共有偶数个），设k=2i+1。那么剩余括号的合法序列数为f(2i)*f(2n-2i-2)个。取i=0到n-1累加，
并且令f(0)=1，再由组合数C(0,0)=0,可得
n+m个人排队买票，并且满足
，票价为50元，其中n个人各手持一张50元钞票，m个人各手持一张100元钞票，除此之外大家身上没有任何其他的钱币，并且初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。
这个题目是Catalan数的变形，不考虑人与人的差异，如果m=n的话那么就是我们初始的Catalan数问题，也就是将手持50元的人看成是+1，手持100元的人看成是-1，任前k个数值的和都非负的序列数。
这个题目区别就在于n>m的情况，此时我们仍然可以用原先的证明方法考虑，假设我们要的情况数是
，无法让每个人都买到的情况数是
，那么就有
，此时我们求，我们假设最早买不到票的人编号是k，他手持的是100元并且售票处没有钱，那么将前k个人的钱从50元变成100元，从100元变成50元，这时候就有n+1个人手持50元，m-1个手持100元的，所以就得到
，于是我们的结果就因此得到了，表达式是
。
问题（《编程之美》4.3买票找零）：2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至于使售票处找不开钱？
分析1：队伍的序号标为0,1,...,2n-1,并把50元看作左括号，100元看作右括号，合法序列即括号能完成配对的序列。对于一个合法的序列，第0个一定是左括号，它必然与某个右括号配对，记其位置为k。那么从1到k-1、k+1到2n-1也分别是两个合法序列。那么，k必然是奇数（1到k-1一共有偶数个），设k=2i+1。那么剩余括号的合法序列数为f(2i)*f(2n-2i-2)个。取i=0到n-1累加，
并且令f(0)=1，再由组合数C(0,0)=0,可得
n+m个人排队买票，并且满足
，票价为50元，其中n个人各手持一张50元钞票，m个人各手持一张100元钞票，除此之外大家身上没有任何其他的钱币，并且初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。这个题目是Catalan数的变形，不考虑人与人的差异，如果m=n的话那么就是我们初始的Catalan数问题，也就是将手持50元的人看成是+1，手持100元的人看成是-1，任前k个数值的和都非负的序列数。
这个题目区别就在于n>m的情况，此时我们仍然可以用原先的证明方法考虑，假设我们要的情况数是
，无法让每个人都买到的情况数是，那么就有，此时我们求，我们假设最早买不到票的人编号是k，他手持的是100元并且售票处没有钱，那么将前k个人的钱从50元变成100元，从100元变成50元，这时候就有n+1个人手持50元，m-1个手持100元的，所以就得到，于是我们的结果就因此得到了，表达式是。