A (proper) Riordan array is an infinite lower triangular matrix, , constructed out of two formal power series, of order 0 and of order 1, in such a way that .
A Riordan array is an element of the Riordan group. It was created by mathematician Louis W. Shapiro and named after mathematician John Riordan.
The study of Riordan arrays is a growing field that is both being influenced by, and continuing its contributions to, other fields such as combinatorics, group theory, matrix theory, number theory, probability, sequences and series, Lie groups and Lie algebras, orthogonal polynomials, graph theory, networks, Beal conjecture, Riemann hypothesis, unimodal sequences, combinatorial identities, elliptic curves, numerical approximation, asymptotics, and data analysis. Riordan arrays is also a powerful unifying concept, binding together important tools: generating functions, computer algebra systems, formal languages, path model, and so on.
Details follow.
A formal power series is said to have order if Write for the formal power series of order A power series of order 0 has a multiplicative inverse (i.e. is a power series) iff it has order 0, i.e. iff it lies in ; it has a composition inverse that is there exists a power series such that iff it has order 1, i.e. iff it lies in
As mentioned a Riordan array is defined usually as a pair of power series The 'array' part in its name stems from the fact that one associates to the array of complex numbers defined by (Here means coefficient of in ) . So column of the array simply consists of the sequence of coefficients of the power series in particular column 0 determines and is determined by the power series As is of order 0, it has a multiplicative inverse and it follows that from the array's column 1 we can recover as Since has order 1, has order and so has It follows that the array is infinite triangular exhibiting a geometric progression on its main diagonal. It also follows that the map associating to a pair of power series its triangular array is injective.
An example for a Riordan array is given by the pair of power series It is not difficult to show that this pair generates the infinite triangular array of binomial coefficients also called Pascal matrix
Proof. If is a power series with associated coefficient sequence then, by Cauchy multiplication of power series, So the latter series has as coefficient sequence and hence Fix any If so that represents column of the Pascal array, then This argument allows to see by induction on that has column of the Pascal array as coefficient sequence.
We are going to prove some much used facts about Riordan arrays. Note that the matrix multiplication rules applied to infinite triangular matrices lead to finite sums only and the product of two infinite triangular matrices is infinite triangular. The next two theorems were discovered essentially by Shapiro and coworkers, who say they modified work they found in papers by Gian-Carlo Rota and the book of Roman
Theorem. a. Let and be Riordan arrays, viewed as infinite lower triangular matrices. Then the product of these matrices is the array associated to the pair of formal power series which itself is a Riordan array.
b. This fact justifies to define a multiplication `' of Riordan arrays viewed as pairs of power series by
Proof. Since have order 0 it is clear that has order 0. Similarly implies
So is a Riordan array. Define a matrix as the Riordan array By definitions its -th column is the sequence of coefficients of the power series If we multiply this matrix from the right with the sequence we get as a result a linear combination of columns of which we can read as a linear combination of power series, namely Thus, viewing sequence as codified by the power series we showed Here the is the symbol for indicating correspondence on the power series level with matrix multiplication. We multiplied a Riordan array with a single power series. Let now be another Riordan array viewn as a matrix. One can form the product The -th column of this product is just multiplied with the -th column of Since the latter corresponds to the power series it follows by above, that the -th column of corresponds to As this holds for all column indices occurring in we have shown part a. Part b is now clear.
Theorem. The family of Riordan arrays endowed with the product '' defined above forms a group: the Riordan group.