Question

一道数奥题

博览会的门票每张50元，每人限购一张，现有十个小朋友排队买票，其中五个小朋友只有100元的钞票一张，另外五个小朋友只有50元的钞票1张，售票员没有准备零钱，那么最多有几种排队方法，使售票员总能找的开钱？

Answer 1

现把拿1元的5个小朋友看成是相同的，把拿2元的5个小朋友也看成是相同的，使用我们常用的“逐点累加法”：

图中每条小横段表示拿1元的小朋友，每条小竖段表示拿2元的小朋友，要求从A走到B的过程中网格中任何点均有横段数不小于竖段数：拿1元的要先，且人数不能少于拿2元的，即不能越过对角线AB：每个点所标的数即为从A走到此点的方法数。求从A到B的走法的方法数。逐点累加可求出为42，即卡特兰数C5＝42。

又由于每个小朋友是不相同的，所以共有42×5！×5！＝42×120×120＝604800种情况

Answer 2

1、100、100、100、100、100 C55=1种
2、100、100、100、100、50、50 C62=15种
3、100、100、100、50、50、50、50 C73=35种
即51种排队方法