6.2 PARTITIONS AND BIJECTIONS 199The left-hand side of (2) is a sum, so we interpret it as a partitioning of a large
set. Each term has the form r (�), which can be interpreted as the number of ways you
choose an r-person team from a pool of n people, and designate a team leader. The
entire left-hand side is the total number of ways of picking a team of any size (between
1 and n) with a designated leader.
The right-hand side counts the same thing, but with an encoding interpretation:
Suppose we number the n people from 1 to n in alphabetical order. First we pick a
leader, which we encode by his or her number (ranging from 1 to n). Then we place
the remaining n - 1 people in alphabetical order, and either include them on the team
or not, encoding our action with the letters y or n. For example, suppose n = 13.
The string Ilnynnnnnnnyyy indicates a team with 5 people, led by #1 1 and also
including #2, #10, #12, and #13. This method codes every possible team-with-Ieader
uniquely, and the number of such strings is equal to n 2 n-^1 , since there are n choices
for the first place in the string (notice that this spot may be occupied with a multi-digit
number, but what we are counting is choices, not digits), and two choices for each of
the remaining n - 1 places. _
Information Management
Proper encoding demands precise information management. The model of storing
information in a computer compels one not to waste "memory" with redundant infor
mation. Here are a few examples of how and how not to organize information.
Example 6.2.2 Suppose that you wanted to count the number of permutations of the
word "BOOBOO." We already know that the answer is 2?�! from the Mississippi for
mula. How to encode this? There are six "slots" in which to place letters. Each
permutation is uniquely determined by knowing in which 2 slots one places the letter
B, since it is understood that the remaining four slots will be occupied by O's. In
other words, there is a bijection between choices of two slots from the six slots and
permutation of the letters. Thus our answer is (�), which of course equals 21�!. A com
mon error is to count choosing slots for Bs and choosing slots for Os as independent
choices, yielding the erroneous answer m (�).
It is hard to avoid all errors of this kind, but try to think carefully about "freedom
of choice": ask yourself what has already been completely determined from previous
choices. In this case, once we choose the slots for the B's, the locations of the O's are
determined and we have no freedom of choice.
Example 6.2.3 Suppose we have three different toys and we want to give them away
to two girls and one boy (one toy per child). The children will be selected from four
boys and six girls. In how many ways can this be done?
Solution: The numerical answer is 36 0. Here are two different approaches.
- Ignore order at first, but don't ignore sex: Then there are (i) ways to pick the
single boy and m ways to pick the two girls. Thus there are (i). (�) ways
of picking one boy and two girls. But this does not distinguish between, say,