Neha Patil (Editor)

Triangular array

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
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.

Contents

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
  • Catalan's triangle, which counts strings of parentheses in which no close parenthesis is unmatched
  • Euler's triangle, which counts permutations with a given number of ascents
  • Floyd's triangle, whose entries are all of the integers in order
  • Hosoya's triangle, based on the Fibonacci numbers
  • Lozanić's triangle, used in the mathematics of chemical compounds
  • Narayana triangle, counting strings of balanced parentheses with a given number of distinct nestings
  • Pascal's triangle, whose entries are the binomial coefficients

    • 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.

    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.

    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.

    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.

    Romberg's method can be used to estimate the value of a definite integral by completing the values in a triangle of numbers.

    The Boustrophedon transform uses a triangular array to transform one integer sequence into another.

    References

    Triangular array Wikipedia
    (Text) CC BY-SA