Triangular array

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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.

Examples[edit]

Notable particular examples include these:

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]

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[edit]

  • Triangular number, the number of entries in such an array up to some particular row

References[edit]

  1. ^ Shallit, Jeffrey (1980), "A triangle for the Bell numbers", A collection of manuscripts related to the Fibonacci sequence, Santa Clara, Calif.: Fibonacci Association, pp. 69–71, MR 624091 .
  2. ^ 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 .
  3. ^ Velleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", Mathematics Magazine 68 (4): 243–253, doi:10.2307/2690567, MR 1363707 .
  4. ^ 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 .
  5. ^ Hosoya, Haruo (1976), "Fibonacci triangle", The Fibonacci Quarterly 14 (2): 173–178 .
  6. ^ Losanitsch, S. M. (1897), "Die Isomerie-Arten bei den Homologen der Paraffin-Reihe", Chem. Ber. 30: 1917–1926 .
  7. ^ Barry, Paul (2011), "On a generalization of the Narayana triangle", Journal of Integer Sequences 14 (4): Article 11.4.5, 22, MR 2792161 .
  8. ^ Edwards, A. W. F. (2002), Pascal's Arithmetical Triangle: The Story of a Mathematical Idea, JHU Press, ISBN 9780801869464 .
  9. ^ Barry, P. (2006), "On integer-sequence-based constructions of generalized Pascal triangles", Journal of Integer Sequences 9 (06.2.4): 1–34 .
  10. ^ 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 .
  11. ^ 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 .
  12. ^ Indurkhya, Nitin; Damerau, Fred J., eds. (2010), Handbook of Natural Language Processing, Second Edition, CRC Press, p. 65, ISBN 9781420085938 .
  13. ^ 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 .
  14. ^ 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 .

External links[edit]