Bijection between the set of coin tosses with an equal number of $H$'s and $T$'s and the set where $H$'s and $T$'s are never equal

Question

Let $D_n$ be the set of $2n$ coin tosses where the number of $H$'s and $T$'s are never equal as you read from left to right. For example, $$D_2 = \lbrace TTTT, TTTH, TTHT, HHTH, HHHT, HHHH \rbrace.$$ And let $E_n$ be the set of $2n$ coin tosses with $n$ $H$'s and $n$ $T$'s. So $$E_2 = \lbrace TTHH, THTH, THHT, HTTH, HTHT, HHTT \rbrace.$$ I have a proof below that $|D_n| = |E_n|$ for any $n$, but I'm interested in a proof by bijection - can you create a bijection between $D_n$ and $E_n$?

I've tried a few variants of the second proof of the Catalan number formula on Wikipedia, taking an element of $D_n$ as a path that starts from $(0, 0)$ and goes right on $H$ and up on $T$, and flipping parts of the path when the path meets the main diagonal (where the number of $H$'s equals the number of $T$'s). Part of the problem is that the path for an element of $E_n$ can cross the main diagonal repeatedly. I've also tried just switching $H \leftrightarrow T$ from the start of a sequence. E.g. take an element of $E_n$, switch the first coin ($H \leftrightarrow T$) and see if this new sequence in $D_n$. If not, keep any switched coins and continue switching until you get an element of $D_n$. This defines a bijection for $n=1,2$ but doesn't work for any larger $n$ (for $n=3$, $HTHHTT$ isn't mapped to anything).

---

Proof that $|D_n| = |E_n| = \binom{2n}{n}$

Clearly $|E_n| = \binom{2n}{n}$. There are $2n$ places to put the $T$'s and you choose $n$ of them.

Let $c_n$ be the number of elements of $D_n$ that begin with a $T$. Considering the numbers of $H$'s that can be in this sequence, we have $$c_n = \sum_{h = 0}^{n-1} b_{n,h},$$ where $b_{n,h}$ is the number of elements of $D_n$ that begin with a $T$ and contain $h$ $H$'s. Using a similar argument to the second proof of the Catalan number formula on Wikipedia, you can show that $$b_{n,h} = \binom{2n - 1}{h} - \binom{2n - 1}{h - 1} = \binom{2n}{h} \frac{2n - h}{2n}.$$ Since the number of elements of $D_n$ that begin with an $H$ equal the number that begin with a $T$, the number of elements of $D_n$ is $2c_n$. \begin{align*} 2c_n &= 2\sum_{h=0}^{n-1} \binom{2n}{h} \frac{2n-h}{2n} \\ &= 2\sum_{h=0}^{n-1} \binom{2n}{h} - 4 \sum_{h=1}^{n-1} \binom{2n-1}{h-1} \\ &= \left[2^{2n} - \binom{2n}{n} \right] - 2\left[2^{2n-1} - \binom{2n-1}{n-1} - \binom{2n-1}{n}\right] \\ &= 2\binom{2n-1}{n-1} + 2\binom{2n-1}{n} - \binom{2n}{n} \\ &= \binom{2n}{n}. \end{align*}

Answer 1

A bijection is given in the following paper. I do not know how to access the conference proceedings below, but you can find the paper online (for now), for example at this link: https://people.bath.ac.uk/masadk/papers/catalan.pdf.

Ömer Eğecioğlu and Alastair King. Random walks and Catalan factorization. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 138, pages 129–140, 1999. MR-1744217

I will use their vocabulary, so let me explain:

• $D_n$ is the set of nonzero walks of length $2n$.
• $E_n$ is the set of balanced walks of length $2n$.

Furthermore, we need an auxilliary definition:

• Let $F_n$ be the set of sequences of $n$ zeroes and $n$ ones such that, as you read from left to right, the number of zeroes you have seen is always greater than or equal to as the number of ones you have seen. The authors refer to these as nonnegative walks. For example, $$ F_2=\{0000,0001,0010,0011,0100,0101\} $$

