Suggest an edit

Improve this article

Refine the answer for “What is Pascal's triangle?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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

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

Markdown · drag & drop images · ⌘B / ⌘I shortcuts656 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.