[Math] Number of five-letter words that use letters from the set $\{A, B, C, D, E\}$ and contain exactly three different letters.

combinatoricsdiscrete mathematicsmultinomial-coefficients

I'd like to see if what I did below makes sense.

We are not allowed to have words like $ABCDE$ because the words must contain exactly three different letters, not at least three different letters. So, the possible permutations are $ABCCC, ABBCC, CDEEE, \ldots$

Now it's clear that our problem can be rewritten as

Find the number of five-letter words that use letters from the set $\{X, Y, Z\}$ where $X, Y, Z \in \{A, B, C, D, E\}$ at least once.

So, we have two sets:

Set $1$ (one of the letters repeated three times): $XYZZZ, XXXYZ, YYYXZ$

Set $2$ (two of the three letters repeated twice each): $XYYZZ, XXYZZ, XXYYZ$

Now the number of permutations of $XYZZZ$ is $\binom {5}{1, 1, 3} = \frac {5!}{1! \cdot 1! \cdot 3!} = 20.$ Since there are two more words in the set $1$, the number of all the possible permutations of this set is $3 \cdot \binom {5}{1, 1, 3} = 60.$

The number of permutations of $XYYZZ$ is $\binom {5}{1, 2, 2} = \frac{5!}{1! \cdot 2! \cdot 2!} = 30.$ Since there are two more permutations in the set $2$, the number of all the possible permutations of this set is $3 \cdot \binom {5}{1, 2, 2} = 90.$

Thus, the number of all the words with the given condition is $\binom 52 \left(3\binom {5}{1, 1, 3} + 3\binom {5}{1, 2, 2}\right) = 1500$ where the binomial coefficient is the number of places to put $X, Y, Z$

EDIT:

Here's the model problem:

Find the number of words of a given length from a given set of letters, if each
letter must occur at least once in each word.

Solution: $T(m, n) = \sum_{m_i \ge 1} \binom{m}{m_1,\ldots, m_n}$ where $\sum_{i =1}^n m_i = m.$

The problem in my OP has an answer in the back of my book given as $\binom{5}{2}T(5, 3) = 1500.$

Best Answer

You are getting the right answer, but your explanation of it doesn't sound quite right. I would approach it this way:

First, pick two letters not to use. This can be done in ${5\choose2}$ ways. Next, with the remaining three letters, consider the two cases:

  1. Pick one letter to use three times, the other two being used just once. This can be done $3$ ways, and then the letters can be arrange in $5\choose1,1,3$ ways.

  2. Pick one letter to use just once, with the other being being used twice each. Again, there are $3$ choices for the singlet, and then $5\choose1,2,2$ ways to arrange the letters.

The total number of words with three different letters is thus

$${5\choose2}\left(3{5\choose1,1,3}+3{5\choose1,2,2}\right)=10(3\cdot20+3\cdot30)=1500$$

Related Question