Content deleted Content added
Citation bot (talk | contribs) m Alter: issue, journal. Add: url, issue, jstor. Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here.| Activated by User:Marianne Zimmerman |
more specific short description |
||
| (20 intermediate revisions by 11 users not shown) | |||
Line 1:
{{Short description|Numbers arranged in a triangle}}
{{
[[Image:BellNumberAnimated.gif|right|thumb|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]
In mathematics and computing, a '''triangular array''' of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the ''i''th row contains only ''i'' elements.
==Examples==
Line 7 ⟶ 8:
*The [[Bell triangle]], whose numbers count the [[Partition of a set|partitions of a set]] in which a given element is the largest [[singleton (mathematics)|singleton]]<ref>{{citation
| last = Shallit | first = Jeffrey | authorlink = Jeffrey Shallit
| editor1-first = Verner E. Jr. | editor1-last = Hoggatt
| editor2-first = Marjorie | editor2-last = Bicknell-Johnson
| contribution = A triangle for the Bell numbers
| ___location = Santa Clara, Calif.
Line 13 ⟶ 16:
| publisher = Fibonacci Association
| title = A collection of manuscripts related to the Fibonacci sequence
| url =
| contribution-url = http://www.fq.math.ca/Books/Collection/shallit.pdf
| year = 1980}}.</ref>
* [[Catalan's triangle]], which counts strings of matched parentheses
| title = Harmonic numbers, Catalan's triangle and mesh patterns▼
| last1 = Kitaev | first1 = Sergey | author1-link = Sergey Kitaev
| last2 = Liese | first2 = Jeffrey
| doi = 10.1016/j.disc.2013.03.017▼
| issue = 14▼
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
|
| pages = 1515–1531▼
▲ | title = Harmonic numbers, Catalan's triangle and mesh patterns
| volume = 313
▲ | issue = 14
| year = 2013| arxiv = 1209.6423▼
▲ | pages = 1515–1531
▲ | doi = 10.1016/j.disc.2013.03.017
| s2cid = 18248485
| url = https://personal.strath.ac.uk/sergey.kitaev/Papers/mesh1.pdf
}}.</ref>
* [[Euler's triangle]], which counts permutations with a given number of ascents<ref>{{citation
| title = Permutations and combination locks▼
| last1 = Velleman | first1 = Daniel J.
| last2 = Call | first2 = Gregory S.
| issue = 4▼
| journal = Mathematics Magazine
| year = 1995 | volume = 68 | issue = 4 | pages = 243–253
▲ | mr = 1363707
| doi = 10.1080/0025570X.1995.11996328
| pages = 243–253▼
▲ | title = Permutations and combination locks
| volume = 68▼
* [[Floyd's triangle]], whose entries are all of the integers in order<ref>{{citation
▲ | year = 1995| jstor = 2690567
| title = Programming by design: a first course in structured programming
| first1=Philip L. | last1=Miller
| first2 = Lee W. | last2 = Miller
| first3 = Purvis M. | last3=Jackson
| publisher = Wadsworth Pub. Co.
| year = 1987
| isbn = 978-0-534-08244-4
}}.</ref>
* [[Hosoya's triangle]], based on the [[Fibonacci number]]s<ref>{{citation
| title = Fibonacci triangle▼
| last = Hosoya | first = Haruo | author-link = Haruo Hosoya
| journal = [[The Fibonacci Quarterly]]
| pages = 173–178
| year = 1976| doi = 10.1080/00150517.1976.12430575 }}.</ref>
▲ | title = Fibonacci triangle
▲ | year = 1976}}.</ref>
* [[Lozanić's triangle]], used in the mathematics of chemical compounds<ref>{{citation
| last = Losanitsch | first = S. M.▼
| journal = Chem. Ber.▼
| title = Die Isomerie-Arten bei den Homologen der Paraffin-Reihe
| trans-title = The isomery species of the homologues of the paraffin series
| last = Losanitsch | first = Sima M. | author-link = Sima Lozanić
▲ | journal = [[Chem. Ber.]] | lang = de
| volume = 30
| issue = 2
| year = 1897
| doi=10.1002/cber.189703002144| url = https://zenodo.org/record/1425862▼
| doi = 10.1002/cber.189703002144
}}.</ref>
* [[Narayana triangle]], counting strings of balanced parentheses with a given number of distinct nestings<ref>{{citation
| title = On a generalization of the Narayana triangle▼
| last = Barry | first = Paul
| journal = Journal of Integer Sequences
|
▲ | title = On a generalization of the Narayana triangle
| volume = 14
| article-number = 11.4.5
| mr = 2792161
| url =
| year = 2011}}.</ref>
* [[Pascal's triangle]], whose entries are the [[binomial coefficients]]<ref>{{citation
| title = Pascal's Arithmetical Triangle: The Story of a Mathematical Idea | first = A. W. F. | last = Edwards | author-link = A. W. F. Edwards | publisher=JHU Press | year=2002 | isbn = Triangular arrays of integers in which each row is symmetric and begins and ends with 1 are sometimes called '''generalized Pascal triangles'''; examples include Pascal's triangle, the Narayana numbers, and the triangle of Eulerian numbers.<ref>{{citation
| issue = 6.2.4▼
| journal = Journal of Integer Sequences▼
▲ | pages = 1–34
| title = On integer-sequence-based constructions of generalized Pascal triangles
▲ | url = http://www.emis.ams.org/journals/JIS/VOL9/Barry/barry91.pdf
▲ | journal = Journal of Integer Sequences
|
| url = http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf
| year = 2006 | bibcode = 2006JIntS...9...24B
}}.</ref>
==Generalizations==
Line 92 ⟶ 113:
| title = Efficient computation of Ihara coefficients using the Bell polynomial recursion
| volume = 436
| year = 2012
}}.</ref>
Arrays in which the length of each row grows as a linear function of the row number (rather than being equal to the row number) have also been considered.<ref>{{citation|contribution=Pascal's triangle: Top gun or just one of the gang?|first1=Daniel C.|last1=Fielder|first2=Cecil O.|last2=Alford|pages=77–90|url=https://books.google.com/books?id=SfWNxl7K9pgC&pg=PA77|title=Applications of Fibonacci Numbers (Proceedings of the Fourth International Conference on Fibonacci Numbers and Their Applications, Wake Forest University, N.C., U.S.A., July 30–August 3, 1990)|editor1-first=Gerald E.|editor1-last=Bergum|editor2-first=Andreas N.|editor2-last=Philippou|editor3-first=A. F.|editor3-last=Horadam|publisher=Springer|year=1991|isbn=9780792313090}}.</ref>
==Applications==
[[Romberg's method]] can be used to estimate the value of a [[definite integral]] by completing the values in a triangle of numbers.<ref>{{citation|last=Thacher
▲[[Romberg's method]] can be used to estimate the value of a [[definite integral]] by completing the values in a triangle of numbers.<ref>{{citation|last=Thacher, Jr.|first=Henry C.|title=Remark on Algorithm 60: Romberg integration|journal=Communications of the ACM|volume=7|pages =420–421|date=July 1964|doi=10.1145/364520.364542|issue=7}}.</ref>
The [[Boustrophedon transform]] uses a triangular array to transform one [[integer sequence]] into another.<ref>{{citation
Line 112 ⟶ 132:
| title = A new operation on sequences: the Boustrouphedon transform
| volume = 76
| year = 1996 | doi=10.1006/jcta.1996.0087| s2cid = 15637402
}}.</ref> In general, a triangular array is used to store any table indexed by two [[natural numbers]] where ''j'' ≤ ''i''.
==Indexing==
Storing a triangular array in a computer requires a mapping from the two-dimensional coordinates (''i'', ''j'') to a linear [[memory address]]. If two triangular arrays of equal size are to be stored (such as in [[LU decomposition]]), they can be combined into a standard [[Array (data structure)|rectangular array]]. If there is only one array, or it must be easily appended to, the array may be stored where row ''i'' begins at the ''i''th [[triangular number]] ''T<sub>i</sub>''. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (<code>i*(i+1)/2</code>), so some optimizations such as using a [[Multiplication algorithm#Usage in computers|sequence of shifts and adds]] are not available.
==See also==
Line 118 ⟶ 144:
==References==
{{
==External links==
*{{mathworld|title=Number Triangle|urlname=NumberTriangle|mode=cs2}}
[[Category:Triangles of numbers| ]]
| |||