## Computing the Binomial Coefficient

2014.04.22

Looking at the recursive definition looks promising. It’s easy to code an almost direct version of it.

import functools

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.

@functools.lru_cache(maxsize=None)
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.

def binomial_coefficient(n, k):
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.