Ticket-Change probability problem Here is another question from the book of V. Rohatgi and A. Saleh. I would like to ask help again. Here it goes:
Waiting in line for a Saturday morning movie show are $2n$ children. Tickets are priced at a quarter each. Find the probability that nobody will have to wait for change if before a ticket is sold to the first customer, the cashier has $2k$ ($k<n$) quarters. Assume that it is equally likely that each ticket is paid for with a quarter or a half-dollar coin.
I find it hard to understand the phrase "nobody waits for change". I hope someone can help. Thanks.
 A: Hint: Apply the reflection principle in a similar way to deal with the general case. 
This problem is equivalent to starting at $(0, 2k)$ with steps of $(1,1)$ and $(1, -1)$. Without restriction, there are $2^{2n}$ possible paths.
How many ways are there which do not go below the line $y=0$? That's the number of ways that do not touch the line $y=-1$. Let's count the complement, namely the number of lines which touch $y=-1$. 
For each such path, using the reflection principle, we reflect the path after the last point of contact with the line $y=-1$. This gives us a path from $(0, 2k)$ which ends with $y \leq -1$. Now show that this is a bijection.
The number of such paths is thus clearly $\sum_{i=0}^j { 2n \choose i}$ for a certain value of $j$ which you should determine.
Let's say we took $a$ up steps and $2n-a$ down steps. Since we started out at $(0,2k)$, we would end up at a y-coordinate of $2k + a - (2n-a) = 2k+2a - 2n$. We want this to be $\leq -1$, and hence $2a \leq 2n - 2k - 1 \Rightarrow a \leq n - k - 1$ (since they are all integers). This is our value of $j$.
