Pascal's Triangle
Each number is the sum of the two directly above it. Row n gives the binomial coefficients C(n, k) — the counts in combinatorics and the coefficients of (a+b)ⁿ.
- Category
- Mathematics
- Time complexity
- O(n²)
- Space complexity
- O(n²)
Pseudocode
row 0 is [1] each interior entry = sum of two above edges are always 1 row n = C(n, 0..n)
Reference implementation
tri = [[1]]
for r in range(1, n):
row = [1]
for k in range(1, r):
row.append(tri[r-1][k-1] + tri[r-1][k])
row.append(1); tri.append(row)