Combinations with adjacent numbers 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)$?
 A: 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.
