Pascal’s Triangle

The numbers in the graphic below form the first five rows of Pascal's Triangle, which in this post I will implement in Python. The first row consists of a single number 1. In subsequent rows, each of which is has one more number than the previous, values are calculated by adding the two numbers above left and above right. For the first and last values in each row we just take the single value above, therefore these are always 1.

Pascal's Triangle

Pascal's Triangle in its conventional centred layout

At first glance you might think Pascal's Triangle is of little interest or use other than perhaps teaching very young children to add up. Nothing could be further from the truth - as with so many areas of mathematics this simple idea has spawned a large area of study and overlaps with even more. The Wikipedia article on the subject is fairly comprehensive but I am writing this article as a precursor to another on the subject of a contraption called a Galton Board, which takes us into the area of statistics and specifically the normal distribution. If you look at the last row of numbers you might be able to discern the first inklings of a normal distribution.

To that end, note that each number represents the number of possible paths to it from the top, asuming we travel downwards and either to the left or right. For example, the second number in the third row is 3, and there are three possible paths to it from the top:

  • left, left, right
  • left, right, left
  • right, left, left

The Data Structure

Let's start of by considering the kind of data structure we need to represent Pascal's Triangle. For this purpose it might be simpler to show it left-aligned rather than centred.

Pascal's Triangle

Pascal's Triangle in a left aligned form

Looking at the layout above it becomes obvious that what we need is a list of lists. In a Pascal's Triangle the rows and columns are numbered from 0 just like a Python list so we don't even have to bother about adding or subtracting 1.

Program Requirements

The purpose of this program is simply to print out Pascal's Triangle to the number of rows which will be specified as a function line argument. Calculating values doesn't present any obvious problems as it is simply the addition of two numbers. However, calculating the indexes of the two numbers in the previous row to add is fiddly so I'll use the following formula, where n is the row number and k is the column number, both 0-based:

Calculating values for Pascal's Triangle

value(n,k) = n!/(k!*(n-k)!)

Starting to Code

Create a new folder and within it create a file called pascalstriangle.py. As this is a short and simple program I will keep all the source code in one file. You can download it from the Downloads page or download/clone from Github if you prefer. This is the listing for the entire file.

pascalstriangle.py

import math

def main():

    """
    Simply create and populate a Pascal's Triangle
    and then print it in two formats
    """

    print("----------------------\n| code-in-python.com |\n| Pascal's Triangle  |\n----------------------\n")

    pt = create(8)

    populate(pt)

    print_left(pt)

    print("")

    print_centre(pt)

def create(rowcount):

    """
    Create an empty list and then append lists of 0s, each list one longer than the previous
    """

    pt = []

    for r in range(1, rowcount + 1):

        pt.append([0] * r)

    return pt

def populate(pt):

    """
    Populate an uninitialized list with actual values
    """

    for r in range(0, len(pt)):

        for c in range(0, len(pt[r])):

            pt[r][c] = math.factorial(r) / (math.factorial(c) * math.factorial(r - c))

def print_left(pt):

    """
    Prints the triangle in a left-aligned format to demonstrate data structure
    """

    for r in range(0, len(pt)):

        for c in range(0, len(pt[r])):

            print("%-4d" % pt[r][c], end="")

        print("")

def print_centre(pt):

    """
    Prints the triangle in a conventional centred format
    """

    inset = int(((((len(pt) * 2) - 1) / 2) * 3))

    for r in range(0, len(pt)):

        print(" " * inset, end="")

        for c in range(0, len(pt[r])):

            print("%-3d   " % pt[r][c], end="")

        print("")

        inset-= 3

#-----------------------------------------------------

main()

The main function simply calls the subsequent functions to create, populate and print the Pascal's Triangle.

The create function creates a new list and then uses a for loop to add lists of 0s to it. These lists are created by multiplying [0] by the current row number; this is the reason we loop from 1 to rowcount + 1 rather than 0 to rowcount. Finally we return the list.

In populate we iterate the rows and columns, setting the values according to the formula above.

The print_left function uses similar nested loops to print each row, the %-4d left-aligns the output within four character widths.

The print_centre function uses similar loops but also utilises an inset to pad the output at the left with spaces. This is calculated using a fiddly formula, and is reduced by 3 after each row.

We have now finished the code so can run it using this command in Terminal . . .

Running the program

python3.6 pascalstriangle.py

. . . which will give you the following output.

Program Output

----------------------
| code-in-python.com |
| Pascal's Triangle  |
----------------------

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   

                      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

You can of course change the number of lines to another value if you wish.

Please follow Code in Python on Twitter to keep up to date with new posts.