Question

How many bit strings contain exactly eight\(0\)s and\(10\)\(1\)s if every\(0\)must be immediately followed by a\(1\)?

Short answer

The required strings are\(45\)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\(8\)zeros and\(10\)ones.

Since every\(0\)must be immediately followed by a \(1\), it requires\(8\)blocks of \(01\)and the remaining\(2\)ones can be in any position between the blocks.

The positions of the\(2\)ones should be selected from the 10 positions in total (for the\(8\)blocks and\(2\)ones):

\(\begin{array}{l}C(10,2) = \frac{{10!}}{{2!(10 - 2)!}}\\C(10,2) = \frac{{10!}}{{2!8!}}\\C(10,2) = 45\end{array}\)