Arrays - Building Java Programs: A Back to Basics Approach - page 474

y) 2 x 2 y 2

(x 2xy

y) 3 x 3 3x 2 y 3xy 2 y 3

(x

y) 4 x 4 4x 3 y 6x 2 y 2 4xy 3 y 4

(x

If you pull out just the coefficients, you get the following values:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

These rows of numbers form a five-row Pascal's triangle. One of the properties of
the triangle is that if you are given any row, you can use it to compute the next row.
For example, let's start with the last row from the preceding triangle:

1 4 6 4 1

We can compute the next row by adding adjacent pairs of values together. So,
we add together the first pair of numbers (1 4), then the second pair of numbers

(4 6), and so on:

5 10 10 5

(1 + 4) (4 + 6) (6 + 4) (4 + 1)

5 10 10 5

Then we put a 1 at the front and back of this list of numbers, and we end up with
the next row of the triangle:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

This property of the triangle provides a technique for computing it. We can con-
struct it row by row, computing each new row from the values in the previous row. In
other words, we write the following loop (assuming that we have a two-dimensional
array called triangle in which to store the answer):

for (int i = 0; i < triangle.length; i++) {
construct triangle[i] using triangle[i - 1].

}