Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If n=m, these are the Catalan numbers you mention, as the Wikipedia page shows under monotonic paths. If you think of forward steps for the .50 and upward steps for the $1, the path has to stay on or below the diagonal –  Ross Millikan Feb 21 '11 at 0:39

2 Answers 2

up vote 10 down vote accepted

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?

share|improve this answer
    
Thank you for this quick response, Arturo. I will try to work my way through it, and see if I have any questions. –  yunone Feb 21 '11 at 0:31
6  
The fraction is essentially the well-known ballot theorem or ballot lemma, the only difference being that you are happy with equality part-way through; that is equivalent adding 1 to n before applying the ballot theorem (where both of the first two moves must be for the more popular choice). Four proofs of a slightly generalised form can be found at webspace.ship.edu/msrenault/ballotproblem/… –  Henry Feb 21 '11 at 0:38
    
@Arturo, I understand up to the point where you say the factor $\frac{n+1-m}{n+1}$ must be the fraction of paths that stay at or below the main diagonal. Based on Ross Millikan's comment on the main question, I see that the number of total paths at or below the main diagonal is $C_n=\frac{1}{n+1}\binom{2n}{n}$. How did you find the numerator $n+1-m$ to find this fraction of acceptable paths? –  yunone Feb 21 '11 at 0:50
    
@Henry, thank you for the link to the paper. I have never heard of the ballot theorem, but I will look into it. –  yunone Feb 21 '11 at 0:51
    
@yunone: I haven't given a derivation: what I tried to say was that, given that $\frac{n+1-m}{n+1}\binom{n+m}{m}$ is the answer to the problem, that the problem counts the number of "acceptable" paths, and that the total number of paths (both acceptable and unacceptable) is $\binom{n+m}{m}$, then the factor $\frac{n+1-m}{n+1}$ must represent the fraction of acceptable paths. I wasn't implying this directly gives the result, by any means. –  Arturo Magidin Feb 21 '11 at 1:49

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.