202 CHAPTER 6 COMBINATORICS
get "free" information and is just another example of monotonizing (see page 75).
Since we are counting combinations and not permutations, order is irrelevant as far as
counting is concerned, but that doesn't mean that we cannot impose useful order on
our own.
Following this convention, let us list all 20 different 3 -sets as three-letter "words."
And of course, we will list them in alphabetical order!abe, abd, abe, ab/, aed, aee, ae/, ade, ad/, ae/,"
bed, bee, be/, bde, bd/, be/,"
ede, ed/, eel;
de!
The solution practically cries out: Classify subsets by their initial letter!
Of the 20 different 3-sets, m = 10 of them begin with the letter a, since we are
fixing the first letter and still have to choose two more from the remaining five letters
available (b through f). If we start with the letter b, we must still chose two more, but
have only four choices available (e through I), so we have (i) possibilities. Similarly,
m = 3 of the 3 -sets start with e and just one (m) starts with d. (No 3 -sets can start
with e or I since the letters in each word are in alphabetical order.)
By now you should have a good understanding of why the hockey stick identity
is true. But let us write a formal argument, just for practice. Note the careful use of
notation and avoidance of "OBOB."
We shall show that(3)
holds for all positive integers I 2 r. Let us consider all (r + 1 )-element subsets of the
set {1, 2, ... ,f + 1}. For j = 1,2, ... ,f - r + 1, let tffj denote the collection of these
subsets whose minimal element is j. The tffj partition the collection of (r + 1 )-element
subsets, soIf the minimal element of an (r + 1 )-element subset is j, then the remaining r
elements will be chosen from the range j + 1, j + 2, ... ,I + 1. There are (f + 1) - (j +
1) + 1 = I - j + 1 integers in this range, so consequentlySumming this as j ranges from 1 to I - r + 1 yields (3 ). •
Balls in Urns and Other Classic Encodings
The following well-known problem crops up in many different forms.