Python Pascal Triangle

Python Pascal Triangle

Pascal triangle

A pascal triangle is a number pattern of triangular array of the binomial coefficients. For designing a pascal triangle, we write a function in the program which takes an integer value as the input and print the number of lines (given by user as the integer value) for the pascal triangle.

Example: Following is the example of a pascal triangle pattern with the first 6 rows:

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

Pascal triangle in Python

In Python, we draw the pascal triangle pattern using the math module. We use the factorial functions of the math module in our Python program to implement the ⁿC_r formula for pascal triangle.

Here, in this tutorial, we will learn about the following methods in our Python program to get the pascal triangle pattern in the output:

1). Directly implementing ⁿC_r formula

2). Using C (line, m-1) implementation

3). Using powers of 11 implementation

Let's learn about the all the above given methods details and understand them with an example program.

Method 1: Directly implementing the ⁿC_r Formula in the program:

When we use the ⁿC_r formula in our program, a pictorial representation as given below will appear on the screen:

           ?C₀

        ¹C₀   ¹C₁

²C₀²C₁²C₂

³C₀³C₁³C₂³C₃

We will use the following steps or algorithm in the program while implementing this method:

• We will first take an input integer which is the number of rows of pascal triangle to be printed. Let's assume this input integer as 'num'.
• We will make outer iteration of m variable from 0 to given num times, for printing the rows of triangle.
• Then, we will make inner iteration of variable n from 0 to (num-1) times, for printing variables in each row.
• After that, we will print single blank space as " ".
• Then, we will close the inner loop (n variable loop) and it will create the left spacing in the rows.
• After that, we will make an inner iteration for the n variable from 0 to m.
• Then, we will print the ⁿC_r result for m and n.
• Now, we will close the inner loop of program.
• In last, we will print or add new line after each inner iteration of n loop. It will add a new line while printing a new row.

Now, look at the following program for the implementation of above algorithm:

Example –

 # importing factorial functions from math module
 from math import factorial
 # taking number of rows as input from user
 num = int (input ("Enter the number of rows for pascal triangle: "))
 # defining the outer iteration for number of loops
 for m in range(num):
         # defining inner iteration for variables in each row
             for n in range(num-m+1):
                         # closing inner n iteration for left spacing
                         print (end=" ")
         # inner n iteration for elements of pascal triangle
             for n in range(m+1):
                         # implementing the nCr = n!/((n-r)!*r!) formula
                         print (factorial(m)//(factorial(n)*factorial(m-n)), end=" ")
             # using print statement for new line
             print () 

Output:

 Enter the number of rows for pascal triangle: 6
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1
 The time complexity for the pascal triangle we have printed above is O(N²). 

Method 2: Using C (line, m-1) implementation:

In this method, we will learn that how we can optimize the complexity of code given in method 1. In this method, we will follow the concept of binomial coefficients i.e., the m^th entry in a given line number (let's say line) is the binomial coefficient for C (line, m). And, all the lines of pascal triangle will start with the value 1.

The basic idea used in this implementation is that we have to calculate the C (line, m) binomial coefficients using the C (line, m-1) coefficient. General formula for such type of implementation is as follows:

C (line, m) = [C (line, m-1) * (line - m + 1)]/ m

Now, look at the following program for the implementation of above given method:

Example – 

 # taking number of rows as input from user
 num = int (input ("Enter the number of rows for pascal triangle: "))
 # defining for loop for number of rows
 for m in range(1, num+1):
 # using inner iteration for elements in triangle rows
 for n in range(0, num-m+1):
         # for left spacing in rows
 print (' ', end='')
 # defining C as first element of array equals to 1
     C = 1
     # using for loop for values in line
 for n in range(1, m+1):
         # the first value in a line is always equals to 1
 print (' ', C, sep='', end='')
      # using Binomial Coefficient for C variable
         C = C * (m - n) // n
 # printing new line for each row
 print() 

Output:

Enter the number of rows for pascal triangle: 7         
         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
 The time complexity for the pascal triangle we have printed above is O(N²). 

Method 3: Using powers of 11 implementation:

This method is considered as the most optimized approach for printing pascal triangle pattern in Python. This method is based on the approach of powers of 11. Look at the following powers of 11 to understand this approach:

 11? = 1
 11¹ = 11
 11² = 121
 11³ = 1331 etc. 

Note: However, this approach is only limited up to the n = 5 i.e., 11?. It means we cannot print more than 5 rows of pascal triangle using this approach.

Now, look at the following program for the implementation of above given approach:

Example – 1

 # taking number of rows as input from user
 num = int (input ("Enter the number of rows for pascal triangle (Maximum 5): "))
 # using for loop for number of rows
 for a in range(num):
     # adjust left spacing between each element
 print (' '*(num-a), end='')
     # computing power of 11 for each row
 print(' '.join(map(str, str(11**a)))) 

Output:

 Enter the number of rows for pascal triangle (Maximum 5): 5
      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 The time complexity for the pascal triangle we have printed above is O(N).