{{short description|Triangular array of the binomial coefficients in mathematics}}{{Image frame|width=230|caption=A diagram showing the first eight rows of Pascal's triangle.|content=begin{array}{c} end{array}}}In mathematics, Pascal's triangle is a 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,Maurice Winternitz, History of Indian Literature, Vol. III China, Germany, and Italy.BOOK, Peter Fox, Cambridge University Library: the great collections,weblink 1998, Cambridge University Press, 978-0-521-62647-7, 13, The kth entry in the nth row of Pascal's triangle is the binomial coefficient "n choose k", written tbinom nk. The rows are enumerated from n = 0 at the top (the 0th row), and the entries in each row are numbered from k = 0 on the left to k = n on the right, and are usually staggered left relative to the numbers in the previous row. The triangle may be constructed as follows: the top entry is equal to 1, and each lower entry is the sum of the two entries above it to the left and 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 first two numbers 1 and 3 in row 3 are added to produce the number 4 below them in row 4.

Formula

(File:PascalTriangleAnimated2.gif|thumb|upright=1|In Pascal's triangle, each number is the sum of the two numbers directly above it.)In the nth row of Pascal's triangle, the k th entry is denoted tbinom nk, pronounced "n choose k". For example, the topmost element is tbinom 00 = 1. With this notation, the downward addition construction of the previous paragraph may be written as: for any non-negative integer n and any integer 0 le k le n.The binomial coefficient scriptstyle {n choose k} is conventionally set to zero if k is either less than zero or greater than n. This recurrence for the binomial coefficients is known as Pascal's rule.

History

File:Yanghui triangle.gif|thumb|right|upright=1|Yang Hui's triangle, as depicted by the Chinese using rod numerals, appears in Jade Mirror of the Four Unknowns, a mathematical work by Zhu ShijieZhu ShijieFile:TrianguloPascal.jpg|thumb|right|upright=1.25|Pascal's version of the triangle]]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.BOOK,weblink Encyclopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures, Selin, Helaine, 2008-03-12, Springer Science & Business Media, 9781402045592, en, 132, 2008ehst.book.....S, The Development of Arabic Mathematics Between Arithmetic and Algebra - R. Rashed "Page 63"BOOK,weblink From Alexandria, Through Baghdad: Surveys and Studies in the Ancient Greek and Medieval Islamic Mathematical Sciences in Honor of J.L. Berggren, Sidoli, Nathan, Brummelen, Glen Van, 2013-10-30, Springer Science & Business Media, 9783642367366, en, 54, 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.BOOK, Kennedy, E., Omar Khayyam. The Mathematics Teacher 1958, i27957284, 1966, National Council of Teachers of Mathematics, 140–142, 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.{{citation 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 () in China.Weisstein, Eric W. (2003). CRC concise encyclopedia of mathematics, p. 2169. {{isbn|978-1-58488-347-0}}.In Europe, Pascal's triangle appeared for the first time in the Arithmetic of Jordanus de Nemore (13th century).JOURNAL, Hughes, Barnabas, The arithmetical triangle of Jordanus de Nemore, Historia Mathematica, 1 August 1989, 16, 3, 213–223, 10.1016/0315-0860(89)90018-9, free, The binomial coefficients were calculated by Gersonides during the early 14th century, using the multiplicative formula for them.{{citation|contribution=The arithmetical triangle|first=A. W. F.|last=Edwards|pages=166–180|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins}}. Petrus Apianus (1495–1552) published the full triangle on the frontispiece of his book on business calculations in 1527.{{citation|title=Nature of Mathematics|first=Karl J.|last=Smith|publisher=Cengage Learning|year=2010|isbn=9780538737586|page=10|url=https://books.google.com/books?id=Di0HyCgDYq8C&pg=PA10}}. 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 posthumously in 1665.Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière at gallica 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 table de M. Pascal pour les combinaisons (French: Mr. Pascal's table for combinations) and Abraham de Moivre (1730) who called it Triangulum Arithmeticum PASCALIANUM (Latin: Pascal's Arithmetic Triangle), which became the basis of the modern Western name.JOURNAL, 10.2307/2975209, The Binomial Coefficient Function, David, Fowler, David Fowler (mathematician), The American Mathematical Monthly, 103, 1, January 1996, 1–17, 2975209, See in particular p. 11.

Binomial expansions

(File:Binomial theorem visualisation.svg|thumb|upright=1.25|Visualisation of binomial expansion up to the 4th power)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 into:(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: 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 sett y = 1 for simplicity. Suppose then that Now {hide}Image frame|width=260|caption=Six rows Pascal's triangle as binomial coefficients|content=begin{array}{c}dbinom{0}{0} dbinom{5}{0} quad dbinom{5}{1} quad dbinom{5}{2} quad dbinom{5}{3} quad dbinom{5}{4} quad dbinom{5}{5}end{array{edih}}The two summations can be reindexed with k=i+1 and combined: 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. Since (a + b)^{n} = b^{n}(tfrac{a}{b} + 1 )^{n} , the coefficients are identical in the expansion of the general case.An interesting consequence of the binomial theorem is obtained by setting both variables x = y = 1 , so that:

{n choose 0} + {n choose 1} + cdots + {n choose n-1} + {n choose n}

(1+1)^n 2^{n}.

In other words, the sum of the entries in the nth row of Pascal's triangle is the nth power of 2. This is equivalent to the statement that the number of subsets of an n-element set is 2^n, as can be seen by observing that each of the n 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 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 This is equal to entry k in row of n 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, which is tbinom{7}{3}=35 .WEB,weblink 2023-06-01, 5010.mathed.usu.edu, Pascal's Triangle in Probability,

Relation to binomial distribution and convolutions

When divided by 2^n, the nth 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.)

Patterns and properties

Pascal's triangle has many properties and contains many patterns of numbers.(File:Pascal's Triangle animated binary rows.gif|thumb|upright=1|Each frame represents a row in Pascal's triangle. Each column of pixels is a number in binary with the least significant bit at the bottom. Light pixels represent 1 and dark pixels 0.)File:pascal_triangle_compositions.svg|thumb|upright=1|The numbers of compositions of n +1 into k +1 ordered partitions form Pascal's triangle.]]

Rows

• 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 {{OEIS|id=A001142}} is related to the base of the natural logarithm, e.{{citation

frac{ displaystyle (n+1)!^{n+2} prod_{k = 0}^{n + 1} frac{1}{k!^2}}{displaystyle 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, ~ nge 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. {{citation

• The nth row reads as the numeral 11^{n}, which holds for its representation in an arbitrary base. For example, row 6 of the triangle is 1, 6, 15, 20, 15, 6, 1, and the sixth power of 11 has base-ten digits: 11^6 = 1061520150601
• 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 {{mvar|n}} equals the middle element of row {{math|2n}}. For example, {{math|1=12 + 42 + 62 + 42 + 12 = 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 {{mvar|p}}, where {{mvar|p}} is a prime number, all the terms in that row except the 1s are divisible by {{mvar|p}}. This can be proven easily, from the multiplicative formula tbinom pk = tfrac{p!}{k!(p-k)!} . Since the denominator p!(p-k)! can have no prime factors equal to {{mvar|p}}, so {{mvar|p}} remains in the numerator after integer division, making the entire entry a multiple of {{mvar|p}}.
• Parity: To count odd terms in row {{mvar|n}}, convert {{mvar|n}} to binary. Let {{mvar|x}} be the number of 1s in the binary representation. Then the number of odd terms will be {{math|2x}}. These numbers are the values in Gould's sequence.{{citation

• Every entry in row 2n âˆ’ 1, n â‰¥ 0, is odd.{{citation

• 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

File:Pascal_triangle_simplex_numbers.svg|thumb|upright=1.25|Derivation of simplexsimplexThe 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.

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 nth d-dimensional number is equal to the dth n-dimensional number.An alternative formula that does not involve recursion isP_d(n)=frac{1}{d!}prod_{k=0}^{d-1} (n+k) = {n^{(d)}over d!} = binom{n+d-1}{d},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 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 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 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: 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}=1timestfrac{5}{1}=5,   tbinom{5}{2}=5timestfrac{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: 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}=6timestfrac{7}{2}=21, etc. By symmetry, these elements are equal to tbinom{5}{5}, tbinom{6}{5}, tbinom{7}{5}, etc.File:Fibonacci in Pascal triangle.png|thumb|Fibonacci sequenceFibonacci sequence

Overall patterns and properties

(File:Sierpinski Pascal triangle.svg|thumb|A level-4 approximation to a Sierpinski triangle obtained by shading the first 32 rows of a Pascal triangle white if the binomial coefficient is even and black if it is odd.)

• The pattern obtained by coloring only the odd numbers in Pascal's triangle closely resembles the fractal known as the Sierpinski 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 Sierpinski 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.

{| cellpadding="0" cellspacing="0" style="line-height: 0; background: white; font-size: 88%; border: 1px #b0b0b0 solid; padding: 0; margin: auto" style="vertical-align: middle"

(File:Chess rll45.svg	alt=a4 white rook|a4 white rook)	(File:Chess x1d45.svg	alt=b4 one|b4 one)	(File:Chess x1l45.svg	alt=c4 one|c4 one)	(File:Chess x1d45.svg	alt=d4 one|d4 one)

style="vertical-align: middle"

(File:Chess x1d45.svg	alt=a3 one|a3 one)	(File:Chess x2l45.svg	alt=b3 two|b3 two)	(File:Chess x3d45.svg	alt=c3 three|c3 three)	(File:Chess x4l45.svg	alt=d3 four|d3 four)

style="vertical-align: middle"

(File:Chess x1l45.svg	alt=a2 one|a2 one)	(File:Chess x3d45.svg	alt=b2 three|b2 three)	(File:Chess x6l45.svg	alt=c2 six|c2 six)	{{resize	10}}

style="vertical-align: middle"

(File:Chess x1d45.svg	alt=a1 one|a1 one)	(File:Chess x4l45.svg	alt=b1 four|b1 four)	{{resize	10}}	{{resize	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.

• 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. On a Plinko game board shaped like a triangle, this distribution should give the probabilities of winning the various prizes.

center|400px

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