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.

In the recent question "What's the probability that a sequence of coin flips never has twice as many heads as tails?" I argue in my answer that the number of ways $S(n)$ to obtain twice as many heads as tails for the first time in $3n$ coin flips is $\binom{3n}{n} \frac{2}{3n-1}$. The argument works by showing that $S(n)$ satisfies a recurrence and then using a binomial convolution identity to show that $\binom{3n}{n} \frac{2}{3n-1}$ satisfies the recurrence as well.

However, it seems to me that there ought to be a nice, direct combinatorial proof that $S(n) = \binom{3n}{n} \frac{2}{3n-1}$. After all, there are $\binom{3n}{n}$ sequences of $3n$ coin flips in which $n$ are tails, and the number of those for which we see twice as many heads as tails for the first time is just $\frac{2}{3n-1}$ of that. I've been thinking about this some the past few days but have been unable to find a combinatorial explanation of the fraction $\frac{2}{3n-1}$.

So my question is...

Can someone provide a combinatorial proof that $S(n) = \binom{3n}{n} \frac{2}{3n-1}$?

And, more generally, if $S(n,r)$ is the number of ways to obtain $r$ times as many heads as tails then my argument in the answer mentioned above shows that $S(n,r) = \binom{(r+1)n}{n} \frac{r}{(r+1)n-1}$. It would be nice if the proof were generalizable to the $S(n,r)$ case.

One thought is that it might be possible to adapt one of the combinatorial proofs that the $n$th Catalan number $C_n$ is $\binom{2n}{n} \frac{1}{n+1}$. In fact, in the $r=1$ case the question is equivalent to finding the number of Dyck paths from $(0,0)$ to $(n,n)$ that do not touch the diagonal $y=x$ except at $(0,0)$ and $(n,n)$. This is known to be $2C_{n-1} = \binom{2n-2}{n-1} \frac{1}{n} = \binom{2n}{n}\frac{1}{2n-1} = S(n,2).$

In fact, that last paragraph makes me wonder if there might be some generalization of the Catalan numbers in this direction. Or perhaps the alternative formulation $S(n,r) = \binom{(r+1)n-2}{n-1} \frac{r+1}{n}$ admits a combinatorial proof more easily.


Added: I think Qiaochu Yuan's argument below about using Raney's lemma is on the right track, but it doesn't quite get to the expression I'm looking for. Raney's lemma is about a sequence in which all partial sums are positive. However, in obtaining $r$ times as many heads as tails for the first time the partial sums ($+r$ for each tail and $-1$ for each head) do not all have to be positive or all negative. For example, you could have a sequence like HHHT, with overall $+1$, and then if the next flip is a tail you would have HHHTT, with overall $-1$, and we still haven't reached exactly twice as many heads as tails.

I suspect the Raney's lemma argument can be adapted, but I don't think we quite have an answer to the question yet. Does anyone see how to do it?


Added 2: I found a complete combinatorial argument. See my answer below.

share|improve this question

2 Answers 2

up vote 15 down vote accepted

Here's the full combinatorial argument. Raney's lemma was about half of it, I'd say. The argument shows that $S(n,2) = \binom{3n-1}{n} \frac{3}{3n-1}$ (which is equivalent to the two formulations I give in the question). At the end I'll discuss the generalization to the $r$ case.


Intro.

Consider the sequences with $2n$ occurrences of $-1$ (i.e., $2n$ heads) and $n$ occurrences of $+2$ (i.e., $n$ tails). We want to show that the number of these sequences with all partial sums nonzero is $\binom{3n-1}{n} \frac{3}{3n-1}$. The complete sum and empty sum are clearly $0$, so "partial sum" excludes those two cases. The sequences we want to count can be split into three groups: (1) all partial sums positive, (2) all partial sums negative, (3) some partial sums positive and some negative.

Group 1: The number of these sequences with all partial sums positive is $\binom{3n-1}{n} \frac{1}{3n-1}$.

This is the part that uses Raney's lemma. If all partial sums are positive, the last element in the sequence must be $-1$. Thus we want to count the number of sequences with $2n-1$ occurrences of $-1$ and $n$ occurrences of $+2$ that add to $+1$ and have all partial sums positive. Ignoring the partial sums restriction, there are $\binom{3n-1}{n}$ such sequences. If we partition these $\binom{3n-1}{n}$ sequences into equivalence classes based on cyclic shifts, Raney's lemma says that exactly one sequence in each equivalence class has all partial sums positive. Because there are $3n-1$ elements in each sequence there $3n-1$ sequences with the same set of cyclic shifts, and so there are $3n-1$ sequences in each equivalence class. Thus the number of sequences in Group 1 is $\binom{3n-1}{n} \frac{1}{3n-1}$.

Group 2: The number of these sequences with all partial sums negative is also $\binom{3n-1}{n} \frac{1}{3n-1}$.

