Binomial coefficients and Pascal's triangle

The binomial coefficients \(\binom{n}{k}\) of lesson 3 count subsets, but they turn up in many other places: in the expansion of \((x + y)^n\), in probability, in lattice paths, in the analysis of algorithms and in the circle-region puzzle of lesson 1. They satisfy a remarkable number of identities, and most of those identities have two proofs, an algebraic one that manipulates factorials and a combinatorial one that explains why the identity must be true by counting something in two ways. This lesson develops both styles. Combinatorial proofs are usually shorter and always more illuminating, and learning to find them is one of the main skills of the course.

Pascal's rule

The most important identity is Pascal's rule: for \(1 \le k \le n - 1\),

\[ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}. \]

Combinatorial proof. The left side counts the \(k\)-element subsets of \(\{1, 2, \dots, n\}\). Split them into two kinds according to whether they contain the element \(n\). A subset that contains \(n\) is determined by its other \(k - 1\) elements, chosen from \(\{1, \dots, n - 1\}\): there are \(\binom{n-1}{k-1}\) of these. A subset that does not contain \(n\) is a \(k\)-element subset of \(\{1, \dots, n - 1\}\): there are \(\binom{n-1}{k}\) of these. The two kinds are disjoint and together make up all \(k\)-element subsets, so by the sum rule the counts add.

Algebraic proof. Put the right side over the common denominator \(k!\,(n - k)!\):

\[ \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-1-k)!} = \frac{(n-1)!\,k + (n-1)!\,(n-k)}{k!\,(n-k)!} = \frac{(n-1)!\,n}{k!\,(n-k)!} = \binom{n}{k}. \]

Both proofs are correct. The algebraic one checks; the combinatorial one explains. The combinatorial proof also suggests the strategy for many other identities: pick a special element and split the count according to what happens to it.

Pascal's triangle

Arrange the binomial coefficients in rows, with row \(n\) containing \(\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}\). Each row starts and ends with 1, and by Pascal's rule every other entry is the sum of the two entries above it. The result is Pascal's triangle, named after Blaise Pascal, who wrote a treatise on it in the 1650s, although the triangle was known centuries earlier to mathematicians in India, Persia and China.

The triangle displays many identities at a glance. It is symmetric, because \(\binom{n}{k} = \binom{n}{n-k}\). The entries in each row rise to a maximum in the middle and fall again. The second diagonal, 1, 2, 3, 4, holds the counting numbers; the third, 1, 3, 6, 10, holds the triangular numbers \(\binom{n}{2}\), which count the handshakes of lesson 1. And the lattice-path count of lesson 3 explains the whole triangle: \(\binom{n}{k}\) is the number of shortest routes from the top of the triangle to the \(k\)th entry of row \(n\), moving down-left or down-right at each step, and Pascal's rule says that every route reaches an entry through one of the two entries above it.

The binomial theorem

Expanding \((x + y)^2 = x^2 + 2xy + y^2\) and \((x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\), the coefficients 1, 2, 1 and 1, 3, 3, 1 are rows of Pascal's triangle. This is true for every power. The binomial theorem states that for every non-negative integer \(n\),

\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k}. \]

Combinatorial proof. Write \((x + y)^n\) as a product of \(n\) factors \((x + y)(x + y) \cdots (x + y)\). Multiplying out, each term of the expansion comes from choosing either \(x\) or \(y\) from each factor. A term equals \(x^{n-k}y^k\) exactly when \(y\) is chosen from \(k\) of the factors and \(x\) from the rest. There are \(\binom{n}{k}\) ways to choose which \(k\) factors give \(y\), so the coefficient of \(x^{n-k} y^k\) is \(\binom{n}{k}\). This is why the numbers are called binomial coefficients.

Identities from the binomial theorem

Substituting particular values into the binomial theorem gives identities immediately. With \(x = y = 1\),

\[ \sum_{k=0}^{n} \binom{n}{k} = 2^n, \]

