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 ''i''th 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 In combinatorial mathematics, Catalan's triangle is a number triangle whose entries C(n,k) give the number of strings consisting of ''n'' X's and ''k'' Y's such that no initial segment of the string has more Y's than X's. It is a generalization of ...
, 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
Floyd's triangle is a triangular array of natural numbers used in computer science education. It is named after Robert Floyd. It is defined by filling the rows of the triangle with consecutive numbers, starting with a 1 in the top left corner:
T ...
, whose entries are all of the integers in order
*
Hosoya's triangle
Hosoya's triangle or the Hosoya triangle (originally Fibonacci triangle; ) is a triangular arrangement of numbers (like Pascal's triangle) based on the Fibonacci numbers. Each number is the sum of the two numbers above in either the left diagonal o ...
, based on the
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
s
*
Lozanić's triangle
Lozanić's triangle (sometimes called Losanitsch's triangle) is a triangular array of binomial coefficients in a manner very similar to that of Pascal's triangle. It is named after the Serbian chemist Sima Lozanić, who researched it in his inves ...
, used in the mathematics of chemical compounds
*
Narayana triangle, counting strings of balanced parentheses with a given number of distinct nestings
*
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, althoug ...
, 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
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
, triangular arrays are used in several
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s. One example is the
CYK algorithm
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke ...
for parsing
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...
s, an example of
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
.
Romberg's method can be used to estimate the value of a
definite integral
In mathematics, an integral assigns numbers to functions in a way that describes displacement, area, volume, and other concepts that arise by combining infinitesimal data. The process of finding integrals is called integration. Along with ...
by completing the values in a triangle of numbers.
The
Boustrophedon transform uses a triangular array to transform one
integer sequence
In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.
An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. Fo ...
into another.
[.]
See also
*
Triangular number
A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots i ...
, the number of entries in such an array up to some particular row
References
External links
*{{mathworld, title=Number Triangle, urlname=NumberTriangle, mode=cs2