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}.$$
• 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}.$$ – Smylic Mar 21 '17 at 20:42