Pascal's triangle with Python lists

Why this matters

Pascal's triangle is a table of numbers with a simple build rule. It shows up in counting problems, in algebra, and in probability. A programmer meets it in practice problems because the rule is short, the numbers grow quickly, and the program has to handle the edges of each row correctly.

This lesson is about the numbers, not the printed shape. The shapes from the last lesson were built from stars and spaces. Here, the values are stored in Python lists, and the program builds each row from the one before it. Floyd's triangle, which comes later in this module, is a different number table with a different rule.

The idea: each value is the sum of the two above

The triangle has rows, and the rows are numbered from 0. Row 0 has one value, which is 1. Each row after that has one more value than the row before. The first and last value of every row is 1. Every other value is the sum of the two values directly above it.

Here is the triangle for rows 0 to 4, with the sums written out:

row 0:             1
row 1:           1   1
row 2:         1   2   1
row 3:       1   3   3   1
row 4:     1   4   6   4   1

Look at row 4. The first and last values are 1, as the rule says. The second value is 4, which is 1 + 3, because the two values above it in row 3 are 1 and 3. The middle value is 6, which is 3 + 3. The value after that is 4, which is 3 + 1. Each step uses the two numbers directly above, one on the left and one on the right.

The rule does not depend on the numbers being small. Once the rule is clear, the program only needs three things: a list for each row, a check for the edges, and a sum of the two values above for everything in the middle.

The values have a second meaning. Row r, value c is written C(r, c) and is called a binomial coefficient. It counts the ways to choose c items from a group of r items, when the order of the choice does not matter. For example, C(4, 2) is 6. Suppose you have four items named A, B, C and D, and you want to choose two. The choices are AB, AC, AD, BC, BD and CD. That is six choices, and it matches the value in row 4, position 2. This is the binomial pattern: each value in the triangle is a count of choices.

Worked example 1: building the rows

The first program builds six rows and prints them. A Python list is an ordered collection that can grow. The outer list tri holds the rows. Each inner list holds one row. The method append adds one item to the end of a list.

The inner loop runs from c = 0 up to c = r. That is r + 1 values, which is the right count for row r. The if checks the two edges. When c is 0 or c equals r, the value is 1. Otherwise, the value is the sum of the two values in the previous row: tri[r - 1][c - 1] and tri[r - 1][c]. The first index picks the row and the second index picks the position in that row. Python lists also start at position 0.

The output is:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

The last loop turns each row into one line of text. The part str(value) for value in row is a generator expression. It makes the text version of each value, one after another. The method " ".join(...) puts those pieces together with a single space between each one.

Row 5 has the value 10 in the middle. That is 4 + 6 from row 4. Notice that 10 has two digits and takes up more room than the other values. Lining up the columns of a table is the subject of a later lesson in this module, so the printout here is left-aligned.

Worked example 2: keeping only one row

The triangle above keeps every row in memory, because tri grows with each row. Often, you only need the current row. In that case, a function that turns one row into the next row is simpler. It takes the current row and returns the row below it.

The function starts with a 1, then adds each pair of neighbouring values, then ends with a 1. A row with n values has n - 1 neighbouring pairs. The loop range(len(prev) - 1) visits each pair once: prev[i] is the left value and prev[i + 1] is the right value. The function len gives the number of items in a list.

The output is:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

The variable row starts as the list [1]. Each pass prints the current row, then replaces row with the next one. The function builds a new list each time and never changes the old one. Only two rows exist at any moment, the old row and the new one.

The pairs can also be written with itertools.pairwise. The itertools module is part of the standard library, which means it comes with Python and needs no install. The function pairwise gives each pair of neighbouring items. This version prints the same output:

The part [left + right for left, right in pairwise(prev)] is a list comprehension. It builds a list in one line, with one value for each pair. Both versions are correct. The loop version is easier to read the first time, and the comprehension is common in Python code once you know it.

This is the form to use when a problem asks for one row, such as row 20, and nothing else. It also uses less memory than the full table, though with a few dozen rows the difference is small.

Worked example 3: the binomial pattern

Now read the numbers as counts. The program below builds 12 rows in the same way as before. It also computes each value directly with a formula and checks that the two methods agree. It prints the sum of each row as well.

The direct formula is written in the choose function. It multiplies and divides one step at a time, so the result stays a whole number at every step. The symbol // is whole-number division, and it is used here on purpose. Here is the trace for C(10, 3), which is 10 choose 3:

After three steps the result is 120, the value in row 10, position 3. The division is always exact at each step, because the result after each step is itself a binomial coefficient, which is a whole number.

