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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{n}{k}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{n}{k} = \binom{n}{n-k} }

Holds for all integers k.

Moving In and Out of Brackets

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k \binom{r}{k} = r \binom{r-1}{k-1} }

valid for all integers k, and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{r} \binom{r}{k} = \frac{1}{k} \binom{r-1}{k-1} }

valid when not dividing by zero.

Similarly:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{r}{k} = \dfrac{r}{r-k} \binom{r-1}{k} }

for k != r.

Addition formulas

To add binomials, we have

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1^2 + 2^2 + \dots + n^2} .

Solve this by recognizing that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k^2 = 2 \binom{k}{2} + \binom{k}{1}}

Therefore, we have:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{0 \leq k \leq n} k^2 = 2 \dfrac{(n+1)n(n-1)}{6} + \dfrac{(n+1)n}{2} }

which becomes:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{0 \leq k \leq n} k^2 = \dfrac{1}{3} n (n + \dfrac{1}{2})(n+1) }

Any polynomial of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_0 + a_1 k + a_2 k^2 + \dots + a_m k^m} can be expressed as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b_0 \binom{k}{0} + b_1 \binom{k}{1} + \dots + b_m \binom{k}{m}} .

Binomial Theorem

The binomial theorem is extremely useful:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k \leq n} \binom{r}{k} (-1)^k = (-1)^n \binom{r-1}{n} }

Prove this by showing:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{n}{m} = (-1)^{n-m} \binom{-(m+1)}{n-m} \qquad m, n \in \mathbb{Z}, n \geq 0 }

Simplifying Products

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r \geq m, 0 \leq k \leq m} , then the following identity holds:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k} \binom{r}{k} \binom{s}{n+k} = \binom{r+s}{r+n} \qquad r, n \in \mathbb{Z}, r \neq 0 }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_k \binom{n}{k} = 2^n }

Furthermore, we know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{n}{n-1}} can only be 2 (if we have 10 slots and 9 items, there are only 2 configurations possible). Thus, if we see sums that are missing one term, such as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^{n-1} \binom{n}{k} }

we can use the properties of series, and the numerical value of the last coefficient, to write:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^{n-1} \binom{n}{k} = \sum_{k=1}^{n} \binom{n}{k} - 2 = 2^n - 2 = 2(2^n-1) }

See the #Sum of Sequence problem below, where we use this fact to address the alternating signs part of the question.

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,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 is odd, then we know the sequence must have an odd number of odd terms.

Summing the sequence:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^{\frac{n-1}{2}} \binom{n}{k} }

Now, through a change of variables in the summation, we can write this as:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^{n-1} \binom{n}{\frac{k}{2}} = \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_k \binom{n}{k} = 2^n }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^{n-1} \binom{n}{k} = \sum_{k=1}^{n} \binom{n}{k} - 2 = 2^n - 2 = 2(2^n-1) }

to write the entire sequence as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{2} \left( \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n-1} \right) = \dfrac{1}{2} (2^n - 2) = 2^{n-1} - 1 }

This is indeed an odd number, so the statement is proven.

Rleated

Cards - probabilities of outcomes for playing cards

AOCP/Multinomial Coefficients

AOCP/Multisets