Pascal's triangle

O(n²)

Pascal's triangle arranges the binomial coefficients so the structure does the arithmetic. Each edge is 1, and every interior entry is the sum of the two above it — which is exactly the identity C(n,k) = C(n−1,k−1) + C(n−1,k). Read across, row n gives the coefficients of (x+y)ⁿ; the diagonals are the natural, triangular, and tetrahedral numbers; shallow diagonals sum to the Fibonacci numbers; and a whole row sums to 2ⁿ. Building it is a tiny O(n²) dynamic program where each cell reads its two parents. The two amber cells are the parents being summed into the orange one.

Number triangle
Press ▶ to run
Edit the input and press Play

How it works

  1. Put a 1 at the top.
  2. Start and end every row with 1.
  3. Each inner cell = sum of the two cells above it.
  4. Row n is C(n,0), C(n,1), …, C(n,n).

Pseudocode

1pascal(n):                          # O(n²)2  for r from 0 to n-1:3    T[r][0] ← 1,  T[r][r] ← 1        # edges4    for c from 1 to r-1:5      T[r][c] ← T[r-1][c-1] + T[r-1][c]6  return T