Showing equivalence between counting problems

34 Views Asked by At

Count the number of five-letter words that use letters from the set $\{A, B, C\}$ in which each letter appears at least once (no missing letters).

Answer: $3 \cdot \binom{5}{3, 1, 1} + 3 \cdot \binom{5}{2, 2, 1}$.

I want to show that the problem above is equivalent to the one below:

Find the number of distributions of five distinct balls into three distinct boxes with no empty boxes.

Case $1$: put exactly three balls in box $A$, exactly one ball in box $B$ and exactly one ball in box $C$.

Case $2$: put exactly two balls in box $A$, exactly two balls in box $B$ and exactly one ball in box $C$.

This gives us $\binom{5}{3, 1, 1} + \binom{5}{2, 2, 1}$.

But what gives us the coefficient of $3$ here? Thanks.

1

There are 1 best solutions below

1
On BEST ANSWER

You're missing four more cases:

Case $3$: put exactly one ball in box $A$, exactly three balls in box $B$, and exactly one ball in box $C$.

Case $4$: put exactly one ball in box $A$, exactly one ball in box $B$, and exactly three balls in box $C$.

Case $5$: put exactly two balls in box $A$, exactly one ball in box $B$, and exactly two balls in box $C$.

Case $6$: put exactly one ball in box $A$, exactly two balls in box $B$, and exactly two balls in box $C$.

After considering all six cases, you get three cases that give us $\binom{5}{3,1,1}$ and three cases that give us $\binom{5}{2,2,1}$, so we get the same answer as for the first problem.