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.