# Counting bit flips

For $n, m \geq 1$, let $\Lambda^{n,m}$ be the set of all $(n+m)$-bit strings with exactly $n$ zeros and $m$ ones.

For instance, $\Lambda^{2,3} = \{00111, 11100, 10011, 11001, 01110, 01011, 01101, 11010, 10110, 10101 \}$.

Let $b=b_1\ldots b_{n+m} \in \Lambda^{n,m}, b_i \in \{0, 1\} \forall i$. Define $T(b)$ as the number of bit flips ocurring in the string $b$. (what i mean mathematically by "the number of bit-flips" is $T(b) = \sum_{i=1}^{n+m-1} b_i\oplus b_{i+1}$ ). Now, for $k\geq 0$, let ${\mathcal{T}^{n,m}_k}$ be the set of all $b\in \Lambda^{n,m}$ such that $T(b)=k$.

My question: is there a closed formula for the number of elements in ${\mathcal{T}^{n,m}_k}$?

For example: taking again $\Lambda^{2,3}$ from above, i have incidentally ordered it such that the first two elements, $00111$ and $11100$, have exactly one bit-flip, thus #${\mathcal{T}^{2,3}_1} = 2$. In a similar way the third to fifth elements have exactly two bit-flips, thus #${\mathcal{T}^{2,3}_2} = 3$. By the same coin, #${\mathcal{T}^{2,3}_3} = 4$ and lastly #${\mathcal{T}^{2,3}_4} = 1$.

Note 1: i have been able to work out the simplest cases ($k=2, 3$) but get intimidated with higher $k$.

Note 2: this problem is my attempt to restate Problem 2-6 of R. Feynman's book on path integrals "The path integral approach to QM". In that context what we are counting is the number of paths possible with a given number of corners in a discrete ((1+1)-dimensional) space-time lattice.

One has to distinguish the cases $k=2j-1$ and $k=2j$, where $j\geq1$. In the following I shall treat the case $k=2j-1$ and leave the case $k=2j$ to you.
When there are $2j-1$ flips we have $j$ nonempty packets of consecutive zeros alternating with $j$ nonempty packets of consecutive ones.
In order to make the $j$ nonempty packets of zeros we have to put separating bars $|$ into $j-1$ of the $n-1$ spaces in a string of $n$ zeros. This can be done in ${n-1\choose j-1}$ ways. Similarly and independently, we can make $j$ nonempty packets of ones in ${m-1\choose j-1}$ ways.
We still can decide whether we begin our final string with $0$ or with $1$.
It follows that $$\left|{\cal T}_{2j-1}^{n,m}\right|=2{n-1\choose j-1}{m-1\choose j-1}\ .$$
• Very nice. If you like to see the binomial coefficients directly and symmetrically, prepare two stacks, one with the $n$ zeros and another with the $m$ ones, and insert twice $j-1$ instructions "switch (back) to the other stack" (or "return from coroutine" for those who know about that) in some of the $n-1$ respectively $m-1$ spaces in each of the stacks. (And of course choose to start with either GOTO 0 or GOTO 1.) – Marc van Leeuwen Aug 28 '13 at 12:57
• Thanks for your clear answer. But most importantly, i was able to work the other case! Let $k=2j$. There are two disjoint cases: (i) starting with zero, which involves $j$ nonempty packets of consecutive ones alternating with $j+1$ nonempty packets of consecutive zeros, all of which can be done in $\binom{m-1}{j-1}\binom{n-1}{j}$ as you showed (warning! this time there's no prefactor of 2 since we chose how to begin the string) and (ii) analogous but starting with ones. I am left with $\left| {\mathcal{T}}^{n,m}_{2j} \right| = \binom{m-1}{j-1}\binom{n-1}{j} + \binom{m-1}{j}\binom{n-1}{j-1}$. – bbn Aug 28 '13 at 13:47