View source for Riordan array

A (proper) '''Riordan array''' is an infinite lower [[Triangular matrix|triangular matrix]], <math>D</math>, constructed out of two [[Formal power series|formal power series]], <math>d(t)</math> of order 0 and <math>h(t)</math> of order 1, in such a way that <math>d_{n,k} = [t^n]d(t) h(t)^k</math>. 
A Riordan array is an element of the Riordan group.<ref name="Shapiro et al 1991">{{cite journal |last1=Shapiro |first1=Louis W. |last2=Getu |first2=Seyoum |last3=Woan |first3=Wen-Jin |last4=Woodson |first4=Leon C. |title=The Riordan group |journal=Discrete Applied Mathematics |date=November 1991 |volume=34 |issue=1?3 |pages=229?239 |doi=10.1016/0166-218X(91)90088-E |doi-access= }}</ref> It was defined by mathematician Louis W. Shapiro and named after mathematician [[Biography:John Riordan (mathematician)|John Riordan]].<ref name="Shapiro et al 1991" />

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|combinatorics]], group theory, matrix theory, number theory, probability, sequences and series, Lie groups and Lie algebras, [[Orthogonal polynomials|orthogonal polynomials]], [[Graph theory|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.<ref>{{Cite web|url=http://www.tsimf.cn/meeting/show?id=169|title=6th International Conference on Riordan Arrays and Related Topics|website=6th International Conference on Riordan Arrays and Related Topics |language=en-US}}</ref>

Details follow.  
    
A formal [[Power series|power series]]  <math> a(x)=a_0+a_1x+a_2x^2+ \cdots =\sum_{j\geq 0}a_j x^j  \in \mathbb{C}x </math>  is said to have  [[Formal power series#Formal Laurent series|order]]    <math>r</math> if <math>a_0=. . .=a_{r-1} =0\neq a_r.</math>    Write <math>\mathcal{F}_r</math> for the formal power series of order <math>r.</math>  A power series <math>a(x)</math> of order 0 has a   [[Formal power series#Multiplicative inverse|''multiplicative inverse'']] (i.e.  <math>1/a(x)</math>  is a power series) if and only if it has order 0, i.e. if and only if it lies in <math>\mathcal{F}_0</math>;  it has a  [[Formal power series#Composition inverse|''composition inverse'']] that is there exists a power series <math>\bar a</math>  such that <math>\bar a(a(x))=x</math> if and only if it has order 1, i.e. if and only if it lies in  <math>\mathcal{F}_1</math>. 
  
As mentioned a Riordan array is  defined usually  as a pair of power series  <math>(a(t),b(t))\in \mathcal{F}_0 \times \mathcal{F}_1</math>. The 'array' part in its name stems from the fact that one associates to <math>(a(t),b(t))</math> the array  of complex numbers defined by <math>d_{n,k}:=[t^n] a(t)b(t)^k,</math>  <math>n,k\in \mathbb{N}=\mathbb{Z}_{\geq 0}.</math>   (Here <math>[t^n] . . . </math> means coefficient of <math>t^n</math> in  <math>\cdots</math>) . So column <math>k</math> of the array simply consists of the sequence of coefficients of the power series <math>a(t)b(t)^k;</math> in particular column 0 determines and is determined by the power series <math>a(t).</math> As <math>a(t)</math> is of order 0, it has a multiplicative inverse and it follows that from the array's column 1 we can recover <math>b(t)</math> as <math>b(t)=a(t)^{-1} a(t)b(t).</math>   Since <math>b(t)=b_1 t+b_2t^2+ \cdots </math> has order 1, <math>b(t)^k</math> has order <math>k</math> and so has <math>a(t)b(t)^k.</math>  It follows that the array <math>d_{n,k}</math>  is infinite triangular exhibiting  a geometric progression  <math>(d_{k,k})_{k\geq 0}=(a_0 b_1^k)_{k\geq 0}</math>  on its main diagonal. It also follows that  the map associating to a pair of power series  <math>(a(t),b(t))\in \mathcal{F}_0 \times \mathcal{F}_1</math> its triangular array is injective.  
 
An example for a Riordan array is given by the pair of power series <math>\left(\frac{1}{1-x}, \frac{x}{1-x}\right)=\left(\sum_{j\geq 0} x^j, \sum_{j\geq 0} x^{j+1}\right)\in \mathcal F_0\times \mathcal F_1</math>. It is not difficult to show that this pair generates the infinite triangular array of binomial coefficients <math>d_{n,k}=\binom{n}{k}</math>, also called Pascal matrix

<math>P=\left(\begin{array}{ccccccc} 
   1 & & & & & &  \\
   1 &1 & & & & &  \\
    1 &2 &1 & & & &  \cdots \\
     1 &3 &3 &1 & & &  \\
      1 &4 &6 &4 &1 & & \\ 
       & & \vdots & & & &  \ddots 
\end{array}\right)</math>
   
   
Proof.  If <math> q(x)=\sum_{j\geq 0} q_j x^j </math>  is a power series with associated coefficient sequence <math>(q_0,q_1,q_2, . . . )</math>,  then, by Cauchy multiplication of power series, 
<math>q(x)\frac{x}{1-x}=\sum_{j\geq 0} (0+q_0+q_1+ \cdots+q_{j-1})x^j.</math>  So the latter series has the coefficient sequence  <math>(0,q_0,q_0+q_1,q_0+q_1+q_2,. . . .)</math>, and hence
<math> [t^n] q(x)\frac{x}{1-x}= q_0+\cdots+q_{n-1}</math>. Fix any <math>k\in \mathbb{Z}_{\geq 0}.</math> If  <math>q_n=\binom{n}{k}</math>, so that <math>(q_n)_{n\geq 0}</math> represents   column <math>k</math>   of the Pascal array, then  <math>\sum_{j= 0}^{n-1} q_j=  \sum_{j= 0}^{n-1} \binom{j}{k}=\binom{n}{k+1}</math>. This argument allows to see by induction on <math>k</math> that <math>\frac{1}{1-x}\left(\frac{x}{1-x}\right)^k</math> has  column  <math>k</math> of the Pascal array as coefficient sequence. <math>\Box</math>

 
 
We are going to prove some much used  facts about Riordan arrays. Note that the matrix multiplication rules applied to infinite lower triangular matrices lead to finite sums only and the product of two infinite lower triangular matrices is infinite lower triangular. The next two theorems were first stated and proved by Shapiro et al.<ref name="Shapiro et al 1991" /> who say they modified work they found in papers by [[Biography:Gian-Carlo Rota|Gian-Carlo Rota]] and the book of Roman <ref name="umbral">{{cite book |last1=Roman |first1=S. |title=The Umbral Calculus |date=1984 |publisher=Academic Press |location=New York}}</ref>

''' Theorem.''' a.  Let <math>(a(x),b(x))</math> and <math>(c(x),d(x))</math> be Riordan arrays, viewed as infinite lower triangular matrices.  Then the product of these matrices is the  array  associated to the pair    <math>(a(x) c(b(x)), d(b(x)) )</math>  of formal power series, which itself is a Riordan array.

b. This fact justifies to define a multiplication `<math>*</math>'  of Riordan arrays viewed as pairs of power series by  {{center|<math>(a(x),b(x))*(c(x),d(x))= (a(x) c(b(x)), d(b(x))</math> }}

Proof. Since <math>a(x), c(x)</math> have order 0 it is clear that <math>a(x) c(b(x))</math> has order 0. Similarly  <math>b(x),d(x)\in \mathcal F_1</math> implies  <math>d(b(x))\in \mathcal F_1.</math>
So <math>(a(x) c(b(x)), d(b(x)) )</math> is a Riordan array. 
Define a matrix <math>M</math> as the Riordan array <math>(a(x),b(x)).</math> By definitions  its <math>j</math>-th column <math>M_{*,j}</math> is the sequence of coefficients of  
the   power series  <math>a(x)b(x)^j</math>.  If we multiply this matrix from the right with the sequence  <math>(r_0,r_1,r_2, . . . )^T</math>  we get as a result a linear combination of columns of <math>M</math> which we can read as a linear combination of  power series, namely <math>\sum_{\nu\geq 0} r_\nu M_{*,\nu}  = \sum_{\nu\geq 0} r_\nu a(x)b(x)^\nu =  a(x) \sum_{\nu\geq 0} r_\nu b(x)^\nu. </math>  Thus, viewing sequence  <math>(r_0,r_1,r_2, . . . )^T</math> as codified by the power series <math>r(x),</math>   we showed  <math>(a(x),b(x))*r(x) = a(x) r(b(x)).</math>  Here the <math>*</math> is the symbol for indicating correspondence on the power series level with matrix multiplication.  We multiplied a Riordan array <math>(a(x),b(x))</math> with  a single power series.  Now let <math>(c(x),d(x))</math> be another Riordan array viewed as a matrix.   One can form the product <math>(a(x),b(x))(c(x),d(x))</math>. The <math>j</math>-th column of this product is just  <math>(a(x),b(x))</math> multiplied with the <math>j</math>-th column of <math>(c(x),d(x)).</math> Since the latter corresponds to  the power series 
<math>c(x) d(x)^j</math>,  it follows by the above that the <math>j</math>-th column of <math>(a(x),b(x))(c(x),d(x))</math> corresponds to  <math>a(x) c(b(x)) d(b(x))^j</math>.  As this holds for all column indices <math>j</math> occurring in <math>(c(x),d(x))</math>  we have shown   part a. Part b is now clear.  <math>\Box</math>
 
''' Theorem.'''  The family of Riordan arrays endowed with the product      '<math>*</math>' defined above forms a group: the Riordan group.<ref name="Shapiro et al 1991"/>     
  
Proof. The associativity of the multiplication  `<math>*</math>' follows from associativity of matrix multiplication.  Next note <math>(1,x)*(c(x),d(x))=(1\cdot c(x), d(x))=(c(x),d(x))</math>.  So <math>(1,x)</math> is a left neutral element.   Finally  we claim that  <math>(c(\bar d(x))^{-1}, \bar d(x))</math>  is the left inverse to the power series   <math>(c(x),d(x))</math>.  For this check  the computation <math>(c(\bar d(x))^{-1}, \bar d(x))* (c(x),d(x))</math> <math>=( (c(\bar d(x) )^{-1} c(d(x))  , d(\bar d(x))  )= (1,x)</math>.  As is well known, an associative structure which has a left neutral element and where each element has a left inverse is a group.   <math>  \Box </math>
 
Of course not all invertible infinite lower triangular arrays are Riordan arrays. Here is a useful characterization for the arrays that are  Riordan. The following result is apparently due to Rogers 
<ref name="renewal">{{cite journal |last1=Rogers |first1=D. G. |title=Pascal triangles, Catalan numbers, and renewal arrays |journal=Discrete Math. |date=1978 |volume=22 |pages=301–310}}</ref>

''' Theorem.''' An infinite lower triangular array <math>D=(d_{n,k})_{n,k\geq 0}</math> is a Riordan array if and only if there exist a  sequence traditionally called the <math>A</math>-sequence, <math>A=(a_0\neq 0,a_1, . . . )</math> such that

{{center|<math> *_1: d_{n+1,k+1}= a_0 d_{n,k}+a_1 d_{n,k+1}+a_2 d_{n,k+2}+ \cdots = \sum_{j\geq 0} a_j d_{n,k+j}</math>}}
  
Proof.<ref name="SeqChar">{{cite journal |last1=He |first1=T.X.|last2=Sprugnoli|first2=R. 
|title=Sequence characterization of Riordan Arrays |journal=Discrete Mathematics |date=2009 |volume=309 |pages=3962–3974}}</ref> <math>\Rightarrow:</math>   Let <math>D</math> be the Riordan array stemming from <math>(d(t),h(t)).</math>  Since <math>d(t)\in \mathcal F_0,</math> <math>d_{0,0}\neq 0.</math> Since <math>h(t)</math> has order 1, it follows that <math>(d(t)h(t)/t, h(t))</math> is a Riordan array and by the group property there exists a Riordan array <math>(A(t),B(t))</math> such that  <math>(d(t),h(t))*(A(t),B(t))=(d(t)h(t)/t, h(t)).</math> Computing the  left hand side yields  <math>(d(t)A(h(t)),B(h(t)) </math> and so comparison yields <math>B(h(t))= h(t).</math> Of course <math>B(t)=t</math> is a solution to this equation; it is unique because <math>B</math> is composition invertible. So we can rewrite the equation as <math>(d(t),h(t))*(A(t), t)=(d(t)h(t)/t, h(t)).</math>
  
Now from the matrix multiplication law, the <math>n,k</math>-entry of the left hand side of this latter equation  is 
  
{{center|<math>    \sum_{j\geq 0} d_{n,j}(A(t),t)_{j,k}=\sum\limits_{j\geq 0} d_{n,j} [t^j] A(t) t^k= \sum\limits_{j\geq 0} d_{n,j} [t^{j-k}]A(t)=\sum\limits_{j\geq 0} d_{n,j} a_{j-k}=\sum\limits_{j\geq 0} a_j d_{n,k+j}.</math> }}
     
At the other hand the <math>n,k</math>-entry of the rhs of the equation above is 
{{center|<math>t^{[n]} \frac{1}{t} d(t) h(t) h(t)^k =  t^{[n+1]}  d(t) h(t)^{k+1} = d_{n+1,k+1},</math>}}
so that i results.  From <math> *_1 </math> we also get  <math>d_{n+1,n+1}=a_0 d_{n,n}</math>  for all <math>n\geq 0</math> and since we know that the diagonal elements are nonzero, we have <math>a_0\neq 0.</math> 
Note that using  equation <math> *_1 </math>  one can compute all entries knowing the entries  <math>(d_{n,0})_{n\geq 0}.</math> 
    
<math>\Leftarrow :</math>  Now assume we know of a triangular array the equations <math> *_1 </math> for some sequence <math>(a_j)_{j\geq 0}.</math>  Let <math>A(t)</math> be the generating function of that  sequence and define <math>h(t)</math> from the equation <math>tA(h(t))=h(t).</math> Check that it is possible to solve the resulting equations for the coefficients of <math>h;</math> and since <math>a_0\neq 0</math> one gets that  <math>h(t)</math> has order 1.   Let <math>d(t)</math> be the generating function of the sequence <math>(d_{0,0},d_{1,0},d_{2,0},. . . ).</math> Then for the pair <math>(d(t), h(t))</math>  we find <math>(d(t),h(t))*(A(t),t)= (d(t)A(h(t)), h(t))= (d(t)h(t)/t, h(t)).</math>  This is precisely the same equations we have found in the first part of the proof and going through its reasoning we find equations like in <math> *_1 </math>.   Since <math>d(t)</math> (or the sequence of its coefficients) determines the other entries we find that the array we started with is the array we deduced. So the array in <math> *_1 </math> is a Riordan array.   <math> \Box</math>

Clearly the  <math>A</math>-sequence alone does not deliver all the information about a Riordan array.   Besides the <math>A</math>-sequence 
it is the <math>Z</math>-sequence that has shown to be surprisingly useful.<ref name="AltChar">{{cite journal |last1=Merlini |first1=D. |
last2=Rogers|first2=D.G.|last3=Sprugnoli|first3=R.|last4=Verri, M.C.|first4=M.C.|
title=On Some Alternative Characterizations of Riordan Arrays |journal=Can. J. Math. |date=1997 |volume=49 |issue=2 |pages=301–320}}</ref>

''' Theorem.'''  Let <math>(d_{n,k})_{n,k\geq 0}</math> be an infinite lower triangular array whose diagonal sequence <math>(d_{n,n})_{n\geq 0}</math>  does not contain zeros.
Then there exists a unique sequence <math>Z=(z_0,z_1,z_2, . . .)</math>     such that 
{{center|<math>d_{n+1,0} =z_0 d_{n,0} + z_1 d_{n,1} + z_2 d_{n,2} + \cdots = \sum\limits_{j\geq 0} z_j d_{n,j},  \quad n=0,1,2,3, . . .</math>  }}
Proof. The proof is simple:  By triangularity of the array,  the equation claimed is equivalent to   <math>d_{n+1,0}=  \sum_{j= 0}^n z_j d_{n,j}.</math> For <math>n=0,</math>  this equation is <math>d_{1,0}=z_0 d_{0,0}</math> and, as <math>d_{0,0}\neq 0,</math>  it allows computing <math>z_0</math> uniquely. In general if <math>z_0,z_1, . . ., z_{n-1}</math> are known, then  <math>d_{n+1,0}-\sum_{j=0}^{n-1} z_j d_{n,j} =z_n d_{n,n}</math> allows computing <math>z_n</math> uniquely. <math> \Box</math>

Very recently there appeared the book<ref name="RiorGroup-book">{{cite book|
last1=Shapiro  |first1=L. |last2=Sprugnoli  |first2=R | last3=Barry  |first3=P. | last4=Cheon  |first4= G.S. |last5=He  |first5= T.X.| last6=Merlini|first6= D.  |last7=Wang  |first7=W.|title=The Riordan Group and Applications|date=2022 |publisher=Springer|isbn= 978-3-030-94150-5}}</ref> which should be a valuable source for further information.

==References==
{{reflist}}

[[Category:Combinatorics]]

{{Sourceattribution|Riordan array}}