Strange Formulas for Binomial Coefficients

Published on May 8, 2024

Binomial coefficients have long been an obsession of mine, since my earliest days of studying the integers, when I naively rediscovered Pascal’s triangle through simple counting. These unassuming numbers, often written as $\binom{n}{k}$ , have a surprising depth and elegance that never cease to amaze me.

For those who may be unfamiliar, binomial coefficients are the coefficients of the terms in the expansion of the binomial expression $(x + 1)^n$ . They also represent the number of ways to choose $k$ objects from a set of $n$ objects, making them fundamental to combinatorics and probability theory. The standard formula for calculating binomial coefficients uses factorials:

$\begin{align*} \binom{n}{k} = \frac{n!}{k!(n-k)!} \end{align*}$

In my recent paper, “Polynomial Quotient Rings and Kronecker Substitution for Deriving Combinatorial Identities” (preprint), I explored a new approach for deriving formulas for combinatorial objects such as these. The key idea is to apply Kronecker substitution, a technique for encoding polynomials as integers, to polynomial expansions.

Through this approach, I was able to discover several new formulas for both binomial coefficients $\binom{n}{k}$ and central binomial coefficients $\binom{2n}{n}$ . Included below are some of the most surprising results.

Binomial Coefficients $\binom{n}{k}$ :

$\begin{align*} & \binom{n}{k} = 2^{-n k} \left( \bigl((2^n + 1)^n \bmod 2^{n k + n} \bigr) - \bigl( (2^n + 1)^n \bmod 2^{n k} \bigr) \right) \\ & \binom{n}{k} = \left( \bigl((2^n + 1)^n \bmod 2^{n k + n} \bigr) - \bigl( (2^n + 1)^n \bmod 2^{n k} \bigr) \right) \bmod (2^n-1) \end{align*}$

Central Binomial Coefficients $\binom{2n}{n}$ :

$\begin{align*} & \binom{2n}{n} = \left( (4^n + 1)^{2n} \bmod (4^{n(n+1)} + 1) \right) \bmod (4^n-1) \\ & \binom{2n}{n} = \left( 4^{2n(n+1)^2} \bmod (4^{n(n+2)} - 4^n - 1) \right) \bmod 4^n \end{align*}$