Pascal’s Triangle Formula with Examples

What is Pascal’s Triangle?

Pascal’s Triangle is a triangular array of numbers that follows a simple pattern based on the row above it. It was popularized by French mathematician Blaise Pascal in the 17th century. The triangle begins with a single “1” at the top, and every subsequent row starts and ends with “1” as well.

Beyond its elegant shape, Pascal’s Triangle encodes deep mathematical relationships. It is closely tied to the binomial theorem, combinatorial counting, and probability, which is why it appears in algebra, statistics, and computer science classrooms worldwide.

Pascal’s Triangle History

Although named after Blaise Pascal, the triangle predates him by centuries. The Chinese mathematical text “The Nine Chapters on the Mathematical Art” contains one of the earliest known examples, displaying many of the same patterns we use today.

Persian mathematician Al-Karaji and Indian scholar Pingala also explored similar arrays. Pascal formalized the triangle’s properties in his 1654 treatise “Traité du triangle arithmétique,” which gave the structure its modern name in Western mathematics.

Construction of Pascal’s Triangle

Constructing Pascal’s Triangle is straightforward. The only rule to remember is that each row starts and ends with 1, and every other number is built from the row above.

For any row r and column c, the value equals the sum of the numbers in columns c-1 and c of row r-1.

Here,

• r = 3, 4, 5, …
• n and c = 2, 3, 4, …, r-1.

Here are the steps to build Pascal’s Triangle:

Step 1) Begin by filling up the first two rows.

Step 2) The second element of the third row is the sum of the first and second numbers in the second row.

Step 3) The fourth row begins with “1”. The second number is 3, which is the sum of 1 and 2 (highlighted in blue).

The image below shows how to fill the fourth row:

Step 4) The fifth row consists of five numbers. We already know the pattern for populating rows from the earlier steps.

Pascal’s Triangle Formula – Binomial Coefficient

A binomial coefficient counts the number of ways to choose a subset of k elements from a collection of n elements. It is commonly written as “C(n, k)” or “n choose k.”

The binomial coefficient is defined as:

The “!” symbol denotes the factorial of a number.

n! = n.(n-1).(n-2)…3.2.1

For example,

5! = 5.4.3.2.1

= 120

So, 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 procedure here mirrors how we drew the triangle manually. Suppose we want to generate Pascal’s triangle up to seven rows.

The steps to do so are as follows:

Step 1) Start the topmost row with “1”.

Step 2) For row “r”, element “c” will be the sum of column “c-1” and column “c” of row “r-1”.

Step 3) The first and last numbers in every row will always be “1”.

Following these three simple steps lets us systematically construct the entire 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 is used in this implementation. Given that N is the number of rows in Pascal’s triangle, this requires N² unit spaces. Therefore, the space complexity is O(N²).

The function uses two nested loops, each running up to “N” times. So, the time complexity is also O(N²), or squared time complexity.

Method 2: Building Pascal’s Triangle by Calculating Binomial Coefficient

We can derive the numbers of Pascal’s triangle directly using binomial coefficients. The diagram below illustrates the relationship:

Here are the steps to build Pascal’s Triangle by calculating the binomial coefficient:

Step 1) The topmost row is C(0, 0). Using the formula above, C(0, 0) = 1, because 0! = 1.

Step 2) For row “i”, there will be a total of “i” elements. Each item is calculated as C(n, r), where n is i-1.

Step 3) Repeat step 2 for as many rows of Pascal’s triangle as you want to generate.

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 are used in this implementation: one to compute the binomial coefficient and two more to iterate through every row and column. With respect to the number of rows, all three loops run up to “n” times. Consequently, the overall time complexity is O(n³).

The space complexity is constant because we do not store any intermediate results. The program computes each element on the fly and prints it within a row, so the space complexity reduces to O(1).

Method 3: Building Pascal’s Triangle by Modified Binomial Coefficient

In the previous technique, we used the binomial coefficient formula to calculate each element. The modified approach derives C(n, r) directly from C(n, r-1), reducing the work by one order of magnitude.

Here are the steps to build Pascal’s Triangle by the 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 index. Assign that value to a variable C.

Step 3) For computing the next coefficient, use C * (n – k) / k. Assign this new value back to C.

Step 4) Continue step 3 until “k” reaches the end of the row. After each iteration, increment 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 uses two loops, each running a maximum of “n” times, where “n” is the number of rows in the triangle. So, the time complexity is O(n²), squared time.

Regarding space complexity, we do not need any array for storage. We only use one variable to keep the previous binomial coefficient, so we need just one extra space. The space complexity is therefore O(1).

Application of Pascal’s Triangle

Here are some practical applications of Pascal’s Triangle:

Binomial Expansions: The coefficients of any binomial expansion can be read directly from Pascal’s triangle. Here is an example:

Calculating Combinations: The elements of Pascal’s triangle correspond directly to binomial coefficients. For example, if you have 6 balls and want to choose 3, the answer is ⁶C₃. You can find that value in the 3rd element of the 6th row of Pascal’s triangle.

Probability: Pascal’s Triangle is widely used to compute probabilities in coin tosses, dice problems, and other combinatorial events where each outcome corresponds to a binomial distribution.

Interesting Facts About Pascal’s Triangle

Here are some facts you will find interesting about Pascal’s triangle:

• The sum of all elements in any row is always a power of 2.

• The diagonal sums of the rows generate the Fibonacci sequence.

• Each row corresponds to the coefficients in the expansion of (a+b)ⁿ.
• If you shade only the odd numbers, the resulting figure forms the Sierpinski triangle fractal.

FAQs