2
$\begingroup$

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?

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

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

$\endgroup$
4
$\begingroup$

Inclusion-Exclusion to Count Bad Strings

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

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