Question

How many bit strings of length \({\rm{10}}\) over the alphabet \({\rm{\{ a,b,c\} }}\) have either exactly three \({\rm{a}}\)s or exactly four \({\rm{b}}\)s?

Short answer

The number of bit strings of length \({\rm{10}}\) over the alphabet \({\rm{\{ a,b,c\} }}\) that have either exactly three \({\rm{a's}}\) or exactly four \({\rm{b's}}\) is \({\rm{24,600}}\) strings.

Step-by-step solution

Concept Introduction

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

Subtraction rule: If an event can occur either in\({\rm{m}}\)ways or in\({\rm{n}}\)ways (overlapping), the number of ways the event can occur is then\({\rm{m + n}}\)decreased by the number of ways that the event can occur commonly to the two different ways.

Definition of permutation (order is important) is –

No repetition allowed:\({\rm{P(n,r) = }}\frac{{{\rm{n!}}}}{{{\rm{(n - r)!}}}}\)

Repetition allowed:\({{\rm{n}}^{\rm{r}}}\)

Definition of combination (order is important) is –

No repetition allowed:\({\rm{C(n,r) = }}\frac{{{\rm{n!}}}}{{{\rm{r!(n - r)!}}}}\)

Repetition allowed:\({\rm{C(n + r - 1,r) = }}\frac{{{\rm{(n + r - 1)!}}}}{{{\rm{r!(n - 1)!}}}}\)

With\({\rm{n! = n}} \cdot {\rm{(n - 1)}} \cdot ... \cdot {\rm{2}} \cdot {\rm{1}}\).

Strings with three \({\rm{a's}}\)

Let the string contain three\({\rm{a's}}\). First select the\({\rm{3}}\)positions of the\({\rm{a's}}\)out of the\({\rm{10}}\)possible positions. The order of the positions does not matter (since they all contain the same element), thus it is needed to use the definition of combination and repetition of positions is not allowed.

\(\begin{array}{c}{\rm{C(10,3) = }}\frac{{{\rm{10!}}}}{{{\rm{3!(10 - 3)!}}}}\\{\rm{ = }}\frac{{{\rm{10!}}}}{{{\rm{3!7!}}}}\\{\rm{ = 120}}\end{array}\)

Since the string has length\({\rm{10}}\), then it is still needed to select\({\rm{7}}\)bits from the\({\rm{2}}\)possible answers\((b,c)\).

The order is important (different order of leads to different strings) and repetition is allowed (because the same bits can occur), thus it is needed to use permutation.

\(\begin{array}{c}{{\rm{n}}^{\rm{r}}}{\rm{ = }}{{\rm{2}}^7}\\{\rm{ = 128}}\end{array}\)

Using the product rule –

\({\rm{120}} \cdot {\rm{128 = 15,360}}\)

Strings with four \({\rm{b's}}\)

Let the string contain four\({\rm{b's}}\). First select the\({\rm{4}}\)positions of the\({\rm{b's}}\)out of the\({\rm{10}}\)possible positions. The order of the positions does not matter (since they all contain the same element), thus it is needed to use the definition of combination and repetition of positions is not allowed.

\(\begin{array}{c}{\rm{C(10,4) = }}\frac{{{\rm{10!}}}}{{{\rm{4!(10 - 4)!}}}}\\{\rm{ = }}\frac{{{\rm{10!}}}}{{{\rm{4!6!}}}}\\{\rm{ = 210}}\end{array}\)

Since the string has length\({\rm{10}}\), then it is still needed to select\({\rm{6}}\)bits from the\({\rm{2}}\)possible answers\((a,c)\).

The order is important (different order of leads to different strings) and repetition is allowed (because the same bits can occur), thus it is needed to use permutation.

\(\begin{array}{c}{{\rm{n}}^{\rm{r}}}{\rm{ = }}{{\rm{2}}^6}\\{\rm{ = 64}}\end{array}\)

Using the product rule –

\({\rm{210}} \cdot {\rm{64 = 13,440}}\)

Strings with three \({\rm{a's}}\) and four \({\rm{b's}}\)

Let the string contain three\({\rm{a's}}\)and four\({\rm{b's}}\). First select the\({\rm{3}}\)positions of the\({\rm{a's}}\)out of the\({\rm{10}}\)possible positions. The order of the positions does not matter (since they all contain the same element), thus it is needed to use the definition of combination and repetition of positions is not allowed.

\(\begin{array}{c}{\rm{C(10,3) = }}\frac{{{\rm{10!}}}}{{{\rm{3!(10 - 3)!}}}}\\{\rm{ = }}\frac{{{\rm{10!}}}}{{{\rm{3!7!}}}}\\{\rm{ = 120}}\end{array}\)

Nextselect the\({\rm{4}}\)positions of the\({\rm{b's}}\)out of the\({\rm{7}}\)remaining possible positions. The order of the positions does not matter (since they all contain the same element), thus it is needed to use the definition of combination and repetition of positions is not allowed.

\(\begin{array}{c}{\rm{C(7,4) = }}\frac{{{\rm{7!}}}}{{{\rm{4!(7 - 4)!}}}}\\{\rm{ = }}\frac{{{\rm{7!}}}}{{{\rm{4!3!}}}}\\{\rm{ = 35}}\end{array}\)

Since the string has length\({\rm{10}}\), then it is still needed to select\({\rm{3}}\)bits from the\({\rm{1}}\)possible remaining possible answer\((c)\).

The order is important (different order of leads to different strings) and repetition is allowed (because the same bits can occur), thus it is needed to use permutation.

\(\begin{array}{c}{{\rm{n}}^{\rm{r}}}{\rm{ = }}{{\rm{1}}^3}\\{\rm{ = 1}}\end{array}\)

Using the product rule –

\({\rm{120}} \cdot {\rm{35}} \cdot {\rm{1 = 4200}}\)

Using the subtracting rule –

\(\begin{array}{c}{\rm{15,360 + 13,440 - 4200 = 28,800 - 4200}}\\{\rm{ = 24,600}}\end{array}\)

Therefore, the result is obtained as \({\rm{24,600}}\).