Binomial coefficient calculator

How it works

The binomial coefficient $\binom{n}{k}$ ("$n$ choose $k$") counts the subsets of size $k$ of a set of $n$ elements, and it is the coefficient of $x^k$ in $(1 + x)^n$. The product formula $\binom{n}{k} = \frac{n (n-1) \cdots (n-k+1)}{k!}$ needs only $k$ factors, and by the symmetry $\binom{n}{k} = \binom{n}{n-k}$ the smaller of $k$ and $n - k$ is enough. The result is a whole number, so every factor of $k!$ cancels against the numerator.

Pascal’s triangle builds all of them by addition: each entry is the sum of the two above it, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$, because a subset of size $k$ either contains the last element or it does not.

Modulo a prime $p$, Lucas’ theorem reduces a huge binomial to small ones: write $n$ and $k$ in base $p$, then $\binom{n}{k} \equiv \prod_i \binom{n_i}{k_i} \pmod p$. For example $\binom{10}{3} = 120 \equiv 1 \pmod 7$, and indeed $10 = 13_7$, $3 = 03_7$, $\binom{1}{0} \binom{3}{3} = 1$. In particular $p$ divides $\binom{n}{k}$ exactly when some digit of $k$ is larger than the digit of $n$ in the same place.