\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{amssymb}
\usepackage{psfig,epsf}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
 
 
\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus 
 -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
% put a period after section or subsection number in header
\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth
     \def\@svsec{}\else 
     \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi
     \@tempskipa #5\relax
      \ifdim \@tempskipa>\z@ 
        \begingroup #6\relax
          \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}%
        \endgroup
       \csname #1mark\endcsname{#7}\addcontentsline
         {toc}{#1}{\ifnum #2>\c@secnumdepth \else
                      \protect\numberline{\csname the#1\endcsname}\fi
                    #7}\else
        \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname
                      {#7}\addcontentsline
                           {toc}{#1}{\ifnum #2>\c@secnumdepth \else
                             \protect\numberline{\csname the#1\endcsname}\fi
                       #7}}\fi
     \@xsect{#5}}
% put a period after theorem and theorem-like numbers
\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}
\makeatother

\newtheorem{theorem}{Theorem}
\begin{document}
  
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo110.eps}
\vskip1cm

{\LARGE\bf Generating Functions via Hankel and} \\ [+.05in]
{\LARGE\bf Stieltjes Matrices}\\
\vskip 1.5cm

{\large Paul Peart and Wen-Jin Woan} \bigskip \\
Department of Mathematics \\
Howard  University \\
Washington D.C. 20059 \medskip \\
Email address: \href{mailto:pp@scs.howard.edu}{pp@scs.howard.edu}
\vskip2cm
{\bf Abstract}
\end{center}
{\em When the Hankel matrix formed from the sequence $%
1,a_1,a_2,...$ has an $LDL^T$ decomposition, we provide a constructive  proof
that the Stieltjes matrix $S_L$ associated with $L$ is tridiagonal. In  the
important case when $L$ is a Riordan matrix using ordinary or  exponential
generating functions, we determine the specific form that $S_L$ must  have,
and we demonstrate, constructively, a one-to-one correspondence between the
generating function for the sequence and $S_L$. If $L$ is Riordan when  using
ordinary generating functions, we show how to derive a recurrence  relation
for the sequence.}

\vspace*{+.1in}
\noindent
\textbf{Keywords. }Hankel matrix, Stieltjes matrix, ordinary generating
function, exponential generating function, Riordan matrix, LDU
decomposition, tridiagonal matrix.\medskip\ 

\section{Introduction}
For each sequence in a large class of important combinatorial sequences,  we
can derive a closed form expression for an ordinary or exponential
generating function starting with the associated Hankel matrix or  Stieltjes
matrix. In this paper we give explicit relationships between  the
generating function, the Hankel matrix and the Stieltjes matrix. We  also
provide several illustrative examples. In [3], some work was  done
using the Hankel matrix approach, but the conditions under which the  method
would work were not determined, or were only implicitly conjectured. In the present
paper we use the Stieltjes matrix to obtain significant improvements in  the
analysis and application of the method.

Our basic assumption is that the Hankel matrix generated by the sequence  has
an $LDU$ factorization, where $L$ is a lower triangular matrix with all
diagonal elements equal to one, $U=L^T,$ and $D$ is a diagonal matrix  with
all diagonal elements nonzero. The Hankel matrix generated by the  sequence $%
a_0,a_1,a_2,...$, is given by the infinite matrix 
\[
H=\left[ 
\begin{array}{cccccc}
a_0 & a_1 & a_2 & a_3 & a_4 & . \\ 
a_1 & a_2 & a_3 & a_4 & a_5 & . \\ 
a_2 & a_3 & a_4 & a_5 & a_6 & . \\ 
a_3 & a_4 & a_5 & a_6 & a_7 & . \\ 
a_4 & a_5 & a_6 & a_7 & a_8 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \;. 
\]

Without loss of generality we take $a_0=1$.
A necessary and  sufficient
condition for $H$ to have an $LDU$ factorization is that $H$ be positive
definite. When $L$ is a Riordan matrix (see Section 2) using ordinary or
exponential generating functions, our method will find a closed form
expression for the generating function of the sequence  $1,a_1,a_2,a_3,...$
In the the ordinary generating function case we can then use [4] to find a recurrence
relation for the sequence.\medskip\ 

\paragraph{Example 1.}
Delannoy numbers: $1,3,13,63,321,1683,...$\\This  is
sequence
\htmladdnormallink{A1850}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001850}
in [5].
See also [1, p.~81].
We apply Gaussian elimination  to
the Hankel matrix to obtain

$H=\left[ 
\begin{array}{cccccc}
1 & 3 & 13 & 63 & 321 & . \\ 
3 & 13 & 63 & 321 & 1683 & . \\ 
13 & 63 & 321 & 1683 & 8989 & . \\ 
63 & 321 & 1683 & 8989 & 48639 & . \\ 
321 & 1683 & 8989 & 48639 & 265729 & . \\ 
. & . & . & . & . & .
\end{array}
\right] =$\medskip\ 

$\left[ 
\begin{array}{cccccc}
1 &  &  &  &  & . \\ 
3 & 1 &  &  &  & . \\ 
13 & 6 & 1 &  &  & . \\ 
63 & 33 & 9 & 1 &  & . \\ 
321 & 180 & 62 & 12 & 1 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \left[ 
\begin{array}{cccccc}
1 &  &  &  &  & . \\ 
& 4 &  &  &  & . \\ 
&  & 8 &  &  & . \\ 
&  &  & 16 &  & . \\ 
&  &  &  & 32 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \left[ 
\begin{array}{cccccc}
1 & 3 & 13 & 63 & 321 & . \\ 
& 1 & 6 & 33 & 180 & . \\ 
&  & 1 & 9 & 62 & . \\ 
&  &  & 1 & 12 & . \\ 
&  &  &  & 1 & . \\ 
. & . & . & . & . & .
\end{array}
\right] .$\bigskip\ 

The Stieltjes matrix $S_L$ associated with $L$ is the matrix 
$S_L=L^{-1}\overline{L}$, where $\overline{L}$ is obtained from $L$  by
deleting the first row.
(See Section 2 for more details about the
Stieltjes matrix.)
In Example 1, 
\[
S_L=\left[ 
\begin{array}{cccccc}
3 & 1 &  &  &  & . \\ 
4 & 3 & 1 &  &  & . \\ 
& 2 & 3 & 1 &  & . \\ 
&  & 2 & 3 & 1 & . \\ 
&  &  & 2 & 3 & . \\ 
. & . & . & . & . & .
\end{array}
\right] . 
\]
From its definition $S_L$ gives the rule of formation of $L.$  Specifically,
it gives a rule for obtaining the $n^{th}$ row of $L$ from the  previous
row. In the example, we have for $n\geq 1$%
\[
l_{n0}=3l_{n-1,0}+4l_{n-1,1} 
\]
\[
l_{nk}=l_{n-1,k-1}+3l_{n-1,k}+2l_{n-1,k+1}\quad ,\quad k\geq 1\,. 
\]
It is convenient to define the leftmost column of $L$ to be the zeroth
column, and the first row to be the zeroth row.
We say that the zeroth  column
of $L$ has a $\{3,4\}$ rule of formation and that the $k^{th}$ column,  $%
k\geq 1,$ has a $\{1,3,2\}$ rule of formation.
Notice that the zeroth  column
of $L$ contains the Delannoy numbers and that $S_L$ is tridiagonal.
In Section 2 we prove that whenever $H=LDU$, then $S_L$ is tridiagonal.
From Theorem 2 in Section 2 we see that the Delannoy numbers have a closed-form
ordinary generating function given by 
\[
g(x)=\frac 1{1-3x-4xf}=\frac 1{\sqrt{1-6x+x^2}}~,
\]
where 
\[
f(x)=x(1+3f+2f^2)=\frac{1-3x-\sqrt{1-6x+x^2}}{4x}~. 
\]
Since $S_L$ is tridiagonal and $L$ is a Riordan matrix, we can use [4]  to
obtain for the Delannoy numbers the recurrence 
\begin{eqnarray*}
na_n &=&3(4n-3)a_{n-1}-19(2n-3)a_{n-2}+3(4n-9)a_{n-3}-(n-3)a_{n-4}; \\
\mbox{for}~n &\geq &4, ~\mbox{with}~ a_0=1, a_1=3, a_2=13, a_3=63\,.
\end{eqnarray*}

\paragraph{Example 2.}
Bell numbers:  $1,1,2,5,15,52,203,877,4140,21147,...$\\%
This sequence illustrates the exponential generating function case. It  is
sequence
\htmladdnormallink{A110}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000110}
in [5].
Here\\$L=\left[ 
\begin{array}{cccccc}
1 &  &  &  &  & . \\ 
1 & 1 &  &  &  & . \\ 
2 & 3 & 1 &  &  & . \\ 
5 & 10 & 6 & 1 &  & . \\ 
15 & 37 & 31 & 10 & 1 & . \\ 
. & . & . & . & . & .
\end{array}
\right]$ and $S_L=\left[ 
\begin{array}{cccccc}
1 & 1 &  &  &  & . \\ 
1 & 2 & 1 &  &  & . \\ 
& 2 & 3 & 1 &  & . \\ 
&  & 3 & 4 & 1 & . \\ 
&  &  & 4 & 5 & . \\ 
. & . & . & . & . & .
\end{array}
\right] .$\\
From Theorem 3 in Section 2, the form of $S_L$ indicates that  the
exponential generating function $g(x)$ of the Bell numbers is given by 
\[
\ln (g)=\int (1+f)dx,\quad g(0)=1, 
\]
where 
\[
f^{\prime }(x)=1+f(x),\quad f(0)=0. 
\]
So we obtain 
\[
f(x)=e^x-1\quad \mbox{and}\quad g(x)=e^{e^x-1}. 
\]

We have found that the method works for many other important combinatorial
sequences. These include
\begin{itemize}
\item
the Catalan numbers: $1, 1, 2, 5, 14, 42, 132, 429, \ldots$ 
(sequence
\htmladdnormallink{A108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000108})
\item
the shortened Catalan sequence:
1, 2, 5, 14, 42, 132, 429, $\ldots$
\item
the Catalan numbers interspersed with
zeros: $1,0,1,0,2,0,5,0,14,0,42, \ldots$
\item
central binomial coefficients:
$1,2,6,20,70,252,,924,3432, \ldots$
(\htmladdnormallink{A984}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000984})
\item
central trinomial coefficients:
$1,1,3,7, 19, 51, 141, \ldots$
(\htmladdnormallink{A2426}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002426}),
\item
Schr\"{o}der's numbers:
$1, 2, 6, 22, 90, 394, 1806, \ldots$
(\htmladdnormallink{A6318}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006318})
\item
Schr\"{o}der's second problem:
$1,1,3,11,45,197,903,4279, \ldots$
(\htmladdnormallink{A1003}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001003})
\item
gamma numbers or Motzkin
sums: $1,0,1,1,3,6,15,36,91,232, \ldots$
(\htmladdnormallink{A5043}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005043})
\item
Fine numbers:
$1,0,1,2,6,18,57,186,622, \ldots$
(\htmladdnormallink{A957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000957})
\item
directed animals: $1,2,5,13,35,96,267,750,2123, \ldots$
(\htmladdnormallink{A5773}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005773})
\item
telephone numbers, or self-inverse permutations:
$1,1,2,4,10,26,76,232,764, \ldots$
(\htmladdnormallink{A85}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000085})
\item
derangement numbers: $1,0,1,2,9,44,265,1854,14833, \ldots$
(\htmladdnormallink{A166}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000166}).
\end{itemize}

