Pascal's triangle

2008/9 Schools Wikipedia Selection. Related subjects: Mathematics

$\begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&1&&3&&3&&1\\ &1&&4&&6&&4&&1 \end{matrix}$

The first five rows of Pascal's triangle

In mathematics, Pascal's triangle is a geometric arrangement of the binomial coefficients in a triangle. It is named after Blaise Pascal in much of the western world, although other mathematicians studied it centuries before him in India, Persia, China, and Italy. The rows of Pascal's triangle are conventionally enumerated starting with row zero, and the numbers in odd rows are usually staggered relative to the numbers in even rows. A simple construction of the triangle proceeds in the following manner. On the zeroth row, write only the number 1. Then, to construct the elements of following rows, add the number directly above and to the left with the number directly above and to the right to find the new value. If either the number to the right or left is not present, substitute a zero in its place. For example, the first number in the first row is 0 + 1 = 1, whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row.

Each number in the triangle is the sum of the two directly above it.

This construction is related to the binomial coefficients by Pascal's rule, which states that if

${n \choose k} = \frac{n!}{k! (n-k)!}$

is the kth binomial coefficient in the binomial expansion of (x + y)ⁿ, where n! is the factorial of n, then

${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$

for any nonnegative integer n and any integer k between 0 and n.

Pascal's triangle has higher dimensional generalizations. The three-dimensional version is called Pascal's pyramid or Pascal's tetrahedron, while the general versions are called Pascal's simplices — see also pyramid, tetrahedron, and simplex.

The triangle

Below are rows zero to sixteen of Pascal's triangle:

                                                1
                                             1     1
                                          1     2     1
                                       1     3     3     1
                                    1     4     6     4     1
                                 1     5    10    10     5     1
                              1     6    15    20    15     6     1
                           1     7    21    35    35    21     7     1
                        1     8    28    56    70    56    28     8     1
                     1     9    36    84    126   126   84    36     9     1
                  1    10    45    120   210   252   210   120   45    10     1
               1    11    55    165   330   462   462   330   165   55    11     1
            1    12    66    220   495   792   924   792   495   220   66    12     1
         1    13    78    286   715  1287  1716  1716  1287   715   286   78    13     1
      1    14    91    364  1001  2002  3003  3432  3003  2002  1001   364   91    14     1
   1    15    105  455   1365  3003  5005  6435  6435  5005  3003  1365   455   105   15     1
1    16    120   560  1820  4368  8008  11440 12870 11440 8008  4368  1820   560   120   16     1

Pascal's triangle and binomial expansions

Pascal's triangle determines the coefficients which arise in binomial expansions. For an example, consider the expansion

(x + y)² = x² + 2xy + y² = 1x²y⁰ + 2x¹y¹ + 1x⁰y².

Notice the coefficients are the numbers in row two of Pascal's triangle: 1, 2, 1. In general, when a binomial like x + y is raised to a positive integer power we have:

(x + y)ⁿ = a₀xⁿ + a₁xⁿ⁻¹y + a₂xⁿ⁻²y² + … + a_n−1xyⁿ⁻¹ + a_nyⁿ,

where the coefficients a_i in this expansion are precisely the numbers on row n of Pascal's triangle. In other words,

$a_i = {n \choose i}.$

This is the binomial theorem.

Notice that entire right diagonal of Pascal's triangle corresponds to the coefficient of yⁿ in these binomial expansions, while the next diagonal corresponds to the coefficient of xy^n-1 and so on.

To see how the binomial theorem relates to the simple construction of Pascal's triangle, consider the problem of calculating the coefficients of the expansion of (x + 1)ⁿ⁺¹ in terms of the corresponding coefficients of (x + 1)ⁿ (setting y = 1 for simplicity). Suppose then that

$(x+1)^n=\sum_{i=0}^n a_i x^i.$

Now

$(x+1)^{n+1} = (x+1)(x+1)^n = x(x+1)^n + (x+1)^n = \sum_{i=0}^n a_i x^{i+1} + \sum_{i=0}^n a_i x^i.$

The two summations can be reorganized as follows:

$\begin{align} & \sum_{i=0}^{n } a_{i } x^{i+1} + \sum_{i=0}^n a_i x^i \\ & {} = \sum_{i=1}^{n+1} a_{i-1} x^{i } + \sum_{i=0}^n a_i x^i \\ & {} = \sum_{i=1}^{n } a_{i-1} x^{i } + \sum_{i=1}^n a_i x^i + a_0x^0 + a_{n}x^{n+1} \\ & {} = \sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + a_0x^0 + a_{n}x^{n+1} \\ & {} = \sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + x^0 + x^{n+1} \end{align}$

(because of how raising a polynomial to a power works, a₀ = a_n = 1).

We now have an expression for the polynomial (x + 1)ⁿ⁺¹ in terms of the coefficients of (x + 1)ⁿ (these are the a_is), which is what we need if we want to express a line in terms of the line above it. Recall that all the terms in a diagonal going from the upper-left to the lower-right correspond to the same power of x, and that the a-terms are the coefficients of the polynomial (x + 1)ⁿ, and we are determining the coefficients of (x + 1)ⁿ⁺¹. Now, for any given i not 0 or n + 1, the coefficient of the xⁱ term in the polynomial (x + 1)ⁿ⁺¹ is equal to a_i (the figure above and to the left of the figure to be determined, since it is on the same diagonal) + a_i−1 (the figure to the immediate right of the first figure). This is indeed the simple rule for constructing Pascal's triangle row-by-row.

It is not difficult to turn this argument into a proof (by mathematical induction) of the binomial theorem.

An interesting consequence of the binomial theorem is obtained by setting both variables x and y equal to one. In this case, we know that $(1 + 1) n = 2 n$ , and so

${n \choose 0} + {n \choose 1} + \cdots +{n \choose n-1} + {n \choose n} = 2^n.$

In other words, the sum of the entries in the nth row of Pascal's triangle is the nth power of 2.

Patterns and properties

Pascal's triangle has many properties and contains many patterns of numbers.

The diagonals

Some simple patterns are immediately apparent in the diagonals of Pascal's triangle:

The diagonals going along the left and right edges contain only 1's.
The diagonals next to the edge diagonals contain the natural numbers in order.
Moving inwards, the next pair of diagonals contain the triangular numbers in order.
The next pair of diagonals contain the tetrahedral numbers in order, and the next pair give pentatope numbers. In general, each next pair of diagonals contains the next higher dimensional "d- simplex" numbers, which can be defined as

$\textrm{tri}_1(n) = n \quad\mbox{and}\quad \textrm{tri}_{d}(n) = \sum_{i=1}^n \mathrm{tri}_{d-1}(i).$

An alternative formula is as follows:

$\textrm{tri}_d(n)=\begin{cases} 1 & \mbox{if } d=0 \\ n & \mbox{if } d=1 \\ \displaystyle \frac{1}{d!}\prod_{k=0}^{d-1} (n+k) & \mbox{if } d\ge 2.\end{cases}$

The geometric meaning of a function tri_d is: tri_d(1) = 1 for all d. Construct a d- dimensional triangle (a 3-dimensional triangle is a tetrahedron) by placing additional dots below an initial dot, corresponding to tri_d(1) = 1. Place these dots in a manner analogous to the placement of numbers in Pascal's triangle. To find tri_d(x), have a total of x dots composing the target shape. tri_d(x) then equals the total number of dots in the shape. A 1-dimensional triangle is simply a line, and therefore tri₁(x) = x, which is the sequence of natural numbers. The number of dots in each layer corresponds to tri_d − 1(x).

Sierpinski triangle

Other patterns and properties

The pattern obtained by coloring only the odd numbers in Pascal's triangle closely resembles the fractal called Sierpinski triangle, and this resemblance becomes more and more accurate as more rows are considered; in the limit, as the number of rows approaches infinity, the resulting pattern is the Sierpinski triangle. More generally, numbers could be colored differently according to whether or not they are multiples of 3, 4, etc.; this results in other patterns and combinations.

Imagine each number in the triangle is a node in a grid which is connected to the adjacent numbers above and below it. Now for any node in the grid, count the number of paths there in the grid (without backtracking) which connect this node to the top node (1) of the triangle. The answer is the Pascal number associated to that node. The interpretation of the number in Pascal's Triangle as the number of paths to that number from the tip means that on a Plinko game board shaped like a triangle, the probability of winning prizes nearer the centre will be higher than winning prizes on the edges.

The value of each row, if each number in it is considered as a decimal place and numbers larger than 9 are carried over accordingly, is a power of 11 (specifically, 11ⁿ, where n is the number of the row). For example, row two reads '1, 2, 1', which is 11² (121). In row five, '1, 5, 10, 10, 5, 1' is translated to 161051 after carrying the values over, which is 11⁵. This property is easily explained by setting x = 10 in the binomial expansion of (x + 1)^{row number}, and adjusting the values to fit in the decimal number system.

More subtle patterns

There are also more surprising, subtle patterns. From a single element of the triangle, a more shallow diagonal line can be formed by continually moving one element to the right, then one element to the bottom-right, or by going in the opposite direction. An example is the line with elements 1, 6, 5, 1, which starts from the row 1, 3, 3, 1 and ends three rows down. Such a "diagonal" has a sum that is a Fibonacci number. In the case of the example, the Fibonacci number is 13:

                                       1
                                    1     1
                                 1     2     1
                              1  →  3 ↓   3     1
                           1     4    →6  →  4 ↓   1
                        1     5     10    10   →5  →  1 ↓
                     1  →  6 ↓   15    20    15    6    →1
                   1     7    →21    35    35    21    7     1
                1     8     28    56    70    56    28    8     1
              1     9     36    84    126   126   84    36    9     1
            1     10    45    120   210   252   210   120   45    10    1
          1     11    55    165   330   462   462   330   165   55    11    1
        1     12    66    220   495   792   924   792   495   220   66    12    1
      1     13    78    286   715   1287  1716  1716  1287  715   286   78    13    1
    1    14     91   364   1001  2002  3003  3432  3003  2002  1001   364   91    14    1 
  1    15   105   455   1365   3003  5005  6435  6435  5005  3003  1365  455   105   15    1
1    16  120   560   1820  4368  8008 11440 12870 11440  8008  4368  1820   560   120   16   1

The second highlighted diagonal has a sum of 233. The numbers 'skipped over' between the move right and the move down-right also sum to Fibonacci numbers, being the numbers 'between' the sums formed by the first construction. For example, the numbers skipped over in the first highlighted diagonal are 3, 4 and 1, making 8.

In addition, if row m is taken to indicate row $(n + 1)$ , the sum of the squares of the elements of row m equals the middle element of row $(2 m - 1)$ . For example, $12 + 4 2 + 6 2 + 4 2 + 1 2 = 70$ . In general form:

$\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}.$

