Pascal’s Triangle – Formula, Patterns & Examples
What is Pascal’s Triangle?
Pascal’s Triangle is a triangular array of numbers followed by a particular pattern and connection to the row before it. It was invented by Blaise Pascal. This triangle starts with one element in the first row. After that, each row starts and ends with “1”.
Pascal’s Triangle History
The Chinese book “The Nine Chapters on the Mathematical Art” contains one of the first examples of Pascal’s Triangle. In addition, it contains some of the same patterns and qualities found in triangles today.
Pascal was one of several people in Europe who studied the triangle. Other mathematicians had examined similar triangular arrays of numbers before him.
Construction of Pascal’s Triangle
Constructing Pascal’s Triangle is simple. The only thing you need to remember is that the Row starts and ends with 1. The rule for the rest of the numbers is as follows:
For any row r and column c, the number will be the sum of columns c-1 and c from Row r-1.
Here,
- r = 3,4,5….
- n and c = 2,3,4,…r-1.
Here are steps to build Pascal’s Triangle:
Step 1) Let’s begin by filling up two rows.
Step 2) The second element for the third line is the sum of the first and second numbers in the second Row.
Step 3) The fourth Row will begin with “1.”. The second number is 3, which is the sum of 1 and 2 (highlighted in blue).
The below image shows how to fill the fourth Row:
Step 4) The fifth Row will consist of five numbers. We already know the pattern for populating the rows from the earlier steps.
Pascal’s Triangle Formula – Binomial Coefficient
A binomial coefficient is a number that expresses different methods to select a subset of k elements from a collection of n elements. Frequently, it is written as “C(n,k)” or “n choose k.”
The binomial coefficient is defined as
The “!” denotes the “factorial.”
n! = n.(n-1). (n-2)…3.2.1
For example,
5! = 5.4.3.2.1
= 120
So, let’s say C(5,3) or 5 choose 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Method 1: Building Pascal’s Triangle by the previous Row
The steps in this procedure are the same as those in Pascal’s triangle. Let’s say we want to create Pascal’s triangle up to seven rows.
The steps to accomplish so are as follows:
Step 1) Start the topmost Row with “1”.
Step 2) For the row “r”, “c” item will be the product of “c-1” and “c” the number of the “r-1” row.
Step 3) The first and last numbers in a row will always be “1.”
We must adhere to these three easy steps to create Pascal’s triangle.
C++ Code of Pascal’s Triangle by the previous Row
#include <bits/stdc++.h> using namespace std; void printRow(int n) { int numbers[n][n]; for (int row = 0; row < n; row++) { for (int col = 0; col <= row; col++) { if (col == 0 || col == row) { numbers[row][col] = 1; } else { numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col]; } cout << numbers[row][col] << "\t"; } cout << endl; } } int main() { int n; cout << "How many rows: "; cin >> n; printRow(n); }
Output:
How many rows: 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
Python Code of Pascal Triangle Formula by the previous Row
def printRow(n): numbers = [[0 for row in range(n)] for col in range(n) ] for row in range(len(numbers)): for col in range(0, row+1): if row == col or col == 0: numbers[row][col] = 1 else: numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col] print(numbers[row][col],end="\t") print("\n") n = int(input("How many rows: ")) printRow(n)
Pascal’s Triangle Example Output:
How many rows: 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
Complexity Analysis
A two-dimensional array was used in the implementation. Given that N is the number of rows in Pascal’s triangle. This will require N2 unit spaces. Therefore, O will be the space complexity (N2).
We have two loops in the function, and each loop runs for “N” times. So, the time complexity is also O(N2) or squared time complexity.
Method 2: Building Pascal’s Triangle by Calculating Binomial Coefficient
We can simply derive the numbers of pascal’s triangle using the binomial coefficient. Here’s the diagram:
Here are the steps to build Pascal’s Triangle by calculating the Binomial:
Step 1) The topmost Row will be C(0,0). Using the formula above for the Binomial Coefficient, C(0,0) = 1. Because 0! = 1.
Step 2) For row “i”, there will be total “i” elements. Each item will be calculated C(n,r) where n will be i-1.
Step 3) Repeat step 2 for the number of rows you want for pascal’s triangle.
C++ Code Pascal’s Triangle by Binomial Coefficient
#include <iostream> using namespace std; int factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; } int binomialCoefficient(int n, int r) { int result = 1; if (r > n) { return -1; } result = factorial(n) / (factorial(r) * factorial(n - r)); return result; } void printPascalTriangle(int row) { for (int i = 0; i <= row; i++) { for (int j = 0; j <= i; j++) { cout << binomialCoefficient(i, j) << "\t"; } cout << endl; } } int main() { int n; cout << "Enter row number: "; cin >> n; printPascalTriangle(n); }
Output:
Enter row number: 9 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 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Python Code Pascal’s Triangle by Binomial Coefficient
def factorial(n): result = 1 for i in range(1,n+1): result*=i return result def binomialCoefficient(n,r): result =1 if r>n: return None result = factorial(n) / (factorial(r) * factorial(n - r)) return int(result) def printPascalTriangle(row): for i in range(row+1): for j in range(i+1): print(binomialCoefficient(i, j), end="\t") print() # print(binomialCoefficient(3, 2)) n = int(input("Enter row number: ")) printPascalTriangle(n)
Pascal’s Triangle Example Output:
Enter row number: 8 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 8 28 56 70 56 28 8 1
Complexity Analysis
Three loops were used in the implementation. One loop is for calculating the Binomial coefficient, and the other two are for creating numbers for all rows. Concerning the number of rows, we have three loops that execute “n” times. Consequently, the overall time complexity will be 0(n3).
The space complexity is now constant because we don’t keep any data in storage. The program computes the element, and it is printed in a row. The space complexity then decreases to 0(1).
Method 3: Building Pascal’s Triangle by Modified Binomial Coefficient
In the previous technique, we have already seen how to use a binomial coefficient to calculate each element of Pascal’s triangle. This approach will determine C(n,r) from C. (n, r-1). It will simplify things by one order.
Here, are the steps to building Pascal’s Triangle by Modified Binomial Coefficient:
Step 1) Initiate the first Row with “1”
Step 2) Calculate C(n,r), where “n” is the row number and “r” is the column or the element. Assign the value in a variable C.
Step 3) For calculating C(n,k), it will be C*(n-k)/k. Now, assign this value to C.
Step 4) Continue step 3 until “k” reaches the end of the Row. After each iteration, increment the value of K by one.
C++ Code for Pascal’s Triangle by modified Binomial Coefficient
#include <bits/stdc++.h> using namespace std; void printpascalTriangle(int n) { for (int row = 1; row <= n; row++) { int previous_coef = 1; for (int col = 1; col <= row; col++) { cout << previous_coef << "\t"; previous_coef = previous_coef * (row - col) / col; } cout << endl; } } int main() { int n; cout << "How many rows: "; cin >> n; printpascalTriangle(n); }
Output:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python code for Pascal’s Triangle by modified Binomial Coefficient
def printpascalTriangle(n): for row in range(1, n+1): previous_coef = 1 for col in range(1, row+1): print(previous_coef, end="\t") previous_coef = int(previous_coef*(row-col)/col) print() n = int(input("How many rows: ")) printpascalTriangle(n)
Pascal’s Triangle Patterns Output:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Complexity Analysis
The implementation has two loops. Each loop runs a maximum of “n” time, where “n” means the number of rows in the pascal triangle. So, the time complexity is O(n2), squared time.
Regarding space complexity, we didn’t need any array to store. We just used one variable to keep the previous binomial coefficient. So, we just needed one extra space. The space complexity became O(1).
Application of Pascal’s Triangle
Here are some applications of Pascal’s Triangle:
Binomial Expansions: We can determine the coefficient of the binomial expansions from pascal’s triangle. Here’s an example:
(x+y)0 | 1 |
(x+y)1 | 1.x + 1.y |
(x+y)2 | 1x2 + 2xy + 1y2 |
(x+y)3 | 1x3 + 3x2y + 3xy2 + 1y3 |
(x+y)4 | 1x4 + 4x3y + 6x2y2 + 4xy3 + 1y4 |
Calculating Combinations: We’ve seen elements of Pascal’s triangle are equivalent to binomial coefficients. For example, if you have 6 balls and have been asked to choose 3 balls, it will be 6C3. Or, you can find the number in the 3rd element of the 6th Row from pascal’s triangle.
Interesting Facts About Pascal’s Triangle
Here are some facts you will find interesting about Pascal’s triangle:
- Sum of all elements in a row is always the power of 2.
- Diagonally sum of the elements of the rows generates the Fibonacci sequence.
Summary
- Pascal’s triangle gives the coefficients for the Binomial Expansions.
- Each Row of pascal’s triangle starts and ends with “1”. The intermediate values are the sum of two elements of the previous row.
- Diagonal addition of all the elements in pascal’s triangle will give you the Fibonacci sequence.
- Pascal’s triangle can also be generated with binomial Coefficients.