Inclusion exclusion: How many bit strings of length eight do not contain six consecutive $0$'s?

Question

Q. How many bit strings of length eight do not contain six consecutive $0$s?

I solved this problem with my hand. $$256 - ( 1 + 2 + 2 + 1 + 2 ) = 248$$ I calculated all possible events.

Is my answer right? And can this problem be solved by the inclusion-exclusion principle?

Answer 1

I think your answer is wrong but the idea is good. The number to subtract can indeed be found using the inclusion-exclusion principle, for 3 sets. Can you explain why you subtracted those numbers ?

EDIT: Apologies - I was mistaken. See N. F. Taussig's answer and comment.

Answer 2

It is good that you want to find the strings that do contain $6$ consecutive zeros, and then exclude them.

Consider the following:

[0 0 0 0 0 0] * *
* [0 0 0 0 0 0] *
* * [0 0 0 0 0 0]

Each of the stars can be a zero or one.

• Assume the first case, we have $4$ combinations (where each star is either $0$ or $1$).

• The second case, again can have four possibilities. However, you should exclude those we counted in the first case. They are all-zero pattern, and 0 0 0 0 0 0 0 1. So only $2$ distinct possibilities.

• The third case has only $2$ new possibilities, which are 0 1 0 0 0 0 0 0 and 1 1 0 0 0 0 0 0.

So the answer to your question is $2^8-(4+2+2)=248$

Answer 3

Let $A_1$ be the set of outcomes in which the first six digits of the bit string are equal to $0$; let $A_2$ be the set of outcomes in which the middle six digits of the bit string are equal to $0$; and let $A_3$ be the set of outcomes in which the last six digits of the bit string are equal to $0$. The Inclusion-Exclusion Principle tells us that the number of bit strings in which there are six consecutive zeros is $$|A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$$ The number of elements in $A_1$ is four since there must be a zero in the first six positions there are two choices, $0$ or $1$, for each of the last two digits. By similar argument, $|A_2| = 4$ and $|A_3| = 4$.

The set $A_1 \cap A_2$ consists of those bit strings in which the first six and middle six digits of the bit string are zeros, so the first seven digits of the bit string are zeros. There are two such bit strings, depending on whether the last digit is a $0$ or $1$. By similar argument, $|A_2 \cap A_3| = 2$.

The set $A_1 \cap A_3$ consists of those bit strings in which the first six and last six digits of the bit string are zeros, so each of the eight digits of the bit string is a zero. There is only one such bit string.

The set $A_1 \cap A_2 \cap A_3$ consists of those bit strings in which the first six, middle six, and last six digits of the bit string are zeros, so each of the eight digits of the bit string is a zero. There is only one such bit string.

Hence, the number of bit strings that contain six consecutive zeros is \begin{align} |A_1| + |A_2| & + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|\\ & = 4 + 4 + 4 - 2 - 2 - 1 + 1\\ & = 8 \end{align} as you found. Since there are $2^8 = 256$ bit strings of length $8$, the number of bit strings of length $8$ that do not contain six consecutive zeros is $2^8 - 8 = 256 - 8 = 248$, again as you found.