Question

请教数学高手一道排列组合的题目怎么都想不通

78．电影院卖票。
　　有一些人排队进电影院，票价是5角。查了一下，进电影院人的个数是2个倍数，在这些人当中，其中一半人只有5角，另外一半人有1元纸票子。电影院开始卖票时竟1分钱也没有。有多少种排队方法使得每当一个1元买票时，电影院都有5角找钱？（拥有1元的人都是纸币，没法破成2个5角的纸币）

答案：（看不明白）
78．此题不在于计算，而在于找技巧。电影院能否找钱，关键在于买票的人如何排队。2a个人有（2a）！/[a！a！]种排法，电影院不可以找钱的排法有（2a）！/[（a-1）！（a+1）！]两者之差就是电影院能够找开钱的排队方法，答案为（2a）！/[a！（a+1）！]

基本的排列组合知识了解比如说阶乘的含义，您只需要告诉我那个没法找零的表达式是按照什么思路写出来的就好。

Answer 1

这是著名的卡特兰数问题，你百度一下“卡特兰数”有很多资料。现把我收集的资料加上我的注释，解释如下：

 

       我们来看一种图形化的方法证明这个等式我们把对n个5角的和n个1元的排队理解为在一个n * n的方格中从一个顶点走向对角的过程。过程中的每个顶点代表一个拿1元的或者5角的。向右走n次（代表5角的），向上走n次（代表1元的）。题意可以得出在任何一个人断开其前面的拿5角的必须大于或等于拿一元的人。也就是只在图中实线部分，而不超过对角线的线路：

        每次沿着实线走，所以，只要求出从方格左下角到右上角路径的个数即可。        我们把表格补全，考虑每一条不合法的路径，如

 

 

 

 

        在这条路径上，必然有一个地方连续两次向上，即从图上蓝点处开始，而且这个点必然在如图所示的绿线上。我们以这个点为起点，把到左上角整条路经取反，也就是对称上去，得到一条新路径，但是超出了表格。我们知道，这条路径包括n + 1次向上和n – 1次向下，也就是在一个(n + 1) * (n - 1)的方格中。由此我们知道，一条不合法路径必然对应一个(n + 1) * (n - 1)方格中的路径。同样地，对于(n + 1) * (n - 1)方格中任意一条路径，以这条路径与绿线的第一个交点为起点到方格的右上方全部取反，即可得到一个在n * n方格中的不合法路径。

 

 

 

 

        我们通过这样的方法确定了每条不合法路径与一个(n + 1) * (n - 1)方格中路径的一一对应关系，因此，方格中不合法路径总数为C(2n, n - 1)，而所有路径总数为C(2n, n)，两式相减即为原组合等式。

Answer 2

佩服1楼的解答，不管对不对，真是耐心啊！