In a queue for tickets costing 5 dinars each, n+m people are…

In a queue for tickets costing $5$ dinars each, $n+m$ people are waiting: $n$ of them have $5$-dinar bills and the remaining $m\lt n$ have $10$-dinar bills. Each person buys one ticket. What is the probability that nobody will have to wait for change? (The cashier has no money at the start.)

Step 1: The condition

All $\binom{n+m}{n}$ orders of the "$5$" and "$10$" people are equally likely. Draw the path: up for a $5$, down for a $10$. The height after $k$ people is the number of $5$-dinar bills in the till. A person with a $10$ can get change iff the height before them is at least $1$, i.e. the path never goes below $0$.

Step 2: Count bad paths (reflection)

A bad path reaches height $-1$ at some point. Reflect the part of the path after the first visit to $-1$ in the line of height $-1$. The path from $0$ to $n-m$ becomes a path from $0$ to $-1-(n-m+1)=-(n-m)-2$. Such a path has $u$ up and $d$ down steps with $u+d=n+m$, $u-d=m-n-2$, so $u=m-1$, $d=n+1$. The correspondence is one-to-one, so

\[ \#\text{bad} = \binom{n+m}{m-1}. \]

Step 3: The probability

\[ P = 1-\frac{\binom{n+m}{m-1}}{\binom{n+m}{m}} = 1-\frac{m}{n+1}, \]

since $\dfrac{\binom{n+m}{m-1}}{\binom{n+m}{m}}=\dfrac{m}{n+1}$.

\[ \boxed{P=\frac{n-m+1}{n+1}.} \]

Step 4: Checks

For $n=m=1$: of the orders "5, 10" and "10, 5", only the first works: $P=\frac12=\frac{1-1+1}{2}$ ✓. For $n=m$ the formula gives $\frac1{n+1}$, the probability behind the Catalan numbers.

Step 5: Comparison with the ballot problem

In Problem 117 the path must stay strictly above $0$; here it may touch $0$ but not go below. That is why the answers differ: $\frac{n-m}{n+m}$ versus $\frac{n-m+1}{n+1}$.