1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Don Thousand May 31 at 17:48
  • $\begingroup$ I couldn't understand what you mean $\endgroup$ – Divya Prakash Sinha May 31 at 17:51
2
$\begingroup$

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.

So the number of such words is

$$ \binom{n+1}{2m+1}. $$

$\endgroup$

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.