Content deleted Content added
fix cat |
more specific short description |
||
| (38 intermediate revisions by 22 users not shown) | |||
Line 1:
{{Short description|Numbers arranged in a triangle}}
{{Distinguish|Triangular matrix}}
[[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==
Notable particular examples include these:
*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.
| mr = 624091
| pages = 69–71
| publisher = Fibonacci Association
| title = A collection of manuscripts related to the Fibonacci sequence
| url = https://www.fq.math.ca/collection.html
| contribution-url = http://www.fq.math.ca/Books/Collection/shallit.pdf
| year = 1980}}.</ref>
* [[Catalan's triangle]], which counts strings of matched parentheses<ref>{{citation
| title = Harmonic numbers, Catalan's triangle and mesh patterns
| last1 = Kitaev | first1 = Sergey | author1-link = Sergey Kitaev
| last2 = Liese | first2 = Jeffrey
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| year = 2013
| volume = 313
| issue = 14
| pages = 1515–1531
| doi = 10.1016/j.disc.2013.03.017
| mr = 3047390
| arxiv = 1209.6423
| 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.
| journal = Mathematics Magazine
| year = 1995 | volume = 68 | issue = 4 | pages = 243–253
| doi = 10.1080/0025570X.1995.11996328
| mr = 1363707 | jstor = 2690567
}}.</ref>
* [[Floyd's triangle]], whose entries are all of the integers in order<ref>{{citation
| title = Programming by design: a first course in structured programming
| pages=211–212
| 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]]
| volume = 14
| issue = 2
| pages = 173–178
| year = 1976| doi = 10.1080/00150517.1976.12430575 }}.</ref>
* [[Lozanić's triangle]], used in the mathematics of chemical compounds<ref>{{citation
| 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
| pages = 1917–1926
| doi = 10.1002/cber.189703002144
| url = https://zenodo.org/record/1425862
}}.</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
| issue = 4
| volume = 14
| article-number = 11.4.5
| mr = 2792161
| url = https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.pdf
| 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 = 978-0-8018-6946-4}}.</ref>
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
| title = On integer-sequence-based constructions of generalized Pascal triangles
| last = Barry | first = Paul
| journal = Journal of Integer Sequences
|
| article-number = 6.2.4
| url = http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf
| year = 2006 | bibcode = 2006JIntS...9...24B
}}.</ref>
==Generalizations==
Triangular arrays may list mathematical values other than numbers; for instance the [[Bell polynomials]] form a triangular array in which each array entry is a polynomial.<ref>{{citation
| last1 = Rota Bulò | first1 = Samuel
| last2 = Hancock | first2 = Edwin R.
| last3 = Aziz | first3 = Furqan
| last4 = Pelillo | first4 = Marcello
| doi = 10.1016/j.laa.2011.08.017
| issue = 5
| journal = Linear Algebra and Its Applications
| mr = 2890929
| pages = 1436–1441
| title = Efficient computation of Ihara coefficients using the Bell polynomial recursion
| volume = 436
| year = 2012| doi-access = free
}}.</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 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|s2cid=29898282 |doi-access=free}}.</ref>
The [[Boustrophedon transform]] uses a triangular array to transform one [[integer sequence]] into another.<ref>{{citation
| last1 = Millar | first1 = Jessica
| last2 = Sloane | first2 = N. J. A.
| last3 = Young | first3 = Neal E.
| arxiv = math.CO/0205218
| issue = 1
| journal = Journal of Combinatorial Theory
| pages = 44–54
| series = Series A
| 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==
* [[Triangular number]]
==References==
{{
==External links==
*{{mathworld|title=Number Triangle|urlname=NumberTriangle|mode=cs2}}
[[Category:Triangles of numbers| ]]
| |||