Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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.

share|improve this 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$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.