On this page
Description
Pascal's Triangle lists the binomial coefficients, "n choose k". Each row is built from the one above it: every inner number is the sum of the two numbers over it. Building it is a first taste of tabulation, where each answer is assembled from answers already computed. The interesting choices are how much of it to keep (the whole triangle, or one row) and which way to update a single row in place.
We'll go from simple to more technical:
- The pattern: each row from the row above.
- A second flavor: one row, updated in place from right to left.
- Where binomial tables are used in production.
- The mistakes: factorial overflow, row-index confusion, and the update direction.
The approach
Row 0 is a single 1. Every later row starts and ends with 1. Each number in between is the sum of the two numbers just above it, to the left and to the right.
| Row | Values | How the inner values are built |
|---|---|---|
| 0 | 1 | |
| 1 | 1 1 | |
| 2 | 1 2 1 | 1 + 1 |
| 3 | 1 3 3 1 | 1 + 2, 2 + 1 |
| 4 | 1 4 6 4 1 | 1 + 3, 3 + 3, 3 + 1 |
Entry k of row n is "n choose k". Row 4 says there are 6 ways to choose 2 things from 4.
Java
List<List<Integer>> triangle = new ArrayList<>();
for (int r = 0; r < numRows; r++) {
List<Integer> row = new ArrayList<>();
for (int c = 0; c <= r; c++) {
row.add(c == 0 || c == r ? 1 : triangle.get(r - 1).get(c - 1) + triangle.get(r - 1).get(c));
}
triangle.add(row);
}
Python
triangle = []
for r in range(num_rows):
row = []
for c in range(r + 1):
row.append(1 if c == 0 or c == r else triangle[r - 1][c - 1] + triangle[r - 1][c])
triangle.append(row)
This is bottom-up dynamic programming in its simplest form. Row r needs only row r - 1, so building the rows in order is enough. There's no recursion and no memo table.
A second flavor: one row, updated in place from right to left
If you only need one row, keeping every earlier row wastes space. Instead, turn one array into the next row, again and again. Add a 1 at the end, then update the inner values from right to left:
Java
List<Integer> row = new ArrayList<>();
row.add(1);
for (int i = 1; i <= rowIndex; i++) {
row.add(1); // the new last entry
for (int j = i - 1; j > 0; j--) { // right-to-left!
row.set(j, row.get(j) + row.get(j - 1));
}
}
Python
row = [1]
for i in range(1, row_index + 1):
row.append(1) # the new last entry
for j in range(i - 1, 0, -1): # right-to-left!
row[j] = row[j] + row[j - 1]
The direction is the whole trick. Each update reads its left neighbor, which must still hold the old row's value. Going right to left, that neighbor hasn't been touched yet. Going left to right, it was just overwritten. Turning row 3 into row 4:
| Step | Right to left (correct) | Left to right (wrong) |
|---|---|---|
| Row 3 plus a new 1 | 1 3 3 1 1 | 1 3 3 1 1 |
| First update | 1 + 3 = 4: 1 3 3 4 1 | 3 + 1 = 4: 1 4 3 1 1 |
| Second update | 3 + 3 = 6: 1 3 6 4 1 | 3 + 4 = 7: 1 4 7 1 1 |
| Third update | 3 + 1 = 4: 1 4 6 4 1 | 1 + 7 = 8: 1 4 7 8 1 |
Where you'll see it
"n choose k" shows up in probability and in A/B-test sample-size calculations. A table built once and indexed is far cheaper than recomputing factorials on every query, and it's exactly Pascal's Triangle.
Which tool for which job?
| You need | Use |
|---|---|
| Every row up to n | build the triangle row by row |
| Only row n | one array updated right to left, O(n) space |
| One C(n, k), n small | the multiplicative formula, dividing as you go |
| Many C(n, k) mod a prime, n up to millions | factorials and inverse factorials mod p |
| C(n, k) exactly, any size, in Python | math.comb |
| A few values reused often | a precomputed table |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Computing n! / (k! (n-k)!) directly | overflow from 13! (int) or 21! (long) | add (triangle) or multiply and divide step by step |
| Mixing row index and row number | every row shifts by one | row 0 is [1] |
| Updating one row left to right | values get added twice | right to left |
int entries past row 33 | the middle values overflow | long (to row 66), then modular or big integers |
| Building the whole triangle for one row | O(n^2) memory for nothing | one row in place |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why is row 0 a single 1, and what goes wrong if you confuse row index with "the n-th row"?
Show answer
Row 0 is the first row, counting from 0. What people call "the first row" is row index 0. Mix the two up and every row is one off: you return 1 3 3 1 when row 4, 1 4 6 4 1, was asked for.
2. Why must the in-place update run from right to left?
Show answer
Each new value is its old value plus its left neighbor's old value. From right to left, the left neighbor hasn't been updated yet in this pass. From left to right, it already holds the new row's value, so the sum is wrong, as in the 7 and 8 above.
3. How is Pascal's Triangle like a prefix-sum array?
Show answer
Both compute shared results once so later queries can look them up. A prefix-sum array turns any range sum into one subtraction. The triangle turns any "n choose k" into a lookup instead of a fresh factorial calculation.
Key takeaways
- Row r depends only on row r - 1, so build the rows in order. No recursion or memo table is needed.
- The whole triangle costs O(n^2) space. For one row, update a single array: O(n).
- Update that array from right to left, or it reads values from the new row.
- Row 0 is
[1]. Mixing row index and row number shifts everything by one. - For one "n choose k" on its own, a formula is cheaper. The table wins when you need many values.