005. Ticket Office with No Small Change

13 students are waiting in line to buy tickets to a museum where the admission fee is 50 cents. 5 of them each have a one-dollar bill, and the other 8 each have a 50-cent coin. At first, there was no change at the ticket office, so change could not be received, and each person should only buy one ticket. Find out how many ways to wait in line so that no student has to wait because they cannot get change. It is considered the same case if students with the same money change their order in a line.

Let aa and bb be a student with a 50-cent coin and a student with a one-dollar bill. Then, 13 students in line can be viewed as a sequence consisting of 8 aa’s and 5 bb’s. In order to receive change right away, the number of aa’s must be greater than or equal to the number of bb’s, no matter which student is selected starting from the first student. So, this is the exactly same with the number of cases going AA to BB as below when aa corresponds to the right-move and bb corresponds to the up-move.


Therefore, the number of cases is 572.

© 2024. All rights reserved.