15,040,212 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:
18 Aug 2014CPOL4 min read
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..

## About the Author

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

## Comments and Discussions

 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
 Re: My rating of 5 with comments. José Cintra20-Aug-14 6:52 José Cintra 20-Aug-14 6:52
 I agree with you, the algorithm is fast, but the implementations of functional languages ​​in general are slower than imperative languages​​. What I meant was about the comparison with languages ​​like Pascal and C for the same algorithm. Luckily, this situation is changing ... The triangle holds many mysteries and new discoveries will yet be found. I did not know about the correlation with the binary numbers. Thanks for your comments.
 Last Visit: 31-Dec-99 18:00     Last Update: 26-Sep-21 21:25 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.