Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

This question already has an answer here:

There are 10 people waiting at the cinema theatre. 5 have Rs 50, 5 have Rs 100. The cost of the ticket is Rs 50. In how many ways can they stand in the queue such that there is no problem of change??

share|improve this question
2  
It’s possible to solve this problem by brute force, but the number is large enough that you’ll really want a better approach. Your problem is the case $n=5$ of the general problem in this question, and the answer that I gave there is essentially the same as the one that I’d give here. – Brian M. Scott Feb 27 at 12:07

marked as duplicate by Andreas Caranti, Asaf Karagila, Chris Eagle, rschwieb, Davide Giraudo Feb 27 at 14:45

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.

1 Answer

up vote 0 down vote

This is the same as the number of ways of balancing parentesis in a string of 10: Each '(' corresponds to somebody paying with Rs.50, an ')' to somebody paying with Rs.100 (you require that at each point there are no more ')' than '(' have shown up). This leads to Catalan numbers, your answer is $C_5 = \frac{1}{6} \binom{10}{5} = 42$.

share|improve this answer
I had a tough time to get the bijective proof of the above question, please explain the solution using bijection. – user64189 Feb 28 at 7:56
To me the biyection balanced parenteses <--> order in the queue is clear from the above. What exactly has you confused? – vonbrand Feb 28 at 9:59
the answer is C5 but not C10.@vonbrand – user64189 Feb 28 at 15:14
i indirectly asked for a proof of the above formula. – user64189 Feb 28 at 15:22
@user64189, you are absolutely right. Fixing. Thanks! – vonbrand Feb 28 at 16:12
show 7 more comments

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