Source code online books for professionals by professionals

Chapter 3
Counting 101
The  greatest  shortcoming  of  the  human  race  is  our  inability  to  understand  the  exponential 
function.
— Dr. Albert A. Bartlett, World Population Balance  
Board of Advisors
At one time, when the famous mathematician Carl Friedrich Gauss was in primary school, his teacher asked the 
pupils to add all the integers from 1 to 100 (or, at least, that’s the most common version of the story). No doubt, the 
teacher expected this to occupy his students for a while, but Gauss produced the result almost immediately. This 
might seem to require lightning-fast mental arithmetic, but the truth is, the actual calculation needed is quite simple; 
the trick is really understanding the problem.
After the previous chapter, you may have become a bit jaded about such things. “Obviously, the answer  
is Q(1),” you say. Well, yes ... but let’s say we were to sum the integers from 1 to n? The following sections deal with 
some important problems like this, which will crop up again and again in the analysis of algorithms. The chapter 
may be a bit challenging at times, but the ideas presented are crucial and well worth the effort. They’ll make the 
rest of the book that much easier to understand. First, I’ll give you a brief explanation of the concept of sums and 
some basic ways of manipulating them. Then come the two major sections of the chapter: one on two fundamental 
sums (or combinatorial problems, depending on your perspective) and the other on so-called recurrence 
relations, which you’ll need to analyze recursive algorithms later. Between these two is a little section on subsets, 
combinations, and permutations.
Tip
 
■
  There’s quite a bit of math in this chapter. If that’s not your thing, you might want to skim it for now and come 
back to it as needed while reading the rest of the book. (Several of the ideas in this chapter will probably make the rest of 
the book easier to understand, though.)
The Skinny on Sums
In Chapter 2, I explained that when two loops are nested and the complexity of the inner one varies from iteration to 
iteration of the outer one, you need to start summing. In fact, sums crop up all over the place in algorithmics, so you 
might as well get used to thinking about them. Let’s start with the basic notation.

---

ChapTer 3 
■
 CounTIng 101
44
More Greek
In Python, you might write the following:
 
x*sum(S) == sum(x*y for y in S)
 
With mathematical notation, you’d write this:
x
y
xy
y S
y S
×
Î
Î
å å
=
Can you see why this equation is true? This capital sigma can seem a bit intimidating if you haven’t worked with 
it before. It is, however, no scarier than the sum function in Python; the syntax is just a bit different. The sigma itself 
indicates that we’re doing a sum, and we place information about what to sum above, below, and to the right of it. 
What we place to the right (in the previous example, y and xy) are the values to sum, while we put a description of 
which items to iterate over below the sigma.
Instead of just iterating over objects in a set (or other collection), we can supply limits to the sum, like with range 
(except that both limits are inclusive). The general expression “sum f (i) for i = m to n” is written like this:
f i
i m
n
( )
=
å
The Python equivalent would be as follows:
 
sum(f(i) for i in range(m, n+1))
 
It might be even easier for many programmers to think of these sums as a mathematical way of writing loops:
 
s = 0
for i in range(m, n+1):
    s += f(i)
 
The more compact mathematical notation has the advantage of giving us a better overview of what’s going on.
Working with Sums
The sample equation in the previous section, where the factor x was moved inside the sum, is just one of several useful 
“manipulation rules” you’re allowed to use when working with sums. Here’s a summary of two of the most important 
ones (for our purposes):