Here is the question
Q:- How many bit strings of length 8 contain three consecutive zeros?
I tried to solve this by making the cases that three consecutive zeros start from bit number 1, 2 and so on. I approached to my answer correctly. I obtained 107 as my answer.
But I am confused about, how can I solve this question using inclusion-exclusioin principle? Can anyone help me with this?
On
Let $X\in\{0,1\}. $First we start with the string $000XXXXX \quad (1)$.
Here we have $2^5$ ways. For the next sequence we move the block $000$ on position to the right. To avoid double counting strings starting with $0$ the string starts with 1:
$1000XXXX \quad (2)\Rightarrow 2^4 \quad (2)$.
Moving the block $000$ one position to the right again. The first position can be 0 or 1:
$X1000XXX \quad (3)\Rightarrow 2^4 $.
Similar reasoning for the next 3 strings.
$XX1000XX \quad (4)\Rightarrow 2^4 $
$XXX1000X \quad (5)\Rightarrow 2^4 $
$XXXX1000 \quad (6)\Rightarrow 2^4 $
Now we compare all the strings if there is still double counting. Equal strings are at
$(1), (5): 00010000$
$(1), (5): 00010001$
$(1), (6): 00001000$
$(1), (6): 00011000$
$(2), (6): 10001000$
Therefore we have $2^5+2^4+2^4+2^4+2^4+2^4-5=32+5\cdot 16-5=107$ bit strings of length 8 contain three consecutive zeros. This matches your proposed result.
On
As N. F. Taussig shows, Inclusion-Exclusion is not easy to apply to this problem. One other method that can be used is generating functions. To count the number of strings with no more than two zeros in succession, we will represent the atomic strings $$ \begin{array}{} 1&x\\ 10&x^2\\ 100&x^3 \end{array}\tag1 $$ Since the atomic strings in $(1)$ can only represent strings that start with a one, we need to also represent $0$-$2$ zeros at the start with $$ \begin{array}{} -&1\\ 0&x\\ 00&x^2 \end{array}\tag2 $$ Using $(2)$ once and $(1)$ as many times as needed, we get the generating function $$ \begin{align} \left(1+x+x^2\right)\color{#090}{\sum_{k=0}^\infty\left(x+x^2+x^3\right)^k} &=\frac{1+x+x^2}{\color{#090}{1-x-x^2-x^3}}\\ &=\left(1+x+x^2\right)\color{#090}{\left(1+x+2x^2+\dots\right)}\\[6pt] &=1+2x+4x^2+\dots\tag3 \end{align} $$ where the denominator $1-x-x^2-x^3$ says that the coefficients of the generating function, for $n\ge3$, obey the recurrence $$ a_n=a_{n-1}+a_{n-2}+a_{n-3}\tag4 $$ Note that $(4)$ is the same recursion that N. F. Taussig got in their answer.
Using $(4)$, we can extend $(3)$ as far as we want: $$ \begin{align} \frac{1+x+x^2}{1-x-x^2-x^3} &=1+2x+4x^2+7x^3+13x^4+24x^5+44x^6\\ &+81x^7+\color{#C00}{149}x^8+274x^9+504x^{10}+\dots\tag5 \end{align} $$ $(5)$ says that the number of strings of length $8$ with no more than two zeros in succession is $149$. Since there are $256$ strings of length $8$, we get that there are $256-149=107$ strings of length $8$ with at least $3$ zeros in succession.
As @robjohn stated in the comments, your calculation of $107$ bit strings of length $8$ with at least three consecutive zeros is correct.
Method 1: We use a recurrence relation.
There are $2^8$ bit strings of length $8$. From these, we wish to subtract the number of bit strings that do not contain three consecutive zeros.
We will find a recurrence relation for the number of bit strings with no three consecutive zeros. Let $a_n$ be the number of bit strings of length $n$ that do not contain three consecutive zeros. Since any bit string with length less than $3$ cannot contain three consecutive zeros, \begin{align*} a_0 & = 1\\ a_1 & = 2\\ a_2 & = 4 \end{align*} For a recursion relation, we consider cases depending on the position of the last zero. Any admissible bit string of length $n$ that ends in a $1$ can be formed by appending a $1$ to an admissible bit string of length $n - 1$, of which there are $a_{n - 1}$. Any admissible bit string of length $n$ that ends in $10$ can be formed by appending a $10$ to an admissible bit string of length $n - 2$, of which there are $a_{n - 2}$. Any admissible bit string of length $n$ that ends in $100$ can be formed by appending a $100$ to an admissible bit string of length $n - 3$, of which there are $a_{n - 3}$. Hence, we have the recurrence relation $$a_n = a_{n - 1} + a_{n - 2} + a_{n - 3}, n \geq 3$$ which gives us the recursive formula \begin{align*} a_0 & = 1\\ a_1 & = 2\\ a_2 & = 4\\ a_n & = a_{n - 1} + a_{n - 2} + a_{n - 3}, n \geq 3 \end{align*} for the number of bit strings of length $n$ that do not have three consecutive zeros. As you can verify, $a_3 = 7$, $a_4 = 13$, $a_5 = 24$, $a_6 = 44$, $a_7 = 81$, and $a_8 = 149$. Hence, the number of bit strings of length $8$ that do have three consecutive zeros is $2^8 - 149 = 256 - 149 = 107$, as you found.
Method 2: We outline how to use the Inclusion-Exclusion Principle, which takes more work.
Define $A_k$, where $1 \leq k \leq 6$, to be the set of bit strings of length $8$ that have three consecutive zeros starting in the $k$th position. What we need to count is $|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6|$. By the Inclusion-Exclusion Principle, \begin{align*} & |A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6|\\ & = |A_1| + |A_2| + |A_3| + |A_4| + |A_5| + |A_6|\\ & \quad - \left(|A_1 \cap A_2| + |A_1 \cap A_3| + \cdots + |A_5 \cap A_6|\right)\\ & \quad + \left(|A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + \cdots + |A_4 \cap A_5 \cap A_6|\right)\\ & \quad - \left(|A_1 \cap A_2 \cap A_3 \cap A_4| + |A_1 \cap A_2 \cap A_3 \cap A_5| + \cdots + |A_3 \cap A_4 \cap A_5 \cap A_6|\right)\\ & \quad + \left(|A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_4| + |A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_6| + \cdots + |A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6\right)\\ & \quad - |A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6| \end{align*}
To get you started:
$|A_1|$: The first three positions are filled with zeros. There are two choices for each of the remaining five positions, so $|A_1| = 2^5$. By symmetry, $$|A_1| = |A_2| = |A_3| = |A_4| = |A_5| = |A_6| = 2^5$$
$|A_1 \cap A_2|$: Since the sets $A_1$ and $A_2$ share two positions in which there must be a zero, four positions must be filled with zeros. There are two choices for each of the remaining four positions, so $|A_1 \cap A_2| = 2^4$. By symmetry, $$|A_1 \cap A_2| = |A_2 \cap A_3| = |A_3 \cap A_4| = |A_4 \cap A_5| = |A_5 \cap A_6| = 2^4$$
$|A_1 \cap A_3|$: Since the sets $A_1$ and $A_3$ share one position in which there must be a zero, five positions must be filled with zeros. There are two choices for each of the remaining three positions, so $|A_1 \cap A_3| = 2^3$. By symmetry, $$|A_1 \cap A_3| = |A_2 \cap A_4| = |A_3 \cap A_5| = |A_4 \cap A_6| = 2^3$$
$|A_1 \cap A_4|$: Since the sets $A_1$ and $A_4$ do not share a position in which there must be a zero, six positions must be filled with zeros. There are two choices for each of the remaining two positions, so $|A_1 \cap A_4| = 2^2$. By symmetry, $$|A_1 \cap A_4| = |A_1 \cap A_5| = |A_1 \cap A_6| = |A_2 \cap A_5| = |A_2 \cap A_6| = |A_3 \cap A_6| = 2^2$$
Since there are $\binom{6}{2} = 15$ intersections of two sets, we have accounted for all intersections of two sets.
By continuing in this way and verifying that you have accounted for all $\binom{6}{3} = 20$ intersections of three sets, $\binom{6}{4} = 15$ intersections of four sets, $\binom{6}{5} = 6$ intersections of five sets, and the only intersection of six sets, you can verify that there are indeed $107$ bit strings of length $8$ that contain three consecutive zeros using the Inclusion-Exclusion Principle.