Python Program for Pascal’s Triangle

Method 1: Using the nCr Formula

The nCr formula, which is also known as the combination formula, can be used to calculate the values in Pascal's triangle. The formula is defined as:

nCr=n!/(r!⋅(n−r)!)

where n is the row number (starting from 0) & r is the position within the row (also starting from 0).

Algorithm

1. Define a function to calculate factorial.
    
2. Use the factorial function to compute combinations using nCr
    
3. Loop through the rows and columns to compute each value using nCr
    
4. Print the triangle row by row.

For example: 

def pascalTriangle(n):
    for i in range(n):
        for j in range(i+1):
            print(nCr(i, j), end=" ")
        print()

def nCr(n, r):
    return factorial(n) // (factorial(r) * factorial(n-r))

def factorial(num):
    if num == 0:
        return 1
    else:
        return num * factorial(num-1)

You can also try this code with Online Python Compiler

Run Code

In this example:

1. The `pascalTriangle` function takes an integer `n` as input, representing the number of rows to generate.
 

2. It uses nested loops to iterate over each row and position within the row.
 

3. For each position, it calls the `nCr` function to calculate the value using the combination formula.
 

4. The calculated values are printed with spaces in between.
 

5. The `nCr` function calculates the combination using the formula `n! / (r! * (n-r)!)`.
 

6. The `factorial` function calculates the factorial of a number recursively.
 

Time Complexity: O(n^3) 

Space Complexity: O(n)
 

The time complexity is O(n^3) because the `nCr` function is called for each position in the triangle, & the factorial calculations take O(n) time. The space complexity is O(n) due to the recursive calls in the factorial function.

Implementation

# Function to calculate factorial
def factorial(num):
    if num == 0 or num == 1:
        return 1
    return num * factorial(num - 1)
# Function to calculate nCr
def combination(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

# Function to print Pascal's Triangle
def pascal_triangle_nCr(rows):
    for i in range(rows):
        for j in range(i + 1):
            print(combination(i, j), end=" ")
        print()  # Move to the next line

# Number of rows
n = 5
pascal_triangle_nCr(n)

You can also try this code with Online Python Compiler

Run Code

Output:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

This method uses the mathematical combination formula and is efficient for small values of nnn.

Method 2: Using Iterative Approach

The iterative approach generates Pascal's triangle using nested loops & a 2D list to store the values. Each value in the triangle is calculated by summing the two values directly above it.

Algorithm

1. Initialize the first row of Pascal’s Triangle.
    
2. For each subsequent row:
   • Start with 1.
      
   • Add the two elements above the current position to calculate the next element.
      
   • End the row with 1.
      
3. Print each row.

Implementation

def pascalTriangle(n):
    triangle = []
    for i in range(n):
        row = []
        for j in range(i+1):
            if j == 0 or j == i:
                row.append(1)
            else:
                value = triangle[i-1][j-1] + triangle[i-1][j]
                row.append(value)
        triangle.append(row)
    return triangle

# Print the triangle
n = 5
result = pascalTriangle(n)
for row in result:
    print(row)

You can also try this code with Online Python Compiler

Run Code

Output:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

This approach uses arrays to store previous rows, making it efficient and easy to implement.
 

In this example:

1. The `pascalTriangle` function takes an integer `n` as input, representing the number of rows to generate.
 

2. It initializes an empty list called `triangle` to store the values.
 

3. The outer loop iterates over each row from 0 to n-1.
 

4. For each row, an empty list called `row` is created to store the values in that row.
 

5. The inner loop iterates over each position within the row.
 

6. If the position is 0 or equal to the row number, a value of 1 is appended to the `row` list.
 

7. Otherwise, the value is calculated by summing the two values directly above it from the previous row.
 

8. The calculated value is appended to the `row` list.
 

9. After each row is generated, it is appended to the `triangle` list.
 

10. Finally, the function returns the `triangle` list containing the generated Pascal's triangle.
 

Time Complexity: O(n^2)

Space Complexity: O(n^2)
 

The time complexity is O(n^2) because we have two nested loops iterating over the rows & positions. The space complexity is O(n^2) since we store the entire Pascal's triangle in the `triangle` list.

Method 3: Using Recursion

The recursive approach calculates the values in Pascal's triangle using recursive function calls. Each value in the triangle is calculated by summing the two values directly above it, which are obtained through recursive calls.

Algorithm

1. Define a recursive function to calculate the value at (n,r) using the formula: pascal(n,r)=pascal(n−1,r−1)+pascal(n−1,r)
    
2. Handle base cases:
   • If r=0 or r=n, return 1.
      
3. Loop through rows and columns to compute values using the recursive function.
    
4. Print the triangle row by row.
    

Implementation

def pascalTriangle(n):
    if n == 0:
        return []
    elif n == 1:
        return [[1]]
    else:
        triangle = pascalTriangle(n-1)
        last_row = triangle[-1]
        new_row = [1]
        for i in range(len(last_row)-1):
            new_value = last_row[i] + last_row[i+1]
            new_row.append(new_value)
        new_row.append(1)
        triangle.append(new_row)
        return triangle


# Print the triangle
n = 5
result = pascalTriangle(n)
for row in result:
    print(row)

You can also try this code with Online Python Compiler

Run Code

Output:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

This method is intuitive but can be slower for large values of n due to repeated calculations.
 

In this example:

1. The `pascalTriangle` function takes an integer `n` as input, representing the number of rows to generate.
 

2. The base cases are handled first:
 

   - If `n` is 0, an empty list is returned.
 

   - If `n` is 1, a list containing a single row `[1]` is returned.
 

3. For `n` greater than 1, the function makes a recursive call to `pascalTriangle(n-1)` to generate the triangle up to the previous row.
 

4. The last row of the previously generated triangle is obtained using `triangle[-1]`.
 

5. A new row is initialized with a value of 1 at the beginning.
 

6. The function iterates over the values in the last row (excluding the last value) and calculates the new values by summing the adjacent pairs.
 

7. The calculated values are appended to the `new_row` list.
 

8. A value of 1 is appended at the end of the `new_row` list.
 

9. The `new_row` is appended to the `triangle` list.
 

10. Finally, the function returns the `triangle` list containing the generated Pascal's triangle.

Time Complexity: O(2^n)

Space Complexity: O(n)

The time complexity is O(2^n) because each recursive call generates two additional recursive calls, forming a binary tree-like structure. The space complexity is O(n) due to the recursive calls on the call stack.

Frequently Asked Questions

What is the main use of Pascal’s Triangle?

Pascal’s Triangle is used in binomial expansions, probability calculations, and combinatorial mathematics.

Which method is the fastest for generating Pascal’s Triangle?

The iterative approach is the fastest as it avoids repeated calculations seen in the recursive method.

Can we generate Pascal’s Triangle for large values of rows?

Yes, but it’s advisable to use the iterative method for better performance with large inputs.

Conclusion

Pascal’s Triangle is a fundamental concept in mathematics with significant applications in programming and problem-solving. In this article, we covered three different methods to generate Pascal’s Triangle in Python: using the nCr formula, the iterative approach, and the recursive method. Each method has its own advantages and is suitable for different use cases.