254 OTHER ALGORITHMIC TECHNIQUES

This example is not very complicated, and you should see that it would even

be possible to accomplish this with just two variables for the last two values

instead of an entire array.

A more involved example is the calculation of the binomial coefficient,

which tells us the number of different ways that we could pick k objects from a

set of N objects if the order we pick them doesn’t matter.^5 The binomial coef-

ficient is given by the equation

This equation cannot be calculated directly, as we discussed in the last section,

because the factorial value gets very large very quickly. An alternative and

equivalent formula for the binomial coefficient is

You should easily be able to write a recursive algorithm from this equation,

but it will have the same recalculation problem that we saw with the Fibonacci

numbers. Instead, we can use this equation to begin calculating at the bottom

and moving up until we reach the answer we are looking for. This process will

be familiar to anyone who has written out the values in Pascal’s Triangle.

For our algorithm, we will need an array called BiCoeff with N + 1 rows

andk + 1 columns that we will number starting at zero. In this array, location

BiCoeff[i, j] stores the value of

We initialize locations BiCoeff[0, 0],BiCoeff[1, 0], and BiCoeff[1,

1] all to a value of 1, and then loop through values until we reach

(^5) The formula given in Section 9.2 under “Probabilistic Counting” is different because
in that application the order mattered.
N
k
N!
= k------------------------!()Nk– !-
N
k
N– 1
k– 1
N– 1
k

• 
  

  0 <<kN
  1 k= 0
   1 kN=
  
  
  
  
  
  

  
  

  i
  j