The standard library also has the function math.comb(n, k), which gives C(n, k) directly. The program prints it as a check.

The output is:

row 0 sum 1 equals 2^0 True
row 1 sum 2 equals 2^1 True
row 2 sum 4 equals 2^2 True
row 3 sum 8 equals 2^3 True
row 4 sum 16 equals 2^4 True
row 5 sum 32 equals 2^5 True
row 6 sum 64 equals 2^6 True
row 7 sum 128 equals 2^7 True
row 8 sum 256 equals 2^8 True
row 9 sum 512 equals 2^9 True
row 10 sum 1024 equals 2^10 True
row 11 sum 2048 equals 2^11 True
C(10,3) = 120
every value matches C(r,c): True
math.comb(10, 3) = 120

Python writes the two truth values as True and False, with a capital letter. The f-string f"... {total == (1 << r)}" puts the result of the comparison into the text.

Two patterns show up. First, every value in the triangle equals the direct formula C(r, c). The rule of adding the two values above and the formula agree, so you can use either one. Second, the sum of row r is 2 to the power r. Row 3 is 1 + 3 + 3 + 1, which is 8, and 8 is 2 to the power 3. The expression 1 << r moves the bits of 1 left by r places, which doubles 1 a total of r times and gives 2 to the power r. The expression 2 ** r gives the same number and is easier to read for most people.

Worked example 4: counting the odd values

Harder problems ask you to look for a pattern across many rows, not just one. This example counts the odd values in rows 0 to 15. It uses the next_row function from the second example, and it adds up the odd values as each row is printed.

The output is:

row 5 = [1, 5, 10, 10, 5, 1]
odd values in rows 0 to 15 = 81

The check value % 2 == 1 uses the remainder operator %. A number is odd when dividing it by 2 leaves a remainder of 1. The count of 81 is not a coincidence. Look at a few rows from the earlier output and count their odd values:

• Row 3 is 1 3 3 1, and all four values are odd. The number 3 in binary, the base-2 form that computers use, is 11, which has two 1 digits. The count of odd values is 2 raised to that number of 1 digits, which is 2 to the power 2, or 4. In Python, bin(3) gives 0b11. The prefix 0b only marks the text as binary.
• Row 5 is 1 5 10 10 5 1. The odd values are 1, 5, 5 and 1, which is four values. The number 5 is 101 in binary, and it has two 1 digits, so the count is 2 to the power 2, or 4.
• Row 7 is 1 7 21 35 35 21 7 1. All eight values are odd. The number 7 is 111 in binary, with three 1 digits, so the count is 2 to the power 3, or 8.

For the rows 0 to 15, each row number is a 4-digit binary number, and each binary digit is either 0 or 1. Each 1 digit doubles the count and each 0 digit does not change it. Over all 16 row numbers, the total works out as (1 + 2) multiplied by itself four times, which is 3 to the power 4, or 81. The lesson does not prove the rule. The program confirms that the total is 81 for these rows.

This is a good example of reading a pattern. The program did not need the rule to find the answer. It only needed to count. The rule explains why the answer makes sense, and it tells you what to expect for other row ranges.

How big do the numbers get?

The values in the triangle grow fast. The total of each row is twice the total of the row before it, so the middle values grow quickly as the rows go down.

Python integers have no fixed size limit. A Python int grows to hold as many digits as the number needs. The only limits are the memory of the computer and the time the arithmetic takes. This is different from languages such as Java, where an int holds at most 2147483647 and a value that is too big wraps around to a wrong number. In Python, the triangle never overflows, so no check for overflow is needed for the integer rows.

The program below prints some large values from math.comb. The last part shows the one limit that does apply. Converting a very large integer to a float, which is a decimal number with limited precision, raises an error:

The output is:

C(34,17) = 2333606220
C(66,33) = 7219428434016265740
C(67,33) = 14226520737620288370
C(1100,550) has 330 digits
OverflowError: int too large to convert to float

The keyword try runs the code that might fail. The except block runs only if an OverflowError is raised inside the try. The value C(1100, 550) has 330 digits. It is too large for a float, which stops at about 1.8 times 10 to the power 308, so the conversion raises the error. The integer itself is fine. It is only the float conversion that fails. Keep values as integers when they can get large.

Common mistakes

Mistake 1: forgetting the edge values

If the code adds the two values above without checking the edges, it tries to read a position that does not exist. The program below leaves out the edge check:

def main():
    tri = []
    for r in range(4):
        row = []
        for c in range(r + 1):
            row.append(tri[r - 1][c - 1] + tri[r - 1][c])
        tri.append(row)
    print(tri)
 
 
