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 India, Persia, China, Germany, and Italy.

The rows of Pascal's triangle are conventionally enumerated starting with row \(n = 0\) at the top (the 0th row). The entries in each row are numbered from the left beginning with \(k = 0\) 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.

In the \(n\)th row of Pascal's triangle, the \(k\)th entry is denoted \(\tbinom nk\), pronounced "n choose k" because it describes the number of combinations: the number of ways of choosing ⁠\(k\)⁠ things from among a collection of ⁠\(n\)⁠ things. Row numbering starts at 0, and likewise entries within a row are numbered from 0. For example, the topmost entry is \(\tbinom 00 = 1\). With this notation, the construction of the previous paragraph may be written as

\[{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\]for any positive integer \(n\) and any integer \(0 \le k \le n\). This recurrence for the binomial coefficients is known as Pascal's rule. An arbitrary binomial coefficient can be calculated as \[{n \choose k} = \frac{n!}{ k! (n-k)!}.\]

The pattern of numbers that forms Pascal's triangle was known well before Pascal's time. In India, the Chandaḥśāstra by the Ancient Indian poet and mathematician Piṅgala (3rd or 2nd century BC) describes a method of arranging two types of syllables to form metres of various lengths and counting them; as interpreted and elaborated by Pingala's 10th-century commentator Halāyudha his "method of pyramidal expansion" (meru-prastāra) for counting metres is equivalent to Pascal's triangle.The 6th-century Indian mathematician and astronomer Varāhamihira later described a recursive method for computing binomial coefficients that is mathematically equivalent to Pascal's triangle, although arranged in a different orientation.

The Persian mathematician Karaji (953-1029), roughly contemporary with Halāyudha, wrote a now-lost book which contained an explicit description of Pascal's triangle. His work was preserved and repeated by the Persian polymath Omar Khayyám (also known as Khayyám Nishapuri, after his birthplace of Nishapur, 1048-1131) in his Treatise on Demonstration of Problems of Algebra (c. 1070). Khayyám's distinctive contribution was to apply the triangle's binomial coefficients to a general method for extracting nth roots, an application not found in the earlier Indian or Karajian sources. Owing to this innovation and Khayyám's broad influence on later Islamic mathematics, the triangle is known in Iran as Khayyam's triangle (مثلث خیام) or the Khayyam-Pascal triangle (مثلث خیام-پاسکال). Several theorems related to the triangle were known, including the binomial theorem.

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.

Condensed: the full section is in Wikipedia.

Pascal's triangle determines the coefficients which arise in binomial expansions. For example, in the expansion \[(x + y)^2 = x^2 + 2xy + y^2 = \mathbf{1} x^2 y^0 + \mathbf{2} x^1 y^1 + \mathbf{1} x^0 y^2,\] the coefficients are the entries in the second row of Pascal's triangle: \(\tbinom 20 = 1\), \(\tbinom 21 = 2\), \(\tbinom 22 = 1\).

In general, the binomial theorem states that when a binomial like \(x + y\) is raised to a positive integer power \(n\), the expression expands as \[(x + y)^n = \sum_{k=0}^{n} a_{k} x^{n-k} y^{k} = a_{0} x^n + a_{1} x^{n - 1} y + a_{2} x^{n - 2} y^{2} + \ldots + a_{n - 1} x y^{n-1} + a_{n} y^{n},\] where the coefficients \(a_{k}\) are precisely the numbers in row \(n\) of Pascal's triangle: \[a_k = {n \choose k}.\]

The entire left diagonal of Pascal's triangle corresponds to the coefficient of \(x^n\) in these binomial expansions, while the next left diagonal corresponds to the coefficient of \(x^{n-1} y\), 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 \((x + y)^{n + 1}\) in terms of the corresponding coefficients of \((x + 1)^{n}\), where we set \(y = 1\) for simplicity. Suppose then that \[(x + 1)^{n} = \sum_{k = 0}^{n} a_{k} x^{k}.\] Now \[(x+1)^{n+1} = (x+1)(x+1)^n = x(x+1)^n + (x+1)^n = \sum_{i=0}^n a_i x^{i+1} + \sum_{k=0}^n a_k x^k.\]

The two summations can be reindexed with \(k=i+1\) and combined to yield \[\begin{align} \sum_{i=0}^{n} a_{i} x^{i+1} + \sum_{k=0}^n a_k x^k &= \sum_{k=1}^{n+1} a_{k-1} x^{k} + \sum_{k=0}^n a_k x^k \\ [4pt] &= \sum_{k=1}^{n} a_{k-1} x^{k} + a_{n}x^{n+1} + a_0x^0 + \sum_{k=1}^n a_k x^k \\[4pt] &= a_0x^0 + \sum_{k=1}^{n} (a_{k-1} + a_k)x^{k} + a_{n}x^{n+1} \\[4pt] &= x^0 + \sum_{k=1}^{n} (a_{k-1} + a_k)x^{k} + x^{n+1}. \end{align}\]

Thus the extreme left and right coefficients remain as 1, and for any given \(0 < k < n + 1\), the coefficient of the \(x^{k}\) term in the polynomial \((x + 1)^{n + 1}\) is equal to \(a_{k-1} + a_{k}\), the sum of the \(x^{k-1}\) and \(x^{k}\) coefficients in the previous power \((x + 1)^n\). 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.

Condensed: the full section is in Wikipedia.

A second useful application of Pascal's triangle is in the calculation of combinations. The number of combinations of \(n\) items taken \(k\) at a time, i.e. the number of subsets of \(k\) elements from among \(n\) elements, can be found by the equation

\({n \choose k} = \frac{n!}{k!(n-k)!}\).

(Other common notations for ⁠\(\tbinom nk\)⁠ include ⁠\(C(n, k)\)⁠, ⁠\(C_k^n\)⁠, and ⁠\({}_nC_k\)⁠.) This is equal to entry \(k\) in row \(n\) 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 \(\tbinom{7}{3}=35\).

When divided by \(2^n\), the \(n\)th row of Pascal's triangle becomes the binomial distribution in the symmetric case where \(p = \tfrac{1}{2}\). By the central limit theorem, this distribution approaches the normal distribution as \(n\) 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 \(\{ \ldots, 0, 0, 1, 1, 0, 0, \ldots \}\) with itself corresponds to taking powers of \(x + 1\), 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.)

• The sum of the elements of a single row is twice the sum of the row preceding it. For example, row 0 (the topmost row) 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 \(n\) equals to \(2^n\).
• Taking the product of the elements in each row, the sequence of products (sequence A001142 in the OEIS) is related to the base of the natural logarithm, e. Specifically, define the sequence \(s_{n}\) for all \(n \ge 0\) as follows: \(s_{n} = \prod_{k = 0}^{n} {n \choose k} = \prod_{k = 0}^{n} \frac{n!}{k!(n-k)!}\) Then, the ratio of successive row products is \[\frac{s_{n+1}}{s_{n}} = \frac{ \displaystyle (n+1)!^{n+2} \prod_{k = 0}^{n + 1} \frac{1}{k!^2}}n!^{n+1}\prod_{k=0}^{n}{\frac{1}{k!^2}}} = \frac{(n + 1)^n}{n!\] and the ratio of these ratios is \[\frac{s_{n + 1} \cdot s_{n - 1}}{s_{n}^{2}} = \left( \frac{n + 1}{n} \right)^n, ~ n\ge 1.\] The right-hand side of the above equation takes the form of the limit definition of \(e\) \[e =\lim_{n \to \infty} \left( 1 + \frac{1}{n} \right)^{n}.\]
• \(\pi\) can be found in Pascal's triangle by use of the Nilakantha infinite series. \[\pi = 3 + \sum_{n = 1}^{\infty} (-1)^{n + 1} \frac{{2n + 1 \choose 1}}{{2n + 1 \choose 2}{2n + 2 \choose 2}}\]
• 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 n equals the middle element of row 2n. For example, 1 + 4 + 6 + 4 + 1 = 70. In general form, \[\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}.\]
• In any even row \(n=2m\), the middle term minus the term two spots to the left equals a Catalan number, specifically \(C_{m-1} = \tbinom{2m}{m} - \tbinom{2m}{m-2}\). For example, in row 4, which is 1, 4, 6, 4, 1, we get the 3rd Catalan number \(C_3 = 6-1 = 5\).
• In a row p, where p is a prime number, all the terms in that row except the 1s are divisible by p. This can be proven easily, from the multiplicative formula \(\tbinom pk = \tfrac{p!}{k!(p-k)!}\). Since the denominator \(k!(p-k)!\) can have no prime factors equal to p, so p remains in the numerator after integer division, making the entire entry a multiple of p.
• Parity: To count odd terms in row n, convert n to binary. Let x be the number of 1s in the binary representation. Then the number of odd terms will be 2. These numbers are the values in Gould's sequence.
• Every entry in row 2 − 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.

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.

