Pascal's triangle: Difference between revisions

Revision as of 06:16, 31 January 2025

Latest revision as of 16:36, 29 July 2025

(29 intermediate revisions by 17 users not shown)

Line 27:

[[File:TrianguloPascal.jpg|thumb|right|upright=1.25|[[Blaise Pascal|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 description of Pascal's triangle.<ref>{{Cite book|url=https://books.google.com/books?id=kt9DIY1g9HYC&q=al+karaji+pascal%27s+triangle&pg=PA132|title=Encyclopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures|last=Selin|first=Helaine|date=2008-03-12|publisher=Springer Science & Business Media|isbn=9781402045592|language=en|page=132|bibcode=2008ehst.book.....S|quote=Other, lost works of al-Karaji's are known to have dealt with inderterminate algebra, arithmetic, inheritance algebra, and the construction of buildings. Another contained the first known explanation of the arithmetical (Pascal's) triangle; the passage in question survived through al-Sama'wal's Bahir (twelfth century) which heavily drew from the Badi.}}</ref><ref>{{Cite book |last=Rashed |first=R. |url=https://books.google.com/books?id=vSkClSvU_9AC&pg=PA62 |title=The Development of Arabic Mathematics: Between Arithmetic and Algebra |date=1994-06-30 |publisher=Springer Science & Business Media |isbn=978-0-7923-2565-9 |pages=63 |language=en}}</ref><ref>{{Cite book|url=https://books.google.com/books?id=kAjABAAAQBAJ&q=al+karaji+binomial+theorem&pg=PA54|title=From Alexandria, Through Baghdad: Surveys and Studies in the Ancient Greek and Medieval Islamic Mathematical Sciences in Honor of J.L. Berggren|last1=Sidoli|first1=Nathan|last2=Brummelen|first2=Glen Van|date=2013-10-30|publisher=Springer Science & Business Media|isbn=9783642367366|language=en|page=54|quote=However, the use of binomial coefficients by Islamic mathematicians of the eleventh century, in a context which had deep roots in Islamic mathematics, suggests strongly the table was a local discovery - most probably of al-Karaji."}}</ref> In India, the ''[[Chandaḥśāstra]]'' by the Indian lyricistpoet and mathematician [[Piṅgala]] (3rd or 2nd century BC) somewhat crypicallycryptically describes a method of arranging two types of syllables to form [[metre (poetry)|metre]]s of various lengths and counting them; as interpreted and elaborated by Piṅgala's 10th-century commentator [[Halāyudha]] his "method of pyramidal expansion" (''meru-prastāra'') for counting metres is equivalent to [[Pascal's triangle]].<ref>{{cite journal |last=Alsdorf |first=Ludwig |year=1991 |orig-year=1933 |title=The Pratyayas: Indian Contribution to Combinatorics |journal=Indian Journal of History of Science |volume=26 |number=1 |pages=17–61 |url=https://insa.nic.in/(S(f0a4mvblfb5vfmialsdau2an))/writereaddata/UpLoadedFiles/IJHS/Vol26_1_3_SRSarma.pdf}} Translated by S. R. Sarma from {{cite journal |last=Alsdorf |first=Ludwig |display-authors=0 |title={{mvar|π}} Die Pratyayas. Ein Beitrag zur indischen Mathematik |journal=Zeitschrift furfür Indologie und Iranistik |volume=9 |year=1933 |pages=97–157 }} {{pb}} {{cite journal |last=Bag |first=Amulya Kumar |title=Binomial theorem in ancient India |journal=Indian Journal of History of Science |volume=1 |number=1 |year=1966 |pages=68–74 |url=http://repository.ias.ac.in/70374/1/10-pub.pdf }} {{pb}} Tertiary sources: {{pb}} {{cite book |title=A Concise History Of Science In India |year=1971 |publisher=Indian National Science Academy |editor-last=Bose |editor-first=D. M. |editor-link=Debendra Mohan Bose |last=Sen |first=Samarendra Nath |chapter=Mathematics |chapter-url=https://archive.org/details/in.ernet.dli.2015.502083/page/n178 |at=Ch. 3, {{pgs|136–212}}, esp. "Permutations, Combinations and Pascal Triangle", {{pgs|156–157}} }} {{pb}} {{cite journal |title=The Binomial Coefficient Function |last=Fowler |first=David H. |author-link= David Fowler (mathematician) |journal=The American Mathematical Monthly |year=1996 |volume=103 |number=1 |pages=1–17, esp. §4 "A Historical Note", {{pgs|10–17}} |doi=10.2307/2975209 |jstor=2975209 }}</ref> It was later repeated by [[Omar Khayyám]] (1048–1131), another Persian mathematician; thus the triangle is also referred to as '''Khayyam's triangle''' ({{langx|fa|مثلث خیام|label=none}}) in Iran.<ref>{{cite book |author=Kennedy, E. |title=Omar Khayyam. The Mathematics Teacher 1958 |jstor=i27957284|year=1966 |publisher=National Council of Teachers of Mathematics |pages=140–142}}</ref> Several theorems related to the triangle were known, including the [[binomial theorem]]. Khayyam used a method of finding [[nth root|''n''th roots]] based on the binomial expansion, and therefore on the binomial coefficients.<ref name=":0">{{citation

| last = Coolidge | first = J. L. | author-link = Julian Coolidge

| journal = [[The American Mathematical Monthly]]

Line 92:

Thus the extreme left and right coefficients remain as 1, and for any given <math>0 < k < n + 1 </math>, the coefficient of the <math>x^{k} </math> term in the polynomial <math>(x + 1)^{n + 1} </math> is equal to <math>a_{k-1} + a_{k} </math>, the sum of the <math>x^{k-1} </math> and <math>x^{k} </math> coefficients in the previous power <math>(x + 1)^n </math>. This is indeed the downward-addition rule for constructing Pascal's triangle.

It is not difficult to turn this argument into a [[proof (mathematics)|proof]] (by [[mathematical induction]]) of the binomial theorem.

Since <math>(a + b)^{n} = b^{n}(\tfrac{a}{b} + 1 )^{n} </math>, the coefficients are identical in the expansion of the general case.

Line 118:

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 [[composition (combinatorics)|compositions]] of ''n''&hairsp;+1 into ''k''&hairsp;+1 ordered partitions form Pascal's triangle.]]

=== Rows ===

Line 142:

}}.</ref> Specifically, define the sequence <math> s_{n}</math> for all <math>n \ge 0</math> as follows: <math>s_{n} = \prod_{k = 0}^{n} {n \choose k} = \prod_{k = 0}^{n} \frac{n!}{k!(n-k)!}</math> {{pb}} Then, the ratio of successive row products is <math display="block">\frac{s_{n+1}}{s_{n}} =

\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!}</math> and the ratio of these ratios is <math display="block">\frac{s_{n + 1} \cdot s_{n - 1}}{s_{n}^{2}} =

\left( \frac{n + 1}{n} \right)^n, ~ n\ge 1.</math> The right-hand side of the above equation takes the form of the limit definition of [[e (mathematical constant)|<math>e</math>]] <math display="block">e =\lim_{n \to \infty} \left( 1 + \frac{1}{n} \right)^{n}.</math>.

* [[pi|<math>\pi</math>]] can be found in Pascal's triangle by use of the [[Nilakantha Somayaji|Nilakantha]] infinite series.<ref> {{citation

| last = Foster | first = T.

| doi = 10.5951/mathteacher.108.4.0246

Line 220:

=== Overall patterns and properties ===

[[File:Sierpinski Pascal triangle.svg|thumb|A level-4 approximation to a Sierpinski[[Sierpiński 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 [[SierpinskiSierpiń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 SierpinskiSierpiń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.<ref>Ian Stewart, "How to Cut a Cake", Oxford University Press, page 180</ref>

<div class="thumb tright" style="clear: right; text-align: center;">

Line 328:

===Construction of Clifford algebra using simplices===

Labelling the elements of each n-simplex matches the basis elements of [[Clifford algebra]] used as forms in [[Geometric_algebraGeometric algebra|Geometric Algebra]] rather than matrices. Recognising the geometric operations, such as rotations, allows the algebra operations to be discovered. Just as each row, {{mvar|n}}, starting at 0, of Pascal's triangle corresponds to an {{mvar|(n-1)}}-simplex, as described below, it also defines the number of named basis forms in {{mvar|n}} dimensional [[Geometric algebra]]. The [[binomial theorem]] can be used to prove the geometric relationship provided by Pascal's triangle.<ref>{{citation |url=https://github.com/GPWilmot/geoalg|title=The Algebra Of Geometry|year=2023|last=Wilmot|first=G.P.}}</ref> 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, <math>\R</math>, with basis 1.

=== Relation to geometry of polytopes ===

{{unreferencedmore citations needed section|date=OctoberFebruary 20162025}}

Each row of Pascal's triangle cangives bethe usednumber of elements (such as edges and corners) of each dimension in a corresponding [[lookup tablesimplex]] (such as a triangle or tetrahedron). In particular, for {{math| ''k'' > 0}}, the {{mvar|k}}th entry in the {{mvar|n}}th row is the number of {{math|(''k'' − 1)}}-dimensional elements in a {{math|(such''n'' as− 1)}}-dimensional simplex. For example, a triangle (the 2-dimensional simplex) one 2-dimensional element (itself), three 1-dimensional elements (lines, or edges), and corners)three within0-dimensional aelements ([[polytopeVertex (graph theory)|vertices]], (suchor ascorners); athis trianglecorresponds to the third row 1, a3, tetrahedron3, 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 squaresimplex of one lower dimension by the addition of a new vertex, oroutside the space in which the lower-dimensional simplex lies. Then each {{mvar|d}}-dimensional element in the smaller simplex remains a cube{{mvar|d}}-dimensional element of the higher simplex, and each {{math|(''d'' − 1)}}-dimensional element when joined to the new vertex forms a new {{mvar|d}}-dimensional element of the higher simplex.<ref>{{Cite book |last=Coxeter |first=Harold Scott Macdonald |url=https://books.google.com/books?id=iWvXsVInpgMC |title=Regular Polytopes |date=1973-01-01 |publisher=Courier Corporation |isbn=978-0-486-61480-9 |edition=3rd |pages=118–144 |language=en |chapter=Chapter VII: ordinary polytopes in higher space, 7.2: Pyramids, dipyramids and prisms}}</ref>

==== Number of elements of simplices ====

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 ([[Vertex (graph theory)|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 [[simplex|simplices]]).

To understand why this pattern exists, one must first understand that the process of building an ''n''-simplex from an {{math|(''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. 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 [[cell (mathematics)|cells]] (polyhedral elements) is {{math|1={{define|0|the original triangle possesses none}} + {{define|1|built upon the single face of the original triangle}} = '''1'''}}; the number of faces is {{math|1={{define|1|the original triangle itself}} + {{define|3|the new faces, each built upon an edge of the original triangle}} = '''4''';}} the number of edges is {{math|1={{define|3|from the original triangle}} + {{define|3|the new edges, each built upon a vertex of the original triangle}} = '''6''';}} the number of new vertices is {{math|1={{define|3|from the original triangle}} + {{define|1|the new vertex that was added to create the tetrahedron from the triangle}} = '''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.

==== Number of elements of hypercubes ====

A similar pattern is observed relating to [[square (geometry)|squares]], as opposed to triangles. To find the pattern, one must construct an analog to Pascal's triangle, whose entries are the coefficients of {{math|(''x'' + 2)^{row number}}}, instead of {{math|(''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:

Line 402 ⟶ 392:

=== To complex numbers ===

When the factorial function is defined as <math>z! = \Gamma(z + 1)</math>, Pascal's triangle can be extended beyond the integers to <math>\Complex</math>, since <math>\Gamma(z + 1)</math> is [[Meromorphic_functionMeromorphic function|meromorphic]] to the entire [[complex plane]].<ref>{{cite book

| display-authors = etal

| last = Hilton | first = P.

Line 424 ⟶ 414:

| quote = But these in the alternate areas, which are given, I observed were the same with the figures of which the several ascending powers of the number 11 consist, viz. <math>11^{0}</math>, <math>11^{1}</math>, <math>11^{2}</math>, <math>11^{3}</math>, <math>11^{4}</math>, etc. that is, first 1; the second 1, 1; the third 1, 2, 1; the fourth 1, 3, 3, 1; the fifth 1, 4, 6, 4, 1, and so on

| url = https://www.loc.gov/item/42048007/

}}.</ref> In 1964, Robert L. Morton presented the more generalized argument that each [[#Rows|row]] <math>n</math> can be read as a radix <math>a</math> numeral, where [[E (mathematical constant)|<math>\lim_{n \to \infty} 11^{n}_{a}</math>]] is the hypothetical terminal row, or [[Infinite_productInfinite product|limit]], of the triangle, and the rows are its partial products.<ref>{{citation

| last = Morton | first = Robert L.

| issue = 6

Line 461 ⟶ 451:

| last = Kallós | first = Gábor

| issue = 1

| journal = Annales Mathématiques Blaise Pascal

| pages = 1–15

| title = A generalization of Pascal's triangle using powers of base numbers

Line 468 ⟶ 458:

| doi = 10.5802/ambp.211

| url = https://ambp.centre-mersenne.org/item/10.5802/ambp.211.pdf

}}.</ref> as demonstrated [[#Binomial expansions|above]]. Thus, when the entries of the row are concatenated and read in radix <math>a</math> they form the numerical equivalent of <math>(a + 1)^{n} = 11^{n}_{a}</math>. If <math>c = a + 1</math> for <math>c < 0</math>, then the theorem [[Negative_baseNegative base|holds]] for <math>a =\bmod 2c</math>, with <math>a</math> congruent to <math>\{c - 1, -(c + 1)\} \;\mathrm{mod}\; 2c</math>, and with odd values of <math>n</math> [[Negative_numberNegative number#Multiplication|yielding]] negative row products.<ref>{{cite book

| display-authors = etal

| last = Hilton | first = P.

Line 505 ⟶ 495:

: <math>11^{12}_{12} = 1:10:56:164:353:560:650:560:353:164:56:10:1_{12} = 27433a9699701_{12}</math>

with compound digits (delimited by ":") in radix twelve. The digits from <math>k = n - 1</math> through <math>k = 1</math> are compound because these row entries compute to values greater than or equal to twelve. To [[Trapdoor_functionTrapdoor function|normalize]]<ref>{{citation

| last = Fjelstad | first = P.

| issue = 9

Line 515 ⟶ 505:

| year = 1991

| doi-access = free

}}.</ref> the numeral, simply carry the first compound entry's prefix, that is, remove the prefix of the coefficient <math>\textstyle {n \choose n - 1}</math> from its leftmost digit up to, but excluding, its rightmost digit, and use radix-twelve arithmetic to sum the removed prefix with the entry on its immediate left, then repeat this process, proceeding leftward, until the leftmost entry is reached. In this particular example, the normalized string ends with <math>01</math> for all <math>n</math>. The leftmost digit is <math>2</math> for <math>n > 2</math>, which is obtained by carrying the <math>1</math> of <math>10_{n}</math> at entry <math>k = 1</math>. It follows that the length of the normalized value of <math>11^{n}_{n}</math> is [[Bijection|equal]] to the row length, <math>n + 1</math>. The integral part of <math>1.1^{n}_{n}</math> contains exactly one digit because <math>n</math> (the number of places to the left the decimal has moved) is one less than the row length. Below is the normalized value of <math>1.1^{1234}_{1234}</math>. Compound digits remain in the value because they are radix <math>1234</math> [[Modular_arithmeticModular arithmetic#Integers modulo m|residues]] represented in radix ten:

: <math>1.1^{1234}_{1234} = 2.885:2:35:977:696:\overbrace{\ldots}^\text{1227 digits}:0:1_{1234} = 2.717181235\ldots_{10}</math>