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'm trying to understand from a combinatoric point of view why a particular answer is wrong. I'm given the alphabet $\Sigma = \{ 0,1,2 \}$ and the set of 8 letter words made from that alphabet, $\Sigma_8$ . There are $3^8 =6561$ such 8 letter words.

How many words have exactly three 1's?

How many words have at least one each of 0,1 and 2?

In the first question I reasoned that first I choose $\binom{8}{3}$ places for the three 1's. Then I have 5 place left where I can put 0's and 2's which is $2^5$. Since I can combine each choice of 1 positions with every one of the $2^5$ arrangements of 0's and 2's then I get $\binom{8}{3}\cdot 2^5 = 1792$ which is correct.

I tried applying the same reasoning to the second question and got $\binom{8}{3}\cdot 3^5 = 13608$ which is obviously wrong.

Was my reasoning sound in the first question or did I just happen to get the correct answer by chance? If it is sound, why doesn't it work with the second question?

share|improve this question
    
Why was this question marked down, especially more than two years after it was asked? –  Robert S. Barnes Mar 15 at 17:43
add comment

1 Answer 1

up vote 4 down vote accepted

Your reasoning is correct in the first question.

In the second question, by choosing three places to put a $0$, a $1$, and a $2$, you are counting each word several times. For example, you count the word $01222222$ once as $\underline{012}22222$, once as $\underline{01}2\underline{2}222$, once as $\underline{01}222\underline{2}22$, and so on, where the underline denotes the three chosen places.

You are also undercounting, for each choice of 3 places, the permutations of $0$, $1$, and $2$ that go in them, but that's a different story.

This was not a problem in the first question because once you have chosen 3 places for the $1$'s, the rest of the places can't have a $1$ in them, so you never count a word more than once.

The easiest way to get the right answer to the second question is probably to count the number of words that have no $0$, or no $1$, or no $2$, and subtract that from the total number of words. Remember not to overcount the words that have no $0$ and no $1$, etc.

share|improve this answer
add comment

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.