In Section 2 we show that whenever $H=LDU$ then $S_L$ is always
tridiagonal, and we give the specific form of $S_L$. Theorem 2 in that
section indicates the specific form that $S_L$ must have for $L$ to be a
Riordan matrix with ordinary generating functions. Theorem 3 indicates  the
specific form that $S_L$ must have for $L$ to be Riordan with  exponential
generating functions.
In Section 3 we give some further  examples.\medskip 

\section{Definitions and Theorems}
\paragraph{Definition.}
The\ \textbf{Hankel matrix}\textit{\ }$%
H=(h_{nk})_{n,k\geq 0}$ generated by the sequence $1,a_1,a_2,a_3,...$  is
given by 
\[
h_{00}=1,\quad h_{nk}=a_{n+k}\quad \mbox{for}\quad n\geq 0,\quad k\geq 0.
\]

\paragraph{Definition.}
Let $L=(l_{nk})_{n,k\geq 0}$ be a lower
triangular matrix with $l_{ii}=1$ for all $i\geq 0$ . The  \textbf{Stieltjes
matrix} $S_L$ associated with $L$ is given by  $S_L=L^{-1}\overline{L}$,
where $\overline{L}$ is obtained from $L$ by deleting the first row of  $L.$
That is, the element in the $n^{th}$ row and $k^{th}$ column of  $\overline{L%
}$ is given by 
\[
\overline{l}_{nk}=l_{n+1,k}\,.
\]

