On Some Alternative Characterizations of Riordan Arrays

DOI10.4153/CJM-1997-015-XMaRDI QIDQ4347006zbMATH OpenOpenAlexFDO

Authors Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, Maria Cecilia Verri

Publication date 18 September 1997

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4153/cjm-1997-015-x

zbMATH Keywords

diagonal steps generating function lattice paths Pascal triangle Riordan array template triangular array

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Review text

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 \textit{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 \textit{D. Merlini}, \textit{D. G. Rogers}, \textit{R. Sprugnoli} and \textit{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.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: On Some Alternative Characterizations of Riordan Arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4347006)