341Proof 3 in this link is perhaps what you are looking for: http://en.wikipedia.org/wiki/Catalan_numbers
8 Answers
341
66Or consider the following problem:
Suppose there are 2n persons standing in a straight queue in front of a theater ticket booking office. Each ticket costs Rs 5. Out of the 2n persons, n of them have got only 5 rupees currency while the remaining has got only 10 rupees currency. Each person buys only one ticket. How many ways can the 2n persons (we distinguish them by only the currency they hold) stand so that there is no problem of change at the booking counter? To begin with the ticket clerk has no change.
341That too looks like an application of Catalan sequence. Suppose you denote the 5 rupee wallas by X and 10 rupee walas by Y, then we are looking for a string with X's and Y's in which at no section of the string starting from the beginning do we have more Y's than X's (as that would leave the clerk with no change to hand over the customer)
These are known as Dyck words.
Is there are more elementary way of doing this problem?
