How many ways can we let people into a movie theater if they only have half-dollars and dollars? My interest in combinatorics was recently sparked when I read about the many things that the Catalan numbers count, as found by Richard Stanley. I picked up a copy of Brualdi's Combinatorics, and while browsing the section on counting sequences I found a nice little puzzle that has definitely puzzled me.

Let $m$ and $n$ be nonnegative integers with $n\geq m$. There are $m+n$ people in line to get into a theater for which admission if $50$ cents. Of the $m+n$ people, $n$ have a $50$-cent piece and $m$ have a $\$ 1$ dollar bill. The box offices opens with an empty cash register. Show that the number of ways the people can line up so that change is available when needed is
  $$
\frac{n-m+1}{n+1}\binom{m+n}{m}.
$$


I first noted that the first person to enter must be one of the $n$ with a half-dollar. Now the register has a half-dollar change. The second person can be either a person with a half-dollar or a dollar. In the first case, the register will now have two half-dollars, in the second case, the register will now have one dollar bill. So it seems to me that when one of the $n$ people with a half-dollar enters, the number of half-dollars in the register increases by $1$, and when one of the $m$ people with a bill enters, the number of half-dollars decreases by $1$ but the number of bills increases by $1$. 
I tried to model this by looking at paths in $\mathbb{Z}^2$. The $x$-axis is like the number of half-dollars, and the $y$-axis is the number of bills. You start at $(0,0)$, and you can take steps forward $(1,0)$ or backwards diagonally $(-1,1)$ corresponding to who enters, but you must always stay in the first quadrant of the plane without crossing over the axes. The goal is to make $m+n$ moves, and I figured maybe the number of such paths is counted by $\frac{n-m+1}{n+1}\binom{m+n}{m}$, but I'm not sure how to show this. I don't know if this observation simplifies the problem at all, as I don't know how to finish up. I'd be happy to see how this problem is done, thank you.

There is one nice one-to-one correspondence that may be set up here:
First of all, there is clearly ${n+m \choose{n}}$ different arrangements that people can enter in.
Let $(i,j)$ denote the moment at which $i+j$ people have paid for their ticket, where $i$ represents the number of people paying with a $50$ cent piece, $j$ the number of people paying with a $\$1$. Here it does not matter if everyone receives change or not. Every arrangement of people ends with $(n,m)$. 
To make sure that change is available for everyone, it must always be the case that $i \ge j$. 
We count all the arrangements that are bad, i.e. that at some point someone does not recieve their change. When the first person who does not get change back enters, we have $(k,k+1)$ for some $k$. 
Here, do the following trick: suppose all the people that had $\$1$'s, now wish to pay $50$ cents, and vice versa. So out of the remaining people, $m - (k+1)$ pay $50$ cents and $n - k$ pay $\$1$ bills. In total, we have $(k+m-(k+1),k+1+n-k) = (m-1, n+1)$.
We are given that $n \ge m$, so $n+1 > m-1$. So in this case, the number of people paying $\$1$ bills is strictly greater than the number of peple paying otherwise. Now notice, that in any arrangement of people entering that ends with $(m-1,n+1)$ there must be a a first $k$, when we have $(k,k+1)$.
We can now switch "who pays what" as before, and we get back an arrangement that ends with $(n,m)$.
This creates a nice bijection between all bad arrangements (where someone does not get their change) that end with $(n,m)$ and all possible arrangements that end with $(m-1,n-1)$. Counting as before, there are ${n+1+m-1 \choose{n+1}} = {n+m \choose{n+1}}$ possible arrangements ending with $(m-1, n-1)$. So the number of arrangements where everyone gets their change is:
$${n+m \choose{n}} - {n+m \choose{n+1}} = {{n+m \choose{n}}} \dfrac{n+1-m}{n+1}$$
Note also that the probability of a good arrangement occuring comes out nicely to 
$$\dfrac{n-m+1}{n+1}$$
