Triangular array - Revision history

David Eppstein: more specific short description

2025-05-28T05:17:32Z

more specific short description

← Previous revision		Revision as of 05:17, 28 May 2025
Line 1:		Line 1:
	{{Short description\|~~Concept~~ in ~~mathematics~~ ~~and~~ ~~computing~~}}		{{Short description\|Numbers arranged in a triangle}}
	{{Distinguish\|Triangular matrix}}		{{Distinguish\|Triangular matrix}}
	[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]		[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]

Citation bot: Added doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Triangles of numbers | #UCB_Category 4/29

2025-02-10T09:06:21Z

Added doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Triangles of numbers | #UCB_Category 4/29

← Previous revision		Revision as of 09:06, 10 February 2025
Line 60:		Line 60:
	\| issue = 2		\| issue = 2
	\| pages = 173–178		\| pages = 173–178
	\| year = 1976}}.</ref>		\| 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

Beland: convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)

2025-02-02T02:40:02Z

convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)

← Previous revision		Revision as of 02:40, 2 February 2025
Line 135:		Line 135:
	}}.</ref>		}}.</ref>

	In general, a triangular array is used to store any table indexed by two [[natural numbers]] where ''j'' ~~&leq;~~ ''i''.		In general, a triangular array is used to store any table indexed by two [[natural numbers]] where ''j'' ≤ ''i''.

	==Indexing==		==Indexing==

97.102.205.224: /* Indexing */ New section briefly (one paragraph) describing memory addressing techniques.

2024-12-30T19:35:52Z

Indexing: New section briefly (one paragraph) describing memory addressing techniques.

← Previous revision		Revision as of 19:35, 30 December 2024
Line 134:		Line 134:
	\| 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'' &leq; ''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 [[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<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==

97.102.205.224: /* 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)

2024-12-29T12:36:40Z

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)

Show changes

David Eppstein: /* Applications */ rm CYK algorithm example, which involves a triangular matrix, not the infinite triangles considered here

2024-06-22T21:14:48Z

Applications: rm CYK algorithm example, which involves a triangular matrix, not the infinite triangles considered here

← Previous revision		Revision as of 21:14, 22 June 2024
Line 102:		Line 102:

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

David Eppstein: Undid revision 1230460275 by Jayy V (talk) I think "triangular matrix" generally means a matrix of finite dimensions, not the infinite arrays considered here. See the hatnote. See also https://oeis.org/A007318/table which is a source of mathematics that clearly uses the "array" terminology

2024-06-22T21:12:58Z

Undid revision 1230460275 by Jayy V (talk) I think "triangular matrix" generally means a matrix of finite dimensions, not the infinite arrays considered here. See the hatnote. See also https://oeis.org/A007318/table which is a source of mathematics that clearly uses the "array" terminology

← Previous revision		Revision as of 21:12, 22 June 2024
Line 2:		Line 2:
	{{Distinguish\|Triangular matrix}}		{{Distinguish\|Triangular matrix}}
	[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]		[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]
	In ~~computing~~ and ~~mathematics~~, 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.

	==Examples==		==Examples==

Jayy V: changed "In mathematics and computing" to "In computing and mathematics" as mathematicians rarely use this terminology, preferring "triangular matrix"

2024-06-22T20:48:48Z

changed "In mathematics and computing" to "In computing and mathematics" as mathematicians rarely use this terminology, preferring "triangular matrix"

← Previous revision		Revision as of 20:48, 22 June 2024
Line 2:		Line 2:
	{{Distinguish\|Triangular matrix}}		{{Distinguish\|Triangular matrix}}
	[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]		[[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 computing and mathematics, 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==		==Examples==

Gtgith: /* Examples */

2023-09-24T09:45:28Z

Examples

← Previous revision		Revision as of 09:45, 24 September 2023
Line 18:		Line 18:
	* [[Catalan's triangle]], which counts strings of parentheses in which no close parenthesis is unmatched<ref>{{citation		* [[Catalan's triangle]], which counts strings of parentheses in which no close parenthesis is unmatched<ref>{{citation
	\| last1 = Kitaev \| first1 = Sergey		\| last1 = Kitaev \| first1 = Sergey
			\| author1-link = Sergey Kitaev
	\| last2 = Liese \| first2 = Jeffrey		\| last2 = Liese \| first2 = Jeffrey
	\| doi = 10.1016/j.disc.2013.03.017		\| doi = 10.1016/j.disc.2013.03.017

GraziePrego: Adding short description: "Concept in mathematics and computing"

2023-09-21T03:48:39Z

Adding short description: "Concept in mathematics and computing"

← Previous revision		Revision as of 03:48, 21 September 2023
Line 1:		Line 1:
			{{Short description\|Concept in mathematics and computing}}
	{{Distinguish\|Triangular matrix}}		{{Distinguish\|Triangular matrix}}
	[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]		[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]

← Previous revision		Revision as of 05:17, 28 May 2025
Line 1:		Line 1:
	{{Short description\|~~Concept~~ in ~~mathematics~~ ~~and~~ ~~computing~~}}		{{Short description\|Numbers arranged in a triangle}}
	{{Distinguish\|Triangular matrix}}		{{Distinguish\|Triangular matrix}}
	[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]		[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]

← Previous revision		Revision as of 03:48, 21 September 2023
Line 1:		Line 1:
			{{Short description\|Concept in mathematics and computing}}
	{{Distinguish\|Triangular matrix}}		{{Distinguish\|Triangular matrix}}
	[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]		[[Image:BellNumberAnimated.gif\|right\|thumb\|The triangular array whose right-hand diagonal sequence consists of [[Bell numbers]]]]