Content deleted Content added
No edit summary Tags: Reverted section blanking Mobile edit Mobile web edit |
→To arbitrary bases: refined congruence phrasing |
||
| (22 intermediate revisions by 15 users not shown) | |||
Line 2:
{{Image frame|width=230|caption=A diagram showing the first eight rows of Pascal's triangle.
|content=
<math>
\begin{array}{c}
1 \\
Line 8:
1 \quad 2 \quad 1 \\
1 \quad 3 \quad 3 \quad 1 \\
1 \quad 4 \quad 6 \quad 4 \quad 1 \\
1 \quad 5 \quad 10 \quad 10 \quad 5 \
1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \\
1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1
\end{array}
</math>
}}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">{{
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
== 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 109:
This is equal to entry <math>k</math> in row <math>n</math> 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 <math> \tbinom{7}{3}=35 </math>.<ref>{{Cite web |url=http://5010.mathed.usu.edu/Fall2018/HWheeler/probability.html |access-date=2023-06-01 |website=5010.mathed.usu.edu|title=Pascal's Triangle in Probability}}</ref>
== Relation to binomial distribution and convolutions ==
When divided by <math> 2^n</math>, the <math> n</math>th row of Pascal's triangle becomes the [[binomial distribution]] in the symmetric case where <math> p = \tfrac{1}{2}</math>. By the [[central limit theorem]], this distribution approaches the [[normal distribution]] as <math> n</math> 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 <math> \{ \ldots, 0, 0, 1, 1, 0, 0, \ldots \}</math> with itself corresponds to taking powers of <math> x + 1</math>, 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 [[composition (combinatorics)|compositions]] of ''n''
=== Rows ===
Line 137 ⟶ 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>
| last = Foster | first = T.
| doi = 10.5951/mathteacher.108.4.0246
Line 323 ⟶ 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 397 ⟶ 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 419 ⟶ 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 456 ⟶ 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 463 ⟶ 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 500 ⟶ 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 510 ⟶ 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>
| |||