Discrete Mathematics: Elementary and Beyond

10 1. Let’s Count!

It is not difficult to see that this is always the answer. Suppose you have
to select a subset of a setAwithnelements; let us call these elements
a 1 ,a 2 ,...,an. Then we may or may not want to includea 1 , in other words,
we can make two possible decisions at this point. No matter how we decided
abouta 1 , we may or may not want to includea 2 in the subset; this means
two possible decisions, and so the number of ways we can decide abouta 1
anda 2 is 2·2 = 4. Now no matter how we decide abouta 1 anda 2 ,wehave
to decide abouta 3 , and we can again decide in two ways. Each of these
ways can be combined with each of the 4 decisions we could have made
abouta 1 anda 2 , which makes 4·2 = 8 possibilities to decide abouta 1 ,a 2
anda 3.
We can go on similarly: No matter how we decide about the firstk
elements, we have two possible decisions about the next, and so the number
of possibilities doubles whenever we take a new element. For deciding about
all thenelements of the set, we have 2npossibilities.
Thus we have derived the following theorem.

Theorem 1.3.1A set withnelements has 2 nsubsets.

{a,b,c}

aS

bS
 bS

cS
 cS
 cS
 cS

Y

YY

Y Y Y Y

N

N N

NNNN

{a,b} {a,c} {a} {b,c} {b} {c} ∅∅∅∅

FIGURE 1.2. A decision tree for selecting a subset of{a, b, c}.

We can illustrate the argument in the proof by the picture in Figure 1.2.
We read this figure as follows. We want to select a subset calledS. We start
from the circle on the top (called anode). The node contains a question:
Isaan element ofS? The two arrows going out of this node are labeled
with the two possible answers to this question (Yes and No). We make a
decision and follow the appropriate arrow (also called anedge) to the node
at the other end. This node contains the next question: Isban element of
S? Follow the arrow corresponding to your answer to the next node, which