Thread: Discrete math problem with counting

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

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

3. Re: Discrete math problem with counting

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.