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 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, assuming 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 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.
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.
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( * 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  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 the inset variable to pad the output at the left with spaces. This is calculated using an ugly formula (which I'm not proud of but at least it works!) 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
. . . which will give you the following 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.Follow @CodePythonBlog