Triangular array
{{Short description|Numbers arranged in a triangle}}
{{Distinguish|Triangular matrix}}
Image:BellNumberAnimated.gif]]
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 ith row contains only i elements.
Examples
Notable particular examples include these:
- The Bell triangle, whose numbers count the partitions of a set in which a given element is the largest singleton{{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}}.
- Catalan's triangle, which counts strings of matched parentheses{{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
| 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
}}.
- Euler's triangle, which counts permutations with a given number of ascents{{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
}}.
- Floyd's triangle, whose entries are all of the integers in order{{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
}}.
- Hosoya's triangle, based on the Fibonacci numbers{{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 }}.
- Lozanić's triangle, used in the mathematics of chemical compounds{{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
}}.
- Narayana triangle, counting strings of balanced parentheses with a given number of distinct nestings{{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}}.
- Pascal's triangle, whose entries are the binomial coefficients{{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}}.
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.{{citation
| title = On integer-sequence-based constructions of generalized Pascal triangles
| last = Barry | first = Paul
| journal = Journal of Integer Sequences
| volume = 9 | issue = 2
| article-number = 6.2.4
| url = http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf
| year = 2006 | bibcode = 2006JIntS...9...24B
}}.
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.{{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
}}.
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.{{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}}.
Applications
Romberg's method can be used to estimate the value of a definite integral by completing the values in a triangle of numbers.{{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}}.
The Boustrophedon transform uses a triangular array to transform one integer sequence into another.{{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
}}.
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 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 ith triangular number Ti. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (i*(i+1)/2), so some optimizations such as using a sequence of shifts and adds are not available.
See also
- Triangular number, the number of entries in such an array up to some particular row
References
{{Reflist|30em}}