so the entries of row \(n\) add up to \(2^n\). The combinatorial proof is that both sides count all subsets of an \(n\)-element set, the left side sorted by size. With \(x = 1\) and \(y = -1\), for \(n \ge 1\),

\[ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0, \]

so in every row after the first, the entries in even positions and odd positions have equal sums. In words: a non-empty set has as many subsets of even size as of odd size. A combinatorial proof pairs them up: fix one element \(a\), and pair each subset \(S\) with the subset obtained by adding \(a\) if it is missing or removing it if it is present. Each pair has one even-sized and one odd-sized member.

More identities and their proofs

Vandermonde's identity. For non-negative integers \(m\), \(n\) and \(r\),

\[ \binom{m + n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r - k}. \]

Proof: a committee of \(r\) people chosen from \(m\) women and \(n\) men contains some number \(k\) of women and \(r - k\) men. For each \(k\) there are \(\binom{m}{k}\binom{n}{r-k}\) such committees, and summing over \(k\) counts every committee once. A useful special case, with \(m = n = r\), is \(\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}\).

The hockey-stick identity. For \(0 \le r \le n\),

\[ \sum_{j=r}^{n} \binom{j}{r} = \binom{n + 1}{r + 1}. \]

Proof: the right side counts \((r + 1)\)-element subsets of \(\{1, 2, \dots, n + 1\}\). Sort them by their largest element. If the largest element is \(j + 1\), the other \(r\) elements are chosen from \(\{1, \dots, j\}\) in \(\binom{j}{r}\) ways, and \(j\) can be anything from \(r\) to \(n\). In the triangle the identity looks like a hockey stick: a diagonal run of entries adds up to the entry just below and to the side of its end. With \(r = 1\) it gives \(1 + 2 + \cdots + n = \binom{n+1}{2}\), the handshake formula once again.

The circle-region puzzle solved

Lesson 1 claimed that \(n\) points on a circle, joined by all chords with no three meeting inside, cut the disk into \(1 + \binom{n}{2} + \binom{n}{4}\) regions. Now we can prove it. Draw the chords one at a time. Before any are drawn there is 1 region. When a new chord is drawn, it is cut into pieces by the chords it crosses; if it crosses \(c\) earlier chords, it is cut into \(c + 1\) pieces, and each piece divides one region into two. So the new chord adds \(c + 1\) regions.

Adding over all chords, the number of regions is \(1 + (\text{number of chords}) + (\text{number of crossings})\), because each crossing is counted once, when the second of its two chords is drawn. There are \(\binom{n}{2}\) chords, one for each pair of points. Each crossing point is determined by exactly four of the points, the endpoints of the two crossing chords, and any four points on a circle determine exactly one crossing, between the two diagonals of the quadrilateral they form. So there are \(\binom{n}{4}\) crossings, and the formula follows. For \(n = 6\) it gives \(1 + 15 + 15 = 31\).

Binomial coefficients and chance

Toss a fair coin \(n\) times. Each of the \(2^n\) sequences of heads and tails is equally likely, and exactly \(\binom{n}{k}\) of them contain \(k\) heads, one for each choice of the positions of the heads. So the probability of exactly \(k\) heads is \(\binom{n}{k}/2^n\). In 10 tosses, exactly 5 heads has probability \(252/1024 \approx 0.246\): the most likely single outcome, yet it happens less than a quarter of the time. Row 10 of Pascal's triangle, divided by 1024, is the whole distribution, and its bell shape is the first example of the pattern that the central limit theorem of statistics describes. If the coin lands heads with probability \(p\), the binomial theorem gives the same structure: the terms of \((p + (1 - p))^n = 1\) are the probabilities \(\binom{n}{k} p^k (1 - p)^{n-k}\) of exactly \(k\) heads, and they add to 1 as they must.