main()

The first attempt is in row 0, where r - 1 is -1 and the list tri is still empty. The real output is:

Traceback (most recent call last):
  File "main.py", line 11, in <module>
    main()
    ~~~~^^
  File "main.py", line 6, in main
    row.append(tri[r - 1][c - 1] + tri[r - 1][c])
               ~~~^^^^^^^
IndexError: list index out of range

The path in the lines of the traceback depends on where the file is saved. Here it is shown as main.py. The last line names the problem. An IndexError means the position asked for is outside the list. The fix is the if c == 0 or c == r check.

Python has one more trap here. A negative index such as tri[-1] does not fail when the list has items. Python counts negative positions from the end, so tri[-1] is the last row. Without the edge check, the program can then add values from the wrong row and print a wrong triangle with no error at all. The edge check prevents this too.

Mistake 2: using / for division

In Python 3, the single slash / always gives a float, even when the answer is a whole number. The choose function from the third example shows the problem when // is replaced with /. The program below does that, and it also prints the value from math.comb for comparison:

from math import comb
 
 
def choose(n, k):
    result = 1
    for i in range(k):
        result = result * (n - i) / (i + 1)
    return result
 
 
def main():
    print("C(34,17) =", choose(34, 17))
    print("C(66,33) =", choose(66, 33))
    print("comb(66, 33) =", comb(66, 33))
 
 
main()

The output is:

C(34,17) = 2333606220.0
C(66,33) = 7.219428434016265e+18
comb(66, 33) = 7219428434016265740

The value for C(34, 17) has a .0 at the end, so it is a float, not an integer. The value for C(66, 33) is written in scientific form and is rounded. A float keeps only about 16 to 17 significant digits, so the last digits of a large answer are lost. The math.comb line gives the exact value. The fix is to use //, which keeps the result as an integer.

Mistake 3: forgetting that the rows start at 0

A common error is to treat the first row as row 1. That makes the row numbers and the sizes off by one. Row 0 has one value, row 1 has two, and row r has r + 1 values. In the code, range(6) builds six rows, numbered 0 to 5. If you want rows 1 to 6 in the printout, you must still build row 0 first, because each row uses the row above it.

Mistake 4: using the wrong row or position

The formula C(r, c) uses row r and position c, both counted from 0. The value C(5, 2) is 10, which is the third value in row 5. If you read position 2 as the second value, you get 5, which is wrong. Check each answer by writing the first few rows on paper and counting from 0.

Practice

Exercise 1: the first eight rows

Use the next_row function to print rows 0 to 7. Check that the last row is 1 7 21 35 35 21 7 1.

Show the answer

The program is the second worked example, so the code is not repeated here. The output has eight lines, and the last line is:

1 7 21 35 35 21 7 1

The loop runs eight times, so it prints rows 0 through 7.

Exercise 2: a single binomial value

Use the choose function to find C(12, 5), which is the value in row 12, position 5.

Show the answer

The output is:

C(12,5) = 792

Each step divides exactly, so every intermediate result is a whole number. It also works for much bigger values, because Python integers do not overflow.

Exercise 3: the first row with a large value

Find the first row where a value is greater than 1000. Build the rows one at a time with next_row, and keep track of the largest value in each row.

Show the answer

The program finds the largest value in each row with the built-in function max before it builds the next row:

The output is:

first row with a value over 1000 is row 13 (max 1716)

Row 12 has a largest value of 924, which is C(12, 6). Row 13 has 1716, which is C(13, 6).

Exercise 4: the sum of a row without adding

Row 10 has eleven values. Without adding them one by one, say what their sum is, and explain why.

Show the answer

The sum is 1024. Each row's sum is 2 to the power of its row number, so row 10 sums to 2 to the power 10, which is 1024. The program in the third worked example prints this for every row, and the line for row 10 is row 10 sum 1024 equals 2^10 True. The reason is that each value counts a set of choices, and adding all the values in a row counts every possible subset of the row's items, which is 2 to the power of the number of items.

Summary

• Each row of Pascal's triangle starts and ends with 1. Every other value is the sum of the two values directly above it.
• Row r, position c, is the binomial coefficient C(r, c), which counts the ways to choose c items from r items.
• A row can be built from the row before it with a function that adds neighbouring pairs and adds a 1 at each end.
• Python integers do not overflow, so the triangle can grow as far as memory allows. Use // for whole-number division, because / gives a float that rounds large values.
• math.comb(n, k) gives C(n, k) directly, and a negative list index counts from the end of the list instead of failing.