Triangular array: Difference between revisions
Content deleted Content added
→Applications: rm CYK algorithm example, which involves a triangular matrix, not the infinite triangles considered here |
→Examples: In the strings counted by Catalan's triangle, open parens are not unmatched, either! Ad URL for citation. Clean up a number of other citations (title first, volume/issue/page together) |
||
| Line 8: | Line 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 |
*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 |
| 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 |
| contribution = A triangle for the Bell numbers |
||
| location = Santa Clara, Calif. |
| location = Santa Clara, Calif. |
||
| Line 14: | Line 16: | ||
| 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 = |
| 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 |
||
| ⚫ | |||
| last1 = Kitaev | first1 = Sergey |
|||
| author1-link = Sergey Kitaev |
| last1 = Kitaev | first1 = Sergey | author1-link = Sergey Kitaev |
||
| last2 = Liese | first2 = Jeffrey |
| last2 = Liese | first2 = Jeffrey |
||
| ⚫ | |||
| ⚫ | |||
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] |
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] |
||
| |
| year = 2013 |
||
| ⚫ | |||
| ⚫ | |||
| volume = 313 |
| volume = 313 |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| 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 |
||
| ⚫ | |||
| last1 = Velleman | first1 = Daniel J. |
| last1 = Velleman | first1 = Daniel J. |
||
| last2 = Call | first2 = Gregory S. |
| last2 = Call | first2 = Gregory S. |
||
| doi = 10.2307/2690567 |
|||
| ⚫ | |||
| journal = Mathematics Magazine |
| journal = Mathematics Magazine |
||
| year = 1995 | volume = 68 | issue = 4 | pages = 243–253 |
|||
| ⚫ | |||
| doi = 10.1080/0025570X.1995.11996328 |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
}}.</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 |
|||
| ⚫ | |||
| 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> |
||
* [[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}}.</ref> |
|||
* [[Hosoya's triangle]], based on the [[Fibonacci number]]s<ref>{{citation |
* [[Hosoya's triangle]], based on the [[Fibonacci number]]s<ref>{{citation |
||
| ⚫ | |||
| last = Hosoya | first = Haruo | author-link = Haruo Hosoya |
| last = Hosoya | first = Haruo | author-link = Haruo Hosoya |
||
| issue = 2 |
|||
| journal = [[The Fibonacci Quarterly]] |
| journal = [[The Fibonacci Quarterly]] |
||
| ⚫ | |||
| ⚫ | |||
| volume = 14 |
| volume = 14 |
||
| ⚫ | |||
| ⚫ | |||
| year = 1976}}.</ref> |
| year = 1976}}.</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 |
||
| ⚫ | |||
| ⚫ | |||
| pages = 1917–1926 |
|||
| 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 |
|||
| last = Losanitsch | first = Sima M. | author-link = Sima Lozanić |
|||
| ⚫ | |||
| volume = 30 |
| volume = 30 |
||
| issue = 2 |
| issue = 2 |
||
| year = 1897 |
| year = 1897 |
||
| ⚫ | |||
| ⚫ | |||
| doi = 10.1002/cber.189703002144 |
|||
| ⚫ | |||
}}.</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 |
||
| ⚫ | |||
| last = Barry | first = Paul |
| last = Barry | first = Paul |
||
| ⚫ | |||
| issue = 4 |
| issue = 4 |
||
| ⚫ | |||
| ⚫ | |||
| page = Article 11.4.5, 22 |
|||
| ⚫ | |||
| volume = 14 |
| volume = 14 |
||
| article-number = 11.4.5 |
|||
| ⚫ | |||
| 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|first=A. W. F.|last=Edwards|publisher=JHU Press|year=2002|isbn= |
* [[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 |
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. |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| title = On integer-sequence-based constructions of generalized Pascal triangles |
| title = On integer-sequence-based constructions of generalized Pascal triangles |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| url = http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf |
| url = http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf |
||
| ⚫ | |||
| volume = 9 |
|||
| ⚫ | |||
}}.</ref> |
}}.</ref> |
||
Revision as of 12:36, 29 December 2024
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]
See also
- Triangular number, the number of entries in such an array up to some particular row
References
- ^ Shallit, Jeffrey (1980), "A triangle for the Bell numbers" (PDF), in Hoggatt, Verner E. Jr.; Bicknell-Johnson, Marjorie (eds.), A collection of manuscripts related to the Fibonacci sequence, Santa Clara, Calif.: Fibonacci Association, pp. 69–71, MR 0624091.
- ^ Kitaev, Sergey; Liese, Jeffrey (2013), "Harmonic numbers, Catalan's triangle and mesh patterns" (PDF), Discrete Mathematics, 313 (14): 1515–1531, arXiv:1209.6423, doi:10.1016/j.disc.2013.03.017, MR 3047390, S2CID 18248485.
- ^ Velleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", Mathematics Magazine, 68 (4): 243–253, doi:10.1080/0025570X.1995.11996328, JSTOR 2690567, MR 1363707.
- ^ 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.
- ^ Hosoya, Haruo (1976), "Fibonacci triangle", The Fibonacci Quarterly, 14 (2): 173–178.
- ^ Losanitsch, Sima M. (1897), "Die Isomerie-Arten bei den Homologen der Paraffin-Reihe" [The isomery species of the homologues of the paraffin series], Chem. Ber. (in German), 30 (2): 1917–1926, doi:10.1002/cber.189703002144.
- ^ Barry, Paul (2011), "On a generalization of the Narayana triangle" (PDF), Journal of Integer Sequences, 14 (4) 11.4.5, MR 2792161.
- ^ Edwards, A. W. F. (2002), Pascal's Arithmetical Triangle: The Story of a Mathematical Idea, JHU Press, ISBN 978-0-8018-6946-4.
- ^ Barry, Paul (2006), "On integer-sequence-based constructions of generalized Pascal triangles" (PDF), Journal of Integer Sequences, 9 (2) 6.2.4, Bibcode:2006JIntS...9...24B.
- ^ 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, MR 2890929.
- ^ 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. (eds.), 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.
- ^ 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, S2CID 29898282.
- ^ 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, arXiv:math.CO/0205218, doi:10.1006/jcta.1996.0087, S2CID 15637402.