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 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)^{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{aligned}{\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{aligned}}$

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}}$ 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

$\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:

$\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,

${\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.

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 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, through a change of variables in the summation, we can write this as:

$\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:

$\sum _{k}{\binom {n}{k}}=2^{n}$

$\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

${\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