Another interesting pattern is that on any row m, where m is odd, the middle term minus the term two spots to the left equals a Catalan number, specifically the (m + 1)/2 Catalan number. For example: on row 5, 6 − 1 = 5, which is the 3^rd Catalan number, and (5 + 1)/2 = 3.

Also, the sum of the elements of row m is equal to 2^m−1. For example, the sum of the elements of row 5 is $1 + 4 + 6 + 4 + 1 = 16$ , which is equal to $24 = 16$ . This follows from the binomial theorem proved above, applied to (1 + 1)^m−1.

Some of the numbers in Pascal's triangle correlate to numbers in Lozanić's triangle.

Another interesting property of Pascal's triangle is that in rows where the second number (the 1st number following 1) is prime, all the terms in that row except the 1s are multiples of that prime.

Binomial matrix as matrix exponential (illustration for 5×5 matrices). All the dots represent 0.

The matrix exponential

Due to its simple construction by factorials, a very basic representation of Pascal's triangle in terms of the matrix exponential can be given: Pascal's triangle is the exponential of the matrix which has the sequence 1, 2, 3, 4, … on its subdiagonal and zero everywhere else.

Geometric properties

Pascal's triangle can be used as a lookup table for the number of arbitrarily dimensioned elements within a single arbitrarily dimensioned version of a triangle (known as a simplex). For example, consider the 3rd line of the triangle, with values 1, 3, 3, 1. A 2-dimensional triangle has one 2-dimensional element (itself), three 1-dimensional elements (lines, or edges), and three 0-dimensional elements ( vertices, or corners). The meaning of the final number (1) is more difficult to explain (but see below). Continuing with our example, a tetrahedron has one 3-dimensional element (itself), four 2-dimensional elements (faces), six 1-dimensional elements (edges), and four 0-dimensional elements (vertices). Adding the final 1 again, these values correspond to the 4th row of the triangle (1, 4, 6, 4, 1). Line 1 corresponds to a point, and Line 2 corresponds to a line segment (dyad). This pattern continues to arbitrarily high-dimensioned hyper-tetrahedrons (simplices).

