Question

How many bit strings of length\(10\)contain at least three\(1\)s and at least three\(0\)s?

Short answer

The required strings are \(912\) bit.

Step-by-step solution

Definitions of Product rule, Permutation, and Combination

Product rule: If one event can occur in\(m\)ways and a second event can occur in\(n\)ways, then the number of ways that the two events can occur in sequence is then\(m \cdot n\).

Definition permutation (order is important):

\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Definition combination (order is not important):

\(C(n,r) = \left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)with\(n! = n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1\)

Calculate the number of strings by the formula of Product rule, Permutation or Combination

Total number of strings of length\(10\).

Each bit has\(2\)possible options (\(0\)or\(1\)).

Using the product rule:

$\(2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = {2^{10}} = 1024\)

Strings with no ones or zeros:

The order of the positions of the same bits is not important (since interchange bits with the same values won't affect the string). So, use the definition of combination.

Select\(0\)ones from the\(10\)digits.

\(C(10,0) = \frac{{10!}}{{0!(10 - 0)!}} = \frac{{10!}}{{0!10!}} = 1\)

Similarly, there is exactly 1 string withno zeros.

Strings with\(1\)ones or zeros:

The order of the positions of the same bits is not important (since interchange bits with the same values won't affect the string). So, use the definition of combination.

Select\(1\)one from the\(10\)digits.

\(C(10,1) = \frac{{10!}}{{1!(10 - 1)!}} = \frac{{10!}}{{1!9!}} = 10\)

Strings with\(2\)ones or zeros:

The order of the positions of the same bits is not important (since interchange bits with the same values won't affect the string). So, use the definition of combination.

Select\(2\)ones from the\(10\)digits.

\(C(10,2) = \frac{{10!}}{{2!(10 - 2)!}} = \frac{{10!}}{{2!8!}} = 45\)

Similarly, there is exactly\(45\)strings with\(2\)zeros.

Strings of length\(10\)with at least\(3\)ones and at least\(3\)zeros strings of length\(10\)with at least\(3\)ones and at least\(3\)zeros are then those strings of length\(10\)that do not have no one’s/zeros,\(1\)one/zero,\(2\)ones/zeros.

Subtract the number of strings with 1 ones/zeros, the number of strings with 2 ones/zeros and the number of strings with 2 ones/zeros from the total number of strings.

\(1024 - 1 - 1 - 10 - 10 - 45 - 45 = 912\`

Hence, the required strings are \(912\) bit.