Pascal's triangle

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1

The first six 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 simple terms, Pascal's triangle can be constructed in the following manner. On the first row, write only the number 1. Then, to construct the elements of following rows, add the number directly above and to the left (if any) and the number directly above and to the right (if any) to find the new value. For example, the numbers 1 and 3 in the fourth row are added to produce 4 in the fifth row. More formally, this construction is using Pascal's identity, which states that

<math> {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}<math>

for non-negative integers n and k where n ≥ k and with the initial condition

<math> {n \choose 0} = {n \choose n} = 1.<math>

Note that the first row therefore corresponds to the binomial <math>{0 \choose 0}<math>, and can also be referred to as row <math>(n+1)<math>.

Pascal's triangle generalizes readily into higher dimensions. The three-dimensional version is called Pascal's pyramid or Pascal's tetrahedron. A higher-dimensional analogue is generically called a "Pascal's simplex". See also pyramid, tetrahedron, and simplex.

Contents

1 The triangle

2 Uses of Pascal's triangle

3 Properties of Pascal's triangle

4 Geometric properties of Pascal's triangle

5 History

6 External links

The triangle

Here are 14 lines 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

Uses of Pascal's triangle

Pascal's triangle has many uses in binomial expansions. For example

(x + 1)² = 1x² + 2x + 1².

Notice the coefficients are the third row of Pascal's triangle: 1, 2, 1. In general, when a binomial 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 + 1 of Pascal's triangle; in other words,

<math>a_i = {n \choose i}.<math>

Also, when a Pascal's triangle is constructed with 2ⁿ levels and all odd numbers are shaded, the result is an approximation to the Sierpinski triangle. Shading all multiples of 3, 4, etc. results in other patterns.

Properties of Pascal's triangle

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

The diagonals going along the left and right edges contain only 1s.
The diagonals next to the edge diagonals contain the natural numbers in order.
Moving inwards, the next pair of diagonals contain the triangle numbers in order.
The next pair of diagonals contain "tetrahedral" numbers in order.
Each next pair of diagonals contains the next higher dimensional "d-triangle" numbers, which can be defined as

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

The geometric meaning of a function tri_d is as follows: tri_d(1) = 1 for all d. Now, 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. Note that a 1-dimensional triangle is simply a line, and therefore tri₁(x)=x, which is the sequence of natural numbers. Also note that the number of dots in each layer corresponds to tri_d-1(x).

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 left, then one element to the top-left, or by going in the opposite direction. One such 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 our example's case, 13. Observe:

                                        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

The second highlighted diagonal has a sum of 233.

In addition, if we allow row m to indicate row <math>(n+1)<math>, the sum of the squares of the elements of row m equals the middle element of row <math>(2m-1)<math>. For example, <math>1^2 + 4^2 + 6^2 + 4 ^2 + 1^2 = 70<math>. In general form, that is:

<math>\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}<math>

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 <math>1 + 4 + 6 + 4 + 1 = 16<math>, which is equal to <math>2^4 = 16<math>.

Geometric properties of Pascal's triangle

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. For example, consider the 3rd line of the triangle, with values 1, 3, 3, 1. A 2-dimensional equilateral triangle has one 2-dimensional element (itself), 3 1-dimensional elements (lines, or edges), and 3 0-dimensional elements (vertices, or corners). The meaning of the final number (1) is ambiguous at best. Continuing with our example, a tetrahedron has 1 3-dimensional element (itself), 4 2-dimensional elements (faces), 6 1-dimensional elements (edges), and 4 0-dimensional elements (vertices). These values correspond to the 4th row of the triangle. Line 1 corresponds to a point, and Line 2 corresponds to a line. This pattern continues to arbitrarily high-dimensioned hyper-tetrahedrons.

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:

<math> {n \choose k} = 2\times{n-1 \choose k-1} + {n-1 \choose k}<math>

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      104     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 1's correspond 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 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.

History

The first reference to this triangle occurs in Indian mathematician Pingala's book on Sanskrit poetics that may be as early as 450 BC as Meru-prastaara, the "staircase of Mount Meru". The commentators of this book were also aware that the shallow diagonals of the triangle sum to the Fibonacci numbers. It was known to Chinese and Islamic scholars in medieval times. It is said that the triangle was called "Yang Hui's triangle" by the Chinese. Several theorems related to the triangle were known, including the binomial theorem. In Italy, it is referred to as "Tartaglia's triangle", named for the Italian algebraist Niccolo Fontana Tartaglia who lived a century before Pascal; Tartaglia is credited with the general formula for solving cubic polynomials.

In modern times, Pascal's triangle takes its name from the Traité du triangle arithmétique (1655) by Blaise Pascal. In that work, Pascal collected several results then known about the triangle, and employed them to solve problems in probability theory. The "arithmetical" triangle was later called after Pascal by Pierre Raymond de Montmort (1708) and Abraham de Moivre (1730).

External links

The Old Method Chart of the Seven Multiplying Squares (http://www.york.ac.uk/depts/maths/histstat/images/triangle.gif) (from the Ssu Yuan Yü Chien of Chu Shi-Chieh, 1303, depicting the first nine rows of Pascal's triangle)

Pascal's Treatise on the Arithmetic Triangle (http://www.lib.cam.ac.uk/RareBooks/PascalTraite) (page images of Pascal's treatise, 1655; summary: [1] (http://www.lib.cam.ac.uk/RareBooks/PascalTraite/pascalintro.pdf))