\paragraph{Remark.}
We note that $S_L$ is unique, and so 
\[
S_L=S_{\widetilde{L}}\Leftrightarrow L=\widetilde{L}\,.
\]

\paragraph{Remark.}
If $S_L=(s_{ik})_{i,k\geq 0}$ then 
\[
l_{nk}=\sum\limits_{i\geq o}s_{ik}l_{n-1,i}\quad \mbox{for}\quad n\geq 1\,.
\]
That is, from $S_L$ , we obtain a rule for computing the $n^{th}$ row of  $L$
from the $(n-1)^{th}$ row.\\ \medskip


\paragraph{Remark.}
$S_L$ is tridiagonal
if and only if there exist sequences $\{\lambda _k\}_{k\geq 0}$ , and  $\{\mu
_k\}_{k\geq 0}$ such that 
\[
l_{n0}=\lambda _0l_{n-1,0}+\mu _0l_{n-1,1}\quad \mbox{for}\quad n\geq 1,
\]
\[
l_{nk}=l_{n-1,k-1}+\lambda _kl_{n-1,k}+\mu _kl_{n-1,k+1}\quad \mbox{for}\quad  k\geq
1\quad \mbox{and}\quad n\geq 1,
\]
and 
\[
s_{00}=\lambda _0,\quad s_{10}=\mu _0\;,\quad \mbox{and~for}\quad k\geq
1\;,\;s_{kk}=\lambda _k\;,\;s_{k+1,k}=\mu _k\,.
\]

