Number of binary words that can be formed

Question

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.

Edit: Hw Chu has given a wonderful solution and I really appreciate this solution. But I am now interested in the intuition behind his solution. Further, I request to provide a relatively easier solution to this problem.

Answer 1

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}. $$

Update:

Alright, so I get it as you want some reasoning on the seemingly unnatural construction.

To compute the number of bit strings of length $n$ containing $m$ $01$ cluster, the best hope is to arrange $m$ slots for the $01$ cluster and fill in the remaining $n-2m$ slots with random bits. But then there will be two problems: i) the resulting bit string might have unexpected $01$ clusters; ii) the same bit string may be counted twice.

So we need to be more careful. After reserving the slots for $01$ clusters, you need to fill up the remaining free slots so that no extra $01$ clusters are generated. For a slot containing $l$ consecutive bits, there are $l+1$ ways to avoid extra $01$s: they are some $1$s followed by some $0$s (no $1$ or $0$ are also acceptable, so we do have $l+1$). As the counting is accurate now, one can try to compute the number of combinations from here, but it should be too out of hand.

It is time to improve. The first observation is that, among the $l+1$ legit $l$ bits string as in the previous paragraph, with two exceptions $1\cdots1$ and $0\cdots0$, all combinations contains a $10$ cluster. So with "even more exceptions", the $m+1$ margins separated by the $m$ $01$ blocks will generate $m+1$ $10$ blocks.

What exactly are the "even more exceptions" in the last paragraph? i) two $01$ blocks might be adjacent; ii) the $1\cdots1$ and $0\cdots0$ cases.

For i), you still witness (just one) $10$ block: $0\color{red}{10}1$. Similarly for ii) it is also almost fine: if the exceptions are bounded by two $01$ blocks, you still witness (just one) $10$ block: $011\cdots\color{red}{10}1$ or $0\color{red}{10}\cdots001$.

Now there are only two cases you do not witness a $10$ block: i) a string starts as $0\cdots001$; and ii) a string ends as $011\cdots1$. This is why I padded a $1$ at the front and $0$ at the end to enforce a $10$ block.

Now you get a $n+2$ bits string, and can comfortably say there are $m$ $01$ blocks and $m+1$ $10$ blocks. Then you can mess up the $01$ and $10$ block by calling it a "bit change". This is the hidden reasoning of my solution.

A simpler solution? Well, I feel that if the idea is simpler, then the computations will be harder. Inspired by my update, I think you can try this.

Let $N(n,m)$ be the number of combinations with $n$ bits and $m$ $01$ blocks. So $N(2m,m) = 1$.

For a $(n,m)$ bit string, let $l$ be the number of bits before the first $01$ blocks. Then you get $l+1$ choices for the first $l$ bits and $N(n-l-2,m-1)$ choices for the remaining bits (note that the $l+1$- and $l+2$-th bits must be $0$ and $1$).

Hence $$N(n,m) = \sum_{l=0}^{n-2m} (l+1)N(n-l-2,m-1).$$

If you a priori know the answer, do induction.

Answer 2

Here is another approach. It is "relatively easier" in the sense that setting up recurrence relations that condition on the last few digits of the binary word to force what we're interested in, is a standard way to approach such questions.

Let $a_{n,m}$ be the number of binary words of length $n$ with exactly $m$ 01 blocks that end with a $0$.
Let $b_{n,m}$ be the number of binary words of length $n$ with exactly $m$ 01 blocks that end with a $1$.
We want to find $a_{n,m} + b_{n,m}$.

Observe that the recurrance relations are:
$a_{n+1, m} = a_{n, m} + b_{n,m},$
$b_{n+1, m} = a_{n, m-1} + b_{n,m} $.
This follows directly because the only way to get an additional 01 block is to add a 1 to something in $a_{n, m}$.

Claim: $a_{n,m} = { n \choose 2m+1}, b_{n,m} = { n \choose 2m}$.
(You can guess this by looking at several initial terms.)

Proof: This can be shown by induction on $n$.
First, the base case of $n=1$ only involves $m=0$, and is clearly true.
For the induction step,
$a_{n+1,m} = a_{n,m} + b_{n,m} = { n \choose 2m+1} + { n \choose 2m} = {n+1 \choose 2m+1}$, and
$b_{n+1,m } = a_{n, m-1} + b_{n,m} = {n \choose 2m-1} + { n \choose 2m} = {n+1 \choose 2m}$.

Hence, the number of binary words of length $n$ with exactly $m$ 01 blocks is $a_{n,m} + b_{n,m} = { n+1 \choose 2m+1} $.

---

You could modify this approach to count the number of

• binary words with $m$ 11 blocks (where 111 has 2 such blocks)
• trenary words with $m$ 01 blocks
• binary words with $m$ 010 blocks