To understand why this pattern exists, one must first understand that the process of building an n-simplex from an (n − 1)-simplex consists of simply adding a new vertex to the latter, positioned such that this new vertex lies outside of the space of the original simplex, and connecting it to all original vertices. As an example, consider the case of building a tetrahedron from a triangle, the latter of whose elements are enumerated by row 3 of Pascal's triangle: 1 face, 3 edges, and 3 vertices (the meaning of the final 1 will be explained shortly). To build a tetrahedron from a triangle, we position a new vertex above the plane of the triangle and connect this vertex to all three vertices of the original triangle.

The number of a given dimensional element in the tetrahedron is now the sum of two numbers: first the number of that element found in the original triangle, plus the number of new elements, each of which is built upon elements of one fewer dimension from the original triangle. Thus, in the tetrahedron, the number of cells (polyhedral elements) is 0 (the original triangle possesses none) + 1 (built upon the single face of the original triangle) = 1; the number of faces is 1 (the original triangle itself) + 3 (the new faces, each built upon an edge of the original triangle) = 4; the number of edges is 3 (from the original triangle) + 3 (the new edges, each built upon a vertex of the original triangle) = 6; the number of new vertices is 3 (from the original triangle) + 1 (the new vertex that was added to create the tetrahedron from the triangle) = 4. This process of summing the number of elements of a given dimension to those of one fewer dimension to arrive at the number of the former found in the next higher simplex is equivalent to the process of summing two adjacent numbers in a row of Pascal's triangle to yield the number below. Thus, the meaning of the final number (1) in a row of Pascal's triangle becomes understood as representing the new vertex that is to be added to the simplex represented by that row to yield the next higher simplex represented by the next row. This new vertex is joined to every element in the original simplex to yield a new element of one higher dimension in the new simplex, and this is the origin of the pattern found to be identical to that seen in Pascal's triangle.

