This question already has an answer here:

Suppose that you are ticket collector in Cinema office. It cost 50 dollars to watch a movie. There are 20 people in line. 10 people in that line have exactly 100 dollar bills and 10 people have exactly 50 dollar bill. Now, since it is early in morning,you do not have any change. So,the people should be arranged in such a way that the line goes on without any interruption. What are total number of ways to arrange people in such a way that line proceeds smoothly?

One valid combination:


An invalid one:


My take: I tried to do this problem for small number like 3,4,5. However,I see no pattern to generalize the result to more people.


marked as duplicate by saulspatz, Jendrik Stelzner, YuiTo Cheng, Parcly Taxel, N. F. Taussig combinatorics May 26 at 11:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Interpret a person with a \$50 note as an opening bracket (you gain a \$50 note for later use) and a person with a \$100 note as a closing bracket (you use up a \$50 note in giving change to this person). Then, since there are an equal number of persons with \$50 and \$100 notes, the valid arrangements are in bijection with the number of ways to arrange ten pairs of brackets, correctly matched, so there are $C_{10}=16796$ valid arrangements, where $C_n$ denotes the Catalan numbers.


Not the answer you're looking for? Browse other questions tagged or ask your own question.