On some alternative characterizations of Riordan arrays. (English) Zbl 0886.05013

Enumeration of lattice paths having diagonal steps is investigated in this important paper from the Riordan array point of view. This theory had previously been developed for lattice paths with ‘steep’ diagonal steps. The authors extend the Riordan array theory to both shallow and steep diagonal steps. Here, by a Riordan array is meant a pair \((d(t),h(t))\) of formal power series with \(d(t)\) being an invertible series; if it holds \(h(0)\neq 0\) as well then the Riordan array is called proper. Such an array defines a lower triangular array \((d_{n,k}\mid n,k\in\mathbb{N})\), where \(d_{n,k}= [t^n]d(t) (th(t))^k\). An example is given by the Pascal triangle, where \(d(t)= h(t)= {1\over 1-t}\). Due to D. G. Rogers [Discrete Math. 22, 301-310 (1978; Zbl 0398.05007)] it is known that an array \((d_{n,k}\mid n,k\in\mathbb{N})\) is a proper Riordan array iff there exists a sequence \(A= (a_i\mid i\in\mathbb{N})\) with \(a_0\neq 0\) and such that for every element not lying in the \(0\)th row and the \(0\)th column, \(d_{n+1, k+1}= a_0d_{n,k}+ a_1d_{n,k+1}+\cdots\). The sequence \(A\) is called an \(A\)-sequence for the given Riordan array. If \(A(t)\) is the generating function for \(A\), then \(h(t)\) is a solution for the functional equation \(h(t)= A(th(t))\). Conversely, \(A(y)\) can be obtained by substituting the solution of \(t= yh(t)^{-1}\) having \(h(0)= 0\), for \(t\) into \(h(t)\).
In this paper several results are formulated (Theorems 2.2-2.8) that characterize Riordan arrays in a new way, together with giving sketches of their proofs. In particular, the authors give the following Theorem 2.5: A lower triangular array \((d_{n,k}\mid n,k\in\mathbb{N})\) is Riordan iff there exists an another array \((\alpha_{i,j}\mid i,j\in\mathbb{N})\) with \(\alpha_{0,0}\neq 0\) and such that for every \(d_{n+1,k+1}\) \((n,k\geq 0)\) we have \(d_{n+1, k+1}= \sum_{i\geq 0}\sum_{j\geq 0} \alpha_{i,j}d_{n-i,k+j}\). For details of complete proofs the reader is referred to D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri [Technical Report 14, Dipartimento di Sistemi e Informatica, Università di Ferenze (1995)].
Thereafter, generating functions and lattice path problems are considered. By a lattice path is meant a sequence \((s_1,\dots, s_m)\) of pairs \(s_i= ((x_{i-1}, y_{i-1}),(x_i,y_i))\), \(i=1,\dots,m\), such that \(x_0= y_0= 0\) and \(x_i= x_{i-1}+\delta_i\), \(y_i= y_{i-1}+ \delta_i'\) with \((\delta_i,\delta_i')\) drawn from the set \[ T= \{(\delta,\delta')\in \mathbb{N}^2\mid\delta+ \delta'>0\}\cup \{(\delta, \delta')\in\mathbb{Z}^2\mid\delta<0\text{ and }\delta'>0\} \] of permissible step templates (together with some conditions on their occurrence). A template \((\delta,\delta')\) is called steep if \(\delta\leq\delta'\), shallow if \(\delta>\delta'+1\) and almost steep if \(\delta= \delta'+1\). By a lattice path problem \(R\) is meant a pair \((R_A,R_\Delta)\) with \(R_A\subseteq T\) and \(R_\Delta\) being a subset of steep templates in \(T\). To \(R\) it corresponds a lower triangular array \((d_{n,k}\mid n,k\in\mathbb{N})\) counting the paths from \((0,0)\) to the point \((n,n-k)\). According to the authors’ Theorem 4.1, this array is Riordan iff \(R_A\) is made of both steep templates and, at least, one almost steep template, and there exists a number \(D\) such that for every template \((\delta,\delta')\in R_A\cup R_\Delta\) with \(\delta<0\), we have \(\delta'<D\). If, in addition, \(R_A\) contains the almost steep template \((1,0)\), then the array \((d_{n,k}\mid n,k\in\mathbb{N})\) is proper. The last pages of the paper contain plenty of examples and illustrations of the above extension of the theory of Riordan arrays.


05A15 Exact enumeration problems, generating functions


Zbl 0398.05007
Full Text: DOI