A similar pattern is observed relating to squares, as opposed to triangles. To find the pattern, one must construct an analog to Pascal's triangle, whose entries are the coefficients of (x + 2)^{Row Number}, instead of (x + 1)^{Row Number}. There are a couple ways to do this. The simpler is to begin with Row 0 = 1 and Row 1 = 1, 2. Proceed to construct the analog triangles according to the following rule:

${n \choose k} = 2\times{n-1 \choose k-1} + {n-1 \choose k}.$

That is, choose a pair of numbers according to the rules of Pascal's triangle, but double the one on the left before adding. This results in:

                             1
                         1       2
                     1       4       4
                 1       6       12      8
             1       8       24      32      16
         1       10      40      80      80       32
     1       12      60      160     240     192       64
 1       14      84      280     560     672      448       128

The other way of manufacturing this triangle is to start with Pascal's triangle and multiply each entry by 2^k, where k is the position in the row of the given number. For example, the 2nd value in row 4 of Pascal's triangle is 6 (the slope of 1s corresponds to the zeroth entry in each row). To get the value that resides in the corresponding position in the analog triangle, multiply 6 by 2^{Position Number} = 6 × 2² = 6 × 4 = 24. Now that the analog triangle has been constructed, the number of elements of any dimension that compose an arbitrarily dimensioned cube (called a hypercube) can be read from the table in a way analogous to Pascal's triangle. For example, the number of 2-dimensional elements in a 2-dimensional cube (a square) is one, the number of 1-dimensional elements (sides, or lines) is 4, and the number of 0-dimensional elements (points, or vertices) is 4. This matches the 2nd row of the table (1, 4, 4). A cube has 1 cube, 6 faces, 12 edges, and 8 vertices, which corresponds to the next line of the analog triangle (1, 6, 12, 8). This pattern continues indefinitely.

