Riordan array

A formal power series $a(x)=a\_0+a\_1x+a\_2x^2+\; \backslash cdots\; =\backslash sum\_\{j\backslash geq\; 0\}a\_j\; x^j\; \backslash in\; \backslash mathbb\{C\}x$ (where $\backslash mathbb\{C\}x$ is the ring of formal power series with complex coefficients) is said to have order $r$ if $a\_0=\backslash cdots=a\_\{r-1\}\; =0\backslash neq\; a\_r$. Write $\backslash mathcal\{F\}\_r$ for the set of formal power series of order $r$. A power series $a(x)$ has a multiplicative inverse (i.e. $1/a(x)$ is a power series) if and only if it has order 0, i.e. if and only if it lies in $\backslash mathcal\{F\}\_0$; it has a composition inverse that is there exists a power series $\backslash bar\; a$ such that $\backslash bar\; a(a(x))=x$ if and only if it has order 1, i.e. if and only if it lies in $\backslash mathcal\{F\}\_1$.

As mentioned previously, a Riordan array is usually defined via a pair of power series $(d(t),h(t))\backslash in\; \backslash mathcal\{F\}\_0\; \backslash times\; \backslash mathcal\{F\}\_1$. The "array" part in its name stems from the fact that one associates to $(d(t),h(t))$ the array of complex numbers defined by $d\_\{n,k\}:=[t^n]\; d(t)h(t)^k,$ $n,k\backslash in\; \backslash mathbb\{N\}$ (here "$[t^n]\backslash cdots$" means "coefficient of $t^n$ in $\backslash cdots$"). Thus column $k$ of the array consists of the sequence of coefficients of the power series $d(t)h(t)^k;$ in particular, column 0 determines and is determined by the power series $d(t).$ Because $d(t)$ is of order 0, it has a multiplicative inverse, and it follows that from the array's column 1 we can recover $h(t)$ as $h(t)=d(t)^\{-1\}\; d(t)h(t)$. Since $h(t)$ has order 1, $h(t)^k$ is of order $k$ and so is $d(t)h(t)^k.$ It follows that the array $d\_\{n,k\}$ is lower triangular and exhibits a geometric progression $(d\_\{k,k\})\_\{k\backslash geq\; 0\}=(d\_0\; h\_1^k)\_\{k\backslash geq\; 0\}$ on its main diagonal. It also follows that the map sending a pair of power series $(d(t),h(t))\backslash in\; \backslash mathcal\{F\}\_0\; \backslash times\; \backslash mathcal\{F\}\_1$ to its triangular array is injective.

An example of a Riordan array is given by the pair of power series

$\backslash left(\backslash frac\{1\}\{1-x\},\; \backslash frac\{x\}\{1-x\}\backslash right)=\backslash left(\backslash sum\_\{j\backslash geq\; 0\}\; x^j,\; \backslash sum\_\{j\backslash geq\; 0\}\; x^\{j+1\}\backslash right)\backslash in\; \backslash mathcal\; F\_0\backslash times\; \backslash mathcal\; F\_1$.

It is not difficult to show that this pair generates the infinite triangular array of binomial coefficients $d\_\{n,k\}=\backslash binom\{n\}\{k\}$, also called the Pascal matrix:

$P=\backslash left(\backslash begin\{array\}\{ccccccc\}$

1 & & & & & & \\

1 &1 & & & & & \\

1 &2 &1 & & & & \cdots \\

1 &3 &3 &1 & & & \\

1 &4 &6 &4 &1 & & \\

& & \vdots & & & & \ddots

\end{array}\right).

Proof: If $q(x)=\backslash sum\_\{j\backslash geq\; 0\}\; q\_j\; x^j$ is a power series with associated coefficient sequence $(q\_0,q\_1,q\_2,\backslash dotsc)$, then, by Cauchy multiplication of power series,

