Permutation/Combinations in bit Strings

I have a bit string with 10 letters, which can be {a, b, c}. How many bit strings can be made that have exactly 3 a's, or exactly 4 b's?

I thought that it would be C(7,2) + C(6,2), but that's wrong (the answer is 24,600).

-

Hint: By the inclusion-exclusion principle, the answer is equal to \begin{align} & \text{(number of strings with exactly 3 a's)}\\ + & \text{(number of strings with exactly 4 b's)}\\ - &\text{(number of strings with exactly 3 a's and 4 b's)} \end{align}

Suppose I want to make a string with exactly 3 a's. First, I need to choose where to put the a's; the number of ways of choosing 3 places to put the a's, out of 10 places, is $\binom{10}{3}$. Now, I need to choose how to fill in the other places with b's or c's; there are 2 choices of letters and 7 places left. Thus, the number of strings that have exactly 3 a's is equal to $$\binom{10}{3}\cdot 2^7$$ You should be able to use similar reasoning to find the other numbers.

-
It seems like in your answer , in the written part, you do not include the fact that you are dividing by 3!7!, when you say there are 10 choices for the first, nine for the second, etc. –  gary Jun 22 '11 at 2:59
@gary, that's a good point, I forgot include that bit. –  Zev Chonoles Jun 22 '11 at 3:04

This is a complicated problem whose solution requires a number of steps.

Let us first count the number of strings that have exactly $3$ a's. Note that there are lots of them, many more than the $C(7,2)$ that you thought there are.

Even if we only think about the words that start with $3$ a's, there are quite a few, for then the rest of the $7$ remaining places can be filled with any string made up of b's and/or c's. And there are $2^7$ "words" of length $7$ that only use b's and or c's. Now let's start the analysis.

The location of the $3$ a's can be chosen in $C(10,3)$ ways. For each of these ways, there are $7$ open spots left. At each spot, you have a choice about whether to fill it with b or c. So for every possible location of the $3$ a's, there are $2^7$ ways to fill in the rest of the spots.

Thus the number of strings of length $10$ that have exactly $3$ a's is $$C(10,3) \times 2^7.$$ Call this number $A$.

The same kind of reasoning shows that the number of strings of length $10$ with exactly $4$ b's is $$C(10,4)\times 2^6.$$ Call this number $B$.

It might be a good idea at this point to draw a Venn Diagram. Draw two intersecting circles. One of them has the words that have exactly $3$ a's, the other has the words that have exactly $4$ b's. The two circles have a region in common which represents all the strings that fit both descriptions.

If we add $A$ and $B$, we will be counting each string that has exactly $3$ a's and exactly $4$ b's twice. So $A+B$ is not our answer, it is too large.

To get the correct count, we must subtract from $A+B$ the number of strings that have $3$ a's, $4$ b's, and the rest c's, since they made up part of the count in $A$, and also part of the count in $B$.

Let's now count these "double-counted" strings. The location of the a's can be chosen in $C(10,3)$ ways. For each such choice, there are $7$ candidate spots left for the b's. The $4$ spots for the b's can be chosen from these $7$ in $C(7,4)$ ways, for a total of

$$C(10,3) \times C(7,4).$$

Now it remains to put the pieces together and get a final count. And you would be expected, probably, to actually compute and get an explicit numerical answer.

-

First note that

Number of ways of event $A$ or event $B =$ (Number of ways of event $A$) + (Number of ways of event $B$) - (Number of ways of event $A$ and $B$ occurring simultaneously)

In our problem, event $A$ is the number of strings containing exactly $3$ $a$'s and event $B$ is the number of strings containing exactly $4$ $b$'s

We are interested in the number of strings containing exactly $3$ $a$'s and in the number of strings containing exactly $4$ $b$'s.

Number of strings containing exactly $3$ $a$'s is obtained as follows. Of the $10$ letters in our string, if we want exactly $3$ $a$'s, each of the remaining $7$ has $2$ choices, namely, it should be either $b$ or $c$ and hence we have $2^7$ choices for the remaining $7$. Once we have this, we can now arrange them in $\frac{10!}{3! \times 7!}$ ways. Hence, number of ways of this event is $\frac{10!}{3! \times 7!} \times 2^7$.

Similarly, number of strings containing exactly $4$ $b$'s is obtained as follows. Of the $10$ letters in our string, if we want exactly $4$ $b$'s, each of the remaining $6$ has $2$ choices, namely, it should be either $a$ or $c$ and hence we have $2^6$ choices for the remaining $6$. Once we have this, we can now arrange them in $\frac{10!}{4! \times 6!}$ ways. Hence, number of ways of this event is $\frac{10!}{4! \times 6!} \times 2^6$.

Number of strings containing exactly $3$ $a$'s and $4$ $b$'s is $\frac{10!}{3! 4! 3 !}$.

Hence, the total number of strings containing exactly $3$ $a$'s or exactly $4$ $b$'s is $$\frac{10!}{3! \times 7!} \times 2^7 + \frac{10!}{4! \times 6!} \times 2^6 - \frac{10!}{3! 4! 3 !} = 24,600$$

-