The Art and Craft of Problem Solving

6.2 PARTITIONS AND BIJECTIONS 197

example, let us apply this method to Problem 6.1 .23, which asked us to prove that a

set of n elements has 2 n subsets. Denote the set of subsets of the set S by sub(S). For

example, if S = {a, b, c}, then

sub(S) = {0, {a}, {b}, {c}, {a,b}, {a,c}, {b, c}, {a, b, c}}.

Let gk denote the collection of subsets of S that have k elements.^2 The 6j naturally

partition sub(S), since they are mutually disjoint. In other words,

sub(S) = go u gl U g 2 U g3·

The cardinality of 6j is just (D, since counting the number of i-element subsets is

exactly the same as counting the number of ways we can choose i elements from the

original set of three elements. This implies that

Isub(S) 1 = Igol + WII + Ig^21 + Ig^31 = (�) + G) + G) + G)·

In general, then, if lSI = n, the number of subsets of S must be

(�)

+

G)

+

G)

+ ... +

G) '

N ow we must prove that this sum is equal to 2n. This can be done by induction, but
we will try another approach, the encoding tactic. Instead of partitioning the collection
of subsets into many classes, look at this collection as a whole and encode each of its
elements (which are subsets) as a string of symbols. Imagine storing information in a
computer. How can you indicate a particular subset of S = {a, b, c}? There are many
possibilities, but what we want is a uniform coding method that is simple to describe
and works essentially the same way for all cases. That way it will be easy to count.
For example, any subset of S is uniquely determined by the answers to the fo llowing
yes/no questions:

• Does the subset include a?


• Does the subset include b?


• Does the subset include c?

We can encode the answers to these questions by a three-letter string that uses only
the letters y and n. For example, the string yyn would indicate the subset {a, b}.
Likewise, the string nnn indicates 0 and yyy indicates the entire set S. Thus

There is a bijection between strings and subsets.

In other words, to every three-letter string there corresponds exactly one subset, and to
every subset there corresponds exactly one string. And it is easy to count the number
of strings; two choices for each letter and three letters per string means 23 different
strings in all.

(^2) We often use the word "collection" or "class" for sets of sets, and conventionally denote them with script
letters.