To see this, just reverse the sequences counted in Part 1.

Group 3: The number of these sequences with some positive partial sums and some negative partial sums is, yet again, $\binom{3n-1}{n} \frac{1}{3n-1}$.

This one is a little trickier. First, because of the $-1$'s, it is not possible to switch from positive partial sums to negative partial sums. Thus any sequence counted here must have exactly one switch: from negative partial sums to positive partial sums. The switch must occur at some point where the partial sum is $-1$ and the next element is $+2$. Thus we have some sequence $(a_1, \ldots, a_m, +2, a_{m+2}, \ldots, a_n)$ where the sums $a_1, a_1 + a_2, \ldots, a_1 + \ldots + a_m$ are all negative. Consider the sequence $(+2, a_m, \ldots, a_2, a_1, a_{m+2}, \ldots, a_n)$. Since $+2 + a_m + \ldots + a_1 = 1$, and $a_k + a_{k-1} + \ldots + a_1 < 0$ for all $k$, $1 \leq k \leq m$, it must be the case that $+2 + a_m + \cdots + a_{k+1} > 1$ for all $k$, $1 \leq k \leq m-1$. So the sequence $(+2, a_m, \ldots, a_2, a_1, a_{m+2}, \ldots, a_n)$ is in Group 1. To see that this mapping is a bijection, note that any sequence in Group 1 must start with $+2$ and have a first time that a partial sum is equal to $+1$. Thus this transformation is reversible.

Summing up.

Putting Groups 1, 2, and 3 together we see that the total number of sequences we want to count is $\binom{3n-1}{n} \frac{3}{3n-1}$.


Generalization to the $r$ case.

The arguments for Group 1 and Group 2 adapt in a straightforward manner for general $r$; we get $\binom{(r+1)n-1}{n} \frac{1}{(r+1)n-1}$ for both. Sequences in Group 3 can still only switch once - from negative partial sums to positive partial sums. But Group 3 can be broken up into subgroups depending on whether the first partial sum to become positive is $+1, +2, \ldots, r-1$. Using transformations like the one described above for Group 3 in the $r = 2$ case, we can show that there is a bijection between each of these $r-1$ subgroups and Group 1. Thus there are $\binom{(r+1)n-1}{n} \frac{r-1}{(r+1)n-1}$ sequences in Group 3. In total, then, $S(n,r) = \binom{(r+1)n-1}{n} \frac{r+1}{(r+1)n-1}$.


Final comment.

All of this is may be easier to visualize in terms of paths from $(0,0)$ to $((r+1)n,(r+1)n)$ that use right steps of size $1$ and up steps of size $r$ and that do not step on the diagonal except at $(0,0)$ and $((r+1)n,(r+1)n)$. (They can cross the diagonal, though.) I found it easier to discuss the partial sums interpretation, though, given the difficulty of creating such graphics on this forum.

share|improve this answer
1  
Nice! And a nice coincidence that this was exactly what was needed for this question. I think the one occurrence of $a_{m+2}$ and the two occurrences of $a_{m+1}$ are all supposed to refer to the same number? –  joriki Oct 1 '11 at 14:05
    
@joriki: I'm glad this was helpful in the other answer! And nice catch; they should all be $a_{m+2}$. I'll fix the post. –  Mike Spivey Oct 1 '11 at 15:54

A direct combinatorial proof follows from

Raney's lemma: Let $a_1, ... a_m$ be a sequence of integers such that $\sum a_i = 1$. There is a unique index $j$ such that the partial sums of the sequence $a_j, a_{j+1}, ... a_{j+m-1}$ (cyclic indices) are positive.

The only writeup I know of this argument is this blog post; I learned it from solving a problem on AoPS which strongly suggested Raney's lemma as its solution. (In the post I might be counting something slightly different.)

There is a nice generalization hiding here given by the combinatorial proof of Lagrange inversion, which is given, for example, in Stanley's Enumerative Combinatorics Vol. II, Section 5.4.

share|improve this answer
    
Wow, that was fast. Thanks! A quick glance through the blog post looks good. I'll have to take a closer look and track down the other references when I have more time. –  Mike Spivey Aug 31 '11 at 17:35
    
Now that I look more closely at your blog post I think you are counting something slightly different. In your post you require the sequences to have all positive partial sums. In this problem, though, the sums could be positive or negative, as long as they're not zero until the final flip. Still, the scenario is similar enough that perhaps your argument could be adapted. –  Mike Spivey Aug 31 '11 at 19:36
5  
The result in the blog post is essentially Example 5 in Section 7.5 of Graham, Knuth, & Patashnik, Concrete Mathematics, though they simply count the $m$-Raney sequences rather than the trees. –  Brian M. Scott Sep 1 '11 at 5:35

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.