Discrete Math › Section D · Counting › Topic D.1
Pascal's triangle and the binomial theorem
One triangle of numbers, built by nothing more than addition, answers a surprising range of counting questions: grid paths, strings of 0s and 1s, subsets, and the coefficients you get when you expand a power of a binomial.
A triangle built by addition
Start with a single 1 at the top. Each new row begins and ends with 1, and every other entry is the sum of the two entries just above it. The first rows are: 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. This is Pascal's triangle, named after Blaise Pascal, who studied it in the 1650s, although mathematicians in China, India and Persia knew it centuries earlier. The rule for building it is trivial. What makes the triangle remarkable is how many different counting problems turn out to have its entries as their answers.
Naming the entries
Rows are numbered from 0 at the top, and positions within a row are also numbered from 0 at the left. The entry in row \(n\), position \(k\) is written \(\binom{n}{k}\) and read "\(n\) choose \(k\)". So row 6 is \(\binom{6}{0}, \binom{6}{1}, \ldots, \binom{6}{6}\), and \(\binom{6}{2} = 15\). The building rule, called Pascal's rule, becomes
with \(\binom{n}{0} = \binom{n}{n} = 1\) along the edges. Each row also reads the same backwards, so \(\binom{n}{k} = \binom{n}{n-k}\). A formula that computes any entry directly comes later, in "Combinations and permutations".
Counting grid paths
Picture a grid of streets. A shortest path from \((0,0)\) to \((a,b)\) uses only steps right (R) and up (U): exactly \(a\) steps R and \(b\) steps U, \(a + b\) in all. To \((2,2)\) there are six such paths: RRUU, RURU, RUUR, URRU, URUR and UURR. Why the triangle? Every path to a point arrives either from the point on its left or from the point below it, so the number of paths to a point is the sum of the counts for those two neighbours. That is Pascal's rule exactly. Rotate the grid so \((0,0)\) sits at the top, and the path counts fill in Pascal's triangle: paths to \((a,b)\) number \(\binom{a+b}{b}\).
Bit strings and subsets
A bit string is a sequence of 0s and 1s, and its weight is the number of 1s. Write each R in a path as 0 and each U as 1, and paths to \((a,b)\) become bit strings of length \(a + b\) and weight \(b\). So the number of \(n\)-bit strings of weight \(k\) is \(\binom{n}{k}\): there are \(\binom{5}{2} = 10\) five-bit strings with two 1s. Subsets fit the same pattern. List the elements of \(\{1, 2, \ldots, n\}\) in order and mark each one 1 if it is in the subset and 0 if not. The string 0110 names the subset \(\{2, 3\}\) of \(\{1, 2, 3, 4\}\). Hence a set of \(n\) elements has exactly \(\binom{n}{k}\) subsets of size \(k\).
Worked example: paths across a city grid
How many shortest grid paths run from \((0,0)\) to \((5,3)\)? 1. Every path has \(5 + 3 = 8\) steps, of which 3 are up. 2. So the answer is \(\binom{8}{3}\), the entry in row 8, position 3. 3. Build row 8 from row 7 (1 7 21 35 35 21 7 1) by adding neighbours: 1 8 28 56 70 56 28 8 1. 4. Position 3 is 56. 5. Check with the last-step argument: paths reach \((5,3)\) from \((4,3)\), which has \(\binom{7}{3} = 35\) paths, or from \((5,2)\), which has \(\binom{7}{2} = 21\). Indeed \(35 + 21 = 56\).
The binomial theorem
Expand \((x + y)^n\) as a product of \(n\) brackets, each \((x + y)\). Every term of the expansion comes from picking either \(x\) or \(y\) from each bracket. A term \(x^{n-k}y^k\) arises once for each way to choose which \(k\) brackets supply a \(y\), and there are \(\binom{n}{k}\) such choices. Collecting like terms gives the binomial theorem:
So row \(n\) of the triangle lists the coefficients. Row 4 gives
Notice the powers: \(x\) counts down from \(n\) while \(y\) counts up from 0, and in every term the two powers add to \(n\).
Worked example: a coefficient with a negative term
Find the coefficient of \(x^3\) in \((2x - 1)^6\). 1. Treat the binomial as \((2x) + (-1)\), so the general term is \(\binom{6}{k}(2x)^{6-k}(-1)^k\). 2. For \(x^3\) we need \(6 - k = 3\), so \(k = 3\). 3. Row 6 gives \(\binom{6}{3} = 20\). 4. The term is
5. The coefficient is \(-160\). A quick sanity check on a full expansion: \((x + 2)^3 = x^3 + 6x^2 + 12x + 8\), using row 3 (1 3 3 1) and powers of 2. At \(x = 1\) the left side is \(3^3 = 27\), and \(1 + 6 + 12 + 8 = 27\).
Row sums and patterns
Put \(x = y = 1\) into the binomial theorem and the left side becomes \(2^n\), so each row sums to \(2^n\). Row 6 gives \(1 + 6 + 15 + 20 + 15 + 6 + 1\), which is 64. That matches the subset count: each of \(n\) elements is either in or out, so there are \(2^n\) subsets in total. Put \(x = 1\), \(y = -1\) instead, and the alternating sum of any row from row 1 on is 0: a non-empty set has as many even-sized subsets as odd-sized ones. The triangle holds more patterns. The diagonal next to the edge lists 1, 2, 3, 4, and so on; the next one lists the triangular numbers 1, 3, 6, 10, 15. Shading the odd entries draws the Sierpinski triangle fractal, and adding along shallow diagonals gives the Fibonacci numbers.
A link to probability
Flip a fair coin \(n\) times. Each of the \(2^n\) sequences of heads and tails is equally likely, and the number with exactly \(k\) heads is \(\binom{n}{k}\), so
For 6 flips, \(P(3 \text{ heads}) = \frac{20}{64} = 0.3125\). Dividing a whole row by \(2^n\) therefore gives the binomial distribution with success probability one half, which the statistics course treats in "The binomial distribution". Later in this section, "Counting and probability" builds on the same idea.
Common mistakes to avoid
First, numbering rows from 1: the single 1 at the top is row 0, so 1 4 6 4 1 is row 4, not row 5. Second, forgetting to raise a coefficient inside the bracket: in \((2x - 1)^6\) the factor is \((2x)^3 = 8x^3\), not \(2x^3\). Third, dropping the sign of a negative term, which needs \((-1)^k\). Fourth, matching the wrong power to \(k\): \(\binom{n}{k}\) multiplies \(x^{n-k}y^k\), so find \(k\) from the power you want before reading the row. Symmetry means \(\binom{n}{k} = \binom{n}{n-k}\) rescues some slips, but not those involving coefficients like 2 or signs.
Key takeaways
Pascal's triangle starts with 1 and builds each entry as the sum of the two above it: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\), counting rows and positions from 0. The entry \(\binom{n}{k}\) counts grid paths with \(n\) steps of which \(k\) go one way, \(n\)-bit strings of weight \(k\), and \(k\)-element subsets of an \(n\)-element set. Row \(n\) supplies the coefficients of \((x + y)^n\), with each row summing to \(2^n\). Divided by \(2^n\), a row gives coin-flip probabilities.
Flashcards
Flashcard
Rows of numbers where each entry is the sum of the two above it
Test your understanding
Question 1 of 5
What is the coefficient of x⁵y² in the expansion of (x + y)⁷?
Question 2 of 5
How many shortest grid paths, using only steps right and up, go from (0, 0) to (3, 4)?
Question 3 of 5
What is the coefficient of x² in the expansion of (2x + 3)⁴?
Question 4 of 5
Row 9 of Pascal's triangle is 1 9 36 84 126 126 84 36 9 1. What is C(10, 4)?
Question 5 of 5
How many subsets of any size does a set with 8 elements have?
