What is Pascal's triangle?

AlgorithmsJunior~3 min read

Short answer

Pascal's triangle is an infinite table of binomial coefficients C(n, k), where each row n starts and ends with a one, and each interior number equals the sum of the two numbers above it: C(n, k) = C(n−1, k−1) + C(n−1, k). It is used to compute combinations and the coefficients in the expansion of (a + b)^n.

Detailed explanation

Definition

Pascal's triangle is a way to arrange the numbers C(n, k) ("n choose k" combinations). The edges of the triangle are filled with ones: C(n, 0) = C(n, n) = 1. The interior elements are computed by the recurrence: C(n, k) = C(n−1, k−1) + C(n−1, k). Indexing usually starts at n = 0 in the top row (where the single element equals 1).

First rows

n	Values of C(n, k) left to right
0	1
1	1 1
2	1 2 1
3	1 3 3 1
4	1 4 6 4 1
5	1 5 10 10 5 1

Key properties

Recurrence relation: C(n, k) = C(n−1, k−1) + C(n−1, k); base cases: C(n, 0) = C(n, n) = 1.
Binomial theorem: (a + b)^n = Σ C(n, k) a^(n−k) b^k.
Symmetry: C(n, k) = C(n, n − k).
Row sum: Σ_{k=0..n} C(n, k) = 2^n.
Diagonals: the edge is all ones; the next diagonal is the natural numbers; then the triangular numbers, and so on. Shallow diagonals give the Fibonacci sequence.
Combinatorial meaning: C(n, k) is the number of ways to choose k elements out of n without regard to order.
Parity: modulo 2, the triangle's pattern forms the Sierpinski fractal.

Algorithms and code (JavaScript)

Below is a practical implementation for getting the n-th row and the first R rows. BigInt is used to avoid overflow for large n. The formula for neighboring coefficients: C(n, k+1) = C(n, k) × (n − k) / (k + 1).

javascript

function pascalRow(n) {
  const row = Array(n + 1);
  row[0] = 1n;
  for (let k = 1; k <= n; k++) {
    row[k] = (row[k - 1] * BigInt(n - (k - 1))) / BigInt(k);
  }
  return row;
}

function pascalTriangle(rows) {
  const tri = [];
  for (let n = 0; n < rows; n++) {
    tri.push(pascalRow(n));
  }
  return tri;
}

// Usage examples
console.log(pascalRow(5).map(Number));       // [1, 5, 10, 10, 5, 1]
console.log(pascalTriangle(6).map(r => r.map(Number)));
// [
//   [1],
//   [1, 1],
//   [1, 2, 1],
//   [1, 3, 3, 1],
//   [1, 4, 6, 4, 1],
//   [1, 5, 10, 10, 5, 1]
// ]

This implementation does not use factorials, runs in O(n) for a single row, and is resistant to overflow thanks to BigInt.

Typical interview problems

Print the first R rows of Pascal's triangle (iteratively, without recursion).
Get the n-th row in O(n) memory (incrementally or in-place from right to left).
Compute C(n, k) without factorials (multiplying and dividing along the way; use the symmetry k = min(k, n − k)).

Complexity

Building up to row n entirely: O(n^2) in time and memory.
A single row n: O(n) in time and O(n) in memory (or O(1) extra memory when printed one number at a time).

Common calculation mistakes

Using factorials (overflow and unnecessary complexity).
Floating-point division instead of integer arithmetic (loses precision).
Ignoring the symmetry C(n, k) = C(n, n − k), which makes the loop do twice the work.

Quick formulas

Closed form (factorial): C(n, k) = n! / (k! (n − k)!).
Recurrence formula: C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Neighboring coefficients: C(n, k + 1) = C(n, k) × (n − k) / (k + 1).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.