How many ways can we let people into a movie theater if they only have half-dollars and dollars?

Question

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.

Answer 1

You are correct that you can think of this as a problem of counting (restricted) paths on the $\mathbb{Z}^2$, and that this is probably a good way to think about it. But I think it is easier if you think of a square array, and you are trying to get from the bottom left, $(0,0)$, to the upper right $(n,m)$, and your steps must be from $(k,\ell)$ to $(k+1,\ell)$ or from $(k,\ell)$ to $(k,\ell+1)$:

If $n$ is the number of people with $50$ cent pieces, and $m$ is the number of people with dollar bills. When a person with a 50 cent piece enters, you take a step right. When a person with a dollar bill enters, you take a step up.

If you try to take a step from $(k,\ell)$ to $(k,\ell+1)$, you will only have enough change in the till if $\ell+1\leq k$. Otherwise, you'll be out of luck (because you need one person with 50 cent piece for every person with a dollar that has managed to come in).

So, you must always stay at or below the diagonal. So the paths you want to count are the paths from $(0,0)$ to $(n,m)$ that stay at or below the main diagonal.

(Notice that $\binom{n+m}{m}$ is the number of total paths from $(0,0)$ to $(n,m)$ taking only steps right or up: you must take $n+m$ steps total, and of those $m$ will be steps up; so $\binom{n+m}{m}$ picks which of the $n+m$ steps will be steps up. So the factor $\frac{n+1-m}{n+1}$ must be the fraction of the paths that stay at or below the main diagonal.)

Does that help sufficiently, or should I expand more?

Answer 2

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}$$