有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的电影院开始卖票时1分钱也没有。
问： 有多少种排队方法 使得 每当一个拥有1美元买票时，电影院都有50美分找钱
注：
1美元=100美分
拥有1美元的人，拥有的是纸币，没法破成2个50美分

【15】一个人花8块钱买了一只鸡，9块钱卖掉了，然后他觉得不划算，花10块钱又买回来了，11块卖给另外一个人。问他赚了多少?
user
有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的电影院开始卖票时1分钱也没有。
问： 有多少种排队方法 使得 每当一个拥有1美元买票时，电影院都有50美分找钱
注：
1美元=100美分
拥有1美元的人，拥有的是纸币，没法破成2个50美分

【15】一个人花8块钱买了一只鸡，9块钱卖掉了，然后他觉得不划算，花10块钱又买回来了，11块卖给另外一个人。问他赚了多少?
assistant
本题可用递归算法，但时间复杂度为2的n次方，也可以用动态规划法，时间复杂度为n的平方，实现起来相对要简单得多，但最方便的就是直接运用公式：$$排队的种数=(2n)!/[n!(n 1)!]$$。
如果不考虑电影院能否找钱，那么一共有$$(2n)!/[n!n!]$$种排队方法（即从$$2n$$个人中取出$$n$$个人的组合数），对于每一种排队方法，如果他会导致电影院无法找钱，则称为不合格的，这种的排队方法有$$(2n)!/[(n-1)!(n 1)!]$$（从$$2n$$个人中取出$$n-1$$个人的组合数）种，所以合格的排队种数就是$$(2n)!/[n!n!]- (2n)!/[(n-1)!(n 1)!] =(2n)!/[n!(n 1)!]$$。