$q(x)\backslash frac\{x\}\{1-x\}=\backslash sum\_\{j\backslash geq\; 0\}\; (0+q\_0+q\_1+\; \backslash cdots+q\_\{j-1\})x^j.$ Thus, the latter series has the coefficient sequence $(0,q\_0,q\_0+q\_1,q\_0+q\_1+q\_2,\backslash dotsc)$, and hence

$[t^n]\; q(x)\backslash frac\{x\}\{1-x\}=\; q\_0+\backslash cdots+q\_\{n-1\}$. Fix any $k\backslash in\; \backslash mathbb\{Z\}\_\{\backslash geq\; 0\}.$ If $q\_n=\backslash binom\{n\}\{k\}$, so that $(q\_n)\_\{n\backslash geq\; 0\}$ represents column $k$ of the Pascal array, then $\backslash sum\_\{j=\; 0\}^\{n-1\}\; q\_j=\; \backslash sum\_\{j=\; 0\}^\{n-1\}\; \backslash binom\{j\}\{k\}=\backslash binom\{n\}\{k+1\}$. This argument shows by induction on $k$ that $\backslash frac\{1\}\{1-x\}\backslash left(\backslash frac\{x\}\{1-x\}\backslash right)^k$ has column $k$ of the Pascal array as coefficient sequence.

Below are some often-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., which describes them as derived from results in papers by Gian-Carlo Rota and the book of Roman.{{cite book |last1=Roman |first1=S. |title=The Umbral Calculus |date=1984 |publisher=Academic Press |location=New York}}

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

b. This fact justifies the definition of the multiplication '$*$' of Riordan arrays viewed as pairs of power series by {{center|$(a(x),b(x))*(c(x),d(x))=\; (a(x)\; c(b(x)),\; d(b(x)))$ }}

Proof: Since $a(x)$ and $c(x)$ have order 0, it is clear that $a(x)\; c(b(x))$ has order 0. Similarly, $b(x),d(x)\backslash in\; \backslash mathcal\; F\_1$ implies $d(b(x))\backslash in\; \backslash mathcal\; F\_1$.

Therefore, $(a(x)\; c(b(x)),\; d(b(x))\; )$ is a Riordan array.

Define a matrix $M$ as the Riordan array $(a(x),b(x))$. By definition, its $j$-th column $M\_\{*,j\}$ is the sequence of coefficients of

the power series $a(x)b(x)^j$. If we multiply this matrix from the right with the sequence $(r\_0,r\_1,r\_2,\; .\; .\; .\; )^T$ we get as a result a linear combination of columns of $M$ which we can read as a linear combination of power series, namely $\backslash sum\_\{\backslash nu\backslash geq\; 0\}\; r\_\backslash nu\; M\_\{*,\backslash nu\}\; =\; \backslash sum\_\{\backslash nu\backslash geq\; 0\}\; r\_\backslash nu\; a(x)b(x)^\backslash nu\; =\; a(x)\; \backslash sum\_\{\backslash nu\backslash geq\; 0\}\; r\_\backslash nu\; b(x)^\backslash nu.$ Thus, viewing sequence $(r\_0,r\_1,r\_2,\; .\; .\; .\; )^T$ as codified by the power series $r(x),$ we showed that$(a(x),b(x))*r(x)\; =\; a(x)\; r(b(x)).$ Here the $*$ is the symbol for indicating correspondence on the power series level with matrix multiplication. We multiplied a Riordan array $(a(x),b(x))$ with a single power series. Now let $(c(x),d(x))$ be another Riordan array viewed as a matrix. One can form the product $(a(x),b(x))(c(x),d(x))$. The $j$-th column of this product is just $(a(x),b(x))$ multiplied with the $j$-th column of $(c(x),d(x)).$ Since the latter corresponds to the power series

$c(x)\; d(x)^j$, it follows by the above that the $j$-th column of $(a(x),b(x))(c(x),d(x))$ corresponds to $a(x)\; c(b(x))\; d(b(x))^j$. As this holds for all column indices $j$ occurring in $(c(x),d(x))$ we have shown part a. Part b is now clear. $\backslash Box$

