# Number of ways of getting valid change

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$.

-

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.

-
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
@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