To understand why this pattern exists, first recognize that the construction of an n-cube from an (n − 1)-cube is done by simply duplicating the original figure and displacing it some distance (for a regular n-cube, the edge length) orthogonal to the space of the original figure, then connecting each vertex of the new figure to its corresponding vertex of the original. This initial duplication process is the reason why, to enumerate the dimensional elements of an n-cube, one must double the first of a pair of numbers in a row of this analog of Pascal's triangle before summing to yield the number below. The initial doubling thus yields the number of "original" elements to be found in the next higher n-cube and, as before, new elements are built upon those of one fewer dimension (edges upon vertices, faces upon edges, etc.). Again, the last number of a row represents the number of new vertices to be added to generate the next higher n-cube.

In this triangle, the sum of the elements of row m is equal to 3^m − 1. Again, to use the elements of row 5 as an example: $1 + 8 + 24 + 32 + 16 = 81$ , which is equal to $34 = 81$ .

Yang Hui (Pascal's) triangle, as depicted by the Chinese using rod numerals.

Calculating an individual row

This algorithm is an alternative to the standard method of calculating individual cells with factorials. Starting at the left, the first cell's value is 1. For each cell after, the value is determined by multiplying the value to the left by a slowly changing fraction:

$v(c) = \frac{r-c}{c}$

Where r = row + 1, starting with 0 at the top, and c = the column, starting with 0 on the left. For example, to calculate row 5, r=6. The first value is 1. The next value is 1 x 5/1 = 5. The numerator decreases by one, and the denominator increases by one with each step. So 5 x 4/2 = 10. Then 10 x 3/3 = 10. Then 10 x 2/4 = 5. Then 5 x 1/5 = 1. Notice that the last cell always equals 1, the final multiplication is included for completeness of the series.

A similar pattern exists on a downward diagonal. Starting with the one and the natural number in the next cell, form a fraction. To determine the next cell, increase the numerator and denominator each by one, and then multiply the previous result by the fraction. For example, the row starting with 1 and 7 form a fraction of 7/1. The next cell is 7 x 8/2 = 28. The next cell is 28 x 9/3 = 84.

Note that for any individual row you only need to calculate half (rounded up) the number of values in the row. This is because the row is symmetrical.

History

The earliest explicit depictions of a triangle of binomial coefficients occur in the 10th century in commentaries on the Chandas Shastra, an ancient Indian book on Sanskrit prosody written by Pingala between the 5th– 2nd centuries BC. While Pingala's work only survives in fragments, the commentator Halayudha, around 975, used the triangle to explain obscure references to Meru-prastaara, the "Staircase of Mount Meru". It was also realised that the shallow diagonals of the triangle sum to the Fibonacci numbers. The Indian mathematician Bhattotpala (c. 1068) later gives rows 0-16 of the triangle.

At around the same time, it was discussed in Persia (Iran) by the mathematician Al-Karaji (953–1029) and the poet- astronomer-mathematician Omar Khayyám (1048-1131); thus the triangle is referred to as the "Khayyam triangle" in Iran. Several theorems related to the triangle were known, including the binomial theorem. In fact we can be fairly sure that Khayyam used a method of finding nth roots based on the binomial expansion, and therefore on the binomial coefficients.

In 13th century, Yang Hui (1238-1298) presented the arithmetic triangle, which was the same as Pascal's Triangle. Today Pascal's triangle is called " Yang Hui's triangle" in China.

Finally, in Italy, it is referred to as "Tartaglia's triangle", named for the Italian algebraist Niccolò Fontana Tartaglia who lived a century before Pascal (1500-1577); Tartaglia is credited with the general formula for solving cubic polynomials (which may be really from Scipione del Ferro but was published by Gerolamo Cardano 1545).

Petrus Apianus ( 1495 -1552 ) published the Triangle on the frontispiece of his book on business calculations 1531/32 and an earlier version in 1527 the first record of it in Europe.

In 1655, Blaise Pascal wrote a Traité du triangle arithmétique (Treatise on arithmetical triangle), wherein he collected several results then known about the triangle, and employed them to solve problems in probability theory. The triangle was later named after Pascal by Pierre Raymond de Montmort (1708) and Abraham de Moivre (1730).

Retrieved from " http://en.wikipedia.org/wiki/Pascal%27s_triangle"