5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}\ .$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Marc van Leeuwen Aug 28 '13 at 12:57
  • $\begingroup$ 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}$. $\endgroup$ – bbn Aug 28 '13 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.