Let's say a choir director must select six hymns for a Sunday church service. She has three hymn books, each containing 25 hymns, for a total of 75 different hymns. The question asks for how many ways can she select the six hymns if she chooses at least one hymn from each book.
The correct answer given is as follows:
$$
3 \binom{25}{1}^2 \binom{25}{4} + 6 \binom{25}{1} \binom{25}{2} \binom{25}{3} + \binom{25}{2}^2
$$
I can see why that's correct. But I want to understand why my following approach is wrong.
Specifically, I thought, let's first choose one hymn from each book. There are 25 choices for each book, so there are $25^3$ ways to choose one hymn from each book. Then, we just need to choose three of the hymns from the remaining 72 hymns–since we already have the three hymns from each book selected, it doesn't matter from where we get the remaining hymns. So, in my mind, the answer should be:
$$
25^3 \times \binom{72}{3}
$$
That's clearly not the same answer as the given, and correct, answer, though. I know I'm missing something basic, so any help would be greatly appreciated. Thank you!
(For reference, this is Exercise 4(b) from the Supplementary Exercises for Ch. 1 in Grimaldi.)
Best Answer
This is very common error in combinatorics. The problem is that your method does not uniquely specify the choice of hymns; certain selections are being counted multiple times.
For example, suppose the hymns are labeled $A_1$ to $A_{25}$ in the first book, and $B$ and $C$ for the other two books. Here is one way of choosing hymns according to your method:
Choose one hymn from each book: $A_1$ from the first, $B_1$ from the second, $C_1$ from the third.
Choose the remaining three hymns from any books: $A_2,A_3,B_2$
Here is another way of choosing hymns:
Choose one hymn from each book: $A_2$ from the first, $B_1$ from the second, $C_1$ from the third.
Choose the remaining three hymns from any books: $A_1,A_3,B_2$
Here is the problem; your method counts these two selections as different, when they both resulted in the same set of hymns.
Another way to state this: your method treats the hymns selected in the first stage as "special." So really, what you are counting is the number of ways to select six hymns, with at least one from each book, and to select one chosen hymn from each book to be "special." Since you are making extra choices, you will get a higher count for the number of ways.