Probability questions in discrete settings are usually counting questions in disguise. What is the probability that a 5-card hand is a flush? Divide the number of flushes from lesson 3 by \(\binom{52}{5}\). What is the probability that a random 8-bit string has more 1s than 0s? Add \(\binom{8}{k}\) for \(k = 5, \dots, 8\), giving \(56 + 28 + 8 + 1 = 93\), and divide by 256 to get about 0.363. By symmetry the probability of more 0s is the same, and the remaining \(70/256\) is the chance of a tie.

Isaac Newton found around 1665 that the binomial theorem extends to exponents that are not whole numbers, provided the series is allowed to go on forever: \((1 + x)^{1/2} = 1 + \tfrac12 x - \tfrac18 x^2 + \tfrac1{16} x^3 - \cdots\) for \(|x| < 1\), with coefficients given by the same falling-product formula \(\alpha(\alpha - 1)\cdots(\alpha - k + 1)/k!\). With \(\alpha = -n\) a negative integer, the coefficients turn out to count combinations with repetition, the stars and bars of lesson 3. This is the doorway to generating functions, the main tool of MATH-460.

How big are binomial coefficients?

The largest entry in row \(n\) is the central one, \(\binom{n}{\lfloor n/2 \rfloor}\). Since the \(n + 1\) entries of the row sum to \(2^n\), the central entry is at least \(2^n / (n + 1)\) and at most \(2^n\). A finer estimate, which follows from Stirling's approximation to \(n!\), is \(\binom{2n}{n} \approx 4^n / \sqrt{\pi n}\). So central binomial coefficients grow almost as fast as powers of 4, which matters in computer science: an algorithm that tries every half-size subset of \(n\) items is doing exponential work.

The code below prints the start of Pascal's triangle, checks the identities of this lesson numerically and compares central binomial coefficients with the estimate. It also prints the triangle with each entry replaced by its remainder on division by 2. The odd entries form a famous fractal, the Sierpinski triangle, a first glimpse of the modular arithmetic of lesson 11.

from math import comb, pi, sqrt

for n in range(8):
    row = [comb(n, k) for k in range(n + 1)]
    print(" " * (3 * (7 - n)) + "".join(f"{x:6d}" for x in row))

n = 10
print("row sum:", sum(comb(n, k) for k in range(n + 1)), "= 2^10 =", 2 ** n)
print("alternating sum:", sum((-1) ** k * comb(n, k) for k in range(n + 1)))
m, r = 7, 5
print("Vandermonde:", comb(m + n, r), "=", sum(comb(m, k) * comb(n, r - k) for k in range(r + 1)))
print("hockey stick:", sum(comb(j, 3) for j in range(3, 11)), "=", comb(11, 4))
for n in (10, 20, 40):
    print(f"C({2*n},{n}) = {comb(2*n, n)}, estimate {4**n / sqrt(pi*n):.4g}")

print()
for n in range(16):
    print(" " * (15 - n) + " ".join("#" if comb(n, k) % 2 else "." for k in range(n + 1)))

                          1
                       1     1
                    1     2     1
                 1     3     3     1
              1     4     6     4     1
           1     5    10    10     5     1
        1     6    15    20    15     6     1
     1     7    21    35    35    21     7     1
row sum: 1024 = 2^10 = 1024
alternating sum: 0
Vandermonde: 6188 = 6188
hockey stick: 330 = 330
C(20,10) = 184756, estimate 1.871e+05
C(40,20) = 137846528820, estimate 1.387e+11
C(80,40) = 107507208733336176461620, estimate 1.078e+23

               #
              # #
             # . #
            # # # #
           # . . . #
          # # . . # #
         # . # . # . #
        # # # # # # # #
       # . . . . . . . #
      # # . . . . . . # #
     # . # . . . . . # . #
    # # # # . . . . # # # #
   # . . . # . . . # . . . #
  # # . . # # . . # # . . # #
 # . # . # . # . # . # . # . #
# # # # # # # # # # # # # # # #