Question

How many bit strings of length six do not contain four consecutives\(1's\)?

Short answer

The number of bit string of length six do not contains four consecutives \(1's\) is \(56\).

Step-by-step solution

In the problem given

Bit strings of length six.

The definition and the formula for the given problem

Numbersthat follow each other continuously in the order from smallest to largest are called consecutive numbers.

Determining the sum in expanded form

Let us find first how many bit strings of length six do contains four consecutives\(1's\).

There will be three different positions where four consecutive \(1's\) can start in a bit string of length \(6\), with \({1^{{\rm{st }}}}\), \({2^{{\rm{nd }}}}\) and \({3^{{\rm{rd }}}}\) positions. Let \(\left| {{A_i}} \right|\) denote the number of choices to insert either \(0\) or \(1\) in \({i^{th}}\) position.

That is

\(\begin{array}{c}\left| {{A_i}} \right| = {2^2}\\ = 4\end{array}\)

for each \(i = 1,2,3\) and also

\(\begin{array}{c}\left| {{A_1} \cap {A_2}} \right| = \left| {{A_2} \cap {A_3}} \right|\\ = 2\end{array}\)

whereas

\(\begin{array}{c}\left| {{A_1} \cap {A_3}} \right| = 1,\\\left| {{A_1} \cap {A_2} \cap {A_3}} \right| = 1\end{array}\).

Thus, the total number bit, which contains four consecutives\(1's\) is

\(\begin{array}{c}\left| {{A_1} \cup {A_2} \cup {A_3}} \right| = 3 \cdot 4 - 2 - 2 - 1 + 1\\ = 12 - 4\\ = 8\end{array}\)

and the total number of bits in a string of length is \({2^6} = 64\)

Hence,the number of bit string of length six do not contains four consecutives\(1's\) is \(64 - 8 = 56\).