The authors prove that $|D_n|=|E_n|=|F_n|$. Proposition 2 in the cited paper gives a bijection from $E_n$ to $F_n$. They then modify that to get a bijection between $E_n$ and $D_n$.

These bijections use something called the authors call the "Catalan factorization," which is defined as follows. The input to this method is a finite sequence of zeroes and ones.

Catalan Factorization

Input: A $\{0,1\}$-sequence of length $n$.
Output: An ordered pair $(w,k)$, where $w$ is a $\{0,1,z\}$-sequence of length $n$, and $k$ is a nonnegative integer.

1. First, underline any two entries in the input which are a $0$ followed by a $1$ with only underlined entries between. Repeat this step until no such entries remain.

2. Now, the entries which are not underlined will consist of some number of $1$'s, followed by some number of $0$'s. If not, we would not be done with step $1$.

3. Finally, any entry which is not underlined is replaced with a new symbol, $z$. Call the resulting word $w$. Furthermore, the number of $1$'s which were converted to $z$'s is recorded as a number, $k$. This final result, is $(w,k)$.

The Catalan factorization is injective, and therefore reversible. Given a Catalan factorization $(w,k)$, the corresponding binary string is found by replacing the leftmost $k$ copies of $z$ with $1$, and the remaining copies of $z$ with $0$.

Here are the Catalan factorizations of all of the strings in $E_2$:

Input:	Output:
$0011$	$(0011,0)$
$0101$	$(0101,0)$
$0110$	$(01zz, 1)$
$1001$	$(zz01,1)$
$1010$	$(z01z, 1)$
$1100$	$(zzzz,2)$

Notice the following: because all of the strings in $E_n$ are balanced between zeroes and ones, and because the underlined entries are balanced, then the entries converted to $z$'s must be balanced as well. Therefore, if the Catalan factorization of string in $E_n$ is $(w,k)$, then $w$ must have exactly $2k$ copies of $z$.

Now, let us find the factorizations of all words in $F_2$:

Input	Output
$0000$	$(zzzz,0)$
$0001$	$(zz01,0)$
$0010$	$(z01z, 0)$
$0011$	$(0011,0)$
$0100$	$(01zz, 0)$
$0101$	$(0101,0)$

