Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem
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.
Solution 1:
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.
Solution 2:
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.