In mathematics, Pascal triangle is a triangular array of the binomial coefficients. It is named after the French mathematician Blaise Pascal in much of the Western world, although other mathematicians studied it centuries before him in India, Greece, Iran, China, Germany, and Italy.
The rows of Pascal triangle are conventionally enumerated starting with row n = 0 at the top. The entries in each row are numbered from the left beginning with k = 0 and are usually staggered relative to the numbers in the adjacent rows. A simple construction of the triangle proceeds in the following manner. On row 0, write only the number 1. Then, to construct the elements of following rows, add the number above and to the left with the number above and to the right to find the new value. If either the number to the right or left is not present, substitute a zero in its place. For example, the first number in the first row is 0 + 1 = 1, whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row.
In this post I would be using a double dimension array to store the Pascal Triangle and then I would display the triangle holding the elements of the Pascal Triangle. The first version of the Java program to generate and display the Pascal Triangle, with emphasis only on the generation aspect, is as follows:
class PascalTriangle{
public static void PascalTriangle( int numOfRows ){
int [][]a = new int[ numOfRows ][ numOfRows ];
for( int row = 0; row < a.length ; row++ ){
a[ row ][ 0 ] = 1;
a[ row ][ row ] = 1;
for( int col = 1; col <= row; col++ ){
a[ row ] [ col ] = a[ row - 1][ col - 1] + a[ row -1][ col ];
}
}
display2DArray( a );
}
public static void display2DArray( int [][]arr ){
for( int row = 0; row < arr.length ; row++ ){
for( int col = 0; col < arr[ row ].length ; col++ ){
System.out.print( arr[ row ][ col ] );
if( col < arr[ row ].length - 1 ){
System.out.print("\t");
}
}
System.out.println( );
}
}
public static void main( String args[] ){
generatePascalTriangle( 6 );
}
}
The output of the above program would be as follows:
1 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 1 3 3 1 0 0 1 4 6 4 1 0 1 5 10 10 5 1
Don’t worry about the formatting aspect right now. That we will resolve later. Concentrate on the filling up of array element of the double dimension array a. Line number 3, is creating a square double dimension array whoose size is equal to the argument provided to the function gneratePascalTriangle( ). Line number 5 is for initializing the first column of the double dimension array to 1 and line number 6 is for initializing the diagonal elements of the double dimension array to 1. The function of the line number 8, is to computer the total of the elements diagonally up-left and the element just above the current element. As the output show, the array is now storing the correct elements in their respective array elements. The functioning of the function is relatively straightforward and I had already discussed it on a separate post on double dimension array. Also notice that in the above output the upper triangular portion of the square array is filled with zeros and is resulting in wasted storage because we don’t need that portion of the array. This problem can be removed, if we create a triangular (zagged) array as discussed in my earlier post Non-rectangular double dimension array. Using the technique described in the above mentioned post the modified Java program for generating a Pascal Triangle would be as follows:
class PascalTriangle{
public static void generatePascalTriangle( int numOfRows ){
int a[][] = new int[ numOfRows ][];
for( int row=0; row < a.length ; row++ ){
a[ row ] = new int[ row + 1 ];
}
a[ 0 ][ 0 ] = 1;
a[ 1 ][ 0 ] = 1;
a[ 1 ][ 1 ] = 1;
for( int row = 2; row < a.length ; row++ ){
a[ row ][ 0 ] = 1;
a[ row ][ row ] = 1;
for( int col = 1; col < row; col++ ){
a[ row ] [ col ] = a[ row - 1][ col - 1] + a[ row -1][ col ];
}
}
display2DArray( a );
}
public static void display2DArray( int [][]arr ){
for( int row = 0; row < arr.length ; row++ ){
for( int col = 0; col < arr[ row ].length ; col++ ){
System.out.print( arr[ row ][ col ] );
if( col < arr[ row ].length - 1 ){
System.out.print("\t");
}
}
System.out.println( );
}
}
public static void main( String args[] ){
generatePascalTriangle( 6 );
}
}
In the above program, line numbers 3-6 has been modified to create a triangular array. Line numbers 7-9, has been modified to initialize the first two rows of the triangular matrix to 1 explicitly because now there are no element above the diagonal elements and hence in order to avoid ArrayIndexOutOfBoundsException we must avoid any reference to the non-existent elements above the primary diagonal. The above code would give the following output:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Let us now concentrate on the formatting aspect of the Pascal Triangle. Only two changes are required. Firstly, we have to add a loop to insert the ‘tab’ characters (\t) before the start of each line. Secondly, we have to insert one extra ‘tab’ character (\t) in between each element. The final code to generate the Pascal Triangle for a given number of rows would be as follows:
class PascalTriangle{
public static void generatePascalTriangle( int numOfRows ){
int a[][] = new int[ numOfRows ][];
for( int row=0; row < a.length ; row++ ){
a[ row ] = new int[ row + 1 ];
}
a[ 0 ][ 0 ] = 1;
a[ 1 ][ 0 ] = 1;
a[ 1 ][ 1 ] = 1;
for( int row = 2; row < a.length ; row++ ){
a[ row ][ 0 ] = 1;
a[ row ][ row ] = 1;
for( int col = 1; col < row; col++ ){
a[ row ] [ col ] = a[ row - 1][ col - 1] + a[ row -1][ col ];
}
}
display2DArray( a );
}
public static void display2DArray( int [][]arr ){
for( int row = 0; row < arr.length ; row++ ){
for( int space =1 ; space < arr.length-row; space++ ){
System.out.print("\t");
}
for( int col = 0; col < arr[ row ].length ; col++ ){
System.out.print( arr[ row ][ col ] );
if( col < arr[ row ].length - 1 ){
System.out.print("\t\t");
}
}
System.out.println( );
}
}
public static void main( String args[] ){
generatePascalTriangle( 6 );
}
}
In the above code, notice the highlighted lines, which are inserting the tab character (\t) at the required places. The final output would be as follows:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.