Six-letter ‘words’ are formed using the letters A, B, C and D. In how many of them does each letter appear at least once?
In the answer, it says
$$
4 \cdot 6 \cdot 5 \cdot 4+\left(\begin{array}{l}
4 \\
2
\end{array}\right) \cdot 6 \cdot 5 \cdot\left(\begin{array}{l}
4 \\
2
\end{array}\right)=1560
$$
Could someone please explain this to me, thanks. I tried to solved in both of the following ways but seems like none of them is correct. $$
\begin{aligned}
&\frac{6 !}{3 !}=120\\ or \\
&4^{6}-\left(\begin{array}{l}
4 \\
1
\end{array}\right) \cdot 3^{6}-\left(\begin{array}{l}
4 \\
2
\end{array}\right) \cdot 2^{6}-\left(\begin{array}{l}
4 \\
3
\end{array}\right) \cdot 1^{6}=792
\end{aligned}
$$
Best Answer
Isaac Browne correctly explained how to obtain the answer in the solution manual.
Let's examine two other methods.
Method 1: We consider cases, depending on whether one letter is used three times and the others are each used once or two letters are each used twice and the other two letters are each used once.
One letter is used three times and the others are each used once: There are four choices for the letter which is used three times, $\binom{6}{3}$ ways to fill three of the positions with that letter, and $3!$ ways to arrange the remaining three letters in the remaining three positions. Hence, there are $$\binom{4}{1}\binom{6}{3}3!$$ such arrangements.
Two letters are each used twice and the other two letters are each used once: We can choose which two of those four letters are each used twice in $\binom{4}{2}$ ways, choose two of the six positions for the repeated letter which appears first in an alphabetical listing in $\binom{6}{2}$ ways, choose two of the remaining four positions for the other repeated letter in $\binom{4}{2}$ ways, then arrange the remaining two distinct letters in the remaining two positions in $2!$ ways. Hence, there are $$\binom{4}{2}\binom{6}{2}\binom{4}{2}2!$$ such arrangements.
Total: Since these two cases are mutually exclusive and exhaustive, there are $$\binom{4}{1}\binom{6}{3}3! + \binom{4}{2}\binom{6}{2}\binom{4}{2}2! = 1560$$ six-letter words that can be formed using the letters $A, B, C, D$ in which all four letters appear.
Method 2: We apply the Inclusion-Exclusion Principle. You did not apply it correctly.
The term $4^6$ counts all the six-letter words that can be formed from the alphabet $\{A, B, C, D\}$. From these, we wish to eliminate those words in which one or more letters is omitted.
A letter is omitted from the word: There are four ways to select the omitted letter and $3^6$ ways to fill the six positions with the remaining three letters. Thus, we subtract $$\binom{4}{1}3^6$$ from the total.
However, if we subtract these arrangements from the total, we will have subtracted those arrangements in which two letters are missing twice, once for each way of designating one of those two letters as the missing letter. We only want to subtract such arrangements once, so we must add them to the total.
Two letters are omitted from the word: There are $\binom{4}{2}$ ways to choose which two of the four letters to exclude and $2^6$ ways to fill the six positions with the remaining two letters. Hence, there are $$\binom{4}{2}2^6$$ such arrangements.
However, if we add this amount to our total, we will have added too much. This is because we first subtracted those arrangements in which three letters are missing three times, once for each way of designating one of those three letters as the missing letter, then added those arrangements three times, once for each of the $\binom{3}{2}$ ways of designating two of those three letters as the two missing letters. Thus, we have not subtracted those cases in which three of the letters are missing. Therefore, we must subtract them from the total.
Three letters are missing from the word: There are $\binom{4}{3}$ ways to exclude three of the four letters and one way to fill all six positions with the remaining letters. Hence, there are $$\binom{4}{3}1^6$$ such arrangements.
It is not possible for all four of the letters to be missing from the word, so we are done.
By the Inclusion-Exclusion Principle, we obtain $$4^6 - \frac{4}{1}3^6 + \binom{4}{2}2^6 - \binom{4}{3}1^6 = 1560$$ words of length six formed from the alphabet $\{A, B, C, D\}$ in which all four letters appear. Notice that the signs alternate.
Note: The number $$\frac{6!}{3!}$$ does not make sense in this context. It represents the number of distinguishable permutations of the string $AAABCD$. Pick three of the six positions for the $A$s, then arrange the three distinct letters in the remaining three positions in $$\binom{6}{3}3! = \frac{6!}{3!3!} \cdot 3! = \frac{6!}{3!}$$ ways. The factor of $3!$ in the denominator represents the number of ways the three $A$s can be permuted among themselves within a given arrangement without producing an arrangement distinguishable from that arrangement.