-1
$\begingroup$

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?

  • 0
    Why was this question marked down, especially more than two years after it was asked?2014-03-15

1 Answers 1

4

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.