Characterization of Riordan Arrays by Special Sequences

As already described in the previous chapters, the concept of a Riordan array was introduced in 1991 by Shapiro, Getu, Woan and Woodson [21], with the aim of defining a class of infinite lower triangular arrays with properties analogous to those of the Pascal triangle. This concept was subsequently studied by Sprugnoli [22] in the context of the computation of combinatorial sums. In these papers, Riordan arrays correspond to matrices (dn,k)n,k∈N where each element is described by a linear combination of the elements in the previous row, starting from the previous column; this characterization was already observed by Rogers [18]. The coefficients of this linear combination are independent of n and k, with k≠ 0, and constitute a specific sequence called the A-sequence of the Riordan array; when k= 0 another sequence called the Z- sequence is involved, as illustrated in Sect. 4.1. Later, several new characterizations of Riordan arrays were given in Merlini, Rogers, Sprugnoli and Verri [11]: the main result in that paper shows that a lower triangular array is of Riordan type whenever its generic element d_{n + 1 , k + 1} linearly depends on the elements d_{r , s} lying in a well-defined zone of the array. The coefficients of this dependence constitute the so-called A-matrix and are illustrated in Sect. 4.2. There is no difference between Riordan arrays defined in either way: the A-sequence is a particular case of A-matrix and, given a Riordan array defined by an A-matrix, this corresponds to a well-defined A-sequence. However, there are some examples in which a Riordan array can be easily studied by means of the A-matrix while the A-sequence is very complex. From a combinatorial point of view, this means that it is very challenging to find a construction allowing us to obtain objects of size n+ 1 from objects of size n. Instead, the existence of a simple A-matrix corresponds to a possible construction from objects of different sizes less than n+ 1. Some combinatorial problems studied in terms of A-matrix can be found in [9–12]. Algebraic characterizations of Riordan arrays in terms of A- and Z- sequences are illustrated in [8]; many combinatorial examples where the A- and Z- sequences are strictly related are examined in [4]. In Sect. 4.3 it is shown that the A- and Z- sequences are related to the concept of production matrix and it is highlighted how the A-sequence, A-matrix and production matrix concepts can be used to prove the Riordan array nature of a problem.