Pascal's triangle

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
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} = {n1 \choose k1} + {n1 \choose k}<math>
for nonnegative 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 threedimensional version is called Pascal's pyramid or Pascal's tetrahedron. A higherdimensional analogue is generically called a "Pascal's simplex". See also pyramid, tetrahedron, and simplex.
Contents 
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} = 1x^{2} + 2x + 1^{2}.
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} = a_{0}x^{n} + a_{1}x^{n−1}y + a_{2}x^{n−2}y^{2} + … + a_{n−1}xy^{n−1} + a_{n}y^{n},
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^{n} 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 "dtriangle" 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}_{d1}(i). <math>
The geometric meaning of a function tri_{d} is as follows: tri_{d}(1) = 1 for all d. Now, construct a ddimensional triangle (a 3dimensional 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 1dimensional triangle is simply a line, and therefore tri_{1}(x)=x, which is the sequence of natural numbers. Also note that the number of dots in each layer corresponds to tri_{d1}(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 topleft, 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>(2m1)<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^{m1}. 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 2dimensional equilateral triangle has one 2dimensional element (itself), 3 1dimensional elements (lines, or edges), and 3 0dimensional elements (vertices, or corners). The meaning of the final number (1) is ambiguous at best. Continuing with our example, a tetrahedron has 1 3dimensional element (itself), 4 2dimensional elements (faces), 6 1dimensional elements (edges), and 4 0dimensional 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 highdimensioned hypertetrahedrons.
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{n1 \choose k1} + {n1 \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^{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 2dimensional elements in a 2dimensional cube (a square) is one, the number of 1dimensional elements (sides, or lines) is 4, and the number of 0dimensional 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 Meruprastaara, 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 ShiChieh, 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))
 Earliest Known Uses of Some of the Words of Mathematics (P) (http://members.aol.com/jeff570/p.html)
 Leibniz and Pascal triangles (http://www.cuttheknot.org/Curriculum/Combinatorics/LeibnitzTriangle.shtml)
 Dot Patterns, Pascal's Triangle, and Lucas' Theorem (http://www.cuttheknot.org/Curriculum/Algebra/DotPatterns.shtml)
 Pascal's Triangle From Top to Bottom (http://binomial.csuhayward.edu)de:Pascalsches Dreieck
es:Coeficiente_binomial_y_triángulo_de_Pascal fr:Triangle de Pascal he:משולש פסקל pl:TrÃ³jkÄ…t Pascala sa:मेरु प्रस्तार zh:杨辉三角 sv:Pascals triangel