\(\begin{align} P_0(n) &= P_d(0) = 1, \\ P_d(n) &= P_d(n-1) + P_{d-1}(n) \\ &= \sum_{i=0}^n P_{d-1}(i) = \sum_{i=0}^d P_i(n-1). \end{align}\)

The symmetry of the triangle implies that the n d-dimensional number is equal to the d n-dimensional number.

An alternative formula that does not involve recursion is \[P_d(n)=\frac{1}{d!}\prod_{k=0}^{d-1} (n+k) = {n^{(d)}\over d!} = \binom{n+d-1}{d},\] where n 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₀(x) = 1 and P₁(x) = x, which is the sequence of natural numbers. The number of dots in each layer corresponds to P_d − 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\) with the elements \(\tbinom{n}{0}, \tbinom{n}{1}, \ldots, \tbinom{n}{n}\), begin with \(\tbinom{n}{0}=1\). For each subsequent element, the value is determined by multiplying the previous value by a fraction with slowly changing numerator and denominator:

\({n\choose k}= {n\choose k-1}\times \frac{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}\) and \(\tfrac{1}{5}\), and hence the elements are  \(\tbinom{5}{0}=1\), \(\tbinom{5}{1}=1\times\tfrac{5}{1}=5\), \(\tbinom{5}{2}=5\times\tfrac{4}{2}=10\), etc. (The remaining elements are most easily obtained by symmetry.)

