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.
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 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
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
Apart from the representation of triangular matrices, triangular arrays are used in several algorithms. One example is the CYK algorithm for parsing context-free grammars, an example of dynamic programming.[12]
Romberg'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]
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", A collection of manuscripts related to the Fibonacci sequence (PDF), Santa Clara, Calif.: Fibonacci Association, pp. 69–71, MR 624091.
- ↑ Kitaev, Sergey; Liese, Jeffrey (2013), "Harmonic numbers, Catalan's triangle and mesh patterns", Discrete Mathematics, 313 (14): 1515–1531, doi:10.1016/j.disc.2013.03.017, MR 3047390.
- ↑ Velleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", Mathematics Magazine, 68 (4): 243–253, doi:10.2307/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: 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 (06.2.4): 1–34.
- ↑ 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., 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.
- ↑ Indurkhya, Nitin; Damerau, Fred J., eds. (2010), Handbook of Natural Language Processing, Second Edition, CRC Press, p. 65, ISBN 9781420085938.
- ↑ 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.
- ↑ 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.