Latest revision as of 04:35, 20 June 2026

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 n} \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)^r = \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 case of y = 1 is:

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

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

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} \binom{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

Example Problems

Some example problems involving binomial coefficients, to help illustrate.

Knuth AOCP Section 1.2.5 Problem 36

Problem 36. (M10 difficulty) What is the sum $\sum_k \binom{n}{k}$ of the numbers in each row of Pascal's triangle? What is the sum of these numbers with alternating signs, $\sum_k \binom{n}{k} (-1)^k$ ?

Solution

This one is pretty easy. Summing up the terms of each row of Pascal's Triangle gives powers of 2:

$\sum_k \binom{n}{k} = 2^n$

Furthermore, we know that $\binom{n}{n} = 1$ and $\binom{n}{0} = 1$ . Thus, if we see sums that are missing these two terms, such as

$\sum_{k=1}^{n-1} \binom{n}{k}$

we can use the properties of series to write:

$\sum_{k=1}^{n-1} \binom{n}{k} = \sum_{k=0}^{n} \binom{n}{k} - \binom{n}{0} - \binom{n}{n} = 2^n - 1 - 1 = 2^n - 2 = 2(2^{n-1} - 1)$

For the alternating signs part, we note that $\sum_k \binom{n}{k} (-1)^k = (1-1)^n = 0^n = 0$ for n > 0, or 1 for n = 0.

See the #Sum of Sequence problem below.

The Zeta Family

Mr. and Mrs. Zeta wish to name their baby Zeta such that the baby's monogram (First Middle Last initials) has no repeated initials and is in alphabetical order.

How many such monograms are there?

Solution using binomial coefficient

We can re-pose this problem as selecting two unique letters, without regard to order, from a set of 25 possible letters: if we happen to select BAZ, this is equivalent to ABZ, which is the monogram that will actually be used. If we are selecting 2 things from a set of 25 possibilities, this is described the binomial coefficient,

$\binom{n}{k} = \binom{25}{2} = 300$

Note that when k=2, we end up with a special interpretation of this binomial coefficient. If we actually write out the definition of the binomial coefficient, we get:

$\binom{25}{2} = \dfrac{25!}{23! 2!} = \dfrac{25 \times 24}{2} = \dfrac{n(n-1)}{2}$

This is the sum of all of the integers from 1 to n-1 (with n=25).

This solution to the problem can be interpreted as follows: for our first choice of letter, we have 25 possible choices. For our choice of second letter, it depends on our first choice. If we choose A, we have 24 remaining choices. If we choose B, we have 23 remaining choices. If we choose C, we have 22 remaining choices. And so on.

If we sum up all of our possible choices, we get

$24 + 23 + 22 + \dots + 1 = \dfrac{24 (24+1)}{2} = \dfrac{600}{2} = 300$

300 possible choices of monogram.

Sum of Sequence

Let n be an odd integer > 1. Then prove that the following sequence has an odd number of odd numbers:

$\binom{n}{1}, \binom{n}{2}, \dots, \binom{n}{ \frac{n-1}{2} }$

Solution using binomial coefficient properties

The solution given here uses a few binomial coefficient properties not covered by Knuth, plus a few that Knuth covered in the exercise.

We use a trick to show if the sequence has an odd number of odd terms:

Sum up all terms in the sequence. If the entire sequence sum is odd, then we know the sequence must have an odd number of odd terms.

Summing the sequence:

$\sum_{k=1}^{\frac{n-1}{2}} \binom{n}{k}$

Now, by the symmetry of binomial coefficients $\binom{n}{k} = \binom{n}{n-k}$ , for odd n the terms from k=1 to $\frac{n-1}{2}$ pair exactly with terms from $\frac{n+1}{2}$ to n-1. Therefore the sum of the first half equals half the sum from k=1 to n-1:

$\sum_{k=1}^{\frac{n-1}{2}} \binom{n}{k} = \dfrac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k}$

This is now nearly identical to the problem posed by Knuth in Section 1.2.6 Problem 36, except for the change of index. We can now use the following facts: