Triangular array of the binomial coefficients in mathematics
formula_1A diagram showing the first eight rows of Pascal's triangle.In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.
The rows of Pascal's triangle are conventionally enumerated starting with row formula_2 at the top (the 0th row). The entries in each row are numbered from the left beginning with formula_3 and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the following manner: In row 0 (the topmost row), there is a unique nonzero entry 1. Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. For example, the initial number of row 1 (or any other row) is 1 (the sum of 0 and 1), whereas the numbers 1 and 3 in row 3 are added to produce the number 4 in row 4.
Formula.
In the formula_4th row of Pascal's triangle, the formula_5th entry is denoted formula_6, pronounced "n choose k". For example, the topmost entry is formula_7. With this notation, the construction of the previous paragraph may be written as
formula_8
for any positive integer formula_4 and any integer formula_10. This recurrence for the binomial coefficients is known as Pascal's rule.
History.
The pattern of numbers that forms Pascal's triangle was known well before Pascal's time. The Persian mathematician Al-Karaji (953–1029) wrote a now-lost book which contained the first description of Pascal's triangle. In India, the "Chandaḥśāstra" by the Indian lyricist Piṅgala (3rd or 2nd century BC) somewhat crypically describes a method of arranging two types of syllables to form metres of various lengths and counting them; as interpreted and elaborated by Piṅgala's 10th-century commentator Halāyudha his "method of pyramidal expansion" ("meru-prastāra") for counting metres is equivalent to Pascal's triangle. It was later repeated by Omar Khayyám (1048–1131), another Persian mathematician; thus the triangle is also referred to as Khayyam's triangle () in Iran. Several theorems related to the triangle were known, including the binomial theorem. Khayyam used a method of finding "n"th roots based on the binomial expansion, and therefore on the binomial coefficients.
Pascal's triangle was known in China during the 11th century through the work of the Chinese mathematician Jia Xian (1010–1070). During the 13th century, Yang Hui (1238–1298) defined the triangle, and it is known as Yang Hui's triangle () in China.
In Europe, Pascal's triangle appeared for the first time in the "Arithmetic" of Jordanus de Nemore (13th century).
The binomial coefficients were calculated by Gersonides during the early 14th century, using the multiplicative formula for them. Petrus Apianus (1495–1552) published the full triangle on the frontispiece of his book on business calculations in 1527. Michael Stifel published a portion of the triangle (from the second to the middle column in each row) in 1544, describing it as a table of figurate numbers. In Italy, Pascal's triangle is referred to as Tartaglia's triangle, named for the Italian algebraist Tartaglia (1500–1577), who published six rows of the triangle in 1556. Gerolamo Cardano also published the triangle as well as the additive and multiplicative rules for constructing it in 1570.
Pascal's ("Treatise on Arithmetical Triangle") was published posthumously in 1665. In this, Pascal collected several results then known about the triangle, and employed them to solve problems in probability theory. The triangle was later named for Pascal by Pierre Raymond de Montmort (1708) who called it (French: Mr. Pascal's table for combinations) and Abraham de Moivre (1730) who called it (Latin: Pascal's Arithmetic Triangle), which became the basis of the modern Western name.
Binomial expansions.
Pascal's triangle determines the coefficients which arise in binomial expansions. For example, in the expansion
formula_11
the coefficients are the entries in the second row of Pascal's triangle: formula_12, formula_13, formula_14.
In general, the binomial theorem states that when a binomial like formula_15 is raised to a positive integer power formula_4, the expression expands as
formula_17
where the coefficients formula_18 are precisely the numbers in row formula_19 of Pascal's triangle:
formula_20
The entire left diagonal of Pascal's triangle corresponds to the coefficient of formula_21 in these binomial expansions, while the next left diagonal corresponds to the coefficient of formula_22, and so on.
To see how the binomial theorem relates to the simple construction of Pascal's triangle, consider the problem of calculating the coefficients of the expansion of formula_23 in terms of the corresponding coefficients of formula_24, where we set formula_25 for simplicity. Suppose then that
formula_26
Now
formula_27
formula_28The first six rows of Pascal's triangle as binomial coefficients
The two summations can be reindexed with formula_29 and combined to yield
formula_30
Thus the extreme left and right coefficients remain as 1, and for any given formula_31, the coefficient of the formula_32 term in the polynomial formula_33 is equal to formula_34, the sum of the formula_35 and formula_32 coefficients in the previous power formula_37. This is indeed the downward-addition rule for constructing Pascal's triangle.
It is not difficult to turn this argument into a proof (by mathematical induction) of the binomial theorem. 
Since formula_38, the coefficients are identical in the expansion of the general case.
An interesting consequence of the binomial theorem is obtained by setting both variables formula_39, so that
formula_40
In other words, the sum of the entries in the formula_4th row of Pascal's triangle is the formula_4th power of 2. This is equivalent to the statement that the number of subsets of an formula_4-element set is formula_44, as can be seen by observing that each of the formula_4 elements may be independently included or excluded from a given subset.
Combinations.
A second useful application of Pascal's triangle is in the calculation of combinations. The number of combinations of formula_4 items taken formula_5 at a time, i.e. the number of subsets of formula_5 elements from among formula_4 elements, can be found by the equation
formula_50.
This is equal to entry formula_5 in row formula_4 of Pascal's triangle. Rather than performing the multiplicative calculation, one can simply look up the appropriate entry in the triangle (constructed by additions). For example, suppose 3 workers need to be hired from among 7 candidates; then the number of possible hiring choices is 7 choose 3, the entry 3 in row 7 of the above table (taking into consideration the first row is the 0th row), which is formula_53.
Relation to binomial distribution and convolutions.
When divided by formula_54, the formula_55th row of Pascal's triangle becomes the binomial distribution in the symmetric case where formula_56. By the central limit theorem, this distribution approaches the normal distribution as formula_55 increases. This can also be seen by applying Stirling's formula to the factorials involved in the formula for combinations.
This is related to the operation of discrete convolution in two ways. First, polynomial multiplication corresponds exactly to discrete convolution, so that repeatedly convolving the sequence formula_58 with itself corresponds to taking powers of formula_59, and hence to generating the rows of the triangle. Second, repeatedly convolving the distribution function for a random variable with itself corresponds to calculating the distribution function for a sum of "n" independent copies of that variable; this is exactly the situation to which the central limit theorem applies, and hence results in the normal distribution in the limit. (The operation of repeatedly taking a convolution of something with itself is called the convolution power.)
Patterns and properties.
Pascal's triangle has many properties and contains many patterns of numbers.
Diagonals.
The diagonals of Pascal's triangle contain the figurate numbers of simplices:
formula_77
The symmetry of the triangle implies that the "n"th d-dimensional number is equal to the "d"th "n"-dimensional number.
An alternative formula that does not involve recursion is
formula_78
where "n"("d") is the rising factorial.
The geometric meaning of a function "P""d" is: "P""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 "P""d"(1) = 1. Place these dots in a manner analogous to the placement of numbers in Pascal's triangle. To find P"d"("x"), have a total of "x" dots composing the target shape. P"d"("x") then equals the total number of dots in the shape. A 0-dimensional triangle is a point and a 1-dimensional triangle is simply a line, and therefore "P"0("x") = 1 and "P"1("x") = "x", which is the sequence of natural numbers. The number of dots in each layer corresponds to "P""d" − 1("x").
Calculating a row or diagonal by itself.
There are simple algorithms to compute all the elements in a row or diagonal without computing other elements or factorials.
To compute row formula_4 with the elements formula_80, begin with formula_81. For each subsequent element, the value is determined by multiplying the previous value by a fraction with slowly changing numerator and denominator:
formula_82
For example, to calculate row 5, the fractions are  formula_83,  formula_84,  formula_85,  formula_86 and formula_87, and hence the elements are  formula_88,   formula_89,   formula_90, etc. (The remaining elements are most easily obtained by symmetry.)
To compute the diagonal containing the elements formula_91 begin again with formula_92 and obtain subsequent elements by multiplication by certain fractions:
formula_93
For example, to calculate the diagonal beginning at formula_94, the fractions are  formula_95, and the elements are formula_96, etc. By symmetry, these elements are equal to formula_97, etc.
As the proportion of black numbers tends to zero with increasing "n", a corollary is that the proportion of odd binomial coefficients tends to zero as "n" tends to infinity.
Overall patterns and properties.
Pascal's triangle overlaid on a grid gives the number of distinct paths to each square, assuming only rightward and downward steps to an adjacent square are considered.
Construction as matrix exponential.
formula_98
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 sub-diagonal and zero everywhere else.
Construction of Clifford algebra using simplices.
Labelling the elements of each n-simplex matches the basis elements of Clifford algebra used as forms in Geometric Algebra rather than matrices. Recognising the geometric operations, such as rotations, allows the algebra operations to be discovered. Just as each row, n, starting at 0, of Pascal's triangle corresponds to an (n-1)-simplex, as described below, it also defines the number of named basis forms in n dimensional Geometric algebra. The binomial theorem can be used to prove the geometric relationship provided by Pascal's triangle. This same proof could be applied to simplices except that the first column of all 1's must be ignored whereas in the algebra these correspond to the real numbers, formula_99, with basis 1.
Relation to geometry of polytopes.
Pascal's triangle can be used as a lookup table for the number of elements (such as edges and corners) within a polytope (such as a triangle, a tetrahedron, a square, or a cube).
Number of elements of simplices.
Let's begin by considering the 3rd line of Pascal's 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 (known as 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. To build a tetrahedron from a triangle, 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