Manifesto | Index | What's new | rss feed

| Bookmark |

| Follow us

| Recommend | Contact |

Patterns in Pascal's Triangle

Pascal's Triangle conceals a huge number of various patterns, many discovered by Pascal himself and even known before his time.

Pascal's triangle

Pascal's Triangle is symmetric

In terms of the binomial coefficients, C(n, m) = C(n, n - m). This follows from the formula for the binomial coefficient

C(n, m) =
n!

m!(n - m)!

It is also implied by the construction of the triangle, i.e., by the interpretation of the entries as the number of ways to get from the top to a given spot in the triangle.

Some authors even considered a symmetric notation (in analogy with trinomial coefficients)

C(n, m) =

m s

where s = n - m.

The sum of entries in row n equals 2ⁿ

This is Pascal's Corollary 8 and can be proved by induction. The main point in the argument is that each entry in row n, say C(n, k) is added to two entries below: once to form C(n + 1, k) and once to form C(n + 1, k + 1) which follows from Pascal's Identity:

	C(n + 1, k)	= C(n, k - 1) + C(n, k),
	C(n + 1, k + 1)	= C(n, k) + C(n, k + 1).

For this reason, the sum of entries in row n + 1 is twice the sum of entries in row n. (This is Pascal's Corollary 7.)

As a consequence, we have Pascal's Corollary 9: In every arithmetical triangle each base exceeds by unity the sum of all the preceding bases. In other words, 2ⁿ - 1 = 2^n-1 + 2^n-2 + ... + 1.

There are well known sequences of numbers

Some of those sequences are better observed when the numbers are arranged in Pascal's form where because of the symmetry, the rows and columns are interchangeable.

Pascal's triangle in Pascal's form

The first row contains only 1s: 1, 1, 1, 1, ...
The second row consists of all counting numbers: 1, 2, 3, 4, ...
The third row consists of the triangular numbers: 1, 3, 6, 10, ...
The fourth row consists of tetrahedral numbers: 1, 4, 10, 20, 35, ...
The fifth row contains the pentatope numbers: 1, 5, 15, 35, 70, ...

"Pentatope" is a recent term. Regarding the fifth row, Pascal wrote that ... since there are no fixed names for them, they might be called triangulo-triangular numbers. Pentatope numbers exists in the 4D space and describe the number of vertices in a configuration of 3D tetrahedrons joined at the faces.

In the standard configuration, the numbers C(2n, n) belong to the axis of symmetry. Numbers C(2n, n) / (n + 1) are known as Catalan numbers.

Every two successive triangular numbers add up to a square: (n - 1)n/2 + n(n + 1)/2 = n².

Hockey Stick Pattern

In Pascal's words (and with a reference to his arrangement), In every arithmetical triangle each cell is equal to the sum of all the cells of the preceding row from its column to the first, inclusive (Corollary 2). In modern terms,

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

Note that on the right, the two indices in every binomial coefficient remain the same distance apart: n - m = (n - 1) - (m - 1) = ... This allows rewriting (1) in a little different form:

(1')	C(m + r + 1, m) = C(m + r, m) + C(m + r - 1, m - 1) + ... + C(r, 0).

The latter form is amenable to easy induction in m. For m = 0, C(r + 1, 0) = 1 = C(r, 0), the only term on the right. Assuming (1') holds for m = k, let m = k + 1:

	C(k + r + 2, k + 1)	= C(k + r + 1, k + 1) + C(k + r + 1, k)
		= C(k + r + 1, k + 1) + C(k + r, k) + C(k + r - 1, k - 1) + ... + C(r, 0).

Naturally, a similar identity holds after swapping the "rows" and "columns" in Pascal's arrangement: In every arithmetical triangle each cell is equal to the sum of all the cells of the preceding column from its row to the first, inclusive (Corollary 3).

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

where the second index is fixed.

Parallelogram Pattern

Parallelogram pattern

(3)	C(n + 1, m) - 1 = ∑C(k, j),

where k < n, j < m. In Pascal's words: In every arithmetic triangle, each cell diminished by unity is equal to the sum of all those which are included between its perpendicular rank and its parallel rank, exclusively (Corollary 4). This is shown by repeatedly unfolding the first term in (1).

Fibonacci Numbers

If we arrange the triangle differently, it becomes easier to detect the Fibonacci sequence:

another form of Pascal's triangle

The successive Fibonacci numbers are the sums of the entries on sw-ne diagonals:

	1	= 1
	1	= 1
	2	= 1 + 1
	3	= 1 + 2
	5	= 1 + 3 + 1
	8	= 1 + 4 + 3
	13	= 1 + 5 + 6 + 1

The Star of David

The following two identities between binomial coefficients are known as "The Star of David Theorems":

C(n-1, k-1)·C(n, k+1)·C(n+1, k) = C(n-1, k)·C(n, k-1)·C(n+1, k+1) and
gcd(C(n-1, k-1), C(n, k+1), C(n+1, k)) = gcd(C(n-1, k), C(n, k-1), C(n+1, k+1)).

The reason for the moniker becomes transparent on observing the configuration of the coefficients in the Pascal Triangle.

Star of David pattern in Pascal triangle