What is the total number $N(k,m,j)$ of binary strings of length $k$ that have $m$ zeros and $j$ transitions from zero to one (or from one to zero)? We can assume that $k> 2m-1$

For example, $N(k,m,1)=2$ because there are only two such strings: the one that starts with m zeros followed by $k-m$ ones and the one that starts with $k-m$ ones followed by $m$ zeros.

Another example, $N(k,m,2)=k-2$ because there are $m-1$ strings that start with x zeros followed by k-m ones followed by $m-x$ zeros ($x$ is a number between $1$ and $m-1$) and $k-m-1$ strings that start with $y$ ones followed by $m$ zeros followed by $k-m-y$ ones ($y$ is a number between $1$ and $k-m-1$).

Another example, $N(k,m,2m)=\frac{(k-m-1)!}{m!(k-2m-1)!}$ this is the number of combinations of $m$ non-adjacent numbers drawn from $k-2$ numbers (zeros cannot be located in the first or the last position of the string in order to generate exactly $2m$ transitions).

But what about the general case $N(k,m,j)$?


Notice first that it depends on the parity of $j.$ If $j\equiv 0 \pmod 2$ then if you start with $0$ you have to end with $0$ and the same for $1.$ Otherwise it ends with the opposite symbol from which you started with.

I am gonna do it for $j\equiv 1 \pmod 2$
Notice that if you want to start with $0$ you want to have the following configuration $$0^{a_1}1^{a_2}\cdots 0^{a_j}1^{a_{j+1}},$$ those $a_i>0$ for all $i$ and so we have $j$ transitions. In how many blocks are we placing the $0's$? well in $\frac{j+1}{2}$ and hence, by stars and bars, there are $$\binom{m-1}{\frac{j+1}{2}-1}$$ ways to place the $m$ $0s$. What about the $1s$? Well also there are $\frac{j+1}{2}$ blocks and hence $$\binom{k-m-1}{\frac{j+1}{2}-1},$$ then by the product rule there are $$\binom{m-1}{\frac{j+1}{2}-1}\binom{k-m-1}{\frac{j+1}{2}-1},$$ ways when $0$ is place first, doing the same for $1$ we get $$N(k,m,j)=2\binom{m-1}{\frac{j+1}{2}-1}\binom{k-m-1}{\frac{j+1}{2}-1}$$

Doing the same analysis when $j\equiv 0 \pmod 2,$ we get $$N(k,m,j)=\binom{m-1}{j/2}\binom{k-m-1}{j/2-1}+\binom{m-1}{j/2-1}\binom{k-m-1}{j/2}.$$

Which agrees with your computation.

  • $\begingroup$ You can accumulate both cases as: $$N(k, m, j) = \binom{m - 1}{\lfloor j / 2 \rfloor} \binom{k - m - 1}{ \lfloor (j - 1) / 2 \rfloor} + \binom{m - 1}{\lfloor (j - 1) / 2 \rfloor}\binom{k - m - 1}{\lfloor j / 2\rfloor}.$$ $\endgroup$ – Smylic Mar 21 '17 at 20:42
  • $\begingroup$ @Smylic Yes, thanks for noticing! $\endgroup$ – Phicar Mar 21 '17 at 22:31
  • $\begingroup$ nice piece of work. $\endgroup$ – abel Mar 24 '17 at 11:43

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.