choose the Haskell way
Binomial coefficients are a surprisingly interesting subject of study, so interesting in fact that Sherlock Holmes’ arch-enemy Professor Moriarty began his career with a paper on them. Incidentally, this fictional Treatise on the Binomial Theorem has a longer Wikipedia page than any real work of mathematics I’ll ever write. But I digress. Today we’re going to look at a novel way to calculate binomial coefficients in Haskell, the programming language that is basically math.
The binomial coefficients draw their name from the following “Binomial formula”:
Here is the coefficient on the th power of in the expansion of the left-hand side. However, a “purer” definition of is the combinatorial one: the number of ways to choose objects from a set of . From this definition one can see why these numbers show up as the coefficients above. We can also use this point of view to understand some other binomial sum identities – for example, for a finite set with elements, the cardinality of the power set (the set of all subsets of ) is . This gives a way to understand why
which we can of course derive from the binomial formula above but whatever. For each with , there are ways to specify a distinct set of elements, i.e. a subset of size . So the number of subsets of any size is just the sum of these numbers over all possible , and there are total subsets.
Another nice identity is this one:
Combinatorially we can understand it like so: to count the number of ways to pick elements from a set of elements, pick one of the elements and look at the number of ways to pick the other elements from the remaining elements. There are ways to pick the first element, so that’s ways of picking subsets. But we overcounted – each subset is counted times, one time for each of its elements that we pick first. So after dividing by to fix this, we’ve shown the identity holds.
The identity is so nice because it gives a natural recursive algorithm to compute the coefficients; just keep applying the identity to get
where . And since this is a post about in Haskell, I’m going to turn this into a recursive Haskell function right? Unfortunately someone beat me to it, and they even used more identities than I have, so let’s take a different approach and go back to the Binomial formula. If we can expand the polynomial into a sum, we can just read off the coefficients for each power of . Easy right?
A polynomial only has finitely-many powers of , so we can represent a polynomial such as as a list . In Haskell, we use the typeclass
Num to describe things that we can add, multiply, negate, and so on; polynomials can do these things too, so let’s define a
Num instance for lists of
a is an instance of
Num, representing polynomials with coefficients in
instance Num a => Num [a] where fromInteger n = [fromInteger n] (x:xs) + (y:ys) = (x + y) : (xs + ys) xs +  = xs  + ys = ys (x:xs) * (y:ys) = (x*y) : ([x] * ys + xs * (y:ys)) _ * _ = 
This is missing a few
Num functions, but we won’t need them. We add two polynomials by adding the respective coefficients for each power of , and the rather complicated expression for multiplication can be derived without much work.
So now is our representation for . Exponentiation comes for free since Haskell implements it using repeated squaring. So if we try it out,
[1,1]^2 == [1,2,1], and
[1,1]^4 == [1,4,6,4,1]. Translating these back to math world, and . So now it’s only natural to define by:
choose :: Int -> Int -> Int choose n k = ([1,1]^n) !! k
xs !! k is the th element of
xs. Now we may quickly concoct some quality coefficients:
3 `choose` 2 == 3 10 `choose` 6 == 210 434 `choose` 87 == 4614992264942942144
or just generate an infinite Pascal’s triangle with
map ([1,1]^) [0..].
[ ,[1,1] ,[1,2,1] ,[1,3,3,1] ,[1,4,6,4,1] ,[1,5,10,10,5,1] ,[1,6,15,20,15,6,1] ,[1,7,21,35,35,21,7,1] ,[1,8,28,56,70,56,28,8,1] ,[1,9,36,84,126,126,84,36,9,1] , ...
This is honestly an absurd way to calculate binomial coefficients, but the underlying concept of manipulating polynomials as lists is very cool. We can take this in more directions, such as using infinite streams to represent power series, but perhaps that is a topic for a later post.
Thanks to Ira Kones and Rory Bokser for proofreading this post.
When multiplying out , for each of the clauses we have ways of choosing of the 's to get ↩︎
If you’re wondering how we knew the number of subsets in the first place, note that each subset can be identified with a function , where if and only if , and there are such functions by a simple counting argument. ↩︎
You can disable warnings for this by passing
Let . Then ↩︎
Which is why I like it so much. ↩︎