\paragraph{Definition.}
A \textbf{Riordan matrix with ordinary  generating
functions\ }is a lower triangular matrix for which the generating  function
for the $k^{th}$ column, $k\geq 0$, is given by $g(x)[f(x)]^k$ , where 
\[
g(x)=1+g_1x+g_2x^2+
\cdots \quad\mbox{and}\quad f(x)=x+f_2x^2+f_3x^3+ \cdots
\]

\paragraph{Definition.}
A \textbf{Riordan matrix with exponential  generating
functions\ }is a lower triangular matrix for which the generating  function
for the $k^{th}$ column, $k\geq 0,$ is given by $\frac 1{k!}g(x)[f(x)]^k$  ,
where 
\[
g(x)=1+g_1x+g_2\frac{x^2}{2!}+g_3\frac{x^3}{3!}+\cdots
\quad\mbox{and}\quad  f(x)=x+f_2%
\frac{x^2}{2!}+f_3\frac{x^3}{3!}+ \cdots~.
\]
See [2] for a detailed description of Riordan matrices.
In [6]
Woodson explores other kinds of Riordan matrices.\bigskip\ \\ \bigskip%

\begin{theorem}\label{th1}
Let $H=(h_{nk})_{n,k\geq 0}$ be the Hankel matrix
generated by the sequence $1,a_1,a_2,a_3,...$ Assume that $H=LDU$  where 
\[
L=(l_{nk})_{n,k\geq 0}=\left[ 
\begin{array}{cccccc}
1 &  &  &  &  & . \\ 
l_{10} & 1 &  &  &  & . \\ 
l_{20} & l_{21} & 1 &  &  & . \\ 
l_{30} & l_{31} & l_{32} & 1 &  & . \\ 
l_{40} & l_{41} & l_{42} & l_{43} & 1 & . \\ 
. & . & . & . & . & .
\end{array}
\right] ,
\]
\[
D=\left[ 
\begin{array}{cccccc}
d_0 &  &  &  &  & . \\ 
& d_1 &  &  &  & . \\ 
&  & d_2 &  &  & . \\ 
&  &  & d_3 &  & . \\ 
&  &  &  & d_4 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \quad \quad d_i\neq 0\quad for\;all\;i,\quad \quad U=L^T\,.
\]
That is, 
\[
h_{nk}=\sum\limits_{i=0}^kd_il_{ki}l_{ni}\,.
\]
Then the Stieltjes matrix $S_L$ is tridiagonal with the form 
\[
S_L=\left[ 
\begin{array}{cccccc}
\lambda _0 & 1 &  &  &  & . \\ 
\mu _0 & \lambda _1 & 1 &  &  & . \\ 
& \mu _1 & \lambda _2 & 1 &  & . \\ 
&  & \mu _2 & \lambda _3 & 1 & . \\ 
&  &  & \mu _3 & \lambda _4 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \,,
\]
where 
\[
\lambda _0=a_1\;,\quad \mu _0=d_1\;,\quad \lambda
_k=l_{k+1,k}-l_{k,k-1}\;,\quad \mu _k=\frac{d_{k+1}}{d_k}\;,\quad  k\geq 1\,.
\]
\end{theorem}

\paragraph{Proof.}
We will prove that 
\[
l_{n0}=a_1l_{n-1,0}+d_1l_{n-1,1}
\]
and 
\[
l_{nk}=l_{n-1,k-1}+\lambda _kl_{n-1,k}+\mu _kl_{n-1,k+1}\quad
for\;all\;k\geq 1.
\]
We use induction on $k.$ From the definition of the Hankel matrix, 
\[
h_{nk}=h_{n-1,k+1}\quad \mbox{for all}\quad k\geq 0\quad\mbox{and}\quad n\geq 1
\]
\[
h_{n0}=h_{n-1,1}\Leftrightarrow
d_0l_{n0}=d_0l_{n-1,0}l_{10}+d_1l_{n-1,1}l_{11}\Leftrightarrow
l_{n0}=a_1l_{n-1,0}+d_1l_{n-1,1}\;.
\]
\[
h_{n1}=h_{n-1,2}\Leftrightarrow
d_0l_{10}l_{n0}+d_1l_{11}l_{n1}=d_0l_{20}l_{n-1,0}+d_1l_{21}l_{n-1,1}+d _2l_{22}l_{n-1,2}
\]
\begin{eqnarray*}
&\Leftrightarrow
&d_1l_{n1}=l_{20}l_{n-1,0}-l_{10}l_{n0}+d_1l_{21}l_{n-1,1}+d_2l_{n-1,2} \\
&\Leftrightarrow
&d_1l_{n1}=d_1l_{n-1,0}+d_1(l_{21}-l_{10})l_{n-1,1}+d_2l_{n-1,2} \\
\quad  &\Leftrightarrow &l_{n1}=l_{n-1,0}+\lambda _1l_{n-1,1}+\mu  _1l_{n-1,2}
\end{eqnarray*}
Now assume that 
\[
l_{ni}=l_{n-1,i-1}+\lambda _il_{n-1,i}+\mu _il_{n-1,i+1}\quad for\quad  1\leq
i\leq k-1\,.
\]
Then 
\begin{eqnarray*}
h_{nk} &=&h_{n-1,k+1}\Leftrightarrow
\sum\limits_{i=0}^kd_il_{ki}l_{ni}=\sum%
\limits_{i=0}^{k+1}d_il_{k+1,i}l_{n-1,i} \\
&\Leftrightarrow
&\sum\limits_{i=0}^{k-1}d_il_{ki}l_{ni}-\sum%
\limits_{i=0}^{k-1}d_il_{k+1,i}l_{n-1,i}+d_kl_{nk}=d_kl_{k+1,k}l_{n-1 ,k}+d_{k+1}l_{n-1,k+1}
\\
&\Leftrightarrow
&d_0l_{k0}l_{n0}+\sum\limits_{i=1}^{k-1}d_il_{ki}l_{ni}-\left[
d_0l_{k+1,0}l_{n-1,0}+\sum\limits_{i=1}^{k-1}d_il_{k+1,i}l_{n-1,i}\right]
+d_kl_{nk} \\
&=&d_kl_{k+1,k}l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
&\Leftrightarrow &d_0l_{k0}\left[ a_1l_{n-1,0}+d_1l_{n-1,1}\right]
+\sum\limits_{i=1}^{k-1}d_il_{ki}l_{ni} \\
&&-\left[
d_0(a_1l_{k0}+d_1l_{k1})l_{n-1,0}+\sum%
\limits_{i=1}^{k-1}d_il_{k+1,i}l_{n-1,i}\right] +d_kl_{nk} \\
&=&d_kl_{k+1,k}l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
&\Leftrightarrow
&d_1l_{k0}l_{n-1,1}+\sum\limits_{i=1}^{k-1}d_il_{ki}l_{ni}-\left[
d_1l_{k1}l_{n-1,0}+\sum\limits_{i=1}^{k-1}d_il_{k+1,i}l_{n-1,i}\right]
+d_kl_{nk} \\
&=&d_kl_{k+1,k}l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
\, &\Leftrightarrow
&d_1l_{k0}l_{n-1,1}+\sum\limits_{i=1}^{k-1}d_il_{ki}\left[
l_{n-1,i-1}+\lambda _il_{n-1,i}+\frac{d_{i+1}}{d_i}l_{n-1,i+1}\right] 
\end{eqnarray*}
\begin{eqnarray*}
&&-\left[ d_1l_{k1}l_{n-1,0}+\sum\limits_{i=1}^{k-1}d_il_{n-1,i}\left[
l_{k,i-1}+\lambda _il_{ki}+\frac{d_{i+1}}{d_i}l_{k,i+1}\right] \right]
+d_kl_{nk} \\
&=&d_kl_{k+1,k}l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
&\Leftrightarrow
&d_1l_{k0}l_{n-1,1}+\sum\limits_{i=1}^{k-1}d_il_{ki}l_{n-1,i-1}+\sum%
\limits_{i=1}^{k-1}d_{i+1}l_{ki}l_{n-1,i+1} \\
&&-\left[
d_1l_{k1}l_{n-1,0}+\sum\limits_{i=1}^{k-1}d_il_{k,i-1}l_{n-1,i}+\sum%
\limits_{i=1}^{k-1}d_{i+1}l_{k,i+1}l_{n-1,i}\right] +d_kl_{nk} \\
&=&d_kl_{k+1,k}l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
&\Leftrightarrow &\quad \,d_1\left[
l_{k0}l_{n-1,1}+l_{k1}l_{n-1,0}-l_{k1}l_{n-1,0}-l_{k0}l_{n-1,1}\right]   \\
&&+d_2\left[
l_{k2}l_{n-1,1}+l_{k1}l_{n-1,2}-l_{k1}l_{n-1,2}-l_{k2}l_{n-1,1}\right]   \\
&&+d_3\left[
l_{k3}l_{n-1,2}+l_{k2}l_{n-1,3}-l_{k2}l_{n-1,3}-l_{k3}l_{n-1,2}\right]   \\
&&...... \\
&&...... \\
&&+d_{k-1}\left[
l_{k,k-1}l_{n-1,k-2}+l_{k,k-2}l_{n-1,k-1}-l_{k,k-2}l_{n-1,k-1}-l_{k,k-1}l _{n-1,k-2}\right] 
\\
&&+d_k\left[ l_{k,k-1}l_{n-1,k}-l_{kk}l_{n-1,k-1}\right] +d_kl_{nk} \\
&=&d_kl_{k+1,k}l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
&&
\end{eqnarray*}
\begin{eqnarray*}
&\Leftrightarrow &d_kl_{nk}=d_kl_{n-1,k-1}+d_k\left[
l_{k+1,k}-l_{k,k-1}\right] l_{n-1,k}+d_{k+1}l_{n-1,k+1} \\
&\Leftrightarrow &l_{nk}=l_{n-1,k-1}+\lambda _kl_{n-1,k}+\mu
_kl_{n-1,k+1}  
\end{eqnarray*}
When $S_L$ has $\lambda _i=\lambda $ and $\mu _i=\mu $ for all  $i\geq 1$
we can obtain an ordinary generating function for the sequence  $1,a_1,a_2,...
$\medskip\ 

\begin{theorem}\label{th2}
Let $H$ be the Hankel matrix generated by the  sequence $%
1,a_1,a_2,...$, and let $H=LDL^T$. Then $S_L$ has the form 
\[
S_L=\left[ 
\begin{array}{cccccc}
a_1 & 1 &  &  &  & . \\ 
d_1 & \lambda & 1 &  &  & . \\ 
& \mu & \lambda & 1 &  & . \\ 
&  & \mu & \lambda & 1 & . \\ 
&  &  & \mu & \lambda & . \\ 
. & . & . & . & . & .
\end{array}
\right] \,, 
\]
if and only if the ordinary generating function $g(x)$ of the sequence  $%
1,a_1,a_2,...$ is given by 
\[
g(x)=\frac 1{1-a_1x-d_1xf}\,, 
\]
where 
\[
f=x(1+\lambda f+\mu f^2)\;,\quad f(0)=0. 
\]
\end{theorem}

\paragraph{Proof.}
We note that $\mu \neq 0$ and 
\[
f=\frac{1-\lambda x-\sqrt{(1-\lambda x)^2-4\mu x}}{2\mu x}\,. 
\]
Consider the lower triangular matrix $\widetilde{L}$ such that the
generating function for the $k^{th}$ column is $g(x)[f(x)]^k,\quad k\geq  0.$ 
\begin{eqnarray*}
g(x) &=&\frac 1{1-a_1x-d_1xf}\Leftrightarrow g(x)=1+a_1xg(x)+d_1xgf  \\
&\Leftrightarrow &\widetilde{l}_{00}=1\quad \mbox{and}\quad \left[ x^n\right]
g=a_1\left[ x^n\right] xg+d_1\left[ x^n\right] xgf \\
&\Leftrightarrow &\widetilde{l}_{00}=1\quad \mbox{and}\quad  \widetilde{l}_{n0}=a_1%
\widetilde{l}_{n-1,0}+d_1\widetilde{l}_{n-1,1}\quad for\quad n\geq 1.
\end{eqnarray*}
Also, for $k\geq 1$ , 
\begin{eqnarray*}
f &=&x(1+\lambda f+\mu f^2)\Leftrightarrow gf^k=xgf^{k-1}+\lambda  xgf^k+\mu
xgf^{k+1} \\
&\Leftrightarrow &\left[ x^n\right] gf^k=\left[ x^n\right]  xgf^{k-1}+\lambda
\left[ x^n\right] xgf^k+\mu \left[ x^n\right] xgf^{k+1} \\
&\Leftrightarrow &\widetilde{l}_{nk}=\widetilde{l}_{n-1,k-1}+\lambda 
\widetilde{l}_{n-1,k}+\mu \widetilde{l}_{n-1,k+1}\,.
\end{eqnarray*}
Therefore $S_L$ has the given form if and only if  $S_L=S_{\widetilde{L}%
}\Leftrightarrow L=\widetilde{L}. $

We now turn to the exponential generating function case. We get an
exponential generating function for the sequence $1,a_1,a_2,...$ when  the
sequences $\{\lambda _i\}_{i\geq 0}$ and $\{\frac{\mu  _i}{i+1}\}_{i\geq 0}$
are arithmetic sequences.\medskip\ 

\begin{theorem}\label{th3}
Let $H$ be the Hankel matrix generated by the  sequence $%
1,a_1,a_2,...$, and let $H=LDL^T.$ Then $S_L$ has the form given in  Theorem
1. If $\{\lambda _i\}_{i\geq 0}$, is an arithmetic sequence with common
difference $\lambda $ and $\{\frac{\mu _i}{i+1}\}_{i\geq 0}$ an  arithmetic
sequence with common difference $\mu $ , then the exponential generating
function $g(x)$ for the sequence $1,a_1,a_2,...$ is given by 
\[
\ln (g)=\int (a_1+d_1f)dx\;,\quad \quad g(0)=1, 
\]
where $f$ is given by 
\[
f^{\prime }=1+\lambda f+\mu f^2\;,\quad \quad f(0)=0\,. 
\]
\end{theorem}

\paragraph{Proof.}
Consider the lower triangular matrix $\widehat{L}$ with $\frac
1{k!}g(x)[f(x)]^k$ for the exponential generating function of the  $k^{th}$
column, $k\geq 0.$ We note that $\widehat{L}$ is a Riordan matrix with
exponential generating functions. 
\begin{eqnarray*}
\ln (g) &=&\int (a_1+d_1f)dx\Rightarrow g^{\prime  }=a_1g+d_1fg\Rightarrow
\left[ \frac{x^n}{n!}\right] g^{\prime }=a_1\left[  \frac{x^n}{n!}\right]
g+d_1\left[ \frac{x^n}{n!}\right] fg \\
&\Rightarrow &\widehat{l}_{n+1,0}=a_1\widehat{l}_{n0}+d_1\widehat{l}%
_{n1}\Rightarrow \widehat{l}_{n0}=\lambda _0\widehat{l}_{n-1,0}+\mu  _0%
\widehat{l}_{n-1,1}
\end{eqnarray*}
For $k\geq 1$ , 
\begin{eqnarray*}
\left( \frac{gf^k}{k!}\right) ^{\prime } &=&\frac{g^{\prime  }f^k}{k!}+\frac{%
gf^{k-1}f^{\prime  }}{(k-1)!}=\frac{a_1gf^k}{k!}+\frac{d_1gf^{k+1}}{k!}+\frac{%
gf^{k-1}+\lambda gf^k+\mu gf^{k+1}}{(k-1)!} \\
&=&(a_1+\lambda k)\frac{gf^k}{k!}+(d_1+\mu  k)\frac{gf^{k+1}}{k!}+\frac{%
gf^{k-1}}{(k-1)!} \\
&=&\frac{gf^{k-1}}{(k-1)!}+\lambda _k\frac{gf^k}{k!}+\frac{\mu  _k}{k+1}\frac{%
gf^{k+1}}{k!}\,.
\end{eqnarray*}
Therefore
\begin{eqnarray*}
\left[ \frac{x^n}{n!}\right] \left( \frac{gf^k}{k!}\right) ^{\prime }
&=&\left[ \frac{x^n}{n!}\right] \left( \frac{gf^{k-1}}{(k-1)!}+\lambda  _k%
\frac{gf^k}{k!}+\mu _k\frac{gf^{k+1}}{(k+1)!}\right) \,. \\
&&
\end{eqnarray*}
That is, 
\[
\widehat{l}_{n+1,k}=\widehat{l}_{n,k-1}+\lambda _k\widehat{l}_{nk}+\mu  _k%
\widehat{l}_{n,k+1}\,,
\]
\[
\widehat{l}_{nk}=\widehat{l}_{n-1,k-1}+\lambda  _k\widehat{l}_{n-1,k}+\mu _k%
\widehat{l}_{n-1,k+1}\,. 
\]
Therefore $S_L$ has the given form if and only if $L=\widehat{L}.$  \quad
 \medskip\ 

\section{Further Examples}
\paragraph{Example 3.}
Derangements:  $1,0,1,2,9,44,265,1854,14833,...$\\This is
sequence
\htmladdnormallink{A166}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000166}
in [5].
$H=LDL^T$ and 
\[
S_L=\left[ 
\begin{array}{cccccc}
0 & 1 &  &  &  & . \\ 
1 & 2 & 1 &  &  & . \\ 
& 4 & 4 & 1 &  & . \\ 
&  & 9 & 6 & 1 & . \\ 
&  &  & 16 & 8 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \,. 
\]
This is the exponential case with $\lambda _k=2k$ and $\mu  _k=(k+1)^2.$
Therefore $\lambda =2$ and $\mu =1.$ So $f^{\prime }=1+2f+f^2$  with $%
f(0)=0. $ That gives $f=\frac x{1-x}$ and $\ln (g)=\int fdx$ ,  $g(0)=1.$ So 
\[
g(x)=\frac{e^{-x}}{1-x}\,. 
\]

\paragraph{Example 4.}
Here we start with a Stieltjes matrix having the  form
in Theorem 3. The associated sequence is 1,3,10,39,187,1128,8455, ... 
(sequence
\htmladdnormallink{A54912}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054912}
in [5]).
\[
S_L=\left[ 
\begin{array}{cccccc}
3 & 1 &  &  &  & . \\ 
1 & 6 & 1 &  &  & . \\ 
& 6 & 9 & 1 &  & . \\ 
&  & 15 & 12 & 1 & . \\ 
&  &  & 28 & 15 & . \\ 
. & . & . & . & . & .
\end{array}
\right] \,. 
\]
Here $S_L$ has the form in Theorem 3 with $\lambda =3$ and $\mu  =2.$
Therefore the exponential generating function for the sequence in the
leftmost column of $L$ is given by $\ln (g)=\int (3+f)dx,\quad  g(0)=1$ where 
$f^{\prime }=1+3f+2f^2,\quad f(0)=0.$
We get  $f=\frac{e^x-1}{2-e^x}$
and 
\[
g(x)=\sqrt{\frac{e^{5x}}{2-e^x}}=1+3x+10\frac{x^2}{2!}+39\frac{x^3}{3 !}+187%
\frac{x^4}{4!}+1128\frac{x^5}{5!}+8455\frac{x^6}{6!}+O(x^7) 
\]
We can also use Theorem 1 to construct $L$ and $D.$ Recall that  $d_{i+1}=\mu
_id_i,$ and that $d_0=1.$\bigskip\ 

\section*{Acknowledgements}
We thank the other members of the Howard University Combinatorics Group
(Seyoum Getu, Louis Shapiro, Leon Woodson and Asamoah Nkwanta)
for their helpful suggestions and encouragement.

\section*{References}

\begin{description}
\item  1. L. Comtet. {\em Advanced Combinatorics}.
D. Reidel
Publishing Company, 1974.

\item  2. S. Getu, L. W. Shapiro, W.-J. Woan, \& L. C. Woodson.  The
Riordan Group.  {\em Discrete Applied Mathematics},
{\bf 34} (1991), 229-239.

\item  3. S. Getu, L. W. Shapiro, W.-J. Woan, \& L. C. Woodson. How
to Guess a Generating Function.
{\em SIAM  Journal on Discrete Mathematics},
{\bf 5} (1992), 497-499.

\item  4. P. Peart, \& L. C. Woodson. Triple Factorization of some
Riordan Matrices.
{\em Fibonacci Quarterly}, {\bf 31}
(1993), 121-128.

\item  5.
N. J. A. Sloane.
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim
$njas/sequences/}{http://www.research.att.com/~njas/sequences/}.


\item  6. L. C. Woodson.
{\em Infinite Matrices, $C_n$-Functions and Umbral
Calculus}.
Ph.D. Thesis. Howard University, 1991.
\end{description}

\vspace*{+.5in}
\centerline{\rule{5.4in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Concerned with sequences
\htmladdnormallink{A108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000108},
\htmladdnormallink{A166}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000166},
\htmladdnormallink{A957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000957},
\htmladdnormallink{A984}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000984},
\htmladdnormallink{A1003}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001003},
\htmladdnormallink{A1850}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001850},
\htmladdnormallink{A2426}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002426},
\htmladdnormallink{A5773}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005773},
\htmladdnormallink{A6318}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006318},
\htmladdnormallink{A54912}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054912}.)
}

\centerline{\rule{5.4in}{.01in}}

\vspace*{+.1in}
\noindent
Received May 15, 1999;
published in Journal of Integer Sequences June 4, 2000.

\centerline{\rule{5.4in}{.01in}}

\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.research.att.com/~njas/sequences/JIS/}.

\centerline{\rule{5.4in}{.01in}}

\end{document}


.