Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 36 · Permutations and Combinations

Pascal's Triangle and the Binomial Theorem

Build Pascal's triangle, prove Pascal's rule by counting, expand (x+y)^n with the binomial theorem and discover identities such as the hockey stick and Vandermonde.

Write the numbers C(n, k) in rows, one row for each n, and you get Pascal's triangle. Each entry is the sum of the two above it. This lesson explains why, connects the triangle to the expansion of (x + y)^n, and shows several identities that are proved by counting the same set in two ways.

Pascal's rule

Pascal's rule: C(n, k) = C(n-1, k-1) + C(n-1, k).

Counting proof. Pick one special item among the n. A k-subset either contains it, and then you choose the other k-1 from the remaining n-1 (C(n-1, k-1) ways), or does not, and you choose all k from the remaining n-1 (C(n-1, k) ways). Those cases are disjoint and exhaustive, so by the sum rule the two terms add up.

Python Building the triangle from Pascal's rule

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The binomial theorem

Expand (x + y)^2 = x^2 + 2xy + y^2 and (x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3. The coefficients are rows of Pascal's triangle. In general:

(x + y)^n = Σ C(n, k) · x^(n-k) · y^k, the sum running over k from 0 to n.

Why? Multiply out n copies of (x + y). Each term of the product comes from choosing either x or y from each factor. The term x^(n-k) y^k arises exactly when you pick y from k of the n factors, and there are C(n, k) ways to choose which factors.

Python Expand (x + y)^n and check with sympy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Identities from the theorem

Set x = y = 1: 2^n = Σ C(n, k), the sum of row n. Set x = 1, y = -1: 0 = Σ (-1)^k C(n, k) for n >= 1, so even-sized and odd-sized subsets are equally many.

Python Row sums and alternating sums

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hockey stick and Vandermonde

Two more identities come up in practice.

Hockey stick: C(r, r) + C(r+1, r) + ... + C(n, r) = C(n+1, r+1). On the triangle, the numbers form a diagonal stripe whose sum sits just below the end, like the shape of a hockey stick.

Vandermonde: C(m+n, r) = Σ C(m, i) · C(n, r-i). Counting proof: choose r people from a group of m men and n women. Split by how many men i you pick.

Python Check the identities

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A picture: counting lattice paths

Every route on a grid with only right and up steps is a path through Pascal's triangle: the number of routes to a point is the sum of the routes to the point on its left and below. That is Pascal's rule again.

flowchart TD
    A["1"] --> B["1"]
    A --> C["1"]
    B --> D["1"]
    B --> E["2"]
    C --> E
    C --> F["1"]

Each number is the sum of its two parents.

The coefficient of a given term in (a + b)^n is C(n, k); to find it, never expand everything. For the coefficient of x^3 in (2x + 1)^5, take C(5, 3) · 2^3 = 10 · 8 = 80.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the coefficient of x^2 y^3 in (x + y)^5?

    C(5, 2) = C(5, 3) = 10.
  2. 2. By Pascal's rule, C(7, 3) equals:

    C(n, k) = C(n-1, k-1) + C(n-1, k) with n = 7, k = 3.
  3. 3. What is the sum of all entries in row 10 of Pascal's triangle?

    The sum of C(10, k) is 2^10 = 1024.
  4. 4. Why is the alternating sum of a row (n >= 1) zero?

    Setting x = 1 and y = -1 in the binomial theorem gives 0, meaning both kinds of subsets number 2^(n-1).

Summary

  • Pascal's rule C(n, k) = C(n-1, k-1) + C(n-1, k) builds the triangle.
  • The binomial theorem: coefficients of (x + y)^n are C(n, k).
  • Row sums give 2^n; alternating sums give 0.
  • Hockey stick and Vandermonde are proved by counting the same set two ways.

Next: Permutations with Repeated Items