## Computing the Binomial Coefficient

2014.04.22Looking at the recursive definition looks promising.

It’s easy to code an almost direct version of it.

def binomial_coefficient(n, k):

return _bc(n, min(k, n-k))

@functools.lru_cache(maxsize=None)

def _bc(n, k):

if k in (0, n):

return 1

return _bc(n-1, k) + _bc(n-1, k-1)

As an example this image shows all the values that are called to calculate `binomial_coefficient(7, 4)`

.

There’s two nontrivial things in this implementation that isn’t in the original definition. First I’m taking advantage of the symmetry:

So this is why I start computing the binomial coefficient with the second argument being the minimum among k and n-k.

The second thing is that I made `_bc`

a memoized function. For this case python3’s `functools.lru_cache`

decorator works great.

Want more buzzwords? Of course you do. This recursive implementation with the use of memoization characterizes dynamic programming with a top-down approach.

We can push a little further with the symmetry if we just keep using `min(k, n-k)`

at every step.

def binomial_coefficient(n, k):

min_k = min(k, n-k)

if min_k == 0:

return 1

return (binomial_coefficient(n-1, min_k) +

binomial_coefficient(n-1, min_k-1))

Then we won’t need to ever check if k is n. Also no need for a separate `_bc`

function, the idea of having it just to wrap that `min`

was kind of silly anyway.

But hey, we can do considerably better if we change our approach a bit. The problem here is that our recursive formula gives us only a partial order. It’d be nice if we had a total order so that we can have an expression in tail position.

Conveniently the binomial coefficient delivers with this identity:

Now let’s revise our definition:

The best part is that with this we’ll be able to eliminate a lot of calculations.

Notice that this has nothing to do with top-down versus bottom-up approach. The important thing is that now we can define a tail-recursive function. Or in other words, because we’re coding in python, just a simple accumulator loop will do.

min_k = min(k, n-k)

acc = 1

for i in range(1, min_k+1):

acc = (acc*(n-i+1))//i

return acc

With a little attention to keep the accumulator as an integer, we have in essence implemented the following:

Which is the way I like best to define the binomial coefficient.