Content deleted Content added
No edit summary Tags: Reverted Visual edit Mobile edit Mobile web edit |
→To arbitrary bases: refined congruence phrasing |
||
| (19 intermediate revisions by 13 users not shown) | |||
Line 16:
}}In [[mathematics]], '''Pascal's triangle''' is an infinite [[triangular array]] of the [[binomial coefficient]]s 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 [[mathematician]]s studied it centuries before him in Persia,<ref name=":0" /> India,<ref>Maurice Winternitz, ''History of Indian Literature'', Vol. III</ref> China, Germany, and Italy.<ref name="roots">{{cite book |author=Peter Fox |title=Cambridge University Library: the great collections |url=https://books.google.com/books?id=xxlgKP5thL8C&pg=PA13 |year=1998 |publisher=Cambridge University Press |isbn=978-0-521-62647-7 |page=13}}</ref>
The rows of Pascal's triangle are conventionally enumerated starting with row <math>n = 0</math> at the top (the 0th row). The entries in each row are numbered from the left beginning with <math>k = 0</math> 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
== Formula ==
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
| 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''
=== 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
*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 (mathematical constant)|e]]''.<ref>{{citation
| last = Brothers | first = H. J.
Line 140:
| year = 2012| issue = 535
| s2cid = 233356674
}}.</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>
\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>
| last = Foster | first = T.
| doi = 10.5951/mathteacher.108.4.0246
Line 150:
| title = Nilakantha's Footprints in Pascal's Triangle
| volume = 108
| year = 2014}}</ref> <math display="block">\pi = 3 + \
* 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|2''n''}}. For example, {{math|1=1<sup>2</sup> + 4<sup>2</sup> + 6<sup>2</sup> + 4<sup>2</sup> + 1<sup>2</sup> = 70}}. In general form, <math display="block">\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}.</math>
* In any even row <math>n=2m</math>, the middle term minus the term two spots to the left equals a [[
* 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 <math>\tbinom pk = \tfrac{p!}{k!(p-k)!} </math>. Since the denominator <math>k!(p-k)!</math> 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}}.<!--
[[Image:Exp binomial grey.svg|thumb|upright=1.25|left|Binomial matrix as matrix exponential (illustration for 5×5 matrices). All the dots represent 0.]] Comment: picture hidded since useless rescaling, also wrong paragraph for the pic -->
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 [[
=== Relation to geometry of polytopes ===
{{
Each row of Pascal's triangle
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)<sup>row number</sup>}}, instead of {{math|(''x'' + 1)<sup>row number</sup>}}. 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 [[
| 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 [[
| 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 [[
| 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 [[
| 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> [[
: <math>1.1^{1234}_{1234} = 2.885:2:35:977:696:\overbrace{\ldots}^\text{1227 digits}:0:1_{1234} = 2.717181235\ldots_{10}</math>
| |||