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

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) ⁿ. In other words, to obtain the coefficients of the development of the binomial (a + b) ² simply look at the 3rd line from the triangle to write:

(a + b) ² = 1a² + 2ab +1b² 

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;
• Addition;
• 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:

C++ Language
Python Language
Pascal Language
Haskell Language

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 

// 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
-- Language: Haskell 

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: ');
readln(power);
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.

Download the source code here

See you soon..