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.