Triangular array: Difference between revisions
From HandWiki
imported>HamTop fix |
DanMescoff (talk | contribs) link |
||
| Line 1: | Line 1: | ||
{{Short description| | {{Short description|Numbers arranged in a triangle}} | ||
[[Image:BellNumberAnimated.gif|right|thumb|The triangular array whose right-hand diagonal sequence consists of Bell numbers]] | {{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. | 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. | ||
| Line 6: | Line 7: | ||
Notable particular examples include these: | 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 | *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 | ||
| editor1-first = Verner E. Jr. | editor1-last = Hoggatt | |||
| editor2-first = Marjorie | editor2-last = Bicknell-Johnson | |||
| contribution = A triangle for the Bell numbers | | contribution = A triangle for the Bell numbers | ||
| location = Santa Clara, Calif. | | location = Santa Clara, Calif. | ||
| Line 12: | Line 15: | ||
| publisher = Fibonacci Association | | publisher = Fibonacci Association | ||
| title = A collection of manuscripts related to the Fibonacci sequence | | title = A collection of manuscripts related to the Fibonacci sequence | ||
| url = http://www.fq.math.ca/Books/Collection/shallit.pdf | | url = https://www.fq.math.ca/collection.html | ||
| contribution-url = http://www.fq.math.ca/Books/Collection/shallit.pdf | |||
| year = 1980}}.</ref> | | year = 1980}}.</ref> | ||
* [[Catalan's triangle]], which counts strings of parentheses | * [[Catalan's triangle]], which counts strings of matched parentheses<ref>{{citation | ||
| | | title = Harmonic numbers, Catalan's triangle and mesh patterns | ||
| last2 = Liese | first2 = Jeffrey | | last2 = Liese | first2 = Jeffrey | ||
| journal = Discrete Mathematics | |||
| year = 2013 | |||
| volume = 313 | |||
| issue = 14 | |||
| pages = 1515–1531 | |||
| doi = 10.1016/j.disc.2013.03.017 | | doi = 10.1016/j.disc.2013.03.017 | ||
| mr = 3047390 | | mr = 3047390 | ||
| arxiv = 1209.6423 | |||
| s2cid = 18248485 | | s2cid = 18248485 | ||
| url = https://personal.strath.ac.uk/sergey.kitaev/Papers/mesh1.pdf | |||
}}.</ref> | }}.</ref> | ||
* Euler's triangle, which counts permutations with a given number of ascents<ref>{{citation | * Euler's triangle, which counts permutations with a given number of ascents<ref>{{citation | ||
| title = Permutations and combination locks | |||
| last1 = Velleman | first1 = Daniel J. | | last1 = Velleman | first1 = Daniel J. | ||
| last2 = Call | first2 = Gregory S. | | last2 = Call | first2 = Gregory S. | ||
| journal = Mathematics Magazine | | journal = Mathematics Magazine | ||
| mr = 1363707 | | year = 1995 | volume = 68 | issue = 4 | pages = 243–253 | ||
| pages = | | doi = 10.1080/0025570X.1995.11996328 | ||
| | | mr = 1363707 | jstor = 2690567 | ||
| | }}.</ref> | ||
| year = | * [[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> | }}.</ref> | ||
* [[Hosoya's triangle]], based on the [[Fibonacci number]]s<ref>{{citation | * [[Hosoya's triangle]], based on the [[Fibonacci number]]s<ref>{{citation | ||
| title = Fibonacci triangle | |||
| journal = The Fibonacci Quarterly | |||
| volume = 14 | |||
| issue = 2 | | issue = 2 | ||
| pages = 173–178 | | pages = 173–178 | ||
| | | year = 1976| doi = 10.1080/00150517.1976.12430575 }}.</ref> | ||
* [[Lozanić's triangle]], used in the mathematics of chemical compounds<ref>{{citation | * [[Lozanić's triangle]], used in the mathematics of chemical compounds<ref>{{citation | ||
| title = Die Isomerie-Arten bei den Homologen der Paraffin-Reihe | | title = Die Isomerie-Arten bei den Homologen der Paraffin-Reihe | ||
| trans-title = The isomery species of the homologues of the paraffin series | |||
| journal = Chem. Ber. | lang = de | |||
| volume = 30 | | volume = 30 | ||
| issue = 2 | | issue = 2 | ||
| year = 1897 | | year = 1897 | ||
| doi=10.1002/cber.189703002144| url = https://zenodo.org/record/1425862 | | pages = 1917–1926 | ||
| doi = 10.1002/cber.189703002144 | |||
| url = https://zenodo.org/record/1425862 | |||
}}.</ref> | }}.</ref> | ||
* Narayana triangle, counting strings of balanced parentheses with a given number of distinct nestings<ref>{{citation | * 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 | | last = Barry | first = Paul | ||
| journal = Journal of Integer Sequences | |||
| issue = 4 | | issue = 4 | ||
| | | volume = 14 | ||
| article-number = 11.4.5 | |||
| mr = 2792161 | | mr = 2792161 | ||
| | | url = https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.pdf | ||
| year = 2011}}.</ref> | | 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 | * [[Pascal's triangle]], whose entries are the [[Binomial coefficients|binomial coefficients]]<ref>{{citation | ||
| title = Pascal's Arithmetical Triangle: The Story of a Mathematical Idea | |||
| 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 | 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 = | | title = On integer-sequence-based constructions of generalized Pascal triangles | ||
| last = Barry | first = Paul | |||
| journal = Journal of Integer Sequences | | 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 | | url = http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf | ||
| year = 2006 | bibcode = 2006JIntS...9...24B | |||
| year = 2006| bibcode = 2006JIntS...9...24B | |||
}}.</ref> | }}.</ref> | ||
| Line 98: | Line 114: | ||
==Applications== | ==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> | [[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> | ||
| Line 115: | Line 129: | ||
| year = 1996 | doi=10.1006/jcta.1996.0087| s2cid = 15637402 | | year = 1996 | doi=10.1006/jcta.1996.0087| s2cid = 15637402 | ||
}}.</ref> | }}.</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|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|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== | ==See also== | ||
Latest revision as of 19:36, 22 May 2026
Short description: Numbers arranged in a triangle
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[1]
- Catalan's triangle, which counts strings of matched parentheses[2]
- Euler's triangle, which counts permutations with a given number of ascents[3]
- Floyd's triangle, whose entries are all of the integers in order[4]
- Hosoya's triangle, based on the Fibonacci numbers[5]
- Lozanić's triangle, used in the mathematics of chemical compounds[6]
- Narayana triangle, counting strings of balanced parentheses with a given number of distinct nestings[7]
- Pascal's triangle, whose entries are the binomial coefficients[8]
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.[9]
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.[10]
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.[11]
Applications
Romberg's method can be used to estimate the value of a definite integral by completing the values in a triangle of numbers.[12]
The Boustrophedon transform uses a triangular array to transform one integer sequence into another.[13]
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
- ↑ Hoggatt, Verner E. Jr.; Bicknell-Johnson, Marjorie, eds. (1980), "A triangle for the Bell numbers", A collection of manuscripts related to the Fibonacci sequence, Santa Clara, Calif.: Fibonacci Association, pp. 69–71, http://www.fq.math.ca/Books/Collection/shallit.pdf.
- ↑ "Harmonic numbers, Catalan's triangle and mesh patterns", Discrete Mathematics 313 (14): 1515–1531, 2013, doi:10.1016/j.disc.2013.03.017, https://personal.strath.ac.uk/sergey.kitaev/Papers/mesh1.pdf.
- ↑ Velleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", Mathematics Magazine 68 (4): 243–253, doi:10.1080/0025570X.1995.11996328.
- ↑ Miller, Philip L.; Miller, Lee W.; Jackson, Purvis M. (1987), Programming by design: a first course in structured programming, Wadsworth Pub. Co., pp. 211–212, ISBN 978-0-534-08244-4.
- ↑ "Fibonacci triangle", The Fibonacci Quarterly 14 (2): 173–178, 1976, doi:10.1080/00150517.1976.12430575.
- ↑ "Die Isomerie-Arten bei den Homologen der Paraffin-Reihe", Chem. Ber. 30 (2): 1917–1926, 1897, doi:10.1002/cber.189703002144, https://zenodo.org/record/1425862.
- ↑ Barry, Paul (2011), "On a generalization of the Narayana triangle", Journal of Integer Sequences 14 (4), https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.pdf.
- ↑ Pascal's Arithmetical Triangle: The Story of a Mathematical Idea, JHU Press, 2002, ISBN 978-0-8018-6946-4.
- ↑ Barry, Paul (2006), "On integer-sequence-based constructions of generalized Pascal triangles", Journal of Integer Sequences 9 (2), Bibcode: 2006JIntS...9...24B, http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf.
- ↑ Rota Bulò, Samuel; Hancock, Edwin R.; Aziz, Furqan; Pelillo, Marcello (2012), "Efficient computation of Ihara coefficients using the Bell polynomial recursion", Linear Algebra and Its Applications 436 (5): 1436–1441, doi:10.1016/j.laa.2011.08.017.
- ↑ Fielder, Daniel C.; Alford, Cecil O. (1991), "Pascal's triangle: Top gun or just one of the gang?", in Bergum, Gerald E.; Philippou, Andreas N.; Horadam, A. F., 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), Springer, pp. 77–90, ISBN 9780792313090, https://books.google.com/books?id=SfWNxl7K9pgC&pg=PA77.
- ↑ Thacher Jr., Henry C. (July 1964), "Remark on Algorithm 60: Romberg integration", Communications of the ACM 7 (7): 420–421, doi:10.1145/364520.364542.
- ↑ Millar, Jessica; Sloane, N. J. A.; Young, Neal E. (1996), "A new operation on sequences: the Boustrouphedon transform", Journal of Combinatorial Theory, Series A 76 (1): 44–54, doi:10.1006/jcta.1996.0087.
External links
 |  |
