Source code online books for professionals by professionals

Combinations are a close relative of both permutations and subsets. A combination of k elements, drawn from a 
set of n, is sometimes written C(n, k), or, for those of a mathematical bent:
n
k
æ
è
ç
ö
ø
÷
5
Do you see where the –1 in the exponent went? Remember, 2
a+b
 = 2
a
 · 2
b
...

---

ChapTer 3 
■
 CounTIng 101
52
This is also called the binomial coefficient (or sometimes the choose function) and is read “n choose k.” While the 
intuition behind the factorial formula is rather straightforward, how to compute the binomial coefficient isn’t quite as 
obvious.
6
Imagine (once again) you have n people lined up to see a movie, but there are only k places left in the theater. 
How many possible subsets of size k could possibly get in? That’s exactly C(n, k), of course, and the metaphor may do 
some work for us here. We already know that we have n! possible orderings of the entire line. What if we just count all 
these possibilities and let in the first k? The only problem then is that we’ve counted the subsets too many times. A 
certain group of k friends could stand at the head of the line in a lot of the permutations; in fact, we could allow these 
friends to stand in any of their k! possible permutations, and the remainder of the line could stand in any of their 
(n–k)! possible permutations without affecting who’s getting in. Aaaand this gives us the answer!
n
k
n
k n k
æ
è
ç
ö
ø
÷ =
-
!
!(
)!
This formula just counts all possible permutations of the line (n!) and divides by the number of times we count 
each “winning subset,” as explained.
Note
 
■
  a different perspective on calculating the binomial coefficient will be given in Chapter 8, on dynamic  
programming.
Note that we’re selecting a subset of size k here, which means selection without replacement. If we just draw lots 
k times, we might draw the same person more than once, effectively “replacing” them in the pool of candidates. The 
number of possible results then would simply be nk. The fact that C(n, k) counts the number of possible subsets of 
size k and 2
n
 counts the number of possible subsets in total gives us the following beautiful equation:
n
k
n
k
n
æ
è
ç
ö
ø
÷
å
=
=
2
0
And that’s it for these combinatorial objects. It’s time for slightly more mind-bending prospect: solving equations 
that refer to themselves!
Tip
 
■
  For most math, the interactive python interpreter is quite handy as a calculator; the 
math
 module contains 
many useful mathematical functions. For symbolic manipulation like we’ve been doing in this chapter, though, it’s not 
very helpful. There are symbolic math tools for python, though, such as Sage (available from 
http://sagemath.org
). 
If you just need a quick tool for solving a particularly nasty sum or recurrence (see the next section), you might want to 
check out Wolfram alpha (
http://wolframalpha.com
). You just type in the sum or some other math problem, and out 
pops the answer.
6
Another thing that’s not immediately obvious is where the name “binomial coefficient” comes from. You might want to look it up. 
It’s kind of neat.

---

ChapTer 3 
■
 CounTIng 101
53
Recursion and Recurrences
I’m going to assume that you have at least some experience with recursion, although I’ll give you a brief intro in this 
section and even more detail in Chapter 4. If it’s a completely foreign concept to you, it might be a good idea to look it 
up online or in some fundamental programming textbook.
The thing about recursion is that a function—directly or indirectly—calls itself. Here’s a simple example of how to 
recursively sum a sequence:
 
def S(seq, i=0):
    if i == len(seq): return 0
    return S(seq, i+1) + seq[i]
 
Understanding how this function works and figuring out its running time are two closely related tasks. The 
functionality is pretty straightforward: The parameter i indicates where the sum is to start. If it’s beyond the end of 
the sequence (the base case, which prevents infinite recursion), the function simply returns 0. Otherwise, it adds the 
value at position i to the sum of the remaining sequence. We have a constant amount of work in each execution of 
S, excluding the recursive call, and it’s executed once for each item in the sequence, so it’s pretty obvious that the 
running time is linear. Still, let’s look into it:
 
def T(seq, i=0):
    if i == len(seq): return 1
    return T(seq, i+1) + 1
 
This new T function has virtually the same structure as S, but the values it’s working with are different. Instead 
of returning a solution to a subproblem, like S does, it returns the cost of finding that solution. In this case, I’ve just 
counted the number of times the if statement is executed. In a more mathematical setting, you would count any 
relevant operations and use Q(1) instead of 1, for example. Let’s take these two functions out for a spin:
 
>>> seq = range(1,101)
>>> s(seq)
5050
 
What do you know, Gauss was right! Let’s look at the running time:
 
>>> T(seq)
101
 
Looks about right. Here, the size n is 100, so this is n+1. It seems like this should hold in general:
 
>>> for n in range(100):
...     seq = range(n)
...     assert T(seq) == n+1
 
There are no errors, so the hypothesis does seem sort of plausible.
What we’re going to work on now is how to find nonrecursive versions of functions such as T, giving us definite 
running time complexities for recursive algorithms.
Doing It by Hand
To describe the running time of recursive algorithms mathematically, we use recursive equations, called recurrence