Triangular array

Image:BellNumberAnimated.gif|right|thumb|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. That is, the ith row contains only i elements.

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 matched parentheses
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 have also been considered.

Applications

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.
In general, a triangular array is used to store any table indexed by two natural numbers where j ≤ i.

Indexing

Storing a triangular array in a computer requires a mapping from the two-dimensional coordinates to a linear memory address. If two triangular arrays of equal size are to be stored, 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 T_i. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables, so some optimizations such as using a sequence of shifts and adds are not available.