Triangular array: Difference between revisions

Revision as of 14:17, 30 March 2023

Latest revision as of 05:17, 28 May 2025

(12 intermediate revisions by 9 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]]]]

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

| issue = 14

| year = 2013| arxiv = 1209.6423

| pages = 1515–1531

| doi = 10.1016/j.disc.2013.03.017

| mr = 13637073047390

| year = 2013| 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.

| 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

| yearmr = 19951363707 | 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| jstor = 2690567

| title = Programming by design: a first course in structured programming

| pages = 1–34211–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>

* [[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

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

| year = 1897

| pages = 173–1781917–1926

| doi=10.1002/cber.189703002144| url = https://zenodo.org/record/1425862

| doi = 10.1002/cber.189703002144

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

| journal = Journal of Integer Sequences

| article-number = 11.4.5

| mr = 2792161

| url = https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.pdf

| page = Article 11.4.5, 22

| title = On a generalization of the Narayana triangle

| volume = 14

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

* [[c:File:VanDam_Triangular_array_2001.jpg|VanDam's triangle]], which adds the first two digits each time starting in the bottom row from left to right.

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 = 6.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

| journal = Journal of Integer Sequences

| volume = 9 | issue = 42

| issuearticle-number = 6.2.4

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

| year = 2006 | bibcode = 2006JIntS...9...24B

| volume = 9

| year = 2006| bibcode = 2006JIntS...9...24B

}}.</ref>

Line 102 ⟶ 119:

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

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=https://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|doi=10.1145/364520.364542|issue=7|s2cid=29898282 }}.</ref>

The [[Boustrophedon transform]] uses a triangular array to transform one [[integer sequence]] into another.<ref>{{citation

Line 119 ⟶ 134:

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