Theorem: The family of Riordan arrays endowed with the product '$*$' defined above forms a group: the Riordan group.

Proof: The associativity of the multiplication '$*$' follows from associativity of matrix multiplication. Next note $(1,x)*(c(x),d(x))=(1\backslash cdot\; c(x),\; d(x))=(c(x),d(x))$. So $(1,x)$ is a left neutral element. Finally, we claim that $(c(\backslash bar\; d(x))^\{-1\},\; \backslash bar\; d(x))$ is the left inverse to the power series $(c(x),d(x))$. For this check the computation $(c(\backslash bar\; d(x))^\{-1\},\; \backslash bar\; d(x))*\; (c(x),d(x))$ $=(\; (c(\backslash bar\; d(x)\; )^\{-1\}\; c(d(x))\; ,\; d(\backslash bar\; d(x))\; )=\; (1,x)$. As is well known, an associative structure which has a left neutral element and where each element has a left inverse is a group. $\backslash Box$

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.

{{cite journal |last1=Rogers |first1=D. G. |title=Pascal triangles, Catalan numbers, and renewal arrays |journal=Discrete Math. |date=1978 |volume=22 |issue=3 |pages=301–310|doi=10.1016/0012-365X(78)90063-8 }}

Theorem: An infinite lower triangular array $D=(d\_\{n,k\})\_\{n,k\backslash geq\; 0\}$ is a Riordan array if and only if there exist a sequence traditionally called the $A$-sequence, $A=(a\_0\backslash neq\; 0,a\_1,\; .\; .\; .\; )$ such that

{{center|$*\_1:\; d\_\{n+1,k+1\}=\; a\_0\; d\_\{n,k\}+a\_1\; d\_\{n,k+1\}+a\_2\; d\_\{n,k+2\}+\; \backslash cdots\; =\; \backslash sum\_\{j\backslash geq\; 0\}\; a\_j\; d\_\{n,k+j\}$}}

Proof.{{cite journal |last1=He |first1=T.X.|last2=Sprugnoli|first2=R.

|title=Sequence characterization of Riordan Arrays |journal=Discrete Mathematics |date=2009 |volume=309 |issue=12 |pages=3962–3974|doi=10.1016/j.disc.2008.11.021}} $\backslash Rightarrow:$ Let $D$ be the Riordan array stemming from $(d(t),h(t)).$ Since $d(t)\backslash in\; \backslash mathcal\; F\_0,$ $d\_\{0,0\}\backslash neq\; 0.$ Since $h(t)$ has order 1, it follows that $(d(t)h(t)/t,\; h(t))$ is a Riordan array and by the group property there exists a Riordan array $(A(t),B(t))$ such that $(d(t),h(t))*(A(t),B(t))=(d(t)h(t)/t,\; h(t)).$ Computing the left-hand side yields $(d(t)A(h(t)),B(h(t))$, and hence, comparison yields $B(h(t))=\; h(t)$. Thus, $B(t)=t$ is a solution to this equation; it is unique since $B$ is composition invertible. Thus, we can rewrite the equation as $(d(t),h(t))*(A(t),\; t)=(d(t)h(t)/t,\; h(t)).$

From the matrix multiplication law, the $(n,k)$-entry of the left-hand side of this latter equation is

{{center|$\backslash sum\_\{j\backslash geq\; 0\}\; d\_\{n,j\}(A(t),t)\_\{j,k\}=\backslash sum\backslash limits\_\{j\backslash geq\; 0\}\; d\_\{n,j\}\; [t^j]\; A(t)\; t^k=\; \backslash sum\backslash limits\_\{j\backslash geq\; 0\}\; d\_\{n,j\}\; [t^\{j-k\}]A(t)=\backslash sum\backslash limits\_\{j\backslash geq\; 0\}\; d\_\{n,j\}\; a\_\{j-k\}=\backslash sum\backslash limits\_\{j\backslash geq\; 0\}\; a\_j\; d\_\{n,k+j\}.$ }}

At the other hand the $(n,k)$-entry of the right-hand side of the equation above is

{{center|$t^\{[n]\}\; \backslash frac\{1\}\{t\}\; d(t)\; h(t)\; h(t)^k\; =\; t^\{[n+1]\}\; d(t)\; h(t)^\{k+1\}\; =\; d\_\{n+1,k+1\},$}}

so that i results. From $*\_1$ we also get $d\_\{n+1,n+1\}=a\_0\; d\_\{n,n\}$ for all $n\backslash geq\; 0$ and since we know that the diagonal elements are nonzero, we have $a\_0\backslash neq\; 0.$

Note that using equation $*\_1$ one can compute all entries knowing the entries $(d\_\{n,0\})\_\{n\backslash geq\; 0\}.$

$\backslash Leftarrow\; :$ Now assume that, for a triangular array, we have the equations $*\_1$ for some sequence $(a\_j)\_\{j\backslash geq\; 0\}.$ Let $A(t)$ be the generating function of that sequence and define $h(t)$ from the equation $tA(h(t))=h(t)$. Check that it is possible to solve the resulting equations for the coefficients of $h$; and since $a\_0\backslash neq\; 0$ one gets that $h(t)$ has order 1. Let $d(t)$ be the generating function of the sequence $(d\_\{0,0\},d\_\{1,0\},d\_\{2,0\},.\; .\; .\; )$. Then for the pair $(d(t),\; h(t))$ we find $(d(t),h(t))*(A(t),t)=\; (d(t)A(h(t)),\; h(t))=\; (d(t)h(t)/t,\; h(t))$. This is the same equations we found in the first part of the proof, and going through its reasoning, we find equations as in $*\_1$. Since $d(t)$ (or the sequence of its coefficients) determines the other entries, we see that the initial array is the array we deduced. Thus, the array in $*\_1$ is a Riordan array. $\backslash Box$

Clearly, the $A$-sequence alone does not contain all the information about a Riordan array. Indeed, it only determines $h(t)$ and places no restriction on $d(t)$. To determine $d(t)$ "horizontally", a similarly defined $Z$-sequence is used.

Theorem. Let $(d\_\{n,k\})\_\{n,k\backslash geq\; 0\}$ be an infinite lower triangular array whose diagonal sequence $(d\_\{n,n\})\_\{n\backslash geq\; 0\}$ does not contain zeroes. Then there exists a unique sequence $Z=(z\_0,z\_1,z\_2,\; .\; .\; .)$ such that

{{center|$d\_\{n+1,0\}\; =z\_0\; d\_\{n,0\}\; +\; z\_1\; d\_\{n,1\}\; +\; z\_2\; d\_\{n,2\}\; +\; \backslash cdots\; =\; \backslash sum\backslash limits\_\{j\backslash geq\; 0\}\; z\_j\; d\_\{n,j\},\; \backslash quad\; n=0,1,2,3,\; .\; .\; .$ }}

Proof: By the triangularity of the array, the equation claimed is equivalent to $d\_\{n+1,0\}=\backslash sum\_\{j=\; 0\}^n\; z\_j\; d\_\{n,j\}$. For $n=0$, this equation is $d\_\{1,0\}=z\_0\; d\_\{0,0\}$ and, as $d\_\{0,0\}\backslash neq\; 0,$ it allows computing $z\_0$ uniquely. In general, if $z\_0,z\_1,\; .\; .\; .,\; z\_\{n-1\}$ are known, then $d\_\{n+1,0\}-\backslash sum\_\{j=0\}^\{n-1\}\; z\_j\; d\_\{n,j\}\; =\; z\_n\; d\_\{n,n\}$ allows computing $z\_n$ uniquely. $\backslash Box$

{{reflist}}

Category:Combinatorics