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?

Question

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} $$

Answer 1

This can easily be computed using generating functions, where the coefficient of $x$ represents the number of times a letter occurs.

Since we want all four letters in the world, any particular letter can occur a maximum of three times. Also, if we are using a word twice or thrice, we must divide by $2!\; or\;3!$ as we do for permutations with repeated letters

Thus we need to find the coefficient of $x^6$ in
$6!(x^1+\frac{x^2}{2!} +\frac{x^3}{3!})^4$ which wolfram gives as $\boxed{1560}$

---

ADDED EXPLANATION

You can simply regard $x$ as a placeholder for the exponents, thus for the letter $A$, considering the conditions laid down, we can write $(x^1 +\frac{x^2}{2!} + \frac{x^3}{3!}), $ meaning that we can use anyrhing fro $1-3 A's$ I have already explained division by factorials for multiple use of a letter. Each of the letters will need the same expression here, so we multiply the expressions for the four letters, and condense it as $(x^1 +\frac{x^2}{2!} + \frac{x^3}{3!})^4, $

As you know, multiplication of polynomials adds exponents , which is what we are aiming at, because we want to add all possibilities yielding an exponent of $x^6$

That is why the final step is to find the coefficient of $x^6$ in
$6!(x^1+\frac{x^2}{2!} +\frac{x^3}{3!})^4$

Answer 2

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.

Answer 3

There are two disjoint cases that we can separate this into.

1. There are $3$ of a single letter. Then there are $4$ possible letters to repeat. Then, choosing the location of each single letter, the repeated letters must go in the remaining spots and we get $6\cdot 5\cdot 4$ possible orderings. This gives the first $$4\cdot(6\cdot 5\cdot 4)$$

2. There are $2$ letters each repeated once. Then, there are $\binom{4}{2}$ possible choices of two letters to repeat. Then, choosing the location of each single letter and the location of the first of the repeated letters, the second repeated letters must go in the remaining spots and we get $6\cdot 5\cdot \binom{4}{2}$ possible orderings. This gives the second $$\binom{4}{2}\cdot \left(6\cdot 5 \cdot \binom{4}{2}\right)$$

Adding these cases up gives the result you found in the answer.