The binomial theorem and Pascal's triangle
Combinations appear as coefficients when you expand powers like (x + y)^n, and they form the patterns of Pascal's triangle.
The binomial theorem
\((x + y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k\). Each term comes from choosing \(y\) from \(k\) of the \(n\) factors and \(x\) from the rest, and there are \(\binom{n}{k}\) ways to do that. So \((x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\).
(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^{n-k}y^kPascal's triangle
Arrange binomial coefficients in rows: row \(n\) lists \(\binom{n}{0}, \ldots, \binom{n}{n}\). Each entry is the sum of the two above it, because of Pascal's identity \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). Rows begin 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1.
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}A combinatorial proof of Pascal's identity
Count committees of \(k\) from \(n\) people, one of whom is Ada. Committees either include Ada (choose the other \(k - 1\) from \(n - 1\)) or exclude her (choose all \(k\) from \(n - 1\)). Adding the two cases gives the identity. Counting the same thing two ways is a powerful proof technique.
Row sums
Setting \(x = y = 1\) gives \(\sum_k \binom{n}{k} = 2^n\): the total number of subsets of an \(n\)-element set. Setting \(x = 1\), \(y = -1\) gives an alternating sum of \(0\), showing that a set has equally many even-sized and odd-sized subsets.
Worked example
Find the coefficient of \(x^3\) in \((2x + 1)^5\). The general term is \(\binom{5}{k}(2x)^{5-k}\). For \(x^3\), \(5 - k = 3\), so \(k = 2\): \(\binom{5}{2}2^3 = 10 \cdot 8 = 80\).
Patterns in the triangle
Pascal's triangle hides many patterns: diagonals give the natural numbers and triangular numbers; shading odd entries produces the Sierpinski triangle fractal; sums along shallow diagonals give Fibonacci numbers. Exploring these is a fun way to build combinatorial intuition.
Connection to probability
In \(n\) fair coin flips, the probability of exactly \(k\) heads is \(\frac{\binom{n}{k}}{2^n}\). Row \(n\) of Pascal's triangle, divided by \(2^n\), is the binomial distribution with \(p = \frac{1}{2}\). This is why the triangle looks bell-shaped for large \(n\).
Common mistakes
Forgetting to raise the coefficients inside the brackets to the right power, as in \((2x)^3 = 8x^3\). Mixing up which power goes with \(k\). Off-by-one errors in row numbering (the top row is row 0).
Key takeaways
Binomial coefficients give the terms of \((x + y)^n\). Pascal's triangle builds them by adding neighbours. Row sums equal \(2^n\). Combinatorial proofs count one set in two ways. The triangle connects directly to coin-flip probabilities.
Flashcard
(x+y)^n = \sum \binom{n}{k}x^{n-k}y^k
Check your understanding
What is the coefficient of x^2 y^2 in (x + y)^4?