The Sum Principle
We begin with an example that illustrates a fundamental principle.
Exercise 1.1-1 The loop below is part of an implementation of selection sort, which sorts
a list of items chosen from an ordered set (numbers, alphabet characters, words, etc.)
into non-decreasing order.
(1) for i = 1 to n−1
(2) for j = i+ 1 to n
(3) if (A[i] > A[j])
(4) exchange A[i] and A[j]
How many times is the comparison A[i] > A[j] made in Line 3?
In Exercise 1.1-1, the segment of code from lines 2 through 4 is executed n − 1 times, once
for each value of i between 1 and n − 1 inclusive. The first time, it makes n − 1 comparisons.
The second time, it makes n − 2 comparisons. The ith time, it makes n − i comparisons. Thus
the total number of comparisons is
(n−1) + (n−2) +···+ 1 . (1.1)
This formula is not as important as the reasoning that lead us to it. In order to put the
reasoning into a broadly applicable format, we will describe what we were doing in the language
of sets. Think about the set S containing all comparisons the algorithm in Exercise 1.1-1 makes.
We divided set S into n−1 pieces (i.e. smaller sets), the set S1 of comparisons made when i = 1,
the set S2 of comparisons made when i = 2, and so on through the set S
n−1 of comparisons made
when i = n−1. We were able to figure out the number of comparisons in each of these pieces by
observation, and added together the sizes of all the pieces in order to get the size of the set of all
comparisons.
In order to describe a general version of the process we used, we introduce some set-theoretic
terminology. Two sets are called disjoint when they have no elements in common. Each of the
sets Si
we described above is disjoint from each of the others, because the comparisons we make
for one value of i are different from those we make with another value of i. We say the set of
sets {S1,...,Sm} (above, m was n − 1) is a family of mutually disjoint sets, meaning that it is
a family (set) of sets, any two of which are disjoint. With this language, we can state a general
principle that explains what we were doing without making any specific reference to the problem
we were solving.
Principle 1.1 (Sum Principle) The size of a union of a family of mutually disjoint finite sets
is the sum of the sizes of the sets.
Thus we were, in effect, using the sum principle to solve Exercise 1.1-1. We can describe the
sum principle using an algebraic notation. Let |S| denote the size of the set S. For example,
|{a, b, c}| = 3 and |{a, b, a}| = 2.1
Using this notation, we can state the sum principle as: if S1, S2, ...Sm are disjoint sets, then
|S1∪S2∪···∪Sm| = |S1|+|S2|+···+|Sm| . (1.2)
To write this without the “dots” that indicate left-out material, we write
When we can write a set S as a union of disjoint sets S1, S2, ..., Sk
we say that we have partitioned S into the sets S1, S2, ..., Sk, and we say that the sets S1, S2, ..., Sk form a partition of S. Thus {{1},{3,5},{2,4}} is a partition of the set {1,2,3,4,5} and the set {1,2,3,4,5} can
be partitioned into the sets {1}, {3,5}, {2,4}. It is clumsy to say we are partitioning a set into
sets, so instead we call the sets Si into which we partition a set S the blocks of the partition.
Thus the sets {1}, {3,5}, {2,4} are the blocks of a partition of {1,2,3,4,5}. In this language,
we can restate the sum principle as follows.
Principle 1.2 (Sum Principle) If a finite set S has been partitioned into blocks, then the size
of S is the sum of the sizes of the blocks.
Abstraction
The process of figuring out a general principle that explains why a certain computation makes
sense is an example of the mathematical process of abstraction. We won’t try to give a precise
definition of abstraction but rather point out examples of the process as we proceed. In a course
in set theory, we would further abstract our work and derive the sum principle from the axioms of
----------------------------------------------------------------------------------------
1It may look strange to have |{a, b, a}| = 2, but an element either is or is not in a set. It cannot be in a set
multiple times. (This situation leads to the idea of multisets that will be introduced later on in this section.) We
gave this example to emphasize that the notation {a, b, a} means the same thing as {a, b}. Why would someone
even contemplate the notation {a, b, a}. Suppose we wrote S = {x|x is the first letter of Ann, Bob, or Alice}.
Explicitly following this description of S would lead us to first write down {a, b, a} and the realize it equals {a, b}.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
set theory. In a course in discrete mathematics, this level of abstraction is unnecessary, so we will
simply use the sum principle as the basis of computations when it is convenient to do so. If our
goal were only to solve this one exercise, then our abstraction would have been almost a mindless
exercise that complicated what was an “obvious” solution to Exercise 1.1-1. However the sum
principle will prove to be useful in a wide variety of problems. Thus we observe the value of
abstraction—when you can recognize the abstract elements of a problem, then abstraction often
helps you solve subsequent problems as well.
Summing Consecutive Integers
Returning to the problem in Exercise 1.1-1, it would be nice to find a simpler form for the sum
given in Equation 1.1. We may also write this sum as
Now, if we don’t like to deal with summing the values of (n − i), we can observe that the
values we are summing are n−1, n−2,...,1, so we may write that
We write
1 + 2 + ··· + n−2 + n−1
+ n−1 + n−2 + ··· + 2 + 1
---------------------------------------
n + n + ··· + n + n
The sum below the horizontal line has n−1 terms each equal to n, and thus it is n(n−1). It
is the sum of the two sums above the line, and since these sums are equal (being identical except
for being in reverse order), the sum below the line must be twice either sum above, so either of
the sums above must be n(n−1)/2. In other words, we may write
This lovely trick gives us little or no real mathematical skill; learning how to think about
things to discover answers ourselves is much more useful. After we analyze Exercise 1.1-2 and
abstract the process we are using there, we will be able to come back to this problem at the end
of this section and see a way that we could have discovered this formula for ourselves without
any tricks.
The Product Principle
Exercise 1.1-2 The loop below is part of a program which computes the product of two
matrices. (You don’t need to know what the product of two matrices is to answer
this question.)
(1) for i = 1 to r
(2) for j = 1 to m
(3) S = 0
(4) for k = 1 to n
(5) S = S + A[i, k] ∗ B[k, j]
(6) C[i, j] = S
How many multiplications (expressed in terms of r, m, and n) does this code carry
out in line 5?
Exercise 1.1-3 Consider the following longer piece of pseudocode that sorts a list of numbers
and then counts “big gaps” in the list (for this problem, a big gap in the list is
a place where a number in the list is more than twice the previous number:
(1) for i = 1 to n − 1
(2) minval = A[i]
(3) minindex = i
(4) for j = i to n
(5) if (A[j] < minval)
(6) minval = A[j]
(7) minindex = j
(8) exchange A[i] and A[minindex]
(9)
(10) for i = 2 to n
(11) if (A[i] > 2 ∗ A[i − 1])
(12) bigjump = bigjump +1
How many comparisons does the above code make in lines 5 and 11 ?
In Exercise 1.1-2, the program segment in lines 4 through 5, which we call the “inner loop,”
takes exactly n steps, and thus makes n multiplications, regardless of what the variables i and j
are. The program segment in lines 2 through 5 repeats the inner loop exactly m times, regardless
of what i is. Thus this program segment makes n multiplications m times, so it makes nm
multiplications.
Why did we add in Exercise 1.1-1, but multiply here? We can answer this question using
the abstract point of view we adopted in discussing Exercise 1.1-1. Our algorithm performs a
certain set of multiplications. For any given i, the set of multiplications performed in lines 2
through 5 can be divided into the set S1 of multiplications performed when j = 1, the set S2 of
multiplications performed when j = 2, and, in general, the set Sj of multiplications performed
for any given j value. Each set Sj consists of those multiplications the inner loop carries out
for a particular value of j, and there are exactly n multiplications in this set. Let Ti be the set
of multiplications that our program segment carries out for a certain i value. The set Ti is the
union of the sets Sj ; restating this as an equation, we get
Then, by the sum principle, the size of the set Ti is the sum of the sizes of the sets Sj , and a sum
of m numbers, each equal to n, is mn. Stated as an equation,
Thus we are multiplying because multiplication is repeated addition!
From our solution we can extract a second principle that simply shortcuts the use of the sum
principle.
Principle 1.3 (Product Principle) The size of a union of m disjoint sets, each of size n, is
mn.
We now complete our discussion of Exercise 1.1-2. Lines 2 through 5 are executed once for
each value of i from 1 to r. Each time those lines are executed, they are executed with a different
i value, so the set of multiplications in one execution is disjoint from the set of multiplications
in any other execution. Thus the set of all multiplications our program carries out is a union
of r disjoint sets Ti of mn multiplications each. Then by the product principle, the set of all
multiplications has size rmn, so our program carries out rmn multiplications.
Exercise 1.1-3 demonstrates that thinking about whether the sum or product principle is
appropriate for a problem can help to decompose the problem into easily-solvable pieces. If you
can decompose the problem into smaller pieces and solve the smaller pieces, then you either
add or multiply solutions to solve the larger problem. In this exercise, it is clear that the
number of comparisons in the program fragment is the sum of the number of comparisons in the
first loop in lines 1 through 8 with the number of comparisons in the second loop in lines 10
through 12 (what two disjoint sets are we talking about here?). Further, the first loop makes
n(n + 1)/2 − 1 comparisons2, and that the second loop has n − 1 comparisons, so the fragment
makes n(n + 1)/2 − 1 + n −1 = n(n + 1)/2 + n − 2 comparisons.
Two element subsets
Often, there are several ways to solve a problem. We originally solved Exercise 1.1-1 by using the
sum principal, but it is also possible to solve it using the product principal. Solving a problem
two ways not only increases our confidence that we have found the correct solution, but it also
allows us to make new connections and can yield valuable insight.
Consider the set of comparisons made by the entire execution of the code in this exercise.
When i = 1, j takes on every value from 2 to n. When i = 2, j takes on every value from 3 to
n. Thus, for each two numbers i and j, we compare A[i] and A[j] exactly once in our loop. (The
order in which we compare them depends on whether i or j is smaller.) Thus the number of
comparisons we make is the same as the number of two element subsets of the set {1, 2, . . . , n}3.
In how many ways can we choose two elements from this set? If we choose a first and second
element, there are n ways to choose a first element, and for each choice of the first element, there
are n−1 ways to choose a second element. Thus the set of all such choices is the union of n sets
---------------------------------------------------------------------------
2To see why this is true, ask yourself first where the n(n + 1)/2 comes from, and then why we subtracted one.
3The relationship between the set of comparisons and the set of two-element subsets of {1, 2, . . . , n} is an
example of a bijection, an idea which will be examined more in Section 1.2.
---------------------------------------------------------------------------
of size n−1, one set for each first element. Thus it might appear that, by the product principle,
there are n(n − 1) ways to choose two elements from our set. However, what we have chosen is
an ordered pair, namely a pair of elements in which one comes first and the other comes second.
For example, we could choose 2 first and 5 second to get the ordered pair (2, 5), or we could
choose 5 first and 2 second to get the ordered pair (5, 2). Since each pair of distinct elements
of {1, 2, . . . , n} can be ordered in two ways, we get twice as many ordered pairs as two element
sets. Thus, since the number of ordered pairs is n(n − 1), the number of two element subsets of
{1, 2, . . . , n} is n(n − 1)/2. Therefore the answer to Exercise 1.1-1 is n(n − 1)/2. This number
comes up so often that it has its own name and notation. We call this number “n choose 2”
and denote it by
stands for the number of two element subsets of an na second answer to Exercise 1.1-1 is
this shows that = n(n − 1)/2 .Important Concepts, Formulas, and Theorems
1. Set. A set is a collection of objects. In a set order is not important. Thus the set {A,B,C} is the same as the set {A,C,B}. An element either is or is not in a set; it cannot be in a
set more than once, even if we have a description of a set which names that element more
than once.
2. Disjoint. Two sets are called disjoint when they have no elements in common.
3. Mutually disjoint sets. A set of sets {S1, . . . , Sn} is a family of mutually disjoint sets, if
each two of the sets Si are disjoint.
4. Size of a set. Given a set S, the size of S, denoted |S|, is the number of distinct elements
in S.
5. Sum Principle. The size of a union of a family of mutually disjoint sets is the sum of the
sizes of the sets. In other words, if S1, S2, . . . Sn are disjoint sets, then
|S1 ∪ S2 ∪ ·· ·∪Sn| = |S1| + |S2| + · · · + |Sn|.
To write this without the “dots” that indicate left-out material, we write
6. Partition of a set. A partition of a set S is a set of mutually disjoint subsets (sometimes
called blocks) of S whose union is S.
7. Sum of first n − 1 numbers.
8. Product Principle. The size of a union of m disjoint sets, each of size n, is mn.
9. Two element subsets. n
2 stands for the number of two element subsets of an n element set
and equals n(n − 1)/2. n
2 is read as “n choose 2.”