Old MacDonald has 5 chickens, 4 donkeys, and 7 emus. How many ways can he pair up the animals so that every pair consists of animals of different species? (The order of the animals within each pair does not matter, and the order among the pairs does not matter. Assume that all animals are distinguishable.)
I thought the answer would be 83 because the possible pairs are:
Chickens and donkeys, 5*4=20
Chickens and emus, 5*7=35
Donkeys and emus, 4*7=28
So the answer would be 20+35+28=83, but it is not correct.
You're always going to have at least 1 emu, chicken pair. So we make that and reduce the problem.
There are 7*5 = 35 ways to make that pair.
Now he have 4 chickens, 4 donkeys, and 6 emus to pair off.
We must pair off emus with an equal number of chickens and donkeys, otherwise we'll have a pair of the same animal left at the end.
We must pair off all the emus so we must have 3 emu/chicken pairs, and 3 emu/donkey pairs. Then we will have 1 chicken/donkey pair left.
There are 6C3 *3! * 4C3*3! ways to make the emu/chicken pairs.
Then there are 3C3*3! * 4C3*3! ways to make the emu/donkey pairs.
We then have 1 chicken and 1 donkey left that pair up.
That makes (including the 35 ways to make the first emu/chicken pair) 14515200 different arrangements.
Look at it another way.
I have 6*4 choices for the first emu/chicken pair, then 5*3, then 4*2.
I then have 3*4 choices for the first emu/donkey pair, then 2*3, then 1*2
This gives me
35 * 6*4*5*3*4*2*3*4*2*3*1*2 = 14515200