Binomial coefficients via integer division

Daniel Lemire explains how to compute binomial coefficients using only integer multiplications. The binomial coefficient \(n \choose k\) is defined as

\[ {n \choose k} = \frac{n!}{k! (n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{1\cdot 2\cdots k}. \]

Daniel’s strategy of computing binomial coefficients consists of two steps.

First, he expresses the binomial coefficient as an iterative computation

\[ \begin{align} a_1 &= n - k + 1 \\ a_z &= \frac{a_{z-1} (n-k+z)}{z}\label{ii}\hspace{2em}(z=2,\ldots,k)\\ {n \choose k} &= a_k\label{iii} \end{align} \]

Then he replaces integer division in \(\eqref{ii}\) with integer multiplication, following the Granlund-Montgomery-Warren algorithm.

What wasn’t immediately obvious to me is why we can treat the division in \(\eqref{ii}\) as integer division in the first place. Indeed, the equality \({n \choose k} = a_k\) obviously holds if we treat division in \(\eqref{ii}\) as exact rational division. But what happens if we replace it with integer division, throwing away the fractional part at each iteration? Then we might potentially arrive at the wrong answer at the end.

However, it turns out that there never is a fractional part in \(\eqref{ii}\): all \(a_k\) are integers even if we interpret the division as a proper (not truncated or rounded) division of rational numbers.

To see that, expand the definition of \(a_z\):

\[ \begin{equation} \begin{aligned} a_z &= \frac{a_{z-1} (n-k+z)}{z}\\ &= \frac{a_{z-2} (n-k+z)(n-k+z-1)}{z(z-1)}\\ &= \ldots \\ &= \frac{(n-k+z)(n-k+z-1)\cdots (n-k+1)}{z(z-1)\cdots 1} \\ &= {n-k+z \choose z}. \end{aligned}\label{expanded} \end{equation} \]

It turns out that the thing computed at each step of Daniel’s iterative algorithm is itself a binomial coefficient, and is therefore an integer. Notice how \(\eqref{expanded}\) reduces to \(\eqref{iii}\) if we let \(z = k\).

Equation \(\eqref{ii}\) can also be written as

\[ {n-k+z \choose z} = {n-k+z-1 \choose z-1}\cdot \frac{n-k+z}z, \]

which is an instance of the general identity

\[ {p \choose q} = {p-1\choose q-1}\cdot \frac{p}{q}. \]