Source code online books for professionals by professionals

c
f i
c f i
i m
n
i m
n
×
=
×
å
å
( )
( )
=
=
Multiplicative constants can be moved in or out of sums. That’s also what the initial example in the previous 
section illustrated. This is the same rule of distributivity that you’ve seen in simpler sums many times: c(f (m) + ... + 
f (n)) = cf (m) + ... + cf (n).
f i
g i
f i
g i
i m
n
i m
n
i m
n
( )
( )
( ( )
( ))
=
=
=
å
å
å
+
=
+

---

ChapTer 3 
■
 CounTIng 101
45
Instead of adding two sums, you can sum their added contents. This just means that if you’re going to sum  
up a bunch of stuff, it doesn’t matter how you do it; that is,
 
sum(f(i) for i in S) + sum(g(i) for i in S)
 
is exactly the same as sum(f(i) + g(i) for i in S).
1
 This is just an instance of associativity. If you want to subtract 
two sums, you can use the same trick. If you want, you can pretend you’re moving the constant factor –1 into the 
second sum.
A Tale of Two Tournaments
There are plenty of sums that you might find useful in your work, and a good mathematics reference will probably give 
you the solution to most of them. There are, however, two sums, or combinatorial problems, that cover the majority of 
the cases you’ll meet in this book—or, indeed, most basic algorithm work.
I’ve been explaining these two ideas repeatedly over the years, using many different examples and metaphors, 
but I think one rather memorable (and I hope understandable) way of presenting them is as two forms of 
tournaments.
Note
 
■
  There is, actually, a technical meaning of the word tournament in graph theory (a complete graph, where each 
edge is assigned a direction). That’s not what I’m talking about here, although the concepts are related.
There are many types of tournaments, but let’s consider two quite common ones, with rather catchy names. 
These are the round-robin tournament and the knockout tournament.
In a round-robin tournament (or, specifically, a single round-robin tournament), each contestant meets each of 
the others in turn. The question then becomes, how many matches or fixtures do we need, if we have, for example, 
n knights jousting? (Substitute your favorite competitive activity here, if you want.) In a knockout tournament, the 
competitors are arranged in pairs, and only the winner from each pair goes on to the next round. Here there are more 
questions to ask: For n knights, how many rounds do we need, and how many matches will there be, in total?
Shaking Hands
The round-robin tournament problem is exactly equivalent to another well-known puzzler: If you have n algorists 
meeting at a conference and they all shake hands, how many handshakes do you get? Or, equivalently, how many 
edges are there in a complete graph with n nodes (see Figure 
3-1
)? It’s the same count you get in any kind of “all 
against all” situations. For example, if you have n locations on a map and want to find the two that are closest to each 
other, the simple (brute-force) approach would be to compare all points with all others. To find the running time to 
this algorithm, you need to solve the round-robin problem. (A more efficient solution to this closest pair problem is 
presented in Chapter 6.)
1
As long as the functions don’t have any side effects, that is, but behave like mathematical functions.

---

ChapTer 3 
■
 CounTIng 101
46
You may very well have surmised that there will be a quadratic number of matches. “All against all” sounds 
an awful lot like “all times all,” or n
2
. Although it is true that the result is quadratic, the exact form of n
2
 isn’t entirely 
correct. Think about it—for one thing, only a knight with a death wish would ever joust against himself (or herself). 
And if Sir Galahad has crossed swords with Sir Lancelot, there is no need for Sir Lancelot to return the favor, because 
they surely have both fought each other, so a single match will do. A simple “n times n” solution ignores both of these 
factors, assuming that each knight gets a separate match against each of the knights (including themselves). The fix is 
simple: Let each knight get a match against all the others, yielding n(n–1), and then, because we now have counted 
each match twice (once for each participating knight), we divide by two, getting the final answer, n(n–1)/2, which is 
indeed Q(n
2
).
Now we’ve counted these matches (or handshakes or map point comparisons) in one relatively straightforward 
way—and the answer may have seemed obvious. Well, what lies ahead may not exactly be rocket science either, but rest 
assured, there is a point to all of this . . . for now we count them all in a different way, which must yield the same result.
This other way of counting is this: The first knight jousts with n–1 others. Among the remaining, the second 
knight jousts with n–2. This continues down to the next to last, who fights the last match, against the last knight (who 
then fights zero matches against the zero remaining knights). This gives us the sum n–1 + n–2 + ... + 1 + 0, or sum(i for 
i in range(n)). We’ve counted each match only once, so the sum must yield the same count as before:
i
n n
i
n 1
= 0
2
-
å
=
-
(
)
1
I could certainly just have given you that equation up front. I hope the extra packaging makes it slightly more 
meaningful to you. Feel free to come up with other ways of explaining this equation (or the others throughout this 
book), of course. For example, the insight often attributed to Gauss, in the story that opened this chapter, is that the 
sum of 1 through 100 can be calculated “from the outside,” pairing 1 with 100, 2 with 99, and so forth, yielding 50 pairs 
that all sum to 101. If you generalize this to the case of summing from 0 to n–1, you get the same formula as before. 
And can you see how all this relates to the lower-left half, below the diagonal, of an adjacency matrix?
Tip
 
■
  an arithmetic series is a sum where the difference between any two consecutive numbers is a constant.  
assuming this constant is positive, the sum will always be quadratic. In fact, the sum of i
k
, where i = 1. . . n, for some  
positive constant k, will always be 
Q(n
k+1
). The handshake sum is just a special case.