384 Pascal’s triangle

Discovering Pascal’s triangle

Also notice, in order to reach any particular cell,

one has two options: either head to the cell directly

above it and take a final step southward, or head to the

cell just to its left and take a final step eastward. Thus

the number of paths to a particular cell is the sum of

the two counts for the cells above it and to its left. This

is the defining feature of Pascal’s triangle.

We can say more: the numbers in each cell count

the number of ways to arrange a fixed number of Es

and Ss. For instance, the number below the circled cell

in the picture will be 20. This shows that there must be

20 distinct ways to arrange three Es and three Ss. Alter-

natively, we could determine this count by asking: How

many ways are there to select three places (the positions

that the letter E will lie) among a string of six positions?

The answer to this question is in the

COMBINATORIAL

COEFFICIENT

. Counting the top row of

Pascal’s triangle as row zero and the first entry of each

row the zeroth entry of that row, we now see that the

kth entry in the nth row of Pascal’s triangle corresponds

to combinatorial coefficient , which equals the

number of ways to arrange kEs and (n– k) Ss as

a string of nletters. We have:

Pascal’s triangle is the triangular array of all

combinatorial coefficients.

The

BINOMIAL THEOREM

shows that the combinatorial

coefficients also appear in expansions of expressions of

the form (x+ y)n. We have:

The entries in the nth row of Pascal’s triangle

are precisely the coefficients that appear in the

expansion of (x+ y)n.

For instance, we have (x+ y)2= x2+ 2xy + y2, (x+ y)3

= x3+ 3x2y+ 3xy2+ y3, and (x+ y)4= x4+ 4x3y

+6x2y2+ 4xy3+ y4.

Pascal’s triangle possesses a number of remarkable

properties. We list just a sample.

1. The entries in the nth row of Pascal’s triangle sum

to 2n.

For instance, 1 = 1, 1 + 1 = 2, 1 + 2 + 1 = 4,

1 + 3 + 3 + 1 = 8, and 1 + 4 + 6 + 4 + 1 = 16. This

follows from expanding the quantity (1 + 1)n.

2. The alternating sum of the entries of each row of

Pascal’s triangle is zero.

For instance, 1 – 1 = 0, 1 – 2 + 1 = 0, 1 – 3 +

3– 1 = 0, and 1 – 4 + 6 – 4 + 1 = 0. This follows

from expanding the quantity (1 + (–1))n.

It is worth observing that both of these results

can also be obtained by noting that each entry in

Pascal’s triangle is the sum of two entries in the pre-

ceding row. Thus the direct or the alternating sum

of the entries in one row corresponds to a sum that

considers each entry in the previous row twice.

3. The F

IBONACCI NUMBERS

appear as sums of entries

in certain diagonals of Pascal’s triangle.

To explain: the apex 1 constitutes the first diag-

onal. The first 1 in row one constitutes the second

diagonal. The first 1 in row two and the final 1 in

row three constitute the third diagonal. (Note that

1 + 1 = 2.) Continuing in this way, we see that 1 + 3 +

1 = 5, 1 + 4 + 3 = 8, and 1 + 5 + 6 + 1 = 13. By

writing each term in the diagonal as the sum of the

two entries above it, we see that the sum of entries

in one diagonal matches the sums of entries of the

previous two diagonals.

4. Each row of Pascal’s triangle corresponds to the dig-

its of a power of 11.

For instance, 110= 1, 111= 11, 112= 121,

113= 1,331, and 114= 14,461. This follows from

expanding the quantity (10 + 1)n. If we were not

required to carry digits when performing multiplica-

tions, this correspondence would remain exact.

5. Select any entry N in Pascal’s triangle and circle all

the entries that lie in the parallelogram that has N

and the apex as opposite vertices. Then the sum of

all entries in that parallelogram is 1 less than the

number M directly below N two rows down.