Number of elements of $3n$ binary tuples, where the ordinates add up to $2n$.

Question

I have the following problem.

Take $\Omega_n=\{(a_1, a_2 , \cdots , a_{3n})| a_i= 0\rm{\,or}\, 1\}$. Define $A_n=\{\omega \in \Omega_n|\exists k, \sum _{i=1}^{3k} a_i = 2k\}$ and $ S_m=\{(a_1, a_2 , \cdots , a_{3m}) \in A_m|\inf \{ k,| \sum _{i=1}^{3k} a_i = 2k\}=m\} $ we are interested in finding $|S_m|$ the cardinality of $S_m$

There is a straightforward recursive formula$S_n={3n \choose 2n}-\left (S_1 {3(n-1) \choose 2(n-1)}+S_2{3(n-2) \choose 2(n-2)}+ \cdots S_{n-1} {3\cdot(1) \choose 2\cdot(1)} \right )= {3n\choose 2n}-\left (\sum _{i=1}^{n-1}S_i {3(n-i)\choose 2(n-i)} \right )$ I was not sure how to compute that so I used OEIS to see if it has some nice formula. After finding by hand the first values $ 3,6,21,90,429 $ it suggested me the formula $ \frac{2}{3n-1}{3n\choose 2n}$. I managed to prove it by induction.

I would be interested in some combinatorial proof of that, a bijection would be highly appreciated.

Answer 1

Code heads as 1 and tails as 0, and the problem can be phrased in the following way: Flip a fair coin until you have exactly twice as many heads as tails, and then stop. The value of $|S_n|$ is the number of such sequences of coin flips that have length exactly $3n$.

For this rephrased version, I asked the same question as the OP a couple of years ago on this site, under "Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem." It took me a few weeks before I found an answer to my own question, so I wouldn't call this an easy combinatorial proof to come up with. (In fact, I generalized my argument, recast it in terms of counting certain lattice paths, and got the argument published in the Electronic Journal of Combinatorics as "Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points.")

---

Anyway, I'll reproduce my original combinatorial argument here. It uses the equivalent $|S_n| = \frac{3}{3n-1} \binom{3n-1}{n}$ as the formula to be proved. It also uses the following result (see, for example, Section 7.5 of Concrete Mathematics):

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.

On to the proof.

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 are $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 + \cdots + 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 + \cdots + a_1 = 1$, and $a_k + a_{k-1} + \cdots + 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}$.