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.
 A: 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.
A: 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.
