Triangular array
Numbers arranged in a triangle
- 2 min read
- 4 chapters
Related on Lably
Through Pascal's triangle, Binomial coefficient and Integral
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
- Clark's triangle
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.
Sign in to keep reading
3 more chapters are free with a Lably account.
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
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 (i, j) to a linear memory address. If two triangular arrays of equal size are to be stored (such as in LU decomposition), 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 Ti. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (i*(i+1)/2), so some optimizations such as using a sequence of shifts and adds are not available.