Triangular array
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
[edit]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 parentheses in which no close parenthesis is unmatched[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
[edit]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
[edit]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
[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", A collection of manuscripts related to the Fibonacci sequence (PDF), Santa Clara, Calif.: Fibonacci Association, pp. 69–71, MR 0624091.
- ^ Kitaev, Sergey; Liese, Jeffrey (2013), "Harmonic numbers, Catalan's triangle and mesh patterns", 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.2307/2690567, 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 9780534082444.
- ^ Hosoya, Haruo (1976), "Fibonacci triangle", The Fibonacci Quarterly, 14 (2): 173–178.
- ^ Losanitsch, S. M. (1897), "Die Isomerie-Arten bei den Homologen der Paraffin-Reihe", Chem. Ber., 30 (2): 1917–1926, doi:10.1002/cber.189703002144.
- ^ Barry, Paul (2011), "On a generalization of the Narayana triangle", Journal of Integer Sequences, 14 (4): Article 11.4.5, 22, MR 2792161.
- ^ Edwards, A. W. F. (2002), Pascal's Arithmetical Triangle: The Story of a Mathematical Idea, JHU Press, ISBN 9780801869464.
- ^ Barry, P. (2006), "On integer-sequence-based constructions of generalized Pascal triangles" (PDF), Journal of Integer Sequences, 9 (6.2.4): 1–34, 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.