- 1 Knuth Volume 1: Fundamental Algorithms
- 1.1 Chapter 1: Basic Concepts: Binomial Coefficients
- 1.1.1 Definitions
- 1.1.2 Representation by Factorials
- 1.1.3 Symmetry Condition
- 1.1.4 Moving In and Out of Brackets
- 1.1.5 Addition formulas
- 1.1.6 Summation formulas
- 1.1.7 Deriving summation identities
- 1.1.8 Binomial Theorem
- 1.1.9 Negating Upper Index
- 1.1.10 Simplifying Products
- 1.1.11 Sums of Products
- 1.1.12 Stirling Numbers
- 1.1 Chapter 1: Basic Concepts: Binomial Coefficients
- 2 Example Problems
- 3 Rleated
- 4 Flags
Knuth Volume 1: Fundamental Algorithms
Chapter 1: Basic Concepts: Binomial Coefficients
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
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:
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
Holds for integers n and k >= 0
Holds for all integers k.
Moving In and Out of Brackets
This is useful for combining binomial coefficient with other parts of an expression.
By elementary transformation, we have:
valid for all integers k, and
valid when not dividing by zero.
for k != r.
To add binomials, we have
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:
This is useful for proofs by induction on r, when r is an integer.
Two important summation formulas. The first comes from applying the summation identity given above, repeatedly:
We also have:
Valid for integer m and integer n, both >= 0.
Deriving summation identities
Suppose we wish to compute the sum .
Solve this by recognizing that
Therefore, we have:
This simplifies back to polynomial notation as:
Any polynomial of the form can be expressed as .
The binomial theorem is extremely useful:
for integer r >= 0.
Note that we can also express
since if k < 0 or k > r the expressions go to zero.
The caes of y = 1 is:
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:
for integer r>=0, x != 0
Negating Upper Index
This can be used, for example, to show:
and therefore, for integer n >= 0, we have
Prove this by showing:
further, when r is an integer, we can also write:
This holds for integer m and integer k.
If we know , then the following identity holds:
all of which leads to:
Sums of Products
If we need to sum over the products of binomial coefficients, we have several identities, of which the most important is:
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.
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
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 of the numbers in each row of Pascal's triangle? What is the sum of these numbers with alternating signs, ?
This one is pretty easy. Summing up the terms of each row of Pascal's Triangle gives powers of 2:
Furthermore, we know that 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
we can use the properties of series, and the numerical value of the last coefficient, to write:
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,
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:
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
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:
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:
Now, through a change of variables in the summation, we can write this as:
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:
to write the entire sequence as
This is indeed an odd number, so the statement is proven.
Cards - probabilities of outcomes for playing cards
The Art of Computer Programmingnotes from reading Donald Knuth's Art of Computer Programming
Part of the 2017 CS Study Plan.
Volume 2: Seminumerical Algorithms
Volume 3: Sorting and Searching
Flags · Template:AOCPFlag · e
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e