Page 411 - Discrete Mathematics and Its Applications

390 6 / Counting

both a faculty member and a student. By the sum rule it follows that there are 37 + 83 = 120
possible ways to pick this representative. ▲

We can extend the sum rule to more than two tasks. Suppose that a task can be done in one
of n 1 ways, in one of n 2 ways, ... ,orinoneof n m ways, where none of the set of n i ways of
doing the task is the same as any of the set of n j ways, for all pairs i and j with 1 ≤ i< j ≤ m.
Then the number of ways to do the task is n 1 + n 2 + ··· + n m . This extended version of the
sum rule is often useful in counting problems, as Examples 13 and 14 show. This version of the
sum rule can be proved using mathematical induction from the sum rule for two sets. (This is
Exercise 71.)
EXAMPLE 13 A student can choose a computer project from one of three lists. The three lists contain 23, 15,
and 19 possible projects, respectively. No project is on more than one list. How many possible
projects are there to choose from?

Solution: The student can choose a project by selecting a project from the first list, the second
list, or the third list. Because no project is on more than one list, by the sum rule there are
23 + 15 + 19 = 57 ways to choose a project. ▲

EXAMPLE 14 What is the value of k after the following code, where n 1 ,n 2 ,...,n m are positive integers, has
been executed?

k := 0
for i 1 := 1 to n 1
k := k + 1
for i 2 := 1 to n 2
k := k + 1
.
.
.
for i m := 1 to n m
k := k + 1

Solution: The initial value of k is zero. This block of code is made up of m different loops.
Each time a loop is traversed, 1 is added to k. To determine the value of k after this code has
been executed, we need to determine how many times we traverse a loop. Note that there are
n i ways to traverse the ith loop. Because we only traverse one loop at a time, the sum rule
shows that the final value of k, which is the number of ways to traverse one of the m loops is
n 1 + n 2 + ··· + n m . ▲
The sum rule can be phrased in terms of sets as: If A 1 ,A 2 ,...,A m are pairwise disjoint
finite sets, then the number of elements in the union of these sets is the sum of the numbers of
elements in the sets. To relate this to our statement of the sum rule, note there are |A i | ways to
choose an element from A i for i = 1, 2,...,m. Because the sets are pairwise disjoint, when
we select an element from one of the sets A i , we do not also select an element from a different
set A j . Consequently, by the sum rule, because we cannot select an element from two of these
sets at the same time, the number of ways to choose an element from one of the sets, which is
the number of elements in the union, is
|A 1 ∪ A 2 ∪ ··· ∪ A m |=|A 1 |+|A 2 |+· · ·+|A m | when A i ∩ A j = for all i, j.

This equality applies only when the sets in question are pairwise disjoint. The situation is much
more complicated when these sets have elements in common. That situation will be briefly
discussed later in this section and discussed in more depth in Chapter 8.