Construction of Pascal's Triangle
Pascal's triangle - a fascinating mathematical object - admits several constructions. We shall start with a triangular configuration of dots.
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.
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:
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
A few values can be found immediately. For example,
|(1)||C(n, 0) = C(n, n) = 1,|
Concerning all other dots, we can make an important observation: the only way to reach dot
|(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
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.)
|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
- 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
Copyright © 1996-2018 Alexander Bogomolny