Pascal's Triangle
Lesson 1 of 11
1Pascal's Triangle
How to build a list of lists row by row, why every number is the sum of the two above it, and where the off-by-one bugs come from.
What the picture shows: Each row starts and ends with 1, and every number between is the sum of the two above it, like 6 = 3 + 3.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
Pascal's triangle is a pyramid of numbers: each number in a row is the sum of the two directly above it, and every row starts and ends with 1. You build it row by row like a brick wall, each row depending only on the one before it.
You represent it as a list of lists: row i has i + 1 items, and row[j] = prev[j - 1] + prev[j]. The time is O(n^2). It gives the binomial coefficients C(n, k), and you handle edge cases like n <= 0.
Required fundamentals
Nested lists
Pascal's triangle is a list of lists: each element is itself a whole list. If you are comfortable with matrix[row][col] you are comfortable with this project.
A loop inside a loop
An outer loop walks the rows, an inner loop walks the entries of one row. Understanding range(1, row_index) is half the solution.
Negative indexing
triangle[-1] is the last list we appended, which is the previous row. Using it saves you a variable you would otherwise track by hand.
Integer addition
There is no advanced maths here, only addition. But notice the numbers grow fast, and Python never overflows because its integers have no upper bound.
Core concepts
Pascal's triangle is a triangle of numbers that starts with 1 at the top, and every number after that is the sum of the two numbers directly above it. A number with only one number above it, the edge of a row, is always 1.
1The rule in one line
Call the previous row previous and the new row row, and the rule is:
row[i] = previous[i - 1] + previous[i]
That is the whole algorithm. Everything else is arranging the loops and the edges.
2Properties that let you check your own answer
| Property | Value | Example |
|---|---|---|
Length of row r (zero-based) | r + 1 entries | Row 4 has 5: [1,4,6,4,1] |
Sum of row r | 2 ** r | [1,3,3,1] sums to 8 = 2**3 |
| First and last entry | Always 1 | Only one number sits above each |
| Symmetry | row[i] == row[-1-i] | The triangle mirrors around its axis |
| Link to combinations | row[i] == C(r, i) | C(4,2) = 6, the number of ways to pick 2 out of 4 |
3The edges: where off-by-one bugs come from
The most common bug in this project is an inner loop with the wrong bounds. Look at row 4 (the fourth row, length 5): the first and last entries are fixed at 1, and the middle entries are only three of them: positions 1, 2 and 3. That is why the inner loop runs range(1, row_index), starting at 1 and stopping before row_index.
range(1, row_index + 1) for the inner loop. On its last turn that reads previous[row_index], a position the previous row does not have (it is one entry shorter), so you get IndexError. The previous row is always exactly one shorter than the new one.4Edge cases
| Input | Expected | Why |
|---|---|---|
n = 0 | [] | There are no rows to build |
negative n | [] | Same logic: n <= 0 covers both |
n = 1 | [[1]] | One row holding one value, note the list inside a list |
5Complexity
The output itself holds about n(n+1)/2 numbers, which is O(n²). So however clever your solution is, you cannot go below O(n²) in time or O(n²) in space, you are required to return all those numbers. That is the real lesson here: the lower bound is set by the size of the output, not by the cleverness of the algorithm.
How it works
Two pictures: the first is the code's path from the guard clause to the last row, the second is exactly where a new row's numbers come from.
Diagram 1, The build path: the guard clause first, then one new row per turn, fixed edges, middle computed from the previous row.
Diagram 2, Where a row's numbers come from: every middle number has two arrows from the previous row, while the edges have only one, which is why they are 1.
Worked example, step by step
We build the solution and then actually run it. Every output below is real output from running the code.
Step 1, the solution
#!/usr/bin/python3
"""0-pascal_triangle"""
def pascal_triangle(n):
"""Return the first n rows of Pascal's triangle as a list of lists."""
if n <= 0:
return []
triangle = [[1]]
for row_index in range(1, n):
previous = triangle[-1]
row = [1]
for i in range(1, row_index):
row.append(previous[i - 1] + previous[i])
row.append(1)
triangle.append(row)
return triangleStep 2, running it
$ cat 0-main.py
#!/usr/bin/python3
pascal_triangle = __import__('0-pascal_triangle').pascal_triangle
def print_triangle(triangle):
for row in triangle:
print("[{}]".format(",".join([str(x) for x in row])))
if __name__ == "__main__":
print_triangle(pascal_triangle(5))
$ ./0-main.py
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]Step 3, the edges
>>> pascal_triangle(0) [] >>> pascal_triangle(-3) [] >>> pascal_triangle(1) [[1]] >>> len(pascal_triangle(10)[-1]) 10 >>> sum(pascal_triangle(10)[-1]) 512
Those last two lines are your self-test: row ten (index 9) has length 10, and its sum is 512, exactly 2**9. If yours differs, you have a bounds bug.
Step 4, walk it row by row
Building 5 rows, one turn at a time
Row 0. We start with triangle = [[1]] outright. This is the base case: there is no earlier row to compute it from, so we write it by hand.
Row 1. row_index = 1 and previous = [1]. The inner loop range(1, 1) does not run at all, so there are no middle entries. We append 1 and get [1, 1].
Row 2. previous = [1, 1]. The loop runs once, at i = 1: previous[0] + previous[1] = 2. The result is [1, 2, 1].
Row 3. previous = [1, 2, 1]. Two turns: 1+2 = 3 and 2+1 = 3. The result is [1, 3, 3, 1], note the symmetry.
Row 4. previous = [1, 3, 3, 1]. Three turns: 1+3=4, 3+3=6 and 3+1=4, giving [1, 4, 6, 4, 1]. Quick check: the sum is 16, which is 2**4 ✓
row[i] = C(r, i), and you could compute each cell with factorials. But that is slower and more error-prone: factorials build enormous numbers and then divide them, while plain addition gets the same answer in fewer operations. The rule: if an incremental solution can build on what you already computed, let it.Myth vs. reality
| The myth | The reality |
|---|---|
| “This needs recursion because the triangle is defined recursively.” | The definition is recursive, but the iterative build is simpler and faster. Naive recursion without memoisation recomputes the same cells millions of times and hits Python's recursion limit. |
“[[1]*k for k in range(1, n+1)] builds the triangle for me.” | That builds the right lengths but every value is 1. Lengths are not the content, you still have to compute the middle. |
“[] and [[]] are the same thing.” | [] is an empty list (zero rows); [[]] is a list holding one empty row. What n <= 0 must return is the first. |
| “I can mutate the previous row in place to save memory.” | If you mutate previous inside the loop you are corrupting a row that is already part of the final output. Each turn needs a fresh row. |
“The numbers overflow for large n.” | Not in Python 3, its integers have no upper bound. In C or Java they genuinely do overflow, and that is a difference worth knowing. |
Where it is used in practice
Probability
A row of the triangle is exactly the distribution of heads in n coin flips. [1,4,6,4,1] says there are 6 ways out of 16 to get two heads in four flips.
Expanding brackets
The coefficients of (a+b)**n are row n of the triangle. (a+b)**3 has coefficients 1, 3, 3, 1.
An introduction to dynamic programming
This is the first time you build a table where every cell is computed from earlier cells. The very same idea solves far harder problems later.
Combinations without factorials
If you need C(n, k) for many values, building the triangle beats recomputing factorials each time, and it avoids dividing enormous numbers.
Try it yourself
Your inner loop reads for i in range(1, row_index + 1). What happens at row_index = 3?
At row_index = 3 the previous row [1,2,1] has length 3 (positions 0, 1, 2). The loop reaches i = 3 and reads previous[3], which does not exist. The correct bound is range(1, row_index).
Quick review flashcards
row[i] = previous[i-1] + previous[i], every number is the sum of the two above it.r?r + 1 entries, with zero-based indexing.r?2 ** r, a quick self-test that your solution is right.n <= 0?[], not [[]] and not None.range(1, row_index), from 1, stopping before row_index, because both edges are fixed.O(n²) in time and space, the minimum possible, since the output itself holds O(n²) numbers.Check your understanding
1. Why do we write triangle = [[1]] by hand instead of computing it?
Because it is the base case: there is no previous row to sum from. The rule previous[i-1] + previous[i] needs a row to already exist, so one has to be given up front.
2. A friend says [[1]*(k+1) for k in range(n)] solves it. What is wrong?
The lengths are right but the content is wrong: every value is 1, where the task wants computed numbers. The right shape does not mean the right values.
3. (Spot the bug) Your solution returns [[1]] for every n. Where do you look first?
The outer loop: most likely range(1, 1) instead of range(1, n), or triangle = [[1]] sitting inside the loop so it is reinitialised every turn.
4. Why can't we modify previous in place?
Because previous is triangle[-1], the same object that is already in the output. Mutating it changes a row we have already handed over. Lists in Python are passed by reference, not copied.
5. (Decision) You need C(n, k) for many values of n and k. Build the triangle, or use factorials?
For many nearby values the triangle wins: build it once and read any cell in O(1), with addition only and no division of huge numbers. For a single value with a very large n, the reduced factorial formula uses far less memory.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Official docs1
Articles2
Done with this lesson?
Sign in to save your progress.