# Number of binary words that can be formed

How many binary words of length $$n$$ are there with exactly $$m$$ 01 blocks?

I tried by finding number of ways to fill $$n-2m$$ gaps with $$0$$ and $$1$$ such that no $$'01'$$ block gets created again. But this method is not working and I am stuck in this problem. Please provide me an elegant solution of this problem.

• What you really want to count is the number of repeated 0s and 1s. That is quite directly tied to the number of 01 blocks. – Don Thousand May 31 at 17:48
• I couldn't understand what you mean – Divya Prakash Sinha May 31 at 17:51

In each word of length $$n$$, add a $$1$$ in the front and a $$0$$ in the end such that you get a word of length $$n+2$$. Then you get $$n+1$$ space between letters. When you see a transition from $$1$$ to $$0$$ or vice versa, mark it with a "o", else mark it with a "x".
For instance, let $$n = 6$$, then $$110010$$ becomes $$11100100$$ after padding, and the mark becomes xxoxoox.
Now, observe that if a word of length $$n$$ has $$m$$ $$01$$ blocks, you will get exactly $$2m+1$$ "o" marks and $$n-2m$$ "x" marks, and vice versa.
$$\binom{n+1}{2m+1}.$$