Pascal Triangle

Introduction

Pascal's Triangle, named after the French mathematician Blaise Pascal is a triangular array pattern of the binomial coefficients that arise in probability theory, combinatorics, and algebra.

Source: study tonight

As you can see in the above pattern, the triangle is constructed by placing the '1' along the left and right edges. The triangle can be formed from the top by adding the two numbers just above the left and right of each position. Therefore the third row is 1 2 1, and the fourth row will be 1 4 6 1, the fifth row is 1 5 10 10 5 1, and so on. For the first row, the coefficient for the expansion of (x+y)^0 = 1, the second row(1 1) the coefficient for (x+y)^1 = x+y, and so on. 

Important Notes:

• The Pascals triangle elements can be found by finding the sum of the two adjoint elements in the preceding row.
• The sum of values in the nth row is 2n.

Also see, Euclid GCD Algorithm

Problem Statement

We will be provided with a number n, for which we have to form a pascal triangle following its properties. The left and the right edges will be '1'. As you can see in the below picture, the first row contributes to building the second row by adding the elements of the first row. The third row has been built up with the help of the second row and so on. The below pascal triangle is for n=5 as we have 5 rows. Here we can observe that the number of entries in each row depends on the row number.

Resource: tutorial cup

For the ith row, there are i elements, where i≥1. jth element of the ith row is equal to i−1Cj−1 where1≤j≤i.

Other properties:

• The corner elements of each row are always equal to 1(i−1C0 and i−1Ci−1, i≥1).
• All the other (i,j) elements of the triangle (where i≥3 and 2≤j≤i−1) are equal to the sum of (i−1,j−1)th and (i−1,j)th element.

We can easily calculate the next row by iteratively adding adjacent values of the current row. This iterative process of generating a pascal triangle has been considered a dynamic programming approach wherein we construct each row based on the previous row.

Before stepping to the problem's solution- Pascal Triangle, try to give a shot by yourself.