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,[1] China, Germany, and Italy.[2]
The rows of Pascal's triangle are conventionally enumerated starting with row
n=0
k=0
In the
n
k
\tbinomnk
\tbinom00=1
n
0\lek\len
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 formulation of the binomial coefficients and the first description of Pascal's triangle.[4] [5] [6] It was later repeated by Omar Khayyám (1048–1131), another Persian mathematician; thus the triangle is also referred to as Khayyam's triangle (Persian: مثلث خیام|label=none) in Iran.[7] 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.[8]
Pascal's triangle was known in China during the early 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 (Chinese: s=杨辉三角|t=楊輝三角|labels=no) in China.[9]
In Europe, Pascal's triangle appeared for the first time in the Arithmetic of Jordanus de Nemore (13th century).[10] The binomial coefficients were calculated by Gersonides during the early 14th century, using the multiplicative formula for them.[11] Petrus Apianus (1495–1552) published the full triangle on the frontispiece of his book on business calculations in 1527.[12] 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.[11] 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.[11] Gerolamo Cardano also published the triangle as well as the additive and multiplicative rules for constructing it in 1570.[11]
Pascal's French: Traité du triangle arithmétique (Treatise on Arithmetical Triangle) was published posthumously in 1665.[13] 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: table de M. Pascal pour les combinaisons (French: Mr. Pascal's table for combinations) and Abraham de Moivre (1730) who called it Latin: Triangulum Arithmeticum PASCALIANUM (Latin: Pascal's Arithmetic Triangle), which became the basis of the modern Western name.[14]
Pascal's triangle determines the coefficients which arise in binomial expansions. For example, in the expansionthe coefficients are the entries in the second row of Pascal's triangle:
\tbinom20=1
\tbinom21=2
\tbinom22=1
In general, the binomial theorem states that when a binomial like
x+y
n
ak
n
The entire left diagonal of Pascal's triangle corresponds to the coefficient of
xn
xn-1y
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
(x+y)n
(x+1)n
y=1
The two summations can be reindexed with
k=i+1
Thus the extreme left and right coefficients remain as 1, and for any given
0<k<n+1
xk
(x+1)n
ak-1+ak
xk-1
xk
(x+1)n
It is not difficult to turn this argument into a proof (by mathematical induction) of the binomial theorem.
Since
(a+b)n=bn(\tfrac{a}{b}+1)n
An interesting consequence of the binomial theorem is obtained by setting both variables
x=y=1
In other words, the sum of the entries in the
n
n
n
2n
n
A second useful application of Pascal's triangle is in the calculation of combinations. The number of combinations of
n
k
k
n
C(n,k)=
n | |
C | |
k |
={nCk
This is equal to entry
k
n
\tbinom{7}{3}=35
When divided by
2n
n
p=\tfrac{1}{2}
n
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
\{\ldots,0,0,1,1,0,0,\ldots\}
x+1
Pascal's triangle has many properties and contains many patterns of numbers.
n
2n
sn
n\ge0
sn=
n | |
\prod | |
k=0 |
{n\choosek}=
n | |
\prod | |
k=0 |
n! | |
k!(n-k)! |
e
\pi
n=2m
Cm-1=\tbinom{2m}{m}-\tbinom{2m}{m-2}
C3=6-1=5
\tbinompk=\tfrac{p!}{k!(p-k)!}
p!(p-k)!
The diagonals of Pascal's triangle contain the figurate numbers of simplices:
\begin{align} P0(n)&=Pd(0)=1,\\ Pd(n)&=Pd(n-1)+Pd-1(n)\\ &=
n | |
\sum | |
i=0 |
Pd-1(i)=
d | |
\sum | |
i=0 |
Pi(n-1). \end{align}
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 iswhere n(d) is the rising factorial.
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
n
\tbinom{n}{0},\tbinom{n}{1},\ldots,\tbinom{n}{n}
\tbinom{n}{0}=1
{n\choosek}={n\choosek-1} x
n+1-k | |
k |
.
For example, to calculate row 5, the fractions are
\tfrac{5}{1}
\tfrac{4}{2}
\tfrac{3}{3}
\tfrac{2}{4}
\tfrac{1}{5}
\tbinom{5}{0}=1
\tbinom{5}{1}=1 x \tfrac{5}{1}=5
\tbinom{5}{2}=5 x \tfrac{4}{2}=10
To compute the diagonal containing the elements
\tbinom{n}{0},\tbinom{n+1}{1},\tbinom{n+2}{2},\ldots,
\tbinom{n}{0}=1
{n+k\choosek}={n+k-1\choosek-1} x
n+k | |
k |
.
For example, to calculate the diagonal beginning at
\tbinom{5}{0}
\tfrac{6}{1},\tfrac{7}{2},\tfrac{8}{3},\ldots
\tbinom{5}{0}=1,\tbinom{6}{1}=1 x \tfrac{6}{1}=6,\tbinom{7}{2}=6 x \tfrac{7}{2}=21
\tbinom{5}{5},\tbinom{6}{5},\tbinom{7}{5}
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.[20]
Pascal's triangle overlaid on a grid gives the number of distinct paths to each square, assuming only rightward and downward movements are considered.
bgcolor=red | 1 | |||||||||
1 | 1 | |||||||||
1 | bgcolor=lime | 2 | bgcolor=aqua | 1 | ||||||
bgcolor=lime | 1 | bgcolor=aqua | 3 | 3 | bgcolor=red | 1 | ||||
bgcolor=aqua | 1 | 4 | bgcolor=red | 6 | 4 | 1 | ||||
1 | bgcolor=red | 5 | 10 | 10 | bgcolor=lime | 5 | bgcolor=aqua | 1 | ||
bgcolor=red | 1 | 6 | 15 | bgcolor=lime | 20 | bgcolor=aqua | 15 | 6 | bgcolor=red | 1 |
1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |
See also: Pascal matrix. 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.
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,, starting at 0, of Pascal's triangle corresponds to an -simplex, as described below, it also defines the number of named basis forms in 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,
\R
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).
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 -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 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 ; the number of faces is the number of edges is the number of new vertices is . 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, instead of . 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\choosek}=2 x {n-1\choosek-1}+{n-1\choosek}.
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:
\begin{matrix} 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 \end{matrix}
To understand why this pattern exists, first recognize that the construction of an n-cube from an -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:, which is equal to
34=81
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.[21] For example, the values of the step function that results from:
ak{Re}\left(Fourier\left[
\sin(x)5 | |
x |
\right]\right)
compose the 4th row of the triangle, with alternating signs. This is a generalization of the following basic result (often used in electrical engineering):
ak{Re}\left(Fourier\left[
\sin(x)1 | |
x |
\right]\right)
is the boxcar function.[22] The corresponding row of the triangle is row 0, which consists of just the number 1.
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 may be extended upwards, above the 1 at the apex, preserving the additive property, but there is more than one way to do so.[23]
Pascal's triangle has higher dimensional generalizations. The three-dimensional version is known as Pascal's pyramid or Pascal's tetrahedron, while the general versions are known as Pascal's simplices.
When the factorial function is defined as
z!=\Gamma(z+1)
\Complex
\Gamma(z+1)
n
a
\limn
n | |
11 | |
a |
n
(a+1)n=
n | |
11 | |
a |
a
14641a
a
i
i=0
i
14641a=1 ⋅ a4+4 ⋅ a3+6 ⋅ a2+4 ⋅ a1+1 ⋅ a0
(a+b)n
b
b=1
a
a
(a+1)n=
n | |
11 | |
a |
c=a+1
c<0
a=\{c-1,-(c+1)\} mod 2c
n
By setting the row's radix (the variable
a
n
n | |
11 | |
1 |
=2n
n | |
11 | |
10 |
=11n
a=n
nn\left(1+
1 | |
n |
\right)n=
n | |
11 | |
n |
n | |
11 | |
n |
n
12 | |
11 | |
12 |
=1:10:56:164:353:560:650:560:353:164:56:10:112=27433a969970112
with compound digits (delimited by ":") in radix twelve. The digits from
k=n-1
k=1
{n\choosen-1}
01
n
2
n>2
1
10n
k=1
n | |
11 | |
n |
n+1
n | |
1.1 | |
n |
n
1234 | |
1.1 | |
1234 |
1234
1234 | |
1.1 | |
1234 |
=
1227digits:0:1 | |
2.885:2:35:977:696:\overbrace{\ldots} | |
1234 |
=2.717181235\ldots10
\scriptstyle{n\choosek}