Take the 2-minute tour ×
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.

A movie theater charges $50$ Rupees for a ticket.

The cashier starts out with no change, and each change customer pays with a Rupees $50$ note or Rupees $100$ note (& gets change).

Clearly, the cashier will be in trouble if there are too many customers with $100$ rupees note.

It turns out that there are $2n$ customers, and cashier never had to turn them away, but after dealing with last customer, there were no $50$ rupees note left in cash register. Let $w_n$ denote the number of different ways this could have happened.

Find $w_n$.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

HINT: As each customer comes to the cashier, write down a left parenthesis if he pays with a $50$ rupee note and a right parenthesis if he pays with a $100$ rupee note. At the end you will have a string of $2n$ parentheses.

  • Show that exactly $n$ of the customers paid with a $50$ rupee note, so that the string has $n$ left and $n$ right parentheses.

  • Show that as you read the string of parentheses from left to right, you have always seen at least as many left parentheses as right parentheses. For example, if $n=3$, you might see (()()) or ()()(), but you cannot see ())(() or )((()).

Now look at this article on Catalan numbers, especially the part on Dyck words in this section.

share|improve this answer
    
Thanks , your post was indeed usefull including links :) i can show both points easily but i am having difficulties in calculations , how can we calculate possible sequences like you showed using parenthesis ? It would be very useful @Brian M.Scott if you could directly tell the answer/explanation as tomorrow is itself my olympiad :) –  Maggi Iggam Feb 2 '13 at 20:41
    
So is the answer (2n)!/((n+1)!n! ? But how can we prove that ? –  Maggi Iggam Feb 2 '13 at 20:44
1  
@Maggi: The article actually has a proof, though you have to modify it slightly. Look at this proof, but think of each $\to$ step as a ( and each $\uparrow$ step as a ). The legitimate parenthesis strings correspond to the lattice paths that do not cross the diagonal. –  Brian M. Scott Feb 2 '13 at 20:49
    
Thanks a lot Proffessor Brian M.Scott :D I loved combinatorcs a lot but this sector was totally unexplored by me , your links and application of Catalan nos. has really given me more approaches and techniques ! Thanks a looooot :D –  Maggi Iggam Feb 2 '13 at 20:53
    
@Maggi: You’re welcome! –  Brian M. Scott Feb 2 '13 at 20:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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