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
Do'stlaringiz bilan baham: 