To compute the diagonal containing the elements \(\tbinom{n}{0}, \tbinom{n+1}{1}, \tbinom{n+2}{2},\ldots,\) begin again with \(\tbinom{n}{0} = 1\) and obtain subsequent elements by multiplication by certain fractions:

\({n+k\choose k}= {n+k-1\choose k-1}\times \frac{n+k}{k}.\)

For example, to calculate the diagonal beginning at \(\tbinom{5}{0}\), the fractions are  \(\tfrac{6}{1}, \tfrac{7}{2}, \tfrac{8}{3}, \ldots\), and the elements are \(\tbinom{5}{0}=1, \tbinom{6}{1}=1 \times \tfrac{6}{1}=6, \tbinom{7}{2}=6\times\tfrac{7}{2}=21\), etc. By symmetry, these elements are equal to \(\tbinom{5}{5}, \tbinom{6}{5}, \tbinom{7}{5}\), etc.

• The pattern obtained by coloring only the odd numbers in Pascal's triangle closely resembles the fractal known as the Sierpiński triangle. This resemblance becomes increasingly accurate as more rows are considered; in the limit, as the number of rows approaches infinity, the resulting pattern is the Sierpiński triangle, assuming a fixed perimeter. More generally, numbers could be colored differently according to whether or not they are multiples of 3, 4, etc.; this results in other similar patterns.

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.

• In a triangular portion of a grid (as in the images below), the number of shortest grid paths from a given node to the top node of the triangle is the corresponding entry in Pascal's triangle. For example there are four shortest paths to the top from the node with value 4. On a Plinko game board shaped like a triangle, this distribution should give the probabilities of winning the various prizes.

• If the rows of Pascal's triangle are left-justified, the diagonal bands (colour-coded below) sum to the Fibonacci numbers.

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.

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, \(\R\), with basis 1.

Each row of Pascal's triangle gives the number of elements (such as edges and corners) of each dimension in a corresponding simplex (such as a triangle or tetrahedron). In particular, for k > 0, the kth entry in the nth row is the number of (k − 1)-dimensional elements in a (n − 1)-dimensional simplex. For example, a triangle (the 2-dimensional simplex) one 2-dimensional element (itself), three 1-dimensional elements (lines, or edges), and three 0-dimensional elements (vertices, or corners); this corresponds to the third row 1, 3, 3, 1 of Pascal's triangle. This fact can be explained by combining Pascal's rule for generating the triangle with the geometric construction of simplices: each simplex is formed from a simplex of one lower dimension by the addition of a new vertex, outside the space in which the lower-dimensional simplex lies. Then each d-dimensional element in the smaller simplex remains a d-dimensional element of the higher simplex, and each (d − 1)-dimensional element when joined to the new vertex forms a new d-dimensional element of the higher simplex.

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), instead of (x + 1). 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 \choose k} = 2\times{n-1 \choose k-1} + {n-1 \choose k}.\)

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} \text{ 1} \\ \text{ 1} \quad \text{ 2} \\ \text{ 1} \quad \text{ 4} \quad \text{ 4} \\ \text{ 1} \quad\text{ 6} \quad \text{ 12} \quad\text{ 8} \\ \text{ 1} \quad\text{ 8} \quad \text{ 24} \quad \text{ 32} \quad \text{ 16} \\ \text{ 1} \quad \text{ 10} \quad \text{ 40} \quad \text{ 80} \quad \text{ 80} \quad \text{ 32} \\ \text{ 1} \quad \text{ 12} \quad \text{ 60} \quad 160 \quad 240 \quad 192 \quad \text{ 64} \\ \text{ 1} \quad \text{ 14} \quad \text{ 84} \quad 280 \quad 560 \quad 672 \quad 448 \quad 128 \end{matrix}\)

In this triangle, the sum of the elements of row m is equal to 3. Again, to use the elements of row 4 as an example: 1 + 8 + 24 + 32 + 16 = 81, which is equal to \(3^4 = 81\).

Condensed: the full section is in Wikipedia.

As stated previously, the coefficients of (x + 1) are the nth row of the triangle. Now the coefficients of (x − 1) 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)/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:

\(\mathfrak{Re}\left(\text{Fourier} \left[ \frac{\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):

\(\mathfrak{Re}\left(\text{Fourier} \left[ \frac{\sin(x)^1}{x}\right] \right)\)

is the boxcar function. 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: \[+i,-1,-i,+1,+i,\ldots\]