Construction of Pascal's Triangle

Pascal's triangle - a fascinating mathematical object - admits several constructions. We shall start with a triangular configuration of dots.

dots in triangular configuration

We shall imagine traveling from the top dot down to the dots below along the arrows, i.e., at every dot on our itinerary we are given a choice whether to proceed to the right or to the left dots immediately below.

graph on dots in triangular configuration

So that at every dot we have two choices whether to step right or left. We shall call the steps "+" (or +1) for the right move and "-" (or -1) for the left one. The question we shall answer is, how many itineraries are there that join the top dot to a given dot below? The rows of the triangle arrangement of dots are numbered from 0 on and so are the dots in any row:

enumeration of dots in triangular configuration

Thus every dot in the arrangement is assigned a couple of coordinates n, m, where n is the row the dot is in and m is its location in that row. Observe that in row n there are n + 1 dots: one dot (0, 0) in the first row, two dots (1, 0) and (1, 1) in the second, and so on. The number of itineraries from the top dot (0, 0) to the dot (n, m) is denoted C(n, m). The task is to determine C(n, m) for n ≥ 0 and 0 ≤ m ≤ n.

A few values can be found immediately. For example,

(1)	C(n, 0) = C(n, n) = 1,

n > 0, because there is only one way from the top dot to each of the dots at the ends of their rows. Although getting from dot (0, 0) to itself involves no stepping down, we shall define C(0, 0) = 1, as there is only one way to stay in place.

Concerning all other dots, we can make an important observation: the only way to reach dot (n, m) is by first reaching one of the two dots immediately above it. These are the dots (n - 1, m - 1) (up and to the left) and (n - 1, m) (up and to the right). Any path from the top to (n - 1, m - 1) defines uniquely a path to (n, m), for there is just one way to get from (n - 1, m - 1) to (n, m). The same of course holds for the paths to (n - 1, m), with the result that

(2)	C(n, m) = C(n - 1, m - 1) + C(n - 1, m).

This formula can be applied to the dots in successive rows. For example, to complete row 2, i.e., with n = 2, we only need to determine C(2, 1) for we already know that C(2, 0) = C(2, 2) = 1. According to our formula,

C(2, 1) = C(1, 0) + C(1, 1) = 1 + 1 = 2.

Next we complete row three:

C(3, 1) = C(2, 0) + C(2, 1) = 1 + 2 = 3, and
C(3, 2) = C(2, 1) + C(2, 2) = 2 + 1 = 3

In row four, we obtain C(4, 1) = 4, C(4, 2) = 6, C(4, 3) = 4.

The applet below shows the entries for C(n, m) for a few first rows of the triangle. (The applet also displays two additional arrangements, of which one was preferred by Pascal himself.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

There is no mistaking it: the entries in Pascal's triangle are the binomial coefficients, "n choose m". There are at least two reasons why this is so.

First, we may argue that, given the "boundary" conditions (1), the relation (2) determine uniquely the rest of the triangle. For the binomial coefficients, (2), which is known as Pascal's identity, can be verified algebraically. So that the entries in the triangle and the binomial coefficients both satisfy (1) and (2) and thus coincide.

Second, we may directly count the number of ways of getting from (0, 0) to (n, m). However we do that, we need n steps to get from row 0 to row n. Of these n steps, m steps must be +1 and n - m steps -1. Thus the question is of the number of distinct strings of m symbols "+" and n - m symbols "-", or, in other words, the number of possible selections of m items out of n items. Here we associate items with rows of the triangle at each of which a decision is made whether to proceed left or right. Out of n rows we path on the way from (0, 0) to (n, m) we choose m to make a right turn, leaving n - m where we make a left turn. This number is called a combination of "n choose m" and is given by the binomial coefficient C(n, m).

References

J. H. Conway and R. K. Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
Great Books of the Western World, v 33, Encyclopaedia Britannica, Inc., 1952.
P. Hilton, D. Holton, J. Pederson, Mathematical Reflections, Springer Verlag, 1997
A. R. Kanga, Number Mosaics, World Scientific Co., 1995.
J. A. Paulos, Beyond Numeracy, Vintage Books, 1992
D. E. Smith, A Source Book in Mathematics, Dover, 1959
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987

Pascal's Triangle and the Binomial Coefficients

71536363