Question

How many bit strings contain exactly five \(0\)s and\(14\)\(1\)s if every\(0\)must be immediately followed by two\(1\)s?

Short answer

The required strings are\(126\)bit.

Step-by-step solution

Definitions of Permutation and Combination

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 Permutation or Combination

Use the formula of combination:

There are\(5\)zeros and\(14\)ones.

Since every\(0\)must be immediately followed by two ones, it requires\(5\)blocks of \(011\)and the remaining\(4\)ones can be in any position between the blocks.

The positions of the\(4\)ones should be selected from the\(9\)positions in total (for the\(5\)blocks and\(4\)ones):

\(\begin{array}{l}C(9,4) = \frac{{9!}}{{4!(9 - 4)!}}\\C(9,4) = \frac{{9!}}{{4!5!}}\\C(9,4) = 126\end{array}\)

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