This time, we notice two things. First of all, the second index is always zero (any $z$;'s replaced with $1$'s would imply the existence of a prefix with more ones than zeroes. Secondly, the $w$ parts of $F_2$'s output row correspond bijectively between the $w$ parts of $E_2$'s output row; the only difference is the value of $k$, but this is uniquely forced in both cases. We have discovered this bijection:

Bijection between $E_n$ and $F_n$: Given a balanced walk, find its Catalan factorization, $(w,k)$ (where $k$ is the one half of the number of $z$'s in $w$). Then, apply the reverse Catalan factorization to $(w,0)$ to get a walk, which will be a nonnegative walk.

Equivalently, take the Catalan factorization, the replace all $z$'s with zeroes.

Next, we need to modify this to get a bijection between $E_n$ and $D_n$. Here are the last definitions we need.

• Let $E_n^0$ be the set of balanced walks whose first entry is $0$, and let $E_n^1$ be the set of walks whose first entry is $1$. This partitions $E_n$ into two equal sets.
• Let $D_n^+$ be the set of walks in $D_n$ where (# zeroes) - (# ones) is always positive, and $D_n^-$ is the set of walks where (# zeroes) - (# ones) is always negative. Again, this partitions $D_n$ into two equal sets.

To give a bijection $E_n\to D_n$, it suffices to give two bijections, one from $E_n^1\to D_n^+$, and another from $E_n^0$ to $D_n^-$.

Bijection from $E_n^1$ to $D_n^+$: If you restrict the domain of the previous bijection to $E_n^1$, then the restricted range is exactly equal to $D_n^+$.

Why does the bijection applied to a walk in $E_n^1$ yield one in $D_n^+$? Given a walk in $E_n^1$, let its Catalan factorization be $(w,k)$. Necessarily, $w$ begins with a $z$. The result of the bijection replaces all $z$'s with zeroes, so the output path starts with a zero. Furthermore, in $w$, every maximal contiguous sequence of $0$'s and $1$'s will be nonnegative (because these were underlined entries). Therefore, as you read left to right in the output path, the quantity (# zeroes) - (# ones) will start at $+1$, and then it will never go any lower, as desired.

Finally:

Bijection from $E_n^0$ to $D_n^-$: Given a walk in $E_n^0$, complement all entries to get a walk in $E_n^1$. Apply the previous bijection to get a walk in $D_n^+$, and finally, complement all entries again to get a walk in $D_n^-$.

At last, we have described the bijection between $E_n$ and $D_n$!

Answer 2

I've accepted Mike Earnest's answer, but for completeness I thought I would give the other bijection that I saw in the paper. Let a $T$ be an up-step, and an $H$ be a down-step. A balanced walk is an element of $E_n$ and a non-zero walk is an element of $D_n$.

Take the "initial" segment of a balanced walk to be up to the first time it reaches either its minimum value, for walks that start with a down-step, or its maximum value, for walks that start with an up-step. Take the "initial" segment of a non-zero walk to be up to the last time it reaches half its final value either with an up-step, for positive walks, or with a down-step, for negative walks. The bijection and its inverse reverse the signs and order of the steps in the initial segments.

I'll show that this gives a bijection $f:E_n \rightarrow D_n$ and its inverse $g:D_n \rightarrow E_n$.

First of all, let's see that $f(e) \in D_n$ for any $e \in E_n$. WLOG assume that the first step is an up-step. Set $e = e_1 e_2$, where $e_1$ is the initial segment of $e$. If the maximum of $e$ is $m$ (note that $m \geq 1$) then $e_1$ involves going up $m$ overall, and $e_2$ involves going down $m$. So if we reverse the signs and order of the steps in $e_1$ to get $e_1^\prime$, then $e_1^\prime e_2$ goes down $2m$ overall. Reversing the signs and order means that $e_1^\prime$ never returns to $0$ because that would correspond to the maximum being reached twice in $e_1$, but we stop the initial segment the first time that we reach the maximum. And we don't return to $0$ with $e_2$ either: at the end of $e_1^\prime$ the sequence has gone down $m$ steps overall, so when we do the steps of $e_2$, if we got any higher than $-m$, it would mean that at some point in $e_2$ we have gone up overall, but that would mean that the highest point in $e$ is greater than $m$. So $e_1^\prime e_2 \in D_n$.

Now I'll show that $gf(e) = e$ for any $e \in E_n$. Again WLOG assume that $e$ starts with an up-step. Let the maximum of $e$ be $m$. Then $e_1^\prime e_2$ goes to $-2m$ overall. Let $d = f(e)$ and break $d$ down into its initial segment and remainder as $d = d_1 d_2$. Is $d_1^\prime = e_1$? Yes, because 1) $d$ goes to $-2m$ overall and at the end of $d_1$ we have gone down $-m$, and 2) this is the last time that $d$ has gone down to the level $-m$ because we know that $e_2$ begins with a down-step and never returns to $0$. You can also show that $gf(d) = d$ for any $d \in D_n$.

This gives us that $f$ is injective because $f(x) = f(y) \implies gf(x) = gf(y) \implies x = y.$

And $f$ is onto. Let $d = d_1 d_2$ and WLOG let $d$ begin with a down-step. Then $d_1$ and $d_2$ both descend the same amount $m$ overall. So $d_1^\prime$ ascends to $m$ overall, and then $d_2$ takes the sequence back to $0$ overall, so $d_1^\prime d_2 \in E_n$.