Pascal’s Triangle in C++

Filed Under: C++
Pascals Triangle Featured Image

Named after the French mathematician, Blaise Pascal, the Pascal’s Triangle is a triangular structure of numbers. The triangle is constructed using a simple additive principle, explained in the following figure.

Pascal Triangle Principle Edited
Principle of Pascal’s Triangle

Each entry, except the boundary of ones, is formed by adding the above adjacent elements. Even though the formation of Pascal’s triangle is simple, it holds a huge number of mathematical properties and applications.

Properties of Pascal’s Triangle

Let us go through some mind-blowing properties of Pascal’s Triangle.

Combinations

Any high-school student with mathematical background must have gone through the course of Permutations and Combinations. The combinations section refers to the number of ways we can choose certain objects from a group of objects.

Pascals Triangle Equation
Combinations formula

Using the row and the column number, each value can be replaced as follows:

Pascals Triangle Combinations
Pascal’s Triangle as Combinations

This property further extends to the binomial expansions, where each binomial coefficient represents the value of the Pascal’s Triangle.


Hockey Stick Identity

A very unique property of Pascal’s triangle is – “At any point along the diagonal, the sum of values starting from the border, equals to the value in the next row, in the opposite direction of the diagonal.”

Pascal Triangle Hockey Edited
Hockey Stick Identity

It is quite clear from the figure that, the separate sums form individual hockey sticks.


Fibonacci Numbers

The Pascal’s Triangle is related to many sequences like Fibonacci Numbers, Catalan Numbers, Triangular Numbers, etc. To obtain the Fibonacci numbers, we first need to indent the numbers to the left side and then add up numbers along the diagonal.

Pascals Triangle Fibonacci Edited
Pascal’s triangle with Fibonacci numbers

There are too many stunning concepts related to Pascal’s triangle to cover in this article. Curious readers can search for topics like Sierpinski’s triangle and Lozanic’s Triangle, and their connection with Pascal’s triangle.


Efficient Implementation of Pascal’s Triangle in C++

#include<iostream>
using namespace std;

// Function to print the Pascal's Triangle
void print_pascal(int row_num){

	// Loop to print each row
	for(int n = 1; n <= row_num; n++){

		// Loop to print spaces for triangular display
		for(int r = 1; r < row_num-n+1; r++)
			cout<<"  ";

		// Loop to print values using Combinations logic
		int val = 1;
		for(int r = 1; r <= n; r++){
			cout<<val<<"   ";
			
			val = val * (n - r)/r;
		}
		cout<<endl;
	}
}

// The main Function
int main(){

	// Number of rows for Pascal's Triangle
	int row_num = 9;

	//Function call to print Pascal's Triangle
	print_pascal(row_num);

	return 1;
}

Output:

                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   

The insight behind the implementation

The logic for the implementation given above comes from the Combinations property of Pascal’s Triangle. We know that each value in Pascal’s triangle denotes a corresponding nCr value.

Each successive combination value can be calculated using the equation below.

Pascal Triangle Comb Equation
Relation with successive combination values

In the inner loop of the above code, the 'val' variable keeps updating with every successive combination value.


Conclusion

At first, Pascal’s Triangle may look like any trivial numerical pattern, but only when we examine its properties, we can find amazing results and applications.

We hope this article was as interesting as Pascal’s Triangle. Feel free to comment below for any queries or feedback.

Read further: Trie Data Structure in C++

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages