\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \usepackage{amsthm} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{xca}[theorem]{Exercise} \newtheorem{conjecture}[theorem]{Conjecture} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Some Observations on the Lah and Laguerre \\ \vskip .1in Transforms of Integer Sequences} \vskip 1cm \large Paul Barry\\ School of Science\\ Waterford Institute of Technology\\ Ireland\\ \href{mailto:pbarry@wit.ie}{\tt pbarry@wit.ie} \\ \end{center} \vskip .2 in \begin{abstract} We study the Lah and related Laguerre transforms within the context of exponential Riordan arrays. Links to the Stirling numbers are explored. Results for finite matrices are generalized, leading to a number of useful matrix factorizations. \end{abstract} \section{Integer sequences and transforms on them} In this note, we shall consider integer sequences $$a:\mathbf{N}_0 \to \mathbf{Z} $$ with general term $a_n=a(n)$. Normally, sequences will be described by either by their ordinary generating function (o.g.f.), that is, the function $g(x)$ such that $$g(x)=\sum_{n=0}^{\infty}a_nx^n,$$ or by their exponential generating function (e.g.f.) $f(x)$, where $$f(x)=\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}.$$ We shall encounter transformations that operate on integer sequences during the course of this note. An example of such a transformation that is widely used in the study of integer sequences is the so-called Binomial transform \cite{Bin}, which associates to the sequence with general term $a_n$ the sequence with general term $b_n$ where \begin{equation}b_n=\sum_{k=0}^n{{n}\choose{k}}a_k.\end{equation} If we consider the sequence with general term $a_n$ to be the column vector $\mathbf{a}=(a_0,a_1,\ldots)'$ then we obtain the binomial transform of the sequence by multiplying this (infinite) vector by the lower-triangle matrix $\mathbf{B}$ whose $(n,k)$-th element is equal to $\binom{n}{k}$: \begin{displaymath}\mathbf{B}=\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 2 & 1 & 0 & 0 & 0 & \ldots \\ 1 & 3 & 3 & 1 & 0 & 0 & \ldots \\ 1 & 4 & 6 & 4 & 1 & 0 & \ldots \\1 & 5 & 10 & 10 & 5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\end{displaymath} This transformation is invertible, with \begin{equation}a_n=\sum_{k=0}^n {{n}\choose{k}}(-1)^{n-k}b_k.\end{equation} We note that $\mathbf{B}$ corresponds to Pascal's triangle. Its row sums are $2^n$, while its diagonal sums are the Fibonacci numbers $F(n+1)$. If $\mathbf{B}^m$ denotes the $m-$th power of $\mathbf{B}$, then the $n-$th term of $\mathbf{B}^m\mathbf{a}$ where $\mathbf{a}=\{a_n\}$ is given by $\sum_{k=0}^n m^{n-k}{{n}\choose{k}}a_k$. If $\mathcal{A}(x)$ is the ordinary generating function of the sequence $a_n$, then the ordinary generating function of the transformed sequence $b_n$ is $\frac{1}{1-x}\mathcal{A}(\frac{x}{1-x})$. Similarly, if $\mathcal{G}(x)$ is the exponential generating function (e.g.f.) of the sequence $a_n$, then the exponential generating function of the binomial transform of $a_n$ is $\exp(x)\mathcal{G}(x)$. The binomial transform is an element of the exponential Riordan group, which can be defined as follows. The \emph{exponential Riordan group} \cite {PasTri}, \cite{ProdMat}, \cite{DeutschShap}, is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions $g(x)=1+g_1x+g_2x^2+\ldots$ and $f(x)=f_1x+f_2x^2+\ldots$ where $f_1\ne 0$. The associated matrix is the matrix whose $k$-th column has exponential generating function $g(x)f(x)^k/k!$ (the first column being indexed by 0). The matrix corresponding to the pair $f, g$ is denoted by $[g, f]$. The group law is then given by \begin{displaymath} [g, f]*[h, l]=[g(h\circ f), l\circ f].\end{displaymath} The identity for this law is $I=[1,x]$ and the inverse of $[g, f]$ is $[g, f]^{-1}=[1/(g\circ \bar{f}), \bar{f}]$ where $\bar{f}$ is the compositional inverse of $f$. If $\mathbf{M}$ is the matrix $[g,f]$, and $\mathbf{a}=\{a_n\}$ is an integer sequence with exponential generating function $\mathcal{A}$ $(x)$, then the sequence $\mathbf{M}\mathbf{a}$ has exponential generating function $g(x)\mathcal{A}(f(x))$. We shall use the notation $(g(x),f(x))$ to denote an element of the (ordinary) Riordan group \cite{GSWW}. Riordan group techniques have been used to provide alternative proofs of many binomial identities that originally appeared in works such as \cite{Riordan}, \cite{Riordan2}. See for instance \cite{SpruId}, \cite{Spru}. \begin{example} The Binomial matrix $\mathbf{B}$ is the element $[e^x,x]$ of the exponential Riordan group. More generally, $\mathbf{B}^k$ is the element $[e^{kx},x]$ of the exponential Riordan group. It is easy to show that the inverse $\mathbf{B}^{-k}$ of $\mathbf{B}^k$ is given by $[e^{-kx},x]$. Note that as an element of the (ordinary) Riordan group, $\mathbf{B}$ is given by $(\frac{1}{1-x},\frac{x}{1-x})$. Similarly $\mathbf{B}^k$ is the element $(\frac{1}{1-kx},\frac{x}{1-kx})$ of the Riordan group. \end{example} \begin{example} The exponential generating function of the row sums of the matrix $[g, f]$ is obtained by applying $[g, f]$ to $e^x$, the e.g.f. of the sequence $1,1,1,\ldots$. Hence the row sums of $[g,f]$ have e.g.f. $g(x)e^{f(x)}$. \end{example} We shall frequently refer to sequences by their sequence number in the On-Line Encylopedia of Integer Sequences \cite{SL1}, \cite{SL2}. For instance, Pascal's triangle is \seqnum{A007318} while the Fibonacci numbers $F(n)$ are \seqnum{A000045}. \begin{example} \textbf{The Permutation matrix $\mathbf{P}$ and its inverse}. We consider the matrix $$\mathbf{P}=[\frac{1}{1-x},x].$$ The general term $P(n,k)$ of this matrix is easily found: \begin{eqnarray*} P(n,k)&=&\frac{n!}{k!}[x^n]\frac{x^k}{1-x}\\ &=&\frac{n!}{k!}[x^{n-k}]\frac{1}{1-x}\\ &=&\frac{n!}{k!}[x^{n-k}]\sum_{j=0}^{\infty}x^j\\ &=&\frac{n!}{k!}\qquad \mathrm{if} \qquad n-k\ge 0, \qquad =0, \qquad \mathrm{otherwise,}\\ &=& [k\le n]\frac{n!}{k!}.\end{eqnarray*} Here, we have used the Iverson bracket notation \cite{Concrete}, defined by $[\mathcal{P}]=1$ if the proposition $\mathcal{P}$ is true, and $[\mathcal{P}]=0$ if $\mathcal{P}$ is false. For instance, $\delta_{ij}=[i=j]$, while $\delta_n=[n=0]$. Clearly, the inverse of this matrix is $\mathbf{P}^{-1}=[(1-x),x]$. The general term of this matrix is given by \begin{eqnarray*} P^{-1}(n,k)&=&\frac{n!}{k!}[x^n](1-x)x^k\\ &=&\frac{n!}{k!}[x^{n-k}](1-x)\\ &=&\frac{n!}{k!}(\delta_{n-k}-\delta_{n-k-1})\\ &=&\delta_{n-k}-(k+1)\delta_{n-k-1}\end{eqnarray*} Thus \begin{displaymath}\mathbf{P}=\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 2 & 1 & 0 & 0 & 0 & \ldots \\ 6 & 6 & 3 & 1 & 0 & 0 & \ldots \\ 24 & 24 & 12& 4 & 1 & 0 & \ldots \\120 & 120 & 60 & 20 & 5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\end{displaymath} while \begin{displaymath}\mathbf{P}^{-1}=\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\-1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & -2 & 1 & 0 & 0 & 0 & \ldots \\ 0 & 0 & -3 & 1 & 0 & 0 & \ldots \\ 0 & 0 & 0& -4 & 1 & 0 & \ldots \\0 & 0 & 0 & 0 & -5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\end{displaymath} \end{example} \section{The Lah transform} Introduced by Jovovic (see, for instance, \seqnum{A103194}), the Lah transform is the transformation on integer sequences whose matrix is given by $$\mathbf{Lah}=[1,\frac{x}{1-x}].$$ Properties of the matrix obtained from the $n \times n$ principal sub-matrix of $\mathbf{Lah}$, and related matrices have been studied in \cite{LahMatrix}. From the above definition, we see that the matrix $\mathbf{Lah}$ has general term $\mathrm{Lah}(n,k)$ given by \begin{eqnarray*}\mathrm{Lah}(n,k)&=&\frac{n!}{k!}[x^n]\frac{x^k}{(1-x)^k}\\ &=&\frac{n!}{k!}[x^{n-k}]\sum_{j=0}^{\infty}\binom{-k}{j}(-1)^jx^j\\ &=&\frac{n!}{k!}[x^{n-k}]\sum{j}\binom{k+j-1}{j}x^j\\ &=&\frac{n!}{k!}\binom{n-1}{n-k}\end{eqnarray*} Thus if $b_n$ is the Lah transform of the sequence $a_n$, we have $$b_n=\sum_{k=0}^n \frac{n!}{k!}\binom{n-1}{n-k}a_k.$$ It is clear that the inverse of this matrix $\mathbf{Lah}^{-1}$ is given by $[1,\frac{x}{1+x}]$ with general term $\mathrm{Lah}(n,k)(-1)^{n-k}$. Thus $$a_n=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\binom{n-1}{n-k}b_k.$$ Numerically, we have \begin{displaymath}\mathbf{Lah}=\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\0 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & 2 & 1 & 0 & 0 & 0 & \ldots \\ 0 & 6 & 6 & 1 & 0 & 0 & \ldots \\ 0 & 24 & 36 & 12 & 1 & 0 & \ldots \\0 & 120 & 240 & 120 & 20 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\end{displaymath} Operating on the sequence with e.g.f. $f(x)$, it produces the sequence with e.g.f. $f(\frac{x}{1-x})$. \begin{example} The row sums of the matrix $\mathbf{Lah}$, obtained by operating on the sequence $1,1,1\ldots$ with e.g.f. $e^x$, is the sequence $1, 1, 3, 13, 73, 501, \ldots$ (\seqnum{A000262}) with e.g.f. $e^\frac{x}{1-x}$. We observe that this is $n!L(n,-1,-1)=n!L_n^{(-1)}(-1)$ (see Appendix for notation). This sequence counts the number of partitions of $\{1,..,n\}$ into any number of lists, where a list means an ordered subset. \end{example} \section{The generalized Lah transform} Extending the definition in \cite{LahMatrix}, we can define, for the parameter $t$, the generalized Lah matrix $$\mathbf{Lah}[t]=[1,\frac{x}{1-tx}].$$ It is immediate that $\mathbf{Lah}[0]=[1,x]=\mathbf{I}$, and $\mathbf{Lah}[1]=\mathbf{Lah}$. The general term of the matrix $\mathbf{Lah}[t]$ is easily computed: \begin{eqnarray*}\mathrm{Lah}[t](n,k)&=&\frac{n!}{k!}[x^n]\frac{x^k}{(1-tx)^k}\\ &=&\frac{n!}{k!}[x^{n-k}]\sum_{j=0}^{\infty}\binom{-k}{j}(-1)^jt^jx^j\\ &=&\frac{n!}{k!}[x^{n-k}]\sum{j}\binom{k+j-1}{j}t^jx^j\\ &=&\frac{n!}{k!}\binom{n-1}{n-k}t^{n-k}.\end{eqnarray*} We can easily establish that $\mathbf{Lah}[t]^{-1}=[1,\frac{x}{1+tx}]=\mathbf{Lah}[-t]$ with general term $\frac{n!}{k!}\binom{n-1}{n-k}t^{n-k}(-1)^{n-k}.$ We also have $$\mathbf{Lah}[u+v]=\mathbf{Lah}[u]\cdot\mathbf{Lah}[v].$$ This follows since \begin{eqnarray*}\mathbf{Lah}[u]\cdot\mathbf{Lah}[v]&=&[1,\frac{x}{1-ux}][1,\frac{x}{1-vx}]\\ &=&[1,\frac{\frac{x}{1-vx}}{1-\frac{ux}{1-vx}}]\\ &=&[1,\frac{\frac{x}{1-vx}}{\frac{1-vx-ux}{1-vx}}]\\ &=&[1,\frac{x}{1-(u+v)x}]\\ &=&\mathbf{Lah}[u+v].\end{eqnarray*} For integer $m$, it follows that $$\mathbf{Lah}[mt]=(\mathbf{Lah}[t])^m.$$ \section{Laguerre related transforms} In this section, we will define the Laguerre transform on integer sequences to be the transform with matrix given by $$\mathbf{Lag}=[\frac{1}{1-x},\frac{x}{1-x}].$$ We favour this denomination through analogy with the Binomial transform, whose matrix is given by $$(\frac{1}{1-x},\frac{x}{1-x}).$$ Numerically, we have \begin{displaymath}\mathbf{Lag}=\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 4 & 1 & 0 & 0 & 0 & \ldots \\ 6 & 18 & 9 & 1 & 0 & 0 & \ldots \\ 24 & 96 & 72 & 16 & 1 & 0 & \ldots \\120 & 600 & 600 & 200 & 25 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\end{displaymath} The inverse of the Laguerre transform, as we understand it in this section, is given by $$\mathbf{Lag}^{-1}=[\frac{1}{1+x},\frac{x}{1+x}].$$ Clearly, the general term $\mathrm{Lag}(n,k)$ of the matrix $\mathbf{Lag}$ is given by $$\mathrm{Lag}(n,k)=\frac{n!}{k!}\binom{n}{k}.$$ Thus if $b_n$ is the Laguerre transform of the sequence $a_n$, we have $$b_n=\sum_{k=0}^n\frac{n!}{k!}\binom{n}{k}a_k.$$ The e.g.f. of $b_n$ is given by $\frac{1}{1-x}f(\frac{x}{1-x})$ where $f(x)$ is the e.g.f. of $a_n$. The inverse matrix of $\mathbf{Lag}$ has general term given by $(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}$. Thus $$a_n=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}b_k.$$ The relationship between the Lah transform with matrix $\mathbf{Lah}$ and the Laguerre transform with matrix $\mathbf{Lag}$ is now clear: \begin{eqnarray*} \mathbf{Lag}&=&[\frac{1}{1-x},\frac{x}{1-x}]\\ &=&[\frac{1}{1-x},x][1,\frac{x}{1-x}]\\ &=&\mathbf{P}\cdot \mathbf{Lah}\end{eqnarray*} We note that this implies that \begin{eqnarray*} \mathrm{Lag}(n,k)&=&\frac{n!}{k!}\binom{n}{k}\\ &=&\sum_{i=0}^n [i\le n]\frac{n!}{i!}\frac{i!}{k!}\binom{i-1}{i-k}\\ &=&\sum_{i=0}^n[k \le n]\frac{n!}{k!}\binom{i-1}{i-k}\\ &=&\frac{n!}{k!}\sum_{i=0}^n \binom{i-1}{i-k}\end{eqnarray*} which indeed is true since $$\binom{n}{k}=\sum_{i=0}^n \binom{i-1}{i-k}.$$ Numerically, we have \begin{eqnarray*}\mathbf{P}\cdot \mathbf{Lah}&=&\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 2 & 1 & 0 & 0 & 0 & \ldots \\ 6 & 6 & 3 & 1 & 0 & 0 & \ldots \\ 24 & 24 & 12 & 4 & 1 & 0 & \ldots \\120 & 120 & 60 & 20 & 5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right) \left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\0 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & 2& 1 & 0 & 0 & 0 & \ldots \\ 0 & 6 & 6 & 1 & 0 & 0 & \ldots \\ 0& 24 & 36 & 12 & 1 & 0 & \ldots \\0 & 120 & 240 & 120 & 20 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\\ &=& \left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 4 & 1 & 0 & 0 & 0 & \ldots \\ 6& 18 & 9 & 1 & 0 & 0 & \ldots \\ 24 & 96 & 72 & 16 & 1 & 0 & \ldots \\120 & 600 & 600 & 200 & 25 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\\&=&\mathbf{Lag}\end{eqnarray*} Similarly we have $$\mathbf{Lag}^{-1}=\mathbf{Lah}^{-1}\cdot\mathbf{P}^{-1},$$ which implies that \begin{eqnarray*}\mathrm{Lag}^{-1}(n,k)&=&(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}\\ &=&\sum_{i=0}^n (-1)^{n-i}\frac{n!}{i!}\binom{n-1}{n-i}(\delta_{i-k}-(k+1)\delta_{i-k-1}).\end{eqnarray*} It is of course possible to pass from $\mathbf{Lag}$ to $\mathbf{Lah}$ by: $$\mathbf{Lah}=\mathbf{P}^{-1}\cdot\mathbf{Lag}.$$ Thus \begin{eqnarray*}\mathrm{Lah}(n,k)&=&\frac{n!}{k!}\binom{n-1}{n-k}\\ &=&\sum_{i=0}^n (\delta_{n-i}-(i+1)\delta_{n-i-1})\frac{i!}{k!}\binom{i}{k} \end{eqnarray*} We note in passing that this gives us the identity $$n!\binom{n-1}{n-k}\\ =\sum_{i=0}^n (\delta_{n-i}-(i+1)\delta_{n-i-1})i!\binom{i}{k}.$$ Numerically, we have \begin{eqnarray*}\mathbf{P}^{-1}\cdot \mathbf{Lag}&=&\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\-1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & -2 & 1 & 0 & 0 & 0 & \ldots \\ 0 & 0 & -3 & 1 & 0 & 0 & \ldots \\ 0 & 0 & 0 & -4 & 1 & 0 & \ldots \\0 & 0 & 0 & 0 & -5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right) \left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 4& 1 & 0 & 0 & 0 & \ldots \\ 6 & 18 & 9 & 1 & 0 & 0 & \ldots \\ 24 & 96 & 72 & 16 & 1 & 0 & \ldots \\120 & 600 & 600 & 200 & 25 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\\ &=& \left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\0 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & 2 & 1 & 0 & 0 & 0 & \ldots \\ 0 & 6 & 6 & 1 & 0 & 0 & \ldots \\ 0 & 24 & 36 & 12 & 1 & 0 & \ldots \\0 & 120 & 240 & 120 & 20 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\\&=&\mathbf{Lah}\end{eqnarray*} Thus if the Laguerre transform of $a_n$ has general term $b_n$, then the general term of the Lah transform of $a_n$ will be given by $$b_n-nb_{n-1}$$ (for $n > 0)$. \begin{example} The row sums of the matrix $\mathbf{Lag}$, that is, the transform of the sequence $1,1,1,\ldots$ with e.g.f. $e^x$, is the sequence $1, 2, 7, 34, 209, 1546, 13327, \ldots$ with e.g.f. $\frac{1}{1-x}e^{\frac{x}{1-x}}$. This is \seqnum{A002720}. Among other things, it counts the number of matchings in the bipartite graph $K(n,n)$. It general term is $\sum_{k=0}^n \frac{n!}{k!}\binom{n}{k}$. This is equal to $L_n(-1)$ where $L_n(x)$ is the $n$-th Laguerre polynomial. \end{example} \begin{example} The row sums of the matrix $\mathbf{Lag}^{-1}$ yield the sequence $1, 0, -1, 4, -15, 56, -185, 204, \ldots$ with e.g.f. $\frac{1}{1+x}e^{\frac{x}{1+x}}$. It has general term $\sum_{k=0}^n (-1)^{n-k} \frac{n!}{k!}\binom{n}{k}$ which is equal to $(-1)^n L_n(1)$. \end{example} \section{The Associated Laguerre transforms} The Lah and Laguerre transforms, as defined above, are elements of a one-parameter family of transforms, whose general element is given by $$\mathbf{Lag}^{(\alpha)}=[\frac{1}{(1-x)^{\alpha+1}},\frac{x}{1-x}].$$ We can calculate the general term of this matrix in the usual way: \begin{eqnarray*} \mathrm{Lag}^{(\alpha)}(n,k)&=&\frac{n!}{k!}[x^n](1-x)^{-(\alpha+1)}x^k(1-x)^{-k}\\ &=&\frac{n!}{k!}[x^{n-k}](1-x)^{-(\alpha+k+1)}\\ &=&\frac{n!}{k!}\sum_{j=0}^{\infty}\binom{\alpha+k+j}{j}x^j\\ &=&\frac{n!}{k!}\binom{n+\alpha}{n-k}.\end{eqnarray*} We note that $\mathbf{Lah}=\mathbf{Lag}^{(-1)}$ while $\mathbf{Lag}=\mathbf{Lag}^{(0)}$. We can factorize $\mathbf{Lag}^{(\alpha)}$ as follows: \begin{eqnarray*}\mathbf{Lag}^{(\alpha)}&=&[\frac{1}{(1-x)^{\alpha}},x][\frac{1}{1-x},\frac{x}{1-x}]\\ &=&\mathbf{P}^{(\alpha)}\cdot\mathbf{Lag}\end{eqnarray*} where $\mathbf{P}^{(\alpha)}$ has general term $\frac{n!}{k!}\binom{n+\alpha-k-1}{n-k}$. Clearly, $\mathbf{P}^{(1)}=\mathbf{P}$. In fact, we have $\mathbf{P}^{(\alpha)}=\mathbf{P}^\alpha$. The transform of the sequence $a_n$ by the associated Laguerre transform for $\alpha$ is the sequence $b_n$ with general term $b_n=\sum_{k=0}^n \frac{n!}{k!}\binom{n+\alpha}{n-k}a_k,$ which has e.g.f. $\frac{1}{(1-x)^{\alpha+1}}f(\frac{x}{1-x})$. We note that in the literature of Riordan arrays, the subset of matrices of the form $(1,f(x))$ forms a sub-group, called \emph{the associated group}. We trust that this double use of the term ``associated'' does not cause confusion. \section{The Generalized Laguerre transform} We define, for the parameter $t$, the generalized Laguerre matrix $\mathbf{Lag}[t]$ to be $$\mathbf{Lag}[t]=[\frac{1}{1-tx},\frac{x}{1-tx}].$$ We immediately have \begin{eqnarray*}\mathbf{Lag}[t]&=&[\frac{1}{1-tx},\frac{x}{1-tx}]\\ &=&[\frac{1}{1-tx},x][1,\frac{x}{1-tx}]\\ &=&\mathbf{P}[t]\cdot\mathbf{Lah}[t].\end{eqnarray*} where the generalized permutation matrix $\mathbf{P}[t]$ has general term $[k \le n]\frac{n!}{k!}t^{n-k}$. It is clear that $$\mathbf{Lag}[t]^{-1}=\mathbf{Lag}[-t]=[\frac{1}{1+tx},\frac{x}{1+tx}].$$ It is possible to generalize the associated Laguerre transform matrices in similar fashion. \section{Transforming the expansion of $\frac{x}{1-\mu x-\nu x^2}$} The e.g.f. of the expansion of $\frac{x}{1-\mu x-\nu x^2}$ takes the form $$f(x)=A(\mu,\nu)e^{r_1 x}+B(\mu,\nu)e^{r_2 x}$$ which follows immediately from the Binet form of the general term. Thus the transform of this sequence by $\mathbf{Lag}^{(\alpha)}$ will have e.g.f. $$ \frac{A(\mu,\nu)}{(1-x)^{\alpha+1}}e^{\frac{r_1 x}{1-x}}+\frac{B(\mu,\nu)}{(1-x)^{\alpha+1}}e^{\frac{r_2 x}{1-x}}.$$ In the case of the Lah transform ($\alpha=-1$), we get the simple form $$Ae^{\frac{r_1 x}{1-x}}+Be^{\frac{r_2 x}{1-x}}$$ while in the Laguerre case ($\alpha=0$) we get $$A\frac{e^{\frac{r_1 x}{1-x}}}{1-x}+B\frac{e^{\frac{r_2 x}{1-x}}}{1-x}$$ But $\frac{e^{\frac{r x}{1-x}}}{1-x}$ is the e.g.f. of the sequence $n!L_n(-r)$. Thus is this case, the transformed sequence has general term $A n!L_n(-r_1)+B n!L_n(-r_2)$. \begin{example} The Laguerre transform of the Fibonacci numbers $$F(n)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$$ is given by $$\frac{1}{\sqrt{5}}n!L_n(-\frac{1+\sqrt{5}}{2})-\frac{1}{\sqrt{5}}n!L_n(-\frac{1-\sqrt{5}}{2}).$$ This is \seqnum{A105277}. It begins $0, 1, 5, 29, 203, 1680, 16058, \ldots$. \end{example} \begin{example} The Laguerre transform of the Jacobsthal numbers \cite{BarryJac}, \cite{Jac} (expansions of $\frac{x}{1-x-2x^2}$) $$J(n)=\frac{2^n}{3}-\frac{(-1)^n}{3}$$ is given by $$\frac{1}{3}n!L_n(-2)-\frac{1}{3}n!L_n(1).$$ This is \seqnum{A129695}. It begins $0,1,5,30,221,1936,19587,\ldots$. We can use this result to express the Lah transform of the Jacobsthal numbers, since this is equal to $b_n-nb_{n-1}$ where $b_n$ is the Laguerre transform of $J(n)$. We find $$\frac{n!}{3}(L_n(-2)-L_{n-1}(-2)-(L_n(1)-L_{n-1}(1))).$$ \end{example} \begin{example} We calculate the $\mathbf{Lag}^{(1)}$ transform of the Jacobsthal numbers $J(n)$. Since $\mathbf{Lag}^{(1)}=\mathbf{P}\cdot\mathbf{Lag}$, we apply $\mathbf{P}$ to the Laguerre transform of $J(n)$. This gives us $$\sum_{k=0}^n \frac{n!}{k!}(k!L_k(-2)-k!L_k(1))/3=\frac{n!}{3}\sum_{k=0}^n (L_k(-2)-L_k(1)).$$ This sequence has e.g.f. $\frac{1}{(1-x)^2}\frac{e^{\frac{2x}{(1-x)}}-e^{\frac{-x}{1-x}}}{3}$. \end{example} \section{The Lah and Laguerre transforms and Stirling numbers} In this section, we follow the notation of \cite{Concrete}. Thus the Stirling numbers of the first kind, denoted by ${n \brack k}$, are the elements of the matrix $$\mathbf{s}=[1, \ln(\frac{1}{1-x})].$$ ${n \brack k}$ counts the number of ways to arrange $n$ objects into $k$ cycles. The Stirling numbers of the second kind, denoted by ${n \brace k}$, count the number of ways to partition a set of $n$ things into $k$ nonempty subsets. ${n \brace k}$ are the elements of the matrix $$\mathbf{S}=[1, e^x-1].$$ We have $${n \brace k}=\sum_{i=0}^k \binom{k}{i}\frac{i^n}{k!}.$$ We note that the matrix $[1, e^x-1]$ of Stirling numbers of the second kind is the inverse of the matrix with elements $(-1)^{n-k}{n \brack k}$, which is the matrix $[1, \ln(1+x)]$. Related matrices include $$[\frac{1}{1-x},\ln(\frac{1}{1-x})]$$ whose elements are given by ${n+1 \brack k+1}$ and its signed version, $$[\frac{1}{1+x},\ln(\frac{1}{1+x})]$$ whose elements are given by $(-1)^{n-k}{n+1 \brack k+1}$, along with their inverses, given respectively by $[e^{-x}, 1-e^{-x}]$, with general element $(-1)^{n-k}{n+1 \brace k+1}$, and $[e^x, e^x-1]$ with general element ${n+1 \brace k+1}$. We can generalize a result linking the Lah matrix to the Stirling numbers \cite{LahMatrix} to the infinite matrix case as follows: $$\mathbf{Lah}=\mathbf{s}\cdot\mathbf{S}.$$ This is because we have \begin{eqnarray*} \mathbf{s}\cdot\mathbf{S}&=&[1,\ln(\frac{1}{1-x})][1,e^x-1]\\ &=&[1, e^{\ln(\frac{1}{1-x})}-1]\\ &=&[1,\frac{1}{1-x}-1]\\ &=&[1,\frac{x}{1-x}]=\mathbf{Lah}.\end{eqnarray*} Thus we have $$\mathbf{S}=\mathbf{s}^{-1}\cdot\mathbf{Lah}, \qquad\qquad \mathbf{s}=\mathbf{Lah}\cdot\mathbf{S}^{-1}.$$ We now observe that \begin{eqnarray*} [\frac{1}{1-x},\frac{x}{1-x}][1, \ln(1+x)]&=&[\frac{1}{1-x},\ln(1+\frac{x}{1-x})]\\ &=&[\frac{1}{1-x},\ln(\frac{1}{1-x})]\end{eqnarray*} or $$\mathbf{Lag}\cdot\left((-1)^{n-k}{n\brack k}\right)=\left({n+1 \brack k+1}\right).$$ We deduce the identity $$ {n+1 \brack k+1}=\sum_{j=0}^n \frac{n!}{j!}\binom{n}{j}(-1)^{j-k}{j \brack k}.$$ Taking the inverse of the matrix identity above, we obtain $$\left({n+1 \brack k+1}\right)^{-1}=\left((-1)^{n-k}{n\brack k}\right)^{-1}\cdot \mathbf{Lag}^{-1}$$ which can be established alternatively by noting that \begin{eqnarray*} [1,e^x-1][\frac{1}{1+x},\frac{x}{1+x}]&=&[1.\frac{1}{1+e^x-1}, \frac{e^x-1}{1+e^x-1}]\\ &=&[e^{-x},1-e^{-x}].\end{eqnarray*} This establishes the identity $$(-1)^{n-k}{n+1 \brace k+1}=\sum_{j=0}^n (-1)^{j-k}\binom{j}{k}\frac{j!}{k!}{n \brace j}.$$ Finally, from the matrix identity $$\mathbf{Lag}\cdot\left((-1)^{n-k}{n\brack k}\right)=\left({n+1 \brack k+1}\right).$$ we deduce that \begin{eqnarray*}\mathbf{Lag}&=&\left({n+1 \brack k+1}\right)\cdot \left((-1)^{n-k}{n\brack k}\right)^{-1}\\ &=&\left({n+1 \brack k+1}\right)\cdot \left({n \brace k}\right).\end{eqnarray*} Thus $$\mathrm{Lag}(n,k)=\sum_{j=0}^n {n+1 \brack j+1} {j \brace k}.$$ This is equivalent to the factorization $$\mathbf{Lag}=[\frac{1}{1-x},\frac{x}{1-x}]=[\frac{1}{1-x},\ln(\frac{1}{1-x})][1,e^x-1].$$ This implies (see Appendix A) that $$L_n(x)=\frac{1}{n!}\sum_{k=0}^n\sum_{j=0}^n {n+1 \brack j+1}{j \brace k}(-x)^k.$$ It is natural in this context to define as \emph{associated Stirling numbers of the first kind} the elements ${n \brack k }_{\alpha}$ of the matrices $$[\frac{1}{(1-x)^{\alpha}},\ln(\frac{1}{1-x})].$$ For instance, ${n \brack k }_{0}={n \brack k }$ and ${n \brack k }_{1}={n+1 \brack k+1 }$. We note that signed versions of these numbers have been documented by Lang (see for instance \seqnum{A049444} and \seqnum{A049458}). To calculate ${n \brack k }_{2}$, we proceed as follows: \begin{eqnarray*} \left({n \brack k }_{2}\right)&=&[\frac{1}{(1-x)^{2}},\ln(\frac{1}{1-x})]\\ &=&\mathbf{P} \cdot [\frac{1}{1-x},\ln(\frac{1}{1-x})]\\ &=&\left([k\le n]\frac{n!}{k!}\right) \left( {n+1 \brack k+1}\right).\end{eqnarray*} Thus $$ {n \brack k}_2=\sum_{j=0}^n \frac{n!}{j!}{j+1 \brack k+1}=\sum_{j=0}^n \frac{n!}{j!}{n \brack k}_1.$$ More generally, since $[\frac{1}{(1-x)^{\alpha}},\ln(\frac{1}{1-x})]=\mathbf{P}[\frac{1}{(1-x)^{\alpha-1}},\ln(\frac{1}{1-x})]$, we have $${n \brack k}_{\alpha}=\sum_{j=0}^n \frac{n!}{j!}{n \brack k}_{\alpha-1}.$$ $$\mathrm{Lag}^{(\alpha)}(n,k)=\sum_{j=0}^n {n \brack j}_{\alpha+1}{n \brace k}.$$ For example, \begin{eqnarray*}\mathbf{Lag}^{(1)}&=&[\frac{1}{(1-x)^2},\ln(\frac{1}{1-x})][1,e^x-1]\\ &=&\left(\sum_{j=0}^n {n \brack j}_2 {j \brace k}\right)\\ &=&\left(\sum_{j=0}^n\sum_{i=0}^n\frac{n!}{i!}{n+1 \brack j+1}{j \brace k}\right).\end{eqnarray*} In general, we have $$\mathbf{Lag}^{(\alpha)}=[\frac{1}{(1-x)^{\alpha+1}},\frac{x}{1-x}]=[\frac{1}{(1-x)^{\alpha+1}},\ln(\frac{1}{1-x})][1,e^x-1].$$ This implies that $$\mathrm{Lag}^{(\alpha)}(n,k)=\sum_{j=0}^n {n \brack j}_{\alpha+1}{n \brace k}.$$ \section{The generalized Lah, Laguerre and Stirling matrices} Given a parameter $t$ define the generalized Stirling numbers of the first kind to be the elements of the matrix $$\mathbf{s}[t]=[1,\frac{1}{t}\ln(\frac{1}{1-tx})].$$ Similarly, we define the generalized Stirling numbers of the second kind to be the elements of the matrix $$\mathbf{S}[t]=[1,\frac{e^{tx}-1}{t}].$$ Then $$\mathbf{S}[t]^{-1}=\mathbf{s}[-t].$$ For instance, \begin{eqnarray*}\mathbf{s}[-t]\cdot\mathbf{S}[t]&=& [1,-\frac{1}{t}\ln(\frac{1}{1+tx})][1,\frac{e^{tx}-1}{t}]\\ &=&[1,-\frac{1}{t}\ln(\frac{1}{1+t\frac{e^{tx}-1}{t}})]\\ &=&[1,-\frac{1}{t}\ln(\frac{1}{e^{tx}})]\\ &=&[1,\frac{1}{t}\ln(e^{tx})]\\ &=&[1,x]=\mathbf{I}.\end{eqnarray*} The general term of $\mathbf{s}[t]$ is given by $t^{n-k}{n \brack j}$ and that of $\mathbf{S}[t]$ is given by $t^{n-k}{n \brace j}$. An easy calculation establishes that $$\mathbf{Lah}[t]=\mathbf{s}[t]\mathbf{S}[t].$$ From this we immediately deduce that $$\mathbf{Lag}[t]=\mathbf{P}[t]\mathbf{s}[t]\mathbf{S}[t].$$ Similarly results for the generalized associated Laguerre transform matrices can be derived. \section{Appendix A - the Laguerre and associated Laguerre functions} The associated Laguerre polynomials \cite{Laguerre} are defined by $$L_n^{(\alpha)}(x)=\frac{1}{n!}\sum_{k=0}^n \frac{n!}{k!}\binom{n+\alpha}{n-k}(-x)^k.$$ Their exponential generating function is $$\frac{e^{\frac{xz}{1-z}}}{(1-z)^{\alpha+1}}$$ The Laguerre polynomials are given by $L_n(x)=L_n^{(0)}(x).$ The associated Laguerre polynomials are orthogonal on the interval $[0,\infty)$ for the weight $e^{-x}x^{\alpha}$. Using the notation developed above, we have \begin{eqnarray*}L_n^{(\alpha)}(x)&=&\frac{1}{n!}\sum_{k=0}^n \mathrm{Lag}^{(\alpha)}(n,k)(-x)^k\\ &=&\frac{1}{n!}\sum_{k=0}^n\sum_{i=0}^n {n \brack j}_{\alpha+1}{j \brace k}(-x)^k.\end{eqnarray*} In particular, $$L_n(x)=\frac{1}{n!}\sum_{k=0}^n\sum_{i=0}^n {n+1 \brack j+1}{j \brace k}(-x)^k.$$ \section{Acknowledgements} The author would like to thank an anonymous reviewer for their careful reading of this manuscript and their constructive remarks. \section{Appendix B - Lah and Laguerre transforms in the OEIS} \begin{center} \textbf{Table 1. \ Table of Lah transforms } \end{center} \begin{center} \begin{tabular}{|c|c|}\hline $a_n$&Lah transform $b_n$\\\hline $A000290$&$A103194$\\\hline $A104600$&$A121020$\\\hline $A000262$&$A025168$\\\hline $A000079$&$A052897$\\\hline $A000110$&$A084357$\\\hline $A000085$&$A049376$\\\hline $A000670$&$A084358$\\\hline \end{tabular}\end{center} \begin{center} \textbf{Table 2. \ Table of Laguerre transforms } \end{center} \begin{center} \begin{tabular}{|c|c|}\hline $a_n$&Laguerre transform $b_n$\\\hline $A000007$&$A000142$\\\hline $A000012$&$A002720$\\\hline $A000045$&$A105277$\\\hline $A000079$&$A087912$\\\hline $A001045$&$A129695$\\\hline \end{tabular}\end{center} \begin{thebibliography}{9} \bibitem{BarryJac} P. Barry, Triangle Geometry and Jacobsthal Numbers, \emph{Irish Math. Soc. Bulletin} \textbf{51} (2003), 45--57. \bibitem{PasTri} P. Barry, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Barry/barry202.html}{On a family of generalized Pascal triangles defined by exponential Riordan arrays}, \emph{J. Integer Sequences} {\bf 10}, Article 07.3.5. \bibitem{ProdMat} E. Deutsch, L. Ferrari, and S. Rinaldi, \href{http://arxiv.org/abs/math/0702638v1}{Production matrices and Riordan arrays}, arXiv:math.CO/0702638v1, 2007. \bibitem{DeutschShap} E. Deutsch, L. Shapiro, Exponential Riordan Arrays, Lecture Notes, Nankai University, 2004, available electronically at \href{http://www.combinatorics.net/ppt2004/Louis{\%}20W.{\%}20Shapiro/shapiro.pdf}{\tt http://www.combinatorics.net/ppt2004/Louis{\%}20W.{\%}20 Shapiro/shapiro.pdf}, 2007. \bibitem{GSWW} S. Getu, L. Shapiro, W. Woan, and L. Woodson, The Riordan group, {\it Discr. Appl. Math.} {\bf 34} (1991), 229--239. \bibitem{Concrete} R. L. Graham, D. E. Knuth, and O. Patashnik, \emph{Concrete Mathematics}, Addison-Wesley, 1994. \bibitem{LahMatrix} Tan Mingshu, Wang Tianming, Lah Matrix and its algebraic properties, {\it Ars Combinatoria} {\bf 70} (2004), 97--108. \bibitem{Riordan} J. Riordan, \emph{An Introduction to Combinatorial Analysis}, Dover, 2002. \bibitem{Riordan2} J. Riordan, \emph{Combinatorial Identities}, John Wiley \& Sons, 1968. \bibitem{SL1} N. J. A.~Sloane, \emph{The On-Line Encyclopedia of Integer Sequences}. Available at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}. \bibitem{SL2} N. J. A.~Sloane, The on-line encyclopedia of integer sequences, \emph{Notices of the AMS}, \textbf{50} (2003), 912--915. \bibitem{SpruId} R. Sprugnoli, \emph{Riordan Array Proofs of Identities in Gould's Book}. Published electronically at \href{http://www.dsi.unifi.it/~resp/GouldBK.pdf}{http://www.dsi.unifi.it/\char'176resp/GouldBK.pdf}, 2007. \bibitem{Spru} R. Sprugnoli, Riordan arrays and combinatorial sums, \emph{Discrete Math.},\textbf{132} (1994), 267--290. \bibitem{Bin} E. W. Weisstein, \href{http://mathworld.wolfram.com/BinomialTransform.html/}{http://mathworld.wolfram.com/BinomialTransform.html/}, 2007. \bibitem{Jac} E. W. Weisstein, \href{http://mathworld.wolfram.com/JacobsthalNumber.html/}{http://mathworld.wolfram.com/JacobsthalNumber.html/}, 2007. \bibitem{Laguerre} E. W. Weisstein, \href{http://mathworld.wolfram.com/LaguerrePolynomial.html/}{http://mathworld.wolfram.com/LaguerrePolynomial.html/}, 2007. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11B83; Secondary 05A19, 15A30, 33C45. \noindent \emph{Keywords:} Lah transform, Laguerre polynomials, Stirling numbers, exponential Riordan array. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000079}, \seqnum{A000085}, \seqnum{A000110}, \seqnum{A000142}, \seqnum{A000262}, \seqnum{A000290}, \seqnum{A000670}, \seqnum{A002720}, \seqnum{A007318}, \seqnum{A025168}, \seqnum{A049376}, \seqnum{A052897}, \seqnum{A084357}, \seqnum{A084358}, \seqnum{A087912}, \seqnum{A103194}, \seqnum{A104600}, \seqnum{A105277}, \seqnum{A121020}, and \seqnum{A129695}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 18 2007; revised version received May 1 2007. Published in {\it Journal of Integer Sequences}, May 2 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}