Binomial Coefficients Revisited

The binomial coefficient \(\binom{n}{k}\) was originally defined in terms of the factorial notation, and with our recursive definitions of the factorial notation, we also have a complete and legally-correct definition of binomial coefficients. The following recursive formula provides an efficient computational scheme.

Let \(n\) and \(k\) be integers with \(0\le k\le n\). If \(k=0\) or \(k=n\), set \(\binom{n}{k}=1\). If \(0\lt k\lt n\), set \[\begin{aligned}\end{aligned}\] This recursion has a natural combinatorial interpretation. Both sides count the number of \(k\)-element subsets of \(\{1,2,\dots,n\}\), with the right-hand side first grouping them into those which contain the element\(n\) and then those which don't. The traditional form of displaying this recursion is shown in . This pattern is called Pascal's triangle. Other than the \(1\)s at the ends of each row, an entry of the triangle is determined by adding the entry to the left and the entry to the right in the row above.

Xing was intrigued by the fact that he now had two fundamentally different ways to calculate binomial coefficients. One way is to write \(\binom{n}{m}=P(n,m)/m!\) and just carry out the specified arithmetic. The second way is to use the recursion of Pascal's triangle, so that you are just performing additions. So he experimented by writing a computer program to calculate binomial coefficients, using a library that treats big integers as strings. Which of the two ways do you think proved to be faster when \(n\) say was between \(1800\) and \(2000\) and \(m\) was around \(800\)?