Bit String Bijection

Question

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n).

The restriction on the first type of bit string is that they must have the same number of 0's and 1's.

The restriction on the second type is that they can not have any prefix with the same number of 0's and 1's.

Note that I need the actual bijection, it is not enough to simply show that they are in bijection with one another. So I need both a transformation and it's inverse.

This is a sub-problem of a larger problem that I have been working on for some time now and it is the last piece that I have been unable to work out. Thanks in advance for any help.

If any additional clarification or if examples would be helpful, just let me know and I'd be happy to provide it

Answer 1

The Bijection: Let $A$ be the set of bit strings of length $2n$ with the same number of $0$'s and $1$'s, and let $B$ be the set of bit strings of length $2n$ with no prefix with the same number of $0$'s and $1$'s. We construct $f:A\to B$ and $g:B\to A$ as follows.

Given a string $s\in B$, let $a_k$ be the number of $1$'s in the prefix of $s$ of length k, $b_k$ the number of $0$'s, and $c_k = a_k - b_k$. For each $i$, let $m_i$ be the largest $k$ such that $|c_k| = i$. Let $s'$ be the string obtained from $s$ by flipping all bits after $m_1$, then flipping all bits after $m_2$, etc. Put $g(s) = s'$.

Now, given a string $w'\in A$, define $a_k'$, $b_k'$, and $c_k'$ as before. Assume for the moment that the first bit of $s'$ is $1$. Define $m_1'$ to be the first $k$ such that $c_k' = 1$ and $c_{k+1}' = 0$. Let $m_2'$ to be the first $k$ after $m_1'$ such that $c_k' = 0$ and $c_{k+1}' = 1$. Continue in this fashion to define $m_{2r-1}$ and $m_{2r}$. Let $w$ be the string obtained from $w'$ by flipping all bits after $m_1'$, then flipping all bits after $m_2'$, etc. Put $f(w') = w$. (If the first bit of $w'$ is 0, replace $c_k' = 1$ and $c_{k+1}' = 1$ with $c_k' = -1$ and $c_{k+1}' = -1$.)

An Application: One can use this to give a bijective proof of the identity $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=4^n.$$ For more references to combinatorial proofs of this check out Stanley's Enumerative Combinatorics vol.1 exercise I.3(c).

Edit: Thanks to Steve Kass for pointing out a couple of issues with my answer. I will try to give a sense here for where the maps come from, and hopefully the answer will be a little more clear.

Instead of strings of $0$'s and $1$'s, consider a string $s$ of length $2n$ composed of the letters $L$ and $R$. Then we are going to interpret $s$ as a walk on the one-dimensional lattice starting from the origin. So for example, the string $RRLR$ would start at $x=0$ and end at $x=2$. The set $B$ is then the set of "origin-avoiding paths" of length $2n$. We can decompose such a path into a sequence of paths $s_i$ of the form $s_i = t_i + u_i$, where $t_i\in \{L,R\}$ and $u_i$ is a path with an equal number of $L$'s and $R$'s such that any prefix of $u_i$ has at least as many $R$'s as $L$'s. So, for example, $RRRLRLLRRLRRRL = (R + RRLRLL) + (R + RL) + (R) + (R + RL)$.

The idea behind the map from $B$ to $A$ is to make the path which begins with the first path in the decomposition, then concatenate the second path in reverse, then the third path as it originally was, then the fourth path in reverse, etc.

So, for this example, $g(RRRLRLLRRLRRRL)$$ = (R + RRLRLL) + (L + LR) + (R) + (L + LR) = RRRLRLLLLRRLLR$.

To go back (from $A$ to $B$), we decompose our path based on the times when "steps between x=0 and x=1", and we do the same sort of reversing on the even indexed parts. So for our example, we would have the decomposition $RRRLRLLLLRRLLR = (RRRLRLL) + (LLR) + (R) + (LLR)$, and $f(RRRLRLLLLRRLLR) $$= (RRRLRLL) + (RRL) + (R) + (RRL) = RRRLRLLRRLRRRL$.

I apologize if my original description was a little careless, but hopefully this helps make sense of what the maps are doing.

Answer 2

Added: Trying again with $A$ and $B$ switched, but still having trouble:

The Bijection: Let $A$ be the set of bit strings of length $2n$ with the same number of $0$'s and $1$'s, and let $B$ be the set of bit strings of length $2n$ with no prefix with the same number of $0$'s and $1$'s. We construct $f:A\to B$ and $g:B\to A$ as follows. Given a string $s\in B$

Let $n=3$ and $s=111001$. The string $s$ has length $2n$ and no prefix has the same number of $0$’s and $1$’s, so $s\in B$.

Let $a_k$ be the number of $1$'s in the prefix of $s$ of length $k$, $b_k$ the number of $0$'s, and $c_k=a_k−b_k$.

Then

$c_1=1-0=1$, $c_2=2-0=2$, $c_3=3-0=3$,

$c_4=3-1=2$, $c_5=3-2=1$, $c_6=4-2=2$.

For each $i$, let $m_i$ be the largest $k$ such that $|c_k|=i$.

Then $m_1=5$, $m_2=6$, and $m_3=3$.

Let $s'$ be the string obtained from $s$ by flipping all bits after $m_1$, then flipping all bits after $m_2$, etc. Put $g(s)=s'$.

Starting with $s=111001$, flip all bits after $m_1=5$ to get $111000$. Now flip all bits after $m_2=6$, which flips no bits, leaving $111000$. Now flip all bits after $m_3=3$, to yield $111111$, so $g(s)=s'=111111$.

But $s'\notin A$, because it doesn’t have three of each digit.

---

(First version of this, after which Wade modified his answer.)

@WadeHann-Caruthers I’m confused about your answer. Can you tell me where I’m going wrong in trying to understand it?

The Bijection: Let $A$ be the set of bit strings of length $2n$ with the same number of $0$'s and $1$'s, and let $B$ be the set of bit strings of length $2n$ with no prefix with the same number of $0$'s and $1$'s. We construct $f:A\to B$ and $g:B\to A$ as follows. Given a string $s\in A$

Let $n=3$ and $s=101010$. The string $s$ has length $2n$ and the same number of $0$’s and $1$’s

Let $a_k$ be the number of $1$'s in the prefix of $s$ of length $k$, $b_k$ the number of $0$'s, and $c_k=a_k−b_k$.

Then

$c_1=1-0=1$, $c_2=1-1=0$, $c_3=2-1=1$,

$c_4=2-2=0$, $c_5=3-2=1$, $c_6=3-3=0$.

For each $i$, let $m_i$ be the largest $k$ such that $|c_k|=i$.

Then $m_1=5$, and no other $m_i$ are defined ($m_0$ is not needed later).

Let $s'$ be the string obtained from $s$ by flipping all bits after $m_1$, then flipping all bits after $m_2$, etc. Put $f(s)=s'$.

There is no $m_2$ or later, so flip the bits “after $5$.” If this means after position $5$, then $s'=101011$.

But $s'\notin B$, as it has the prefix $10$, with one zero and one one.