Discrete math problem with counting

Hi everyone, I have a problem whose solution I don't understand.

Find the number of five-letter words that use letters from {A,B,C} in which each letters occurs at least once.

Solution:

3^5 -2^5 -2^5 -2^5 +1 +1 +1 = 150

But, my solution is 3^5 -2^5 -2^5 -2^5 -1 -1 -1 = 144

I don't know why I'm wrong. Please, help me to explain it. Thank you very much.

Re: Discrete math problem with counting

The +1's are to make up for the fact that the 2^5 terms double-count words AAAAA, BBBBB, and CCCCC. There are 2^5 ways to make up words using only A and B, including AAAAA and BBBBB. There are also 2^5 ways to make up words using only A and C, including AAAAA and CCCCC. And there are 2^5 ways to make up words using only B and C, including BBBBB and CCCCC. By subtracting 2^5 three times you have eliminated the possibility of AAAAA, BBBBB and CCCC twice each, so you need to add 3 to get the correct answer.

Re: Discrete math problem with counting

Quote:

Originally Posted by

**math88** Hi everyone, I have a problem whose solution I don't understand.

Find the number of five-letter words that use letters from {A,B,C} in which each letters occurs at least once.

Solution:

3^5 -2^5 -2^5 -2^5 +1 +1 +1 = 150

That is the count or the number of surjections (onto functions) from a set of five to a set three.