The Art and Craft of Problem Solving

6.2 PARTITIONS AND BIJECTIONS 201

1. There are exactly two boys, and one girl chosen. Arguing as we did in 6.2.3
   above, there are (i) ways to pick the boys, and (�) ways to pick a girl, and
   then we must correct for order by multiplying by 3!.


2. There are exactly three boys. There will be just P(4,3) choices (since order
   matters).

The final answer is just the sum of these two, or

G) G)3! +P(4,3) = 6·6·6+ 24 = 240,

which indeed is smaller than the incorrect answer of 288. •

Example 6.2.5 The Hockey Stick Identity. Consider the "hockey stick" outlined in
Pascal's Triangle below.

1 1

1 5 5 1

The sum of the elements in the handle is equal to the element in the blade; i.e.,

1 +2 + 3+ 4 = 10.

This works for any parallel "hockey stick" of any length or location that begins at the
border of the triangle. For example, 1 + 3 + 6 = 10 and 1 + 4 + 10 + 20 = 35 (check
that this one works by writing in the next few rows of the triangle). In general, if we
start at row s and continue until row t, we have

Why is this true?

Solution: Consider a specific example, say 1 + 3 + 6 + 10 = 20. We need to
explain why

(�) +(�) + (�) + (�) = (�).

The simple sum suggests partitioning: Let us look at all three-element subsets (which
we will ca1l3-sets) chosen from a set of six elements, and see if we can break them up
into four "natural" classes.
Write the six-element set as {a,b,c,d,e,f} and follow the natural convention that
subsets are written in alphabetic order. This tactic is a simple and natural way to