一场球赛开始前,售票工作正在紧张进行中。每张球票为50元,有m+n个人排队等待购票,其中有m 个人手持50元的钞票,另外n个人手持100元的钞票。这m+n个人排队购票时,特别规定第5位为持50元,第8位为持100元,求出这m+n个人排队购票,使售票处不至出现找不开钱的局面的不同排队种数 。(约定:开始售票时售票处没有零钱,拿同样面值钞票的人对换位置为同一种排队。)
时间: 2023-06-09 15:05:25 浏览: 280
售票排队系统
5星 · 资源好评率100%
这个问题需要使用组合方法进行计算。
首先考虑50元的顾客,假设他们排成一个有序队列,记为$A_1,A_2,\cdots,A_m$。第5位必须是$A_5$,那么他前面有4种选择,后面有$m-5$种选择。其他$m-1$个50元顾客没有限制,可以随意排列,共有$(m-1)!$种排列方式。
同理,考虑100元的顾客,假设他们排成一个有序队列,记为$B_1,B_2,\cdots,B_n$。第8位必须是$B_8$,那么他前面有7种选择,后面有$n-8$种选择。其他$n-1$个100元顾客没有限制,可以随意排列,共有$(n-1)!$种排列方式。
现在需要把$A_1,A_2,\cdots,A_m$和$B_1,B_2,\cdots,B_n$合并成一个队列,使得每个50元顾客前面都是50元顾客,每个100元顾客前面都是50元顾客。考虑将$A_5$和$B_8$插入到队列中间的过程,相当于将$m-5$个50元顾客和$n-8$个100元顾客插入到$m+n-2$个空隙中(这个数目等于队列总人数减去已经插入的顾客数目)。空隙的数目为$m+n-1$个,插入顺序可以任意排列,所以插入的方案数为$(m-5+n-8)!\over(m-5)!(n-8)!$。
最终答案为$$
4\times(m-5)\times(m-1)!\times7\times(n-8)\times(n-1)!\times{(m-5+n-8)!\over(m-5)!(n-8)!}
$$
注意到$m$和$n$的范围比较小,可以直接枚举,时间复杂度为$O(m^2n^2)$。
阅读全文