# Number of bit strings of length four do not have two consecutive 1s

I came across following problem:

How many bit strings of length four do not have two consecutive 1s?

I solved it as follows:

Total number of bit strings of length: $$2^4$$
Total number of length 4 bit strings with 4 consecutive 1s: 1
Total positions for three consecutive 1s in length 4 bit string: 2 (111X, X111)
Number of bit strings for each of above positions: 2 (X can be 0 or 1)
Total positions for two consecutive 1s in length 4 bit string: 3 (11XX, X11X, XX11)
Number of bit strings for each of above positions: 4
By inclusion exlcusion principle, the desired count $$=2^4-3\times 4+2\times 2-1=16-12+4-1=7$$

However the correct solution turns out to be 8. It seems that I incorrectly applied inclusion exclusion principle. Where did I go wrong?

• You should be doing inclusion-exclusion on the number of pairs of consecutive ones, not on the length of a string of consecutive ones. – Gerry Myerson Sep 16 '19 at 6:27

If I were doing this by inclusion-exclusion, I'd go: $$16$$ strings of length four; $$12$$ with at least one pair of consecutive ones ($$11xx,x11x,xx11$$ with $$x$$s arbitrary); five with at least two pair of consecutive ones ($$111x,1111,x111$$); one with three pair of consecutive ones; so $$16-12+5-1=8$$.

To count the number of bit strings with $$2$$ consecutive one bits (bad strings), I would let \begin{align} S_1&=11xx&4\\ S_2&=x11x&4\\ S_3&=xx11&4\\ N_1&=&12 \end{align} Then \begin{align} S_1\cap S_2&=111x&2\\ S_1\cap S_3&=1111&1\\ S_2\cap S_3&=x111&2\\ N_2&=&5 \end{align} and \begin{aligned} S_1\cap S_2\cap S_3&=1111&1\\ N_3&=&1 \end{aligned} The count of bad strings is $$N_1-N_2+N_3=8$$.
The count of good strings is $$16-8=8$$.

Generating Functions

Let $$x$$ represent the atom '$$0$$' and $$x^2$$ represent the atom '$$10$$' and build all possible strings by concatenating one or more atoms and removing the rightmost '$$0$$'. \begin{align} \overbrace{\vphantom{\frac1x}\ \ \ \left[x^4\right]\ \ \ }^{\substack{\text{strings of}\\\text{length 4}}}\overbrace{\ \quad\frac1x\ \quad}^{\substack{\text{remove the}\\\text{rightmost '0'}}}\sum_{k=1}^\infty\overbrace{\vphantom{\frac1x}\left(x+x^2\right)^k}^\text{k atoms} &=\left[x^4\right]\frac{1+x}{1-x-x^2}\\ &=\left[x^4\right]\left(1+2x+3x^2+5x^3+8x^4+13x^5+\dots\right)\\[9pt] &=8 \end{align} Note that the denominator of $$1-x-x^2$$ induces the recurrence $$a_n=a_{n-1}+a_{n-2}$$ on the coefficients.

Recurrence

Good strings of length $$n$$ can be of two kinds: a good string of length $$n-1$$ followed by '$$0$$' or a good string of length $$n-2$$ followed by '$$01$$'. That is, $$a_n=a_{n-1}+a_{n-2}$$ Starting with
$$a_0=$$ the number of good strings of length $$0=1$$.
$$a_1=$$ the number of good strings of length $$1=2$$.
we get $$a_4=8$$.