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 the English-speaking world, even though others studied it centuries before him in Persia, China, India, and Italy.

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 with the number directly above and to the right to find the new value. If either the one to the right or left is not present, substitute a zero in its place (this corresponds to the fact that $\scriptstyle {n \choose k}$ does not exist if $k$ is either less than zero or greater than $n$). For example, the numbers 1 and 3 in the fourth row are added to produce 4 in the fifth row. More formally, this construction uses Pascal's rule, which states that

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

for positive integers n and k where $n\geq k$ and with the initial condition

${n \choose 0}={n \choose 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 lines number 0 to 16 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

Uses of Pascal's triangle

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

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

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

$a_{i}={n \choose i}.$

This is the binomial theorem.

In order to prove this theorem, one must start by considering that the entire right diagonal corresponds to the coefficient of x⁰ when (x + 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

$\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}$

Next we clean up the summations:

$\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_{0}x^{0}+a_{n}x^{n+1}=$

$\sum _{i=1}^{n}(a_{i-1}+a_{i})x^{i}+a_{0}x^{0}+a_{n}x^{n+1}=$

$\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, 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.

One very interesting consequence of this fact is obtained by substituting the number one for x. In this case, we know that $(1+1)^{n}=2^{n}$, hence the sum of

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

That is to say, the sum of the entries in the ith row of Pascal's triangle sum to the ith power of 2.

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 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-triangle" 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 alternate 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\geq 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.

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

Coloring the odd and even numbers with different colors to distinguish them results in a pattern known as Sierpinski triangle, which is a fractal. Shading all multiples of 3, 4, etc., results in other patterns and combinations.

The sum of the numbers in each row is a power of 2 (specifically, 2ⁿ, where n is the is the number of the row, beginning with the first row as row zero, then the second as 1, etc.)

The value of each row, if each number in it is considered as a "place" and numbers larger than 9 are carried over accordingly, is a power of 11 (specifically, 11^n − 1, where n is the number of the row). 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. In the algebraic interpretation of the triangle, in which each row is simply the coefficients of the polynomial (x + 1)^{row number}, setting x = 10 and adjusting the values to fit in the decimal number system gives the above result.

Imagine each number connected in a grid to those adjacent to it (for example, 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 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 $(2m-1)$. For example, $1^{2}+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 $2^{4}=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.

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 $3^{4}=81$.

The matrix exponential

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

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.

For a fuller description of this, see the article Pascal matrix.

History

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

Although its origins can never be known, the earliest explicit depictions of a triangle of binomial coefficients occur around 1000 in commentaries on an ancient book on Sanskrit prosody by Pingala. While Pingala's work only survives in fragments, the commentator Halayudha (writing around 975) uses the triangle to explain obscure references to Meru-prastaara, the "staircase of Mount Meru", while Bhattotpala (around 1068) gives rows 0-16. It was also realised that the shallow diagonals of the triangle sum to the Fibonacci numbers. At around the same time it was discussed by the Persian mathematician Karaji and the Persian astronomer-poet Omar Khayyám; thus the triangle is referred to as the "Khayyam triangle" in Iran. Later, the arithmetic triangle became known to Chinese mathematicians from the twelfth century onwards; today Pascal's triangle is called "Yang Hui's triangle" in China. 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 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).

See also

• Pascal matrix
• multiplicities of entries in Pascal's triangle
• Francis Galton's "quincunx" or bean machine
• Leibniz harmonic triangle

External links

• Weisstein, Eric W. "Pascal's triangle". MathWorld.
• The Old Method Chart of the Seven Multiplying Squares (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 (page images of Pascal's treatise, 1655; summary: [3])
• Earliest Known Uses of Some of the Words of Mathematics (P)
• Leibniz and Pascal triangles
• Dot Patterns, Pascal's Triangle, and Lucas' Theorem
• Pascal's Triangle From Top to Bottom
• Omar Khayyam the mathematician
• Info on Pascal's Triangle
• Explanation of Pascal's Triangle and common occurrences, including link to interactive version specifying # of rows to view