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

Question

有2n个人排队进电影院,票价是50美分.在这2n个人当中,其中n个人只有50美分,另外n个人有1美元（纸票子）.愚蠢的电影院开始卖票时1分钱也没有.问：有多少种排队方法使得每当一个拥有1美元买票时,电影院都有50美分找钱
　　注：1美元=100美分拥有1美元的人,拥有的是纸币,没法破成2个50美分
　　【解答】本题可用递归算法,但时间复杂度为2的n次方,也可以用动态规划法,时间复杂度为n的平方,实现起来相对要简单得多,但最方便的就是直接运用公式：排队的种数=(2n)!/[n!(n+1)!].
　　如果不考虑电影院能否找钱,那么一共有(2n)!/[n!]种排队方法（即从2n个人中取出n个人的组合数）,对于每一种排队方法,如果他会导致电影院无法找钱,则称为不合格的,这种的排队方法有(2n)!/[(n-1)!(n+1)!]（从2n个人中取出n-1个人的组合数）种,所以合格的排队种数就是(2n)!/[n!]-(2n)!/[(n-1)!(n+1)!]=(2n)!/[n!(n+1)!].至于为什么不合格数是(2n)!/[(n-1)!(n+1)!],
谁给解释下为什么总数是那么多,而不符合要求饿的排队数是那么多.

Answer 1

(2n)!/[n!n!]-(2n)!/[(n-1)!(n+1)!]=(2n)!/[n!(n+1)!]