I think this question uses catalan numbers.. but I don't know exactly how to answer it… its not homework or anything but I need to understand how to do it.. I tried drawing up likes for each 5r dolla bill the cashier has and down lines for each one he gave as change.. attempting to create "mountains" but the possibilities become very large extremely quickly which is giving me trouble creating an equation.. anyhow here is the question…
75 people have 5 dollar bills and 25 people have 10 dollar bills, and they are in line at a ticket counter which has no money and which charges 5 dollars for admission. If a 10 dollar bill is presented and there is no change, the line stops. What is the probability that the ticket seller always (after the first person in line, that is) has at least one 5 dollar bill for change?
As above, what is the probability the ticket seller was always able to make change.
What is the probability that the ticket seller was always able to make change if he is now allowed to use his own, single 5 dollar bill, if needed?
Best Answer
Here's an answer to the first question. Since the other two questions are variations of the first one, they are left as challenge for you! :-)
Analysis: We have queues of length $100$ with \begin{align*} \binom{75+25}{25}\tag{1} \end{align*} possible configuration. In order to get a valid configuration it has to be assured, that for each person with a $10$ dollar bill at least one other person with a $5$ bill has to be in front of him.
The number of pathes from $(0,0)$ to $(75,25)$ with length $100$ is according to (1): $\binom{100}{25}$ since we can select $25$ $(0,1)$-steps in $y$-direction out of $100$ leaving $75$ left for the $(1,0)$-steps in $x$-direction.
Since this is a bijection we conclude: The number of invalid paths from $A$ to $B$ is the number of all paths from $A^\prime$ to $B$, namely:
\begin{align*} \binom{76+24}{24} \end{align*}
Note: This problem is a variation of Bertrand's ballot theorem. The relationship with the Catalan Numbers $\frac{1}{n+1}\binom{2n}{n}$ is stated there in the section equivalent problems in this page.