Triangular array: Difference between revisions

Revision as of 01:14, 9 May 2016

Latest revision as of 05:17, 28 May 2025

(24 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Numbers arranged in a triangle}}

{{distinguishDistinguish|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==

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 = httphttps://www.fq.math.ca/Books/Collection/shallitcollection.pdfhtml

| contribution-url = http://www.fq.math.ca/Books/Collection/shallit.pdf

| year = 1980}}.</ref>

* [[Catalan's triangle]], which counts strings of matched parentheses in which no close parenthesis is unmatched<ref>{{citation

| 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]]

| mryear = 30473902013

| pages = 1515–1531

| title = Harmonic numbers, Catalan's triangle and mesh patterns

| volume = 313

| yearissue = 2013}}.</ref>14

| pages = 1515–1531

| doi = 10.1016/j.disc.2013.03.017

| mr = 13637073047390

| arxiv = 1209.6423

| s2cid = 18248485

| url = https://personal.strath.ac.uk/sergey.kitaev/Papers/mesh1.pdf

| year = 1995}}.</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.

| doi = 10.2307/2690567

| 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

| mr = 1363707 | jstor = 2690567

| title = Permutations and combination locks

}}.</ref>

| volume = 68

* [[Floyd's triangle]], whose entries are all of the integers in order<ref>{{citation

| year = 1995}}.</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 =9780534082444 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

| issue = 2

| journal = [[The Fibonacci Quarterly]]

| pages = 173–178

| title = Fibonacci triangle

| volume = 14

| yearissue = 1976}}.</ref>2

| pages = 243–253173–178

| year = 1976| doi = 10.1080/00150517.1976.12430575 }}.</ref>

* [[Lozanić's triangle]], used in the mathematics of chemical compounds<ref>{{citation

| last = Losanitsch | first = S. M.

| journal = Chem. Ber.

| pages = 1917–1926

| 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 = 142

| year = 1897

| pages = 173–1781917–1926

| doi = 10.1002/cber.189703002144}}.</ref>

| 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

| issue = 4

| journal = Journal of Integer Sequences

| mrissue = 27921614

| page = Article 11.4.5, 22

| title = On a generalization of the Narayana triangle

| volume = 14

| article-number = 11.4.5

| mr = 2792161

| url = httphttps://wwwcs.emisuwaterloo.ams.orgca/journals/JIS/VOL9VOL14/BarryBarry4/barry91barry142.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 =9780801869464 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

| last = Barry | first = P.

| issue = 06.2.4

| journal = Journal of Integer Sequences

| pages = 1–34

| title = On integer-sequence-based constructions of generalized Pascal triangles

| last = LosanitschBarry | first = S. M.Paul

| url = http://www.emis.ams.org/journals/JIS/VOL9/Barry/barry91.pdf

| journal = Journal of Integer Sequences

| volume = 9

| yearvolume = 2006}}.</ref>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

}}.</ref>

==Generalizations==

Line 83 ⟶ 108:

| doi = 10.1016/j.laa.2011.08.017

| issue = 5

| journal = Linear Algebra and itsIts Applications

| mr = 2890929

| pages = 1436–1441

| title = Efficient computation of Ihara coefficients using the Bell polynomial recursion

| volume = 436

| year = 2012}}.</ref>| 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=httphttps://books.google.com/books?id=SfWNxl7K9pgC&pg=PA77|title=Applications of Fibonacci Numbers (Proceedings of Thethe 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|url=http://portal.acm.org/citation.cfm?id=364520.364542|doi=10.1145/364520.364542|issue=7|s2cid=29898282 |doi-access=free}}.</ref>

Apart from the representation of [[triangular matrix|triangular matrices]], triangular arrays are used in several [[algorithm]]s. One example is the [[CYK algorithm]] for parsing [[context-free grammar]]s, an example of [[dynamic programming]].<ref>{{citation|title=Handbook of Natural Language Processing, Second Edition|editor1-first=Nitin|editor1-last=Indurkhya|editor2-first=Fred J.|editor2-last=Damerau|publisher=CRC Press|year=2010|isbn=9781420085938|page=65|url=http://books.google.com/books?id=nK-QYHZ0-_gC&pg=PA65}}.</ref>

[[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|url=http://portal.acm.org/citation.cfm?id=364520.364542|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 108 ⟶ 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'',&nbsp;''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_i''. 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 114 ⟶ 144:

==References==

{{reflistReflist|30em}}

==External links==

*{{mathworld|title=Number Triangle|urlname=NumberTriangle|mode=cs2}}

[[Category:Triangles of numbers| ]]