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
editNotable 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]
- Clark's triangle [9]
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.[10]
Generalizations
editTriangular 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.[11]
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.[12]
Applications
editRomberg's method can be used to estimate the value of a definite integral by completing the values in a triangle of numbers.[13]
The Boustrophedon transform uses a triangular array to transform one integer sequence into another.[14]
In general, a triangular array is used to store any table indexed by two natural numbers where j ≤ i.
Indexing
editStoring 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
edit- Triangular number, the number of entries in such an array up to some particular row
References
edit- ^ 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, doi:10.1080/00150517.1976.12430575.
- ^ 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.
- ^ Weisstein, Eric W. "Clark's Triangle". mathworld.wolfram.com. Retrieved 2026-06-07.
- ^ 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.
