15,036,654 members
Articles / General Programming / Algorithms
Article
Posted 18 Aug 2014

37.6K views
13 bookmarked

# Algorithmic approaches to solving the Pascal's Triangle and the Newton's Binomial

Rate me:
Some suggestions of algorithms for solving the Pascal Triangle, addressing iterative, recursive and functional paradigms

## Introduction

The Pascal triangle is a sequence of natural numbers arranged in tabular form according to a formation rule.
Here's an example for a triangle with 9 lines, where the rows and columns have been numbered (zero-based) for ease of understanding:

Note that:

• All lines begins and ends with the number 1;
• Each line has one more element than its predecessor.

The triangle, actually, is a square matrix (T) where each element can be obtained, among others, in the following way, where L is the row index and C, the column index:

T(L,C) = 1, se C = 0 ou L = C
T(L,C) = T(L-1,C) + T(L-1,C-1), se L >= C  (Stifel's Relation)
(With L >= 0 and C >= 0)

Note also that the elements of the (nth + 1) row are the coefficients of expansion of (a + b) n. In other words, to obtain the coefficients of the development of the binomial (a + b) 2 simply look at the 3rd line from the triangle to write:

(a + b) 2 = 1a2 + 2ab +1b2

## A bit of History

The first known reference of the triangle is assigned to the Arabic Al-Karaji (953-1029). Subsequently, several mathematicians of various nationalities have made some kind of related work, of which, we quote the following:

• Omar Khayam (Persia, 1048-1131)
• Jia Xian (China, 1100-1109)
• Yang Hui (China, 1238-1298)
• Al-Kashi (Iran, 1380-1429)
• Petrus Apianus (Saxony, 1501-1552)
• Michael Stifel (Germany, 1487-1567)
• Nicolo Tartaglia (Italy, 1499-1577)

The French mathematician Blaise Pascal (1623-1667) undertook a systematic study of the regularity of the triangle published a document entitled "Treatise on Arithmetical Triangle," where he describes, among other things, "like the numbers on each line indicate how many different ways you can choose P objects from a collection of N objects ". That does not sound like combinatorics?

Pascal was a philosopher, physicist, theologian, writer, and still found time to invent the first digital calculator in 1642, in order to help his father, who was also a mathematician. So it is considered as one of the precursors of the invention of the computer.
In addition to studies around the triangle, Pascal left several works on geometry, foundations of calculus, probability, hydrodynamics, hydrostatic and many other areas.

The best known application of the triangle is on the coefficients of polynomial equations. However there are many other, of which we highlight the following:

• Fibonacci sequence;
• Potentiation;
• Etc.

After Pascal, other mathematicians such as Wallis, Newton and Leibnitz also resorted to interesting properties of this triangle.

## BackGround

To test the algorithms presented here, i suggest the following tools:

## Using The Code

The following are the algorithms to solve the Pascal Triangle through the iterative, recursive and functional paradigms. In all, we have the following variables:
L → index of the array line
C → index of the array column

### 1) Iterative algorithm

C++
```// Purpose: Printing the Pascal's triangle iteratively using the Stifel's Relation
// Parameter: The number of rows you want
// Language: C++
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <iostream>
#include <stdlib.h>
#include <iomanip> // Formatted output
using namespace std;
int main(int argc, char *argv[])
{
int N;
cout << "The Pascal's Triangle\n";
cout << "Enter the number of lines: ";
cin >> N;
int T[N][N];
// generates Triangle using the Stifel's Relation
for (int L = 0;(L<N);L++)
for (int C = 0;(C <= L);C++)
{
if ((C == 0) || (L == C))
T[L][C] = 1;
else
T[L][C] = T[L-1][C] + T[L-1][C-1];
}
// Print triangle
for (int L = 0;(L<N);L++)
{
for (int C = 0;(C<=L);C++)
{
cout << setw(6) << T[L][C];
}
cout << "\n";
}
return 0;
}```

Points of Interest:

1. Note here that we are disregarding the elements for which L <C.
2. This algorithm can be improved if we take into account that the elements of a line from the median are repeated so that T (L, L - C) = T (L, C)

### 2) Recursive Algorithm

```# Purpose: Printing the Pascal's Triangle recursively using the Stifel's Relation
# Parameter: The number of rows you want
# Language: Python 2.X.X
# Author: Jose Cintra (jose.cintra@html-apps.info)

def triangulo(n,k):

if (k == 0) or (k == n):
retorno = 1
else:
retorno = triangulo(n-1, k-1) + triangulo(n-1, k)
return retorno

print "The Pascal's Triangle"
num = int(raw_input('Enter the number of lines: '))
for n in range(0,num):
for k in range(0,n+1):
print triangulo(n, k),
print```

Points of Interest:

1. This recursive version is not the most efficient;
2. The "for" loop could also be done recursively, but for performance reasons, we prefer to keep it, otherwise we would have a recursive function call another.

### 3) Functional Algorithm

```-- Purpose: Printing the Pascal's Triangle through the functional paradigm

pascal :: Int -> [[Integer]]
triangulo = iterate (\row -> zipWith (+) ([0]++row) (row++[0])) [1]
pascal n = take n triangulo```

Point of Interest:

Functional languages ​​are mainly based on recursive list processing. This algorithm is actually an elegant solution, but still has performance issues

### 4) A Alternative Solution without arrays

The binomial coefficient can be interpreted as the number of ways to choose C elements from an L-element set. In combinatorial interpretation, L elements given C by C:

T(L,C) = L! / (C!(L - C)!

```{
Purpose: Printing the Coefficients of The Newton' Binomial
Language: Pascal
Author: Jose Cintra (jose.cintra@html-apps.info)
}

var L, C, power, coef: integer;
begin
writeln('The Newtons''s Binomial');
write('Enter the power of the binomial: ');
coef := 1;
L := power;
writeln('Coefficients:');
write(coef);
for C := 1 to L do
begin
coef := (coef * (L - C + 1)) div C;
write(coef:6);
end;
writeln;

end.```

Point of Interest:

This algorithm is more efficient because is not dependent of arrays or prior long processing.

## Conclusion

This is it!

The results presented by the above algorithms were formatted for numbers up to six digits. If you need larger numbers, change this setting.

As always, a point to be considered when we implement algorithms in conventional languages ​​is that the values ​​of the Triangle's elements tend to grow rapidly, causing overflow of the result. The solution is to adopt a library or language that supports arbitrary precision numbers. Functional languages​​, mostly, do not have this deficiency.

Hope this helps.  Questions and comments are welcome.

See you soon..

## Share

 Software Developer Brazil
I am a software developer focused on Mathematics, IoT and Games.
Homepage: HTML Apps
Blog: www.josecintra.com/blog

 First Prev Next
 Incorrect C++ code Marius Bancila16-Mar-15 13:10 Marius Bancila 16-Mar-15 13:10
 Re: Incorrect C++ code José Cintra20-Aug-15 2:29 José Cintra 20-Aug-15 2:29
 Re: Incorrect C++ code KarstenK20-Aug-15 4:14 KarstenK 20-Aug-15 4:14
 Re: Incorrect C++ code José Cintra20-Aug-15 6:01 José Cintra 20-Aug-15 6:01
 My rating of 5 with comments. Bill_Hallahan19-Aug-14 15:07 Bill_Hallahan 19-Aug-14 15:07
 The article contained: Copy Code `This recursive version is not the most efficient;` That comment makes me think you probably know the algorithm I mention below. I think this is the algorithm your Haskell program is using, although I don't know Haskell, so I can't be sure. The algorithm is to start with the first row, just a single 1, and for the next row, start with the 1, and then sum each two consecutive value, and then at the end add another 1. For the first row, there are no consecutive elements, so just write 1 1 for the second row, i.e., take the 1, and append a 1. Copy Code ``` 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1``` Each digit in the middle of the triangle is just the sum of the two digits it's below in the previous row. Starting with the 1, which remains unchanged, compute each consecutive two digit sum and append another 1 at the end. That recursive algorithm is both simple and fast. Pascal's Triangle is very cool! When each coefficient in a row is summed, the result is always a power-of-two. This is because each N digit binary number with K 'one' digits represents one instance of K out of N items. When the instances for all K instances from 0 to N are summed, this result thus equals the total number of all N digit binary numbers. I believe there is also a relationship to the Fibonacci numbers, but I forget what that relationship is.modified 7-Sep-14 19:57pm.
 Re: My rating of 5 with comments. José Cintra20-Aug-14 6:52 José Cintra 20-Aug-14 6:52
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Sep-21 7:07 Refresh 1