Pascals triangle

From Example Problems
Jump to navigation Jump to search
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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}}

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n \choose 0} = {n \choose n} = 1.}

Note that the first row therefore corresponds to the binomial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {0 \choose 0}} , and can also be referred to as row Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n+1)} .

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.

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)2 = 1x2 + 2x + 12.

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)n = a0xn + a1xn−1y + a2xn−2y2 + … + an−1xyn−1 + anyn,

where the coefficients ai in this expansion are precisely the numbers on row n + 1 of Pascal's triangle; in other words,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i = {n \choose i}.}

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 x0 when (x+1) has been raised to some power equal to the row number. The next diagonal corresponds to the coefficient of x1, and so on. Now, algebraically, we are trying to determine what (x+1)n+1 looks like, if we start by defining (x+1)n as being equal to

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^n a_i x^i}

Now

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+1)^{n+1} = x(x+1)^n + (x+1)^n = \sum_{i=0}^n a_i x^{i+1} + \sum_{i=0}^n a_i x^i}

Next we clean up the summations:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^{n } a_{i } x^{i+1} + \sum_{i=0}^n a_i x^i = }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{n+1} a_{i-1} x^{i } + \sum_{i=0}^n a_i x^i = }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} = }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + a_0x^0 + a_{n}x^{n+1} = }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + x^0 + x^{n+1}} (because of how raising a polynomial to a power works, a0 = an = 1)

We now have an expression for the polynomial (x+1)n+1 in terms of the coefficients of (x+1)n (these are the ais), 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)n, and we are determining the coefficients of (x+1)n+1. Now, for any given i not 0 or n+1, the coefficient of the xi term in the polynomial (x+1)n+1 is equal to ai (the figure above and to the left of the figure to be determined, since it is on the same diagonal) + ai-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 2n 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 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
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{tri}_1(n) = n \quad\mbox{and}\quad \textrm{tri}_{d}(n) = \sum_{i=1}^n \mathrm{tri}_{d-1}(i). }

The geometric meaning of a function trid is as follows: trid(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 trid(1)=1. Place these dots in a manner analogous to the placement of numbers in Pascal's Triangle.

File:Sierpinski triangle.png
Sierpinski triangle

To find trid(x), have a total of x dots composing the target shape. trid(x) then equals the total number of dots in the shape. Note that a 1-dimensional triangle is simply a line, and therefore tri1(x)=x, which is the sequence of natural numbers. Also note that the number of dots in each layer corresponds to trid-1(x).

It should also be said that if one were to color the odd and even numbers different, distinct colors, you 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 112 (121). In Row 6, '1, 5, 10, 10, 5, 1' is translated to 161051 after carrying the values over, which is 115, 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.

There's 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n+1)} , the sum of the squares of the elements of row m equals the middle element of row Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2m-1)} . For example, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1^2 + 4^2 + 6^2 + 4 ^2 + 1^2 = 70} . In general form, that is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 3rd Catalan number, and (5 + 1)/2 = 3.

Also, the sum of the elements of row m is equal to 2m-1. For example, the sum of the elements of row 5 is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 4 + 6 + 4 + 1 = 16} , which is equal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^4 = 16} .

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), 3 1-dimensional elements (lines, or edges), and 3 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 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.

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 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). 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 representing by the next row.

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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {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 2k, 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 2Position Number = 6 * 22 = 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 3m-1. Again, to use the elements of row 5 as an example: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 8 + 24 + 32 + 16 = 81} , which is equal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3^4 = 81} .

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

External links

ca:Triangle de Tartaglia de:Pascalsches Dreieck es:Triángulo de Pascal fa:مثلث خیام-پاسکال fr:Triangle de Pascal it:Triangolo di Tartaglia he:משולש פסקל lt:Paskalio trikampis nl:Driehoek van Pascal pl:Trójkąt Pascala sv:Pascals triangel tr:Pascal üçgeni zh:杨辉三角形