In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises 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 India,Persia, China, Germany, and Italy.
The rows of Pascal's triangle are conventionally enumerated starting with row at the top (the 0th row). 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 (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 in the first (or any other) row is 1 (the sum of 0 and 1), whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row.
The entry in the th row and th column of Pascal's triangle is denoted . For example, the unique nonzero entry in the topmost row is . With this notation, the construction of the previous paragraph may be written as follows:
for any non-negative integer and any integer . This recurrence for the binomial coefficients is known as Pascal's rule.
Pascal's triangle has higher dimensional generalizations. The three-dimensional version is called Pascal's pyramid or Pascal's tetrahedron, while the general versions are called Pascal's simplices .
The pattern of numbers that forms Pascal's triangle was known well before Pascal's time. Pascal innovated many previously unattested uses of the triangle's numbers, uses he described comprehensively in the earliest known mathematical treatise to be specially devoted to the triangle, his Traité du triangle arithmétique (1654; published 1665).
Centuries before, discussion of the numbers had arisen in the context of Indian studies of combinatorics and binomial numbers. It appears from later commentaries that the binomial coefficients and the additive formula for generating them, , were known to Pingala in or before the 2nd century BC. While Pingala's work only survives in fragments, the commentator Varāhamihira, around 505, gave a clear description of the additive formula, and a more detailed explanation of the same rule was given by Halayudha, around 975. Halayudha also explained obscure references to Meru-prastaara, the Staircase of Mount Meru , giving the first surviving description of the arrangement of these numbers into a triangle. In approximately 850, the Jain mathematician Mahāvīra gave a different formula for the binomial coefficients, using multiplication, equivalent to the modern formula . In 1068, four columns of the first sixteen rows were given by the mathematician Bhattotpala, who was the first recorded mathematician to equate the additive and multiplicative formulas for these numbers.
At around the same time, the Persian mathematician Al-Karaji (953–1029) wrote a now-lost book which contained the first description of Pascal's triangle.It was later repeated by the Persian poet-astronomer-mathematician Omar Khayyám (1048–1131); thus the triangle is also referred to as the Khayyam 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 in the early 11th century through the work of the Chinese mathematician Jia Xian (1010–1070). In the 13th century, Yang Hui (1238–1298) presented the triangle and hence it is still called 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 in 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 Niccolò Fontana 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 Traité du triangle arithmétique (Treatise on Arithmetical Triangle) was published in 1655. 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 after Pascal by Pierre Raymond de Montmort (1708) who called it "Table de M. Pascal pour les combinaisons" (French: Table of Mr. Pascal for combinations) and Abraham de Moivre (1730) who called it "Triangulum Arithmeticum PASCALIANUM" (Latin: Pascal's Arithmetic Triangle), which became the modern Western name.
Pascal's triangle determines the coefficients which arise in binomial expansions. For example, consider the expansion
The coefficients are the numbers in the second row of Pascal's triangle: , , .
In general, when a binomial like is raised to a positive integer power of , we have:
where the coefficients in this expansion are precisely the numbers on row of Pascal's triangle. In other words,
This is the binomial theorem.
The entire right diagonal of Pascal's triangle corresponds to the coefficient of in these binomial expansions, while the next 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 (setting for simplicity). Suppose then that
The two summations can be reorganized as follows:
(because of how raising a polynomial to a power works, ).
We now have an expression for the polynomial in terms of the coefficients of (these are the s), 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 , and that the -terms are the coefficients of the polynomial , and we are determining the coefficients of . Now, for any given , the coefficient of the term in the polynomial is equal to . This is indeed the simple rule for constructing Pascal's triangle row-by-row.
It is not difficult to turn this argument into a proof (by mathematical induction) 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 and equal to one. In this case, we know that , and so
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 (the cardinality of the power set) of an -element set is , as can be seen by observing that the number of subsets is the sum of the number of combinations of each of the possible lengths, which range from zero through to .
A second useful application of Pascal's triangle is in the calculation of combinations. For example, the number of combinations of things taken at a time (called n choose k ) can be found by the equation
But this is also the formula for a cell of Pascal's triangle. Rather than performing the calculation, one can simply look up the appropriate entry in the triangle. Provided we have the first row and the first entry in a row numbered 0, the answer will be located at entry in row . For example, suppose a basketball team has 10 players and wants to know how many ways there are of selecting 8. The answer is entry 8 in row 10, which is 45; that is, 10 choose 8 is 45.
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 exactly corresponds 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 leads to the normal distribution in the limit.
Pascal's triangle has many properties and contains many patterns of numbers.
The diagonals of Pascal's triangle contain the figurate numbers of simplices:
The symmetry of the triangle implies that the nth d-dimensional number is equal to the dthn-dimensional number.
An alternative formula that does not involve recursion is as follows:
The geometric meaning of a function Pd is: Pd(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 Pd(1) = 1. Place these dots in a manner analogous to the placement of numbers in Pascal's triangle. To find Pd(x), have a total of x dots composing the target shape. Pd(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 P0(x) = 1 and P1(x) = x, which is the sequence of natural numbers. The number of dots in each layer corresponds to Pd − 1(x).
There are simple algorithms to compute all the elements in a row or diagonal without computing other elements or factorials.
To compute row with the elements , , ..., , begin with . For each subsequent element, the value is determined by multiplying the previous value by a fraction with slowly changing numerator and denominator:
For example, to calculate row 5, the fractions are , , , and , and hence the elements are , , , etc. (The remaining elements are most easily obtained by symmetry.)
To compute the diagonal containing the elements , , , ..., we again begin with and obtain subsequent elements by multiplication by certain fractions:
By symmetry, this same process can be used to compute the diagonal , , ... .
For example, to calculate the diagonal beginning at , the fractions are , , , ..., and the elements are , , , etc. By symmetry, these elements are equal to , , , etc.
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.
This section does not cite any sources . (October 2016) (Learn how and when to remove this template message)
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 and a cube).
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 (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 + 1 = 1; the number of faces is 1 + 3 = 4; the number of edges is 3 + 3 = 6; the number of new vertices is 3 + 1 = 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. The "extra" 1 in a row can be thought of as the -1 simplex, the unique center of the simplex, which ever gives rise to a new vertex and a new dimension, yielding a new simplex with a new center.
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:
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:
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 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 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 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 3m. Again, to use the elements of row 4 as an example: 1 + 8 + 24 + 32 + 16 = 81, which is equal to .
Each row of Pascal's triangle gives the number of vertices at each distance from a fixed vertex in an n-dimensional cube. For example, in three dimensions, the third row (1 3 3 1) corresponds to the usual three-dimensional cube: fixing a vertex V, there is one vertex at distance 0 from V (that is, V itself), three vertices at distance 1, three vertices at distance √ and one vertex at distance √ (the vertex opposite V). The second row corresponds to a square, while larger-numbered rows correspond to hypercubes in each dimension.
As stated previously, the coefficients of (x + 1)n are the nth row of the triangle. Now the coefficients of (x − 1)n are the same, except that the sign alternates from +1 to −1 and back again. After suitable normalization, the same pattern of numbers occurs in the Fourier transform of sin(x)n+1/x. More precisely: if n is even, take the real part of the transform, and if n is odd, take the imaginary part. Then the result is a step function, whose values (suitably normalized) are given by the nth row of the triangle with alternating signs. For example, the values of the step function that results from:
compose the 4th row of the triangle, with alternating signs. This is a generalization of the following basic result (often used in electrical engineering):
is the boxcar function. 1.The corresponding row of the triangle is row 0, which consists of just the number
If n is congruent to 2 or to 3 mod 4, then the signs start with −1. In fact, the sequence of the (normalized) first terms corresponds to the powers of i, which cycle around the intersection of the axes with the unit circle in the complex plane:
Pascal's triangle can be extended to negative row numbers.
First write the triangle in the following form:
Next, extend the column of 1s upwards:
Now the rule:
can be rearranged to:
which allows calculation of the other entries for negative rows:
This extension preserves the property that the values in the mth column viewed as a function of n are fit by an order m polynomial, namely
This extension also preserves the property that the values in the nth row correspond to the coefficients of (1 + x)n:
When viewed as a series, the rows of negative n diverge. However, they are still Abel summable, which summation gives the standard values of 2n. (In fact, the n = -1 row results in Grandi's series which "sums" to 1/2, and the n = -2 row results in another well-known series which has an Abel sum of 1/4.)
Another option for extending Pascal's triangle to negative rows comes from extending the other line of 1s:
Applying the same rule as before leads to
This extension also has the properties that just as
Also, just as summing along the lower-left to upper-right diagonals of the Pascal matrix yields the Fibonacci numbers, this second type of extension still sums to the Fibonacci numbers for negative index.
Either of these extensions can be reached if we define
and take certain limits of the gamma function, .
In probability theory and statistics, the binomial distribution with parameters n and p is the discrete probability distribution of the number of successes in a sequence of n independent experiments, each asking a yes–no question, and each with its own Boolean-valued outcome: success or failure. A single success/failure experiment is also called a Bernoulli trial or Bernoulli experiment, and a sequence of outcomes is called a Bernoulli process; for a single trial, i.e., n = 1, the binomial distribution is a Bernoulli distribution. The binomial distribution is the basis for the popular binomial test of statistical significance.
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and is given by the formula
In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial (x + y)n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with b + c = n, and the coefficient a of each term is a specific positive integer depending on n and b. For example,
In mathematics, a combination is a selection of items from a collection, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements, the number of k-combinations is equal to the binomial coefficient
In mathematics, the falling factorial is defined as the polynomial
In mathematics, Bertrand's postulate states that for each there is a prime such that . It was first proven by Pafnuty Chebyshev, and a short but advanced proof was given by Srinivasa Ramanujan. The gist of the following elementary proof is due to Paul Erdős. The basic idea of the proof is to show that a certain central binomial coefficient needs to have a prime factor within the desired interval in order to be large enough. This is made possible by a careful analysis of the prime factorization of central binomial coefficients.
The term figurate number is used by different writers for members of different sets of numbers, generalizing from triangular numbers to different shapes and different dimensions. The term can mean
A tetrahedral number, or triangular pyramidal number, is a figurate number that represents a pyramid with a triangular base and three sides, called a tetrahedron. The nth tetrahedral number, Ten, is the sum of the first n triangular numbers, that is,
In mathematics, Pascal's pyramid is a three-dimensional arrangement of the trinomial numbers, which are the coefficients of the trinomial expansion and the trinomial distribution. Pascal's Pyramid is the three-dimensional analog of the two-dimensional Pascal's triangle, which contains the binomial numbers and relates to the binomial expansion and the binomial distribution. The binomial and trinomial numbers, coefficients, expansions, and distributions are subsets of the multinomial constructs with the same names.
A pentatope number is a number in the fifth cell of any row of Pascal's triangle starting with the 5-term row 1 4 6 4 1, either from left to right or from right to left.
In mathematics, the Gaussian binomial coefficients are q-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as or , is a polynomial in q with integer coefficients, whose value when q is set to a prime power counts the number of subspaces of dimension k in a vector space of dimension n over a finite field with q elements.
In mathematics the nth central binomial coefficient is the particular binomial coefficient
In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k,
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.
In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer.
In combinatorics, the Eulerian numberA(n, m) is the number of permutations of the numbers 1 to n in which exactly m elements are greater than the previous element. They are the coefficients of the Eulerian polynomials:
In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient by a prime number p in terms of the base p expansions of the integers m and n.
The Leibniz harmonic triangle is a triangular arrangement of unit fractions in which the outermost diagonals consist of the reciprocals of the row numbers and each inner cell is the cell diagonally above and to the left minus the cell to the left. To put it algebraically, L(r, 1) = 1/r and L(r, c) = L(r − 1, c − 1) − L(r, c − 1).
The Star of David theorem is a mathematical result on arithmetic properties of binomial coefficients. It was discovered by Henry W. Gould in 1972.
In combinatorial mathematics and statistics, the Fuss–Catalan numbers are numbers of the form
|Wikimedia Commons has media related to Pascal's triangle .|