Pascal's triangle

From Free net encyclopedia

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, even though others studied it centuries before him.

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 rule, 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>

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.

1 The triangle
2 Uses of Pascal's triangle
3 Properties of Pascal's triangle
4 Geometric properties of Pascal's triangle
5 Pascal's triangle and the matrix exponential
6 History
7 See also
8 External links

[edit]

The triangle

Here are 15 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
1    14     91   364   1001  2002  3003  3432  3003  2002  1001   364   91    14    1

[edit]

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>

In order to prove that this interpretation (that of each line being the coefficients of (x + 1)^{row number}) is the same as the formula given at the beginning of the article (adding two side-by-side numbers to get the one below them), one must start by considering that the entire right diagonal corresponds to the coefficient of x⁰ when (x&nsbp;+ 1) has been raised to some power equal to the row number. The next diagonal corresponds to the coefficient of x¹, and so on. Now, algebraically, we are trying to determine what (x + 1)ⁿ⁺¹ looks like, if we start by defining (x + 1)ⁿ as being equal to

Now

Next we clean up the summations:

<math>\sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + x^0 + x^{n+1}</math> (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). Inspecting Pascal's triangle, we find that this is indeed the rule at the beginning of the article.

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.

[edit]

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 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-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. Image:Sierpinski triangle.pngTo 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).

It should also be said that if one were to color the odd and even numbers different, distinct colors, one would have a pattern known as Sierpinski triangle, which is a fractal.

Another notable trait of the triangle is that the value of each row, if each number in said row is considered as a "place", and numbers larger than 10 are carried over accordingly, is a power of 11. (Specifically, 11^n − 1, where n is the number of the row, beginning at 1). For example, Row 3 reads '1, 2, 1', which is 11^(3 − 1), or 11² (121). In row 6, '1, 5, 10, 10, 5, 1' is translated to 161051 after carrying the values over, which is 11⁵, or 11^6 − 1. If one considers the algebraic interpretation of the triangle, that each row is simply the coefficients of the polynomial (x + 1)^{row number}, then setting x = 10 and adjusting the values to fit in the decimal number system gives the above result.

To see another property of this triangle, imagine each number connected in a grid to those adjacent to it (imagine a Plinko game board). Starting at the top 1, without backtracking or going sideways, try to get to another node via these grid paths as many ways as possible. The answer is whatever number the node has. The interpretation of the value in a node of Pascal's Triangle as the number of paths to that node from the tip means that on a Plinko board shaped like a triangle, the probability of winning prizes nearer the center will be higher than winning prizes on the edges.

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>.

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

[edit]

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 (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:

<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      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 1's 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 measure polytope) 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: <math>1 + 8 + 24 + 32 + 16 = 81</math>, which is equal to <math>3^4 = 81</math>.

[edit]

Pascal's triangle and the matrix exponential

Image:Exp binomial grey wiki.png 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. This alludes to the famous Euler formula, <math>e^{i\pi}=-1</math>, which connects the four most basic constants in one identity.

[edit]

History

Image:Yanghui triangle.gif 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 also known to Chinese mathematicians. It is said that the triangle was called "Yang Hui's triangle" by the Chinese. Later, the Persian mathematician Karaji and the Persian astronomer-poet Omar Khayyám; 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. Finally, 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).

[edit]