AOCP/Binomial Coefficients

Knuth Volume 1: Fundamental Algorithms

Chapter 1: Basic Concepts: Binomial Coefficients

Definitions

The combinations of n objects taken k at a time are the possible choices of k different elements from a collection of n items.

The number of combinations is described by the binomial coefficient $ \binom{n}{k} $

$ \binom{n}{k} = \dfrac{n!}{k! (n-k)!} $

Computing these numbers in a table leads to Pascal's Triangle.

We can define the binomial coefficient for the case when n is not an integer. Define:

$ \binom{r}{k} = \dfrac{r(r-1)(\dots)(r-k+1)}{k(k-1)\dots(1)} = \prod_{1 \leq j \leq k} \left( \frac{r+1-j}{j} \right) \qquad k \in \mathbb{Z}, k \geq 0 $

$ \binom{r}{k} = 0 \qquad k < 0 $

Binomial coefficients satisfy thousands of identities; these can be classified as follows:

• Representation by factorials
• Symmetry condition
• Moving in and out of brackets
• Addition formulas
• Summation formulas
• Binomial theorem
• negating upper index
• Sums of products

Representation by Factorials

$ \binom{n}{k} = \dfrac{n!}{k! (n-k)!} $

Holds for integers n and k >= 0

Symmetry Condition

$ \binom{n}{k} = \binom{n}{n-k} $

Holds for all integers k.

Moving In and Out of Brackets

$ \binom{r}{k} = \frac{r}{k} \binom{r-1}{k-1} \qquad k \neq 0 $

This is useful for combining binomial coefficient with other parts of an expression.

By elementary transformation, we have:

$ k \binom{r}{k} = r \binom{r-1}{k-1} $

valid for all integers k, and

$ \frac{1}{r} \binom{r}{k} = \frac{1}{k} \binom{r-1}{k-1} $

valid when not dividing by zero.

Similarly:

$ \binom{r}{k} = \dfrac{r}{r-k} \binom{r-1}{k} $

for k != r.

Addition formulas

To add binomials, we have

$ \binom{r}{k} = \binom{r-1}{k} + \binom{r-1}{k-1} $

for integer k. This is equivalent to summing the two entries in Pascal's triangle above to the left and above to the right.

Alternatively, we have:

$ r \binom{r-1}{k} + r \binom{r-1}{k-1} = (r-k) \binom{r}{k} + k \binom{r}{k} = r \binom{r}{k} $

This is useful for proofs by induction on r, when r is an integer.

Summation formulas

Two important summation formulas. The first comes from applying the summation identity given above, repeatedly:

$ \sum_{0 \leq k \leq n} \binom{r+k}{k} = \binom{r}{0} + \binom{r+1}{1} + \dots + \binom{r+n}{n} = \binom{r+n+1}{n} \qquad n \geq 0 $

We also have:

$ \sum_{0 \leq k \leq m} \binom{k}{m} = \binom{0}{m} + \binom{1}{m} + \dots + \binom{n}{m} = \binom{n+1}{m+1} $

Valid for integer m and integer n, both >= 0.

Deriving summation identities

Suppose we wish to compute the sum $ 1^2 + 2^2 + \dots + n^2 $.

Solve this by recognizing that $ k^2 = 2 \binom{k}{2} + \binom{k}{1} $

Therefore, we have:

$ \sum_{0 \leq k \leq n} k^2 = \sum_{0 \leq k \leq n} \left( 2 \binom{k}{2} + \binom{k}{1} \right) = 2 \binom{n+1}{3} + \binom{n+1}{2} $

This simplifies back to polynomial notation as:

$ \sum_{0 \leq k \leq n} k^2 = 2 \dfrac{(n+1)n(n-1)}{6} + \dfrac{(n+1)n}{2} $

which becomes:

$ \sum_{0 \leq k \leq n} k^2 = \dfrac{1}{3} n (n + \dfrac{1}{2})(n+1) $

Any polynomial of the form $ a_0 + a_1 k + a_2 k^2 + \dots + a_m k^m $ can be expressed as $ b_0 \binom{k}{0} + b_1 \binom{k}{1} + \dots + b_m \binom{k}{m} $.

Binomial Theorem

The binomial theorem is extremely useful:

$ \left( x + y \right)^n = \sum_{0 \leq k \leq r} \binom{r}{k} x^k y^{r-k} $

for integer r >= 0.

Note that we can also express

$ \sum_{0 \leq k \leq r} = \sum_{k} $

since if k < 0 or k > r the expressions go to zero.

The caes of y = 1 is:

$ \sum_k \binom{r}{k} x^k = \left( 1 + x \right)^r $

for integer r >= 0 or |x| < 0

Isaac Newton discovered the binomial theorem in 1676. First attempted proof was by Euler in 1774. Gauss gave first actual proof in 1812.

Abel found a generalization of the formula:

$ (x+y)^r = \sum_k \binom{r}{k} x (x-kz)^{k-1} (y+kz)^{r-k} $

for integer r>=0, x != 0

Negating Upper Index

$ \binom{-r}{k} = (-1)^k \binom{r+k-1}{k} \qquad k \in \mathbb{Z} $

This can be used, for example, to show:

$ \sum_{k \leq n} \binom{r}{k} (-1)^k = \binom{r}{0} - \binom{r}{1} + \dots + (-1)^n \binom{r}{n} $

and therefore, for integer n >= 0, we have

$ \sum_{k \leq n} \binom{r}{k} (-1)^k = (-1)^n \binom{r-1}{n} $

Prove this by showing:

$ \sum_{k \leq n} \binom{r}{k} (-1)^k = \sum_{k \leq n} \binom{-r+k-1}{k} = \binom{-r+n}{n} = (-1)^n \binom{r-1}{n} $

further, when r is an integer, we can also write:

$ \binom{n}{m} = (-1)^{n-m} \binom{-(m+1)}{n-m} \qquad m, n \in \mathbb{Z}, n \geq 0 $

Simplifying Products

$ \binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k} $

This holds for integer m and integer k.

If we know $ r \geq m, 0 \leq k \leq m $, then the following identity holds:

$ \begin{align} \binom{r}{m}{m}{k} &=& \dfrac{r! m!}{ m! (r-m)! k! (m-k)! } \\ &=& \dfrac{r!(r-k)!}{k!(r-k)! (m-k)! (r-m)!} \end{align} $

all of which leads to:

$ \binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k} $

Sums of Products

If we need to sum over the products of binomial coefficients, we have several identities, of which the most important is:

$ \sum_k \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n} $

This should be memorized. Interpret the right hand side as the number of ways to select n people from among r men and s women.

Each term on the left side is a number of ways to choose k of the men and n-k of the women.

Vandermonde's convolution - published by Vandermonde in 1772.

Further identities:

$ \sum_{k} \binom{r}{k} \binom{s}{n+k} = \binom{r+s}{r+n} \qquad r, n \in \mathbb{Z}, r \neq 0 $

$ \sum_{k} \binom{r}{k} \binom{s+k}{n} (-1)^k = (-1)^r \binom{s}{n-r} \qquad n, r \in \mathbb{Z}, r \geq 0 $

Stirling Numbers

Can convert between polynomial expressed in powers of k to a polynomial expressed in binomial coefficients. This allows us to transform from powers to binomial coefficients.

Stirling numbers of the first kind - convert from binomial coefficients to powers

Stirling numbers of the second kind - convert from powers to binomial coefficients