200 CHAPTER 6 COMBINATORICS
"Joe, Sue, Jane" and "Jane, Joe, Sue." In other words, we need to correct for
order by multiplying by 3! (since we give away the toys, which are different,
in order). So the answer is (i). m · 3!. •- Include order from the start: First, pick a boy (we can do this in (i) ways).
Then, pick a toy for this boy (three ways). Then, pick the two girls, but count
ing order (P( 6,2) = 6·5 ways). The answer is then P( 6,2). (i) ·3. •
Example 6.2.4 Suppose again that we have three different toys and we want to give
them away (one toy per kid) to three children selected from a pool of four boys and six
girls, but now we require that at least two boys get a toy. In how many ways can this
be done?Solution: Beginners are often seduced by the quick answers provided by encoding
and attempt to convert just about any counting problem into a simple multiplication or
binomial coefficient.
The following argument is wrong, but not obviously wrong. Imagine that the toys
are ordered (for example, in order, we give away a video game, a doll, a puzzle). We
first pick a boy to get the video game (four choices). Then another boy gets the doll
(three choices). Then we give the puzzle to one of the eight remaining kids (eight
choices). The number of ways we can do this is just 4·3·8. Of course, we need to
correct for sex bias. With this method, we are guaranteeing that only boys get the
video game and the doll. The puzzle is the "leftover" toy. So, to make the count fair,
and symmetrical, we multiply by 3, for the three different leftover toy possibilities.
(We don't multiply by 3! = 6, since the order of the pick of the two has already been
incorporated into our count.) Anyway, this yields 4·3·8·3 = 288, which is too large!
Why?
The problem is the "leftover" toy. Sometimes a boy gets it, sometimes a girl. If a
girl gets the leftover toy, the count is OK. But if a boy gets it, we will be overcounting
by a factor of three. To see this, imagine that the puzzle is the leftover toy and we
picked (in order) "Joe, Bill, Fred." Then Joe gets the video game, Bill gets the doll,
and Fred gets the puzzle. Now, let the video game be the overflow toy. We will still
end up counting a choice where Fred gets the puzzle, Bill gets the doll, and Joe gets
the video game as a different choice! If a girl ended up with the overflow toy, there
wouldn't be an overcount. For example, if Joe gets the video game, Bill gets the doll,
and Sue gets the puzzle, and then later we made the video game the overflow toy, the
new count would give Sue the video game, which is certainly a different choice!
This is confusing! How do you guard against such subtle errors? There is no
perfect solution, but it is crucial that you check your counting method by looking at
smaller numbers, where you can directly count the choices. And also, in this case, let
the language ("at least") clue you in to other methods. Whenever you see "at least,"
you should investigate partitioning.^3 This gives an easy and reliable solution, for there
are two cases:(^3) Also. you should consider the tactic of counting the complement (page 207 ).