Is there a combinatorially way to count the number of binary strings with consecutive $0$s?

Question

How many strings are there that contain two consecutive $0$s?

The typical way to approach this problem is using the Fibonacci sequence. But I'm wondering whether there's a way to do it purely combinatorially.

The difficulty seems to be in accounting for the other digits in the string. Here's what I mean:

I'd like to count the number of strings of length $i$ that have consecutive zeroes, for each $0\leq i \leq n$. But it gets complicated.

Consider strings of length $4$, for example. We have to count all strings with either $2, 3,$ or $4$ consecutive zeroes.

With strings of length $5$, we have to count all strings with either $2,3,4,$ or $5$ consecutive zeroes, except some (but not all) of those strings would have also been counted in the case of $4$ lengths strings. And I'm not sure how to avoid overcounting.

So is it simply impossible to do this only through combinatorics? Do we have to use the approach involving the Fibonacci sequence? If not, could you point out a solution that doesn't?

Answer 1

The Fibonacci approach really is the neatest, but it is possible to reason combinatorially.

We're trying to find the number of strings of length $n$ with at least two consecutive zeros somewhere, which I will denote $\sigma(n)$. Evidently, $\sigma(n) = 2^n - \textrm{the number of strings of length } n \textrm{ with no consecutive zeros}$.

For a particular length $n$ and number of zeros, $k$, we can build that string as follows:

$$ S = 1^{a_1}011^{a_2}0...11^{a_k}01^{a_{k+1}}, $$

with the requirements that $a_1 + a_2 + \ldots + a_k + a_{k+1} = n - 2k + 1$, and $a_1, a_2,\ldots, a_k, a_{k+1} \geq 0$. That's a number we can find using the stars and bars approach - we have to place $k$ dividers between $n - 2k + 1$ objects, giving the binomial coefficient $\binom{n - k + 1}{k}$.

To find the total number of strings not containing consecutive zeros for a given $n$, we then need to sum over all values of $k$, from 0 to the maximal number of zeroes. That turns out to be $\lceil n/2 \rceil$, since we need to place at least one "1" between every "0".

Putting everything together we find that

$$ \sigma(n) = 2^n - \sum_{k=0}^{\lceil n / 2\rceil} \binom{n - k + 1}{k} $$

Plugging in some values, we find that $\sigma(1) = 0, \sigma(2) = 1, \sigma(3) = 3$, which all fit what you calculate by hand.

Answer 2

Using lulu's suggestion, you can count bit-strings with no consecutive 0's as follows. Any bit string with no consecutive 0's of length $n-1$, you can add a 1. Any bit string with no consecutive 0's of length $n-2$, you can add a 10. This gives all possible bit strings of length $n$ (you may need to think about it to prove how).

Thus, if $a_n$ were the number of bit strings of length $n$ with no consecutive 0's, then

$$a_n = a_{n-1}+a_{n-2}$$

and you have $a_0=1, a_1=2, a_2=3$. The recurrence relation is the Fibonacci relationship, but shifted, although this can be solved through differential equations, as well, which is often used to solve combinatorial recurrence relations.

So, $a_n = \dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+2}}{\sqrt{5}}$.

Then, to find the number of bit-strings with consecutive 0's, you would take the total number of bit-strings and subtract the total number with no consecutive 0's, you have:

$$b_n = 2^n-a_n = 2^n-\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+2}}{\sqrt{5}}$$