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 at the top. The entries in each row are numbered from the left beginning with and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the following manner: In row 0, 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 is 1, whereas the numbers 1 and 3 in row 3 are added to produce the number 4 in row 4.

Formula

In the th row of Pascal's triangle, the th entry is denoted, pronounced " choose ". For example, the topmost entry is. With this notation, the construction of the previous paragraph may be written as
for any positive integer and any integer. 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 wrote a now-lost book which contained the first description of Pascal's triangle. In India, the Chandaḥśāstra by the Indian poet and mathematician Piṅgala 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" for counting metres is equivalent to Pascal's triangle. It was later repeated by Omar Khayyám, 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 nth 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. During the 13th century, Yang Hui 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.
The binomial coefficients were calculated by Gersonides during the early 14th century, using the multiplicative formula for them. Petrus Apianus published the full triangle on the frontispiece of his book on business calculations in 1527. Michael Stifel published a portion of the triangle 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, 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 Traité du triangle arithmétique 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 who called it table de M. Pascal pour les combinaisons and Abraham de Moivre who called it Triangulum Arithmeticum PASCALIANUM, 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
the coefficients are the entries in the second row of Pascal's triangle:,,.
In general, the binomial theorem states that when a binomial like is raised to a positive integer power, the expression expands as
where the coefficients are precisely the numbers in row of Pascal's triangle:
The entire left diagonal of Pascal's triangle corresponds to the coefficient of in these binomial expansions, while the next left diagonal corresponds to the coefficient of, 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 in terms of the corresponding coefficients of, where we set for simplicity. Suppose then that
Now
The two summations can be reindexed with and combined to yield
Thus the extreme left and right coefficients remain as 1, and for any given, the coefficient of the term in the polynomial is equal to, the sum of the and coefficients in the previous power. This is indeed the downward-addition rule for constructing Pascal's triangle.
It is not difficult to turn this argument into a proof of the binomial theorem.
Since, the coefficients are identical in the expansion of the general case.
An interesting consequence of the binomial theorem is obtained by setting both variables, so that
In other words, the sum of the entries in the th row of Pascal's triangle is the th power of 2. This is equivalent to the statement that the number of subsets of an -element set is, as can be seen by observing that each of the 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 items taken at a time, i.e. the number of subsets of elements from among elements, can be found by the equation
This is equal to entry in row of Pascal's triangle. Rather than performing the multiplicative calculation, one can simply look up the appropriate entry in the triangle. 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, which is.

Relation to binomial distribution and convolutions

When divided by, the th row of Pascal's triangle becomes the binomial distribution in the symmetric case where. By the central limit theorem, this distribution approaches the normal distribution as 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 with itself corresponds to taking powers of, 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.

Patterns and properties

Pascal's triangle has many properties and contains many patterns of numbers.

Rows

  • The sum of the elements of a single row is twice the sum of the row preceding it. For example, row 0 has a value of 1, row 1 has a value of 2, row 2 has a value of 4, and so forth. This is because every item in a row produces two items in the next row: one left and one right. The sum of the elements of row equals to.
  • Taking the product of the elements in each row, the sequence of products is related to the base of the natural logarithm, e. Specifically, define the sequence for all as follows: Then, the ratio of successive row products is and the ratio of these ratios is The right-hand side of the above equation takes the form of the limit definition of e |
  • pi| can be found in Pascal's triangle by use of the Nilakantha infinite series.
  • Some of the numbers in Pascal's triangle correlate to numbers in Lozanić's triangle.
  • The sum of the squares of the elements of row equals the middle element of row . For example,. In general form,
  • In any even row, the middle term minus the term two spots to the left equals a Catalan number, specifically. For example, in row 4, which is 1, 4, 6, 4, 1, we get the 3rd Catalan number.
  • In a row , where is a prime number, all the terms in that row except the 1s are divisible by. This can be proven easily, from the multiplicative formula. Since the denominator can have no prime factors equal to, so remains in the numerator after integer division, making the entire entry a multiple of.
  • Parity: To count odd terms in row , convert to binary. Let be the number of 1s in the binary representation. Then the number of odd terms will be. These numbers are the values in Gould's sequence.
  • Every entry in row 2n − 1, n ≥ 0, is odd.
  • Polarity: When the elements of a row of Pascal's triangle are alternately added and subtracted together, the result is 0. For example, row 6 is 1, 6, 15, 20, 15, 6, 1, so the formula is 1 − 6 + 15 − 20 + 15 − 6 + 1 = 0.

    Diagonals

The diagonals of Pascal's triangle contain the figurate numbers of simplices:
  • 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. The 1-dimensional simplex numbers increment by 1 as the line segments extend to the next whole number along the number line.
  • 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.
The symmetry of the triangle implies that the nth d-dimensional number is equal to the dth n-dimensional number.
An alternative formula that does not involve recursion is
where n is the rising factorial.
The geometric meaning of a function Pd is: Pd = 1 for all d. Construct a d-dimensional triangle by placing additional dots below an initial dot, corresponding to Pd = 1. Place these dots in a manner analogous to the placement of numbers in Pascal's triangle. To find Pd, have a total of x dots composing the target shape. Pd 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 P0 = 1 and P1 = x, which is the sequence of natural numbers. The number of dots in each layer corresponds to Pd − 1.