% A LaTeX file for a 14 page document \documentclass[12pt,reqno]{article} \usepackage[usenames]{color} %\usepackage{latexsym} \usepackage{amssymb} \usepackage{amscd} \usepackage{amsmath} \usepackage{amsthm} \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{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newtheorem{lemma}{Lemma}%[section] \newtheorem{theorem}[lemma]{Theorem} \newtheorem{corollary}[lemma]{Corollary} \newtheorem{conjecture}[lemma]{Conjecture} \newtheorem{identity}{Identity} \newtheorem{question}{Question} \newtheorem{definition}{Definition} \newtheorem{prop}{Proposition} \newtheorem{example}{Example} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newcommand{\ignore}[1]{} \def\s{\atopwithdelims[]} \def\S{\atopwithdelims\{\}} \def\zbar{\overline z} \def\rhobar{\overline \rho} \def\ree{\mbox{Re}} \def\imm{\mbox{Im}} \def\zz{\zbar z} \def\sgn{\mbox{sgn}} \def\R{({\bf R},*)} \def\barL{\overline L} \def\Sch{Schr\"oder\ } \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf On Some (Pseudo) Involutions in the Riordan Group} \vskip 1cm \large Naiomi T. Cameron \\ Department of Mathematics \\ Occidental College \\ Los Angeles, CA 90041\\ USA \\ \href{mailto:ncameron@oxy.edu}{\tt ncameron@oxy.edu} \\ \ \\ Asamoah Nkwanta \\ Department of Mathematics \\ Morgan State University\\ Baltimore, MD 21251 \\ USA \\ \href{mailto:nkwanta@jewel.morgan.edu}{\tt nkwanta@jewel.morgan.edu} \\ \end{center} \vskip .2 in \begin{abstract} In this paper, we address a question posed by L. Shapiro regarding algebraic and/or combinatorial characterizations of the elements of order 2 in the Riordan group. We present two classes of combinatorial matrices having {\it pseudo-order 2}. In one class, we find generalizations of Pascal's triangle and use some special cases to discover and prove interesting identities. In the other class, we find generalizations of Nkwanta's RNA triangle and show that they are pseudo-involutions. \end{abstract} \bigskip \section{Introduction} Briefly, let us describe the Riordan group \cite{Riordangroup, sprugnoli}, denoted $(\mathcal{R}, *)$. An element $R\in\mathcal{R}$ is an infinite lower triangular array whose $k$-th column has generating function $g(z)f^k(z)$, where $k=0, 1, 2, \ldots$ and $g(z)$, $f(z)$ are generating functions with $g(0)=1$, $f(0)=0$. We say $R$ is a {\em Riordan matrix}, write $R=(g(z),f(z))$ and note that $g(z)$ and $f(z)$ are elements of $\mathbb{C}[[z]]$. Multiplication in the Riordan group is matrix multiplication. Since a Riordan group element is determined by a pair of generating functions, it makes sense that the product of Riordan matrices can be described in terms of generating functions. In particular, $$(g(z),f(z))*(h(z),l(z))=(g(z)h(f(z)), l(f(z)))$$ It is also not hard to see that the identity element of the Riordan group is $(1,z)$ and that \begin{equation} (g(z),f(z))^{-1}:=\left({1 \over{g(\bar{f}(z))}},\bar{f}(z)\right) \label{inverse} \end{equation} where $\bar{f}$ is the compositional inverse of $f$. One can identify a Riordan matrix by its generating functions or by its {\em dot diagram}. A dot diagram is a symbolic representation of the recursions which define the matrix. Rogers and Merlini et. al. \cite{merlini, rogers} showed that every element of a Riordan matrix can be expressed as a linear combination of the elements in the preceding row. Suppose $r_{n,k}$ is the $(n,k)$ entry of $R\in\mathcal{R}$. We say that $[a_1, a_2, a_3,\ldots ; b_0, b_1, b_2, \ldots]$ is the dot diagram for $R$ if $r_{0,0}=g(0)=1$, $$r_{n,0}=a_1\cdot r_{n-1,0}+a_2 \cdot r_{n-1,1}+a_3\cdot r_{n-1,2}+\cdots \quad \text{for $n\geq 1$}$$ \centerline{and} $$r_{n,k}= b_0\cdot r_{n-1,k-1} + b_1\cdot r_{n-1,k}+ b_2\cdot r_{n-1,k+1}+\cdots \quad \text{for $n,k \geq 1$}.$$ See \cite{nkwanta1,nkwanta2,nkwanta3,sprugnoli, sprugnoli2} for more information regarding the connection between dot diagrams and defining generating functions for Riordan matrices. When studying any group, it is quite natural to want to classify the elements of finite order. As it turns out, in the case of the Riordan group, any element with integer entries having finite order must have order 1 or 2 \cite{Shapiro}. \ignore{(We invite the reader to verify this for $2\times 2$ matrices of the form $\left[\begin{matrix} 1&0 \\a & b \end{matrix}\right]$, and then generalize to infinite Riordan matrices.)} Our goal in this paper is to study the combinatorics of some involutions in the Riordan group. For combinatorial considerations in the Riordan group, it is common to focus on elements with nonnegative integer entries. Since involutions with integer entries necessarily contain negative entries, we direct our attention to {\em pseudo-involutions} \cite{cameron, Shapiro} in order to keep the focus on Riordan matrices with nonnegative entries. \begin{definition} An element $R$ of the Riordan group has {\bf pseudo-order 2} if $RM$ has order 2, where $M=(1,-z)$. \label{pseudo2} \end{definition} A Riordan group element with pseudo-order 2 will be known as a pseudo-involution. Pascal's triangle $P=\left({1 \over{1-z}},{z \over{1-z}}\right)$ \seqnum{A007318} is an example of a pseudo-involution, since right multiplying $P$ by $M=(1,-z)$ (i.e., the element with alternating 1's and -1's on the diagonal and zeros elsewhere) produces a signed version of Pascal's triangle $\left({1 \over{1-z}},{z \over{1-z}}\right)*(1,-z)=\left({1 \over{1-z}},{-z \over{1-z}}\right)$ which is an involution. We can see this using Riordan group multiplication \begin{eqnarray*} \left({1 \over{1-z}},{-z \over{1-z}}\right)*\left({1 \over{1-z}},{-z \over{1-z}}\right)&=&\left({1 \over{1-z}}\cdot {1 \over{1-{-z \over{1-z}}}},{-{-z \over{1-z}} \over{1-{-z \over{1-z}}}}\right) \\ &=& \left({1 \over{1-z}} \cdot {{1-z} \over{1-z+z}},{{-(-z)}\over{1-z+z}}\right) \\ &=& (1,z) \end{eqnarray*} or by looking at the entries of the matrices, where we see that \begin{eqnarray*} \left[\begin{matrix} 1&&&& &&\\ 1&-1&&& &&\\ 1&-2&1&&& &\\ 1&-3&3&-1&&& \\ 1&-4&6&-4&1&&\\ 1&-5&10&-10&5&-1&\\ &&&\dots&&& \end{matrix} \right] \left[\begin{matrix} 1&&&& &&\\ 1&-1&&& &&\\ 1&-2&1&&& &\\ 1&-3&3&-1&&& \\ 1&-4&6&-4&1&&\\ 1&-5&10&-10&5&-1&\\ &&&\dots&&& \end{matrix} \right]&=& \left[\begin{matrix} 1&&&& &&\\ 0&1&&& &&\\ 0&0&1&&& &\\ 0&0&0&1&&& \\ 0&0&0&0&1&&\\ 0&0&0&0&0&1&\\ &&&\dots&&& \end{matrix} \right]. \end{eqnarray*} Notice that we can express this product of matrices as the following identity: $$\sum_{k=0}^n{(-1)^{k+m}{n\choose k}{k\choose m}}=\delta_{n,m}$$ where $\delta_{n,m}=1$ if $n=m$ and $0$ otherwise. In 2001, Shapiro \cite{Shapiro} discussed several examples of nonnegative integer Riordan matrices that have pseudo-order 2, including Pascal's triangle $P=\left({1 \over{1-z}},{z \over{1-z}}\right)$, Nkwanta's RNA triangle $(g(z),zg(z))$, where $g(z)$ is defined as in (\ref{rna}), and Aigner's directed animal matrix $(1+zm, z(1+zm))$, where $m(z)$ is defined as in (\ref{motgf}). He also posed the following question: is it the case that any pseudo-order 2 element can be written as $RMR^{-1}M$, for some $R$? In Section 2, we will show that for at least one class of pseudo-order 2 elements, the answer is yes. One advantage of this knowledge is that one can verify that an element has pseudo-order 2 by simply verifying that it belongs to this certain class of matrices (without having to compose generating functions through Riordan multiplication). This verification can be done with the generating functions or with the dot diagram of $R$. Another advantage of this knowledge is that we can obtain a number of interesting identities with (almost) immediate combinatorial proofs. In Section 3, we present some results regarding a certain class of pseudo-order 2 elements for which Shapiro's question is not answered. Certain elements of this class of Riordan matrices can be interpreted combinatorially as lattice paths, and have connections to the Fibonacci numbers and RNA secondary structures from molecular biology. \subsection*{Characteristics of Pseudo-Involutions} Here, we make some basic observations about elements of pseudo-order 2. If $R=(g(z),f(z))$ has pseudo-order 2, then $$g(z)={1\over{g(-f(z))}} \quad\text{and}\quad f(-f(z))=-z.$$ This statement follows directly from (\ref{inverse}) and Definition \ref{pseudo2}. While pseudo-order 2 elements do not form a subgroup, there are some pseudo-order 2 elements that can be easily recognized by the subgroup to which they belong. Many of the pseudo-involutions presented in this paper, including Pascal's triangle $P=\left({1 \over{1-z}},{z \over{1-z}}\right)$, are elements of the {\em Bell subgroup} which is the set of all Riordan elements of the form $\left(g(z),zg(z)\right)$ \cite{Shapiro2}. However, there are pseudo-involutions which are not in the Bell subgroup, such as the matrix $D_1$ described in Section 3. The {\em associated subgroup} is the set of all Riordan group elements of the form $(1, f(z))$. This set forms a subgroup since $(1, f(z))*(1, g(z))=(1, g(f(z)))$ and $(1,f(z))^{-1}=(1, \bar{f}(z))$ are elements of the set. In the case of an associated subgroup member $(1,f(z))$, we have a test to determine whether it is a pseudo-involution. We leave it to the reader to check that when $f=\bar{f}$, it follows that $(1,f(z))$ is an involution in the Riordan group. \begin{prop} An element $R=(1,f(z))$ of the associated subgroup has pseudo-order 2 if $f=\bar{f}$ and $f$ is odd. \end{prop} \begin{proof} This follows from the fact that $(RM)^2=(1,f(z))*(1,-z)*(1,f(z))*(1,-z)=(1,-f(z))*(1,-f(z))=(1,-f(-f(z)))$. If $f$ is odd then $-f(-f(z))=-f(f(-z))$ and if $f$ is its own compositional inverse, then $-f(f(-z))=-(-z)=z$. Hence, $(RM)^2$ is in fact the identity and $R$ has pseudo-order 2. %If $(1,f(z))$ has pseudo-order 2, then $ $(1,f(z))*(1,-z)*(1,f(z))*(1,-z)=(1,-f(z))*(1,-f(z))=(1,-f(-f(z)))$ \end{proof} Note that, as a consequence of this proposition, $M=(1,-z)$ has pseudo-order 2. Since $M^2$ is the identity, any element of the form $RMR^{-1}M$ will have pseudo-order 2 (because $(RMR^{-1}M)M(RMR^{-1}M)M=RMR^{-1}(MM)RMR^{-1}(MM)$ is also the identity). In the next section, we explore the converse of this statement for a specific class of Riordan matrices. The following is an equivalent characterization of pseudo-order 2 elements. In fact, it is merely the equivalent definition with left multiplication by $M$ \cite{nkwanta3}. \begin{prop} A Riordan group element $R=\left( g\left( z\right) ,f\left( z\right) \right) $ has pseudo-order $2$ if and only if the element $R_{-z}=\left( g\left( -z\right) ,f\left( -z\right) \right) $ has order $2$. \end{prop} \begin{proof} $\left( \Longrightarrow \right) $ Suppose $R$ has order pseudo-order $2$. Then for $M=\left( 1,-z\right) $ we know by the definition of pseudo-order $2$% \begin{equation*} RM=\left( g\left( z\right) ,f\left( z\right) \right) \left( 1,-z\right) =\left( g\left( z\right) ,-f\left( z\right) \right) \end{equation*}% has order $2$ in the Riordan group. Therefore,% \begin{eqnarray*} \left( RM\right) ^{2} &=&\left( g\left( z\right) ,-f\left( z\right) \right) ^{2} \\ &=&\left( g\left( z\right) g\left( -f\left( z\right) \right) ,-f\left( -f\left( z\right) \right) \right) \\ &=&\left( 1,z\right) . \end{eqnarray*}% Equating components in the last two expressions $g\left( z\right) g\left( -f\left( z\right) \right) =1$ and $-f\left( -f\left( z\right) \right) =z,$ and replacing $z$ with $-z$ gives $g\left( -z\right) g\left( -f\left( -z\right) \right) =1$ and $f\left( -f\left( -z\right) \right) =z.$ By these last two equations \begin{eqnarray*} \left( 1,z\right) &=&\left( g\left( -z\right) g\left( -f\left( -z\right) \right) ,f\left( -f\left( -z\right) \right) \right) \\ &=&\left( g\left( -z\right) ,f\left( -z\right) \right) \left( g\left( -z\right) ,f\left( -z\right) \right) \\ &=&R_{-z}R_{-z}. \end{eqnarray*}% Hence $R_{-z}$ has order $2$. It is trivial to prove the opposite direction. Assume $R_{-z}$ has order $2,$ then reverse the above arguments. This leads to $R$ has pseudo-order $2$. This completes the proof of the proposition. \end{proof} \section{A Class of Generalized Pascal's Triangles} In this section, we refer to some common combinatorial sequences. We note here that $C(z)$ is the generating function for the famous Catalan numbers \seqnum{A000108}, \begin{equation} C(z)=\sum_{n\geq 0}{{1\over{n+1}}{2n \choose n}}={{1-\sqrt{1-4z}}\over{2z}}, \label{catgf} \end{equation} while $m(z)$ is the generating function for the Motzkin numbers \seqnum{A001006}, \begin{equation} m(z)={{1-z-\sqrt{1-2z-3z^2}}\over{2z^2}}, \label{motgf} \end{equation} and $S(z)$ is the generating function for the little \Sch numbers \seqnum{A001003}, \begin{equation} S(z)={{1-3z-\sqrt{1-6z+z^2}}\over{4z^2}} \label{schgf}. \end{equation} Consider Pascal's triangle as the Riordan matrix $P=\left({1 \over{1-z}},{z \over{1-z}}\right)$ with dot diagram $[1;1,1]$. We saw in the preceding section that $P$ is an element of pseudo-order 2 and $P=P_{-1}MP_{-1}M$. In fact, it is the case that any generalized Pascal array of the form $P_b=\left({1 \over{1-bz}},{z \over{1-bz}}\right),$ where $b\geq 0,$ is a pseudo-involution. A natural question arises. Can we write any pseudo-involution as $RMR^{-1}M$ for some $R$? If so, how do we classify the $R$? The next theorem provides an answer to these questions for a select class of Riordan matrices. One of the consequences of the theorem is that we can always factor these Pascal-like triangles of the form $\left({1 \over{1-bz}},{z \over{1-bz}}\right)$. In the examples following the theorem, we use this fact to provide some interesting decompositions of sequences associated with the triangles and a combinatorial interpretation of those decompositions. The proof of the following theorem relies on a result known as the Triple Factorization theorem, due to Peart and Woodson \cite{PW}, which says that if $R$ has dot diagram $[b+\epsilon,\lambda+\delta;1,b,\lambda]$, then $R=P_bC_\lambda F_{\epsilon,\delta}$, where $P_b=\left({1\over{1-bz}},{z\over{1-bz}} \right)$, $C_\lambda=\left(C(\lambda z^2),zC(\lambda z^2)\right)$, and $F_{\epsilon,\delta}=\left( {1\over{1-\epsilon z-\delta z^2}}, z \right).$ \begin{theorem} Let $b\in\mathbb{Z}$ and $\delta, \epsilon, \lambda\in\mathbb{R}$. The Riordan matrix \begin{equation} R^*=\left ( { { 1+ { {\epsilon z}\over{1- bz} } { C\left({{\lambda z^2}\over{(1- bz)^2}}\right) } - { {\delta z^2}\over{(1- bz)^2} } { C^2\left({\lambda z^2}\over{(1- bz)^2}\right) } } \over { 1- { {\epsilon z}\over{1- bz} } { C\left({{\lambda z^2}\over{(1- bz)^2}}\right) } - { {\delta z^2}\over{(1- bz)^2} } { C^2\left({\lambda z^2}\over{(1- bz)^2}\right) } } } \cdot {1\over{1-2bz}} , {z\over{1-2bz}} \right) \label{R*} \end{equation} \ignore{ \begin{equation} R^*=\left ( { {1+{ \epsilon/ b}\ m(bz)-{\delta/ b^2}\ m^2(bz)} \over {1-{\epsilon/ b}\ m(bz)-{\delta/ b^2}\ m^2(bz)} } \cdot {1\over{1-2bz}} , {z\over{1-2bz}} \right) \label{R*} \end{equation} } has pseudo-order 2. Furthermore, $R^*=RMR^{-1}M$, where $R=P_bC_\lambda F_{\epsilon,\delta}$ has dot diagram $[b+\epsilon,\lambda+\delta;1,b,\lambda]$. \ignore{ $R=P_bC_\lambda F_{\epsilon,\delta}$, $P_b=\left({1\over{1-bz}},{z\over{1-bz}} \right)$, $C_\lambda=\left(C(\lambda z^2),zC(\lambda z^2)\right)$, and $F_{\epsilon,\delta}=\left( {1\over{1-\epsilon z-\delta z^2}}, z \right)$. } %is the Riordan matrix with dot diagram $[b+\epsilon, b^2+\delta;1,b,b^2]$. \label{thetaclass} \end{theorem} \begin{proof} It suffices to verify that $R^*=RMR^{-1}M$. By the Triple Factorization Theorem \cite{PW}, if $R$ has dot diagram $[b+\epsilon,\lambda+\delta;1,b,\lambda]$, then $R=P_bC_\lambda F_{\epsilon,\delta}$. First, let us note that $$C_\lambda F_{\epsilon,\delta}=\left( { {C(\lambda z^2)}\over{1-\epsilon z C(\lambda z^2) - \delta z^2 C^2(\lambda z^2) } } , zC(\lambda z^2) \right)$$ and by (\ref{inverse}), $$(C_\lambda F_{\epsilon,\delta})^{-1}=F_{\epsilon,\delta}^{-1}C_\lambda^{-1}=\left( { {1- {{\epsilon z}\over{1+\lambda z^2}} { C\left({{\lambda z^2}\over{(1+\lambda z^2)^2}}\right) } - { {\delta z^2}\over{(1+\lambda z^2)^2} } { C^2\left({\lambda z^2}\over{(1+\lambda z^2)^2}\right) } } \over {C\left({{\lambda z^2}\over{(1+\lambda z^2)^2}}\right)} } , {z\over{1+\lambda z^2}} , \right)$$ So, \begin{eqnarray*} RMR^{-1}M&=&(P_bC_\lambda F_{\epsilon,\delta})M(F_{\epsilon,\delta}^{-1}C_\lambda^{-1}P_b^{-1})M\\ &=&P_b(C_\lambda F_{\epsilon,\delta}MF_{\epsilon,\delta}^{-1}C_\lambda^{-1})P_b^{-1} M\\ &=&P_b \left( { {C(\lambda z^2)}\over{1-\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} }, {-zC(\lambda z^2)} \right) \\ &&\left( { {1- {{\epsilon z}\over{1+\lambda z^2}} { C\left({{\lambda z^2}\over{(1+\lambda z^2)^2}}\right) } - { {\delta z^2}\over{(1+\lambda z^2)^2} } { C^2\left({\lambda z^2}\over{(1+\lambda z^2)^2}\right) } }\over { C\left({\lambda z^2}\over{(1+ \lambda z)^2}\right) } } , {z\over{1+\lambda z^2}} \right) P_b^{-1} M\\ \end{eqnarray*} %\eject \begin{eqnarray*} &=&P_b \left( { {C(\lambda z^2)}\over{1-\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} } \cdot { {1+\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} \over {C(\lambda z^2)} } , {-z} \right) P_b^{-1} M\\ &=& P_b\left( { {1+\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} \over {1-\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} } , -z \right) P_b^{-1} M\\ &=&\left({1\over{1-bz}},{z\over{1-bz}} \right) \left( { {1+\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} \over {1-\epsilon z C(\lambda z^2)-\delta z^2 C^2(\lambda z^2)} } , -z \right) \left({1\over{1+bz}},{-z\over{1+bz}} \right) \\ &=&\left( {1\over{1-bz}} \cdot {{ 1+ { {\epsilon z}\over{1- bz} } { C\left({{\lambda z^2}\over{(1- bz)^2}}\right) } - { {\delta z^2}\over{(1- bz)^2} } { C^2\left({\lambda z^2}\over{(1- bz)^2}\right) } } \over { 1- { {\epsilon z}\over{1- bz} } { C\left({{\lambda z^2}\over{(1- bz)^2}}\right) } - { {\delta z^2}\over{(1- bz)^2} } { C^2\left({\lambda z^2}\over{(1- bz)^2}\right) } } } , {-z\over{1-bz}} \right) \left({1\over{1+bz}},{-z\over{1+bz}} \right) \\ &=& \left ( { { 1+ { {\epsilon z}\over{1- bz} } { C\left({{\lambda z^2}\over{(1- bz)^2}}\right) } - { {\delta z^2}\over{(1- bz)^2} } { C^2\left({\lambda z^2}\over{(1- bz)^2}\right) } } \over { 1- { {\epsilon z}\over{1- bz} } { C\left({{\lambda z^2}\over{(1- bz)^2}}\right) } - { {\delta z^2}\over{(1- bz)^2} } { C^2\left({\lambda z^2}\over{(1- bz)^2}\right) } } } \cdot {1\over{1-2bz}} , {z\over{1-2bz}} \right) \end{eqnarray*} The fourth equality follows from the fact that $1+\lambda z^2 C^2(\lambda z^2)=C(\lambda z^2)$. \end{proof} In the case when $\epsilon=\delta=0$, the matrix in (\ref{R*}) represents a ``Pascal-like" Riordan matrix. Theorem \ref{thetaclass} asserts that these Pascal-like matrices can be factored into two Riordan matrices, $R$ and $MR^{-1}M$, where $R$ can be interpreted combinatorially. Notice that in this case the dot diagram of $R$ is $[b, \lambda; 1, b, \lambda]$. This means that if $r_{n,k}$ is the $(n,k)$ entry of $R$, then $$r_{n,0}=b\cdot r_{n-1,0}+\lambda \cdot r_{n-1,1} \quad \text{for $n\geq 0$}$$ and $$r_{n,k}= r_{n-1,k-1} + b\cdot r_{n-1,k}+\lambda \cdot r_{n-1,k+1} \quad \text{for $n,k \geq 1$}$$ We can interpret $R$ in terms of paths. Note that we will use the term {\em restricted} for paths which never go below the $x$-axis. It follows from the recursions above that $r_{n,k}$ as the number of restricted paths from $(0,0)$ to $(n,k)$ using $b$ types of $(1,0)$ level steps, $\lambda$ types of $(1,-1)$ down steps, and one type of $(1,1)$ up step. As we will see in the following examples, this observation will expose a nice vehicle for obtaining and proving combinatorial identities. \medskip \noindent {\bf Example 1:} Let $$R^*=\left({1\over{1-4z}},{z\over{1-4z}}\right)$$ Notice that $R^*$ has the form (\ref{R*}) with $\epsilon=\delta=0$, $b=2$ and $\lambda=1$. Hence, by Theorem \ref{thetaclass}, $R^*$ has pseudo-order 2 and $R^*=RMR^{-1}M$, where $R$ has dot diagram $[ 2,1;1,2,1]$. Solving the recurrence relation given by the dot diagram of $R$, we find that $R=(C^2(z),zC^2(z))$ \seqnum{A039598}, where $C(z)$ is the Catalan generating function (\ref{catgf}). Using (\ref{inverse}) and the fact that $C(z)=1+zC^2(z)$, we can determine that $R^{-1}=\left({1\over{(1+z)^2}}, {z\over{(1+z)^2}}\right)$. That is, $R^*=R\cdot(MR^{-1}M)$ \seqnum{A038231} is given by \begin{eqnarray} \left[\begin{matrix} 1&&&& &\\ 4&1&&& &\\ 16&8&1&&& \\ 64&48&12&1&& \\ 256&256&96&16&1&\\ &&\dots&&& \end{matrix} \right]&=&\left(C^2(z),zC^2(z)\right) \cdot \left((1,-z)\cdot \left({1\over{(1+z)^2}}, {z\over{(1+z)^2}}\right) \cdot (1,-z)\right) \cr %&=& \left( { {C^2(z)}\over{\left(1-zC^2(z)\right)^2} }, { {zC^2(z)}\over{\left(1-zC^2(z)\right)^2} } \right) \\ &=&\left(C^2(z),zC^2(z)\right) \cdot \left({1\over{(1-z)^2}}, {z\over{(1-z)^2}}\right) \cr \ignore{ &=&\left[\begin{matrix} 1&&&& &\\ 2&-1&&& &\\ 5&-4&1&&& \\ 14&-14&6&-1&& \\ 42&-48&27&-8&1&\\ &&\dots&&& \end{matrix} \right] \left[\begin{matrix} 1&&&& &\\ -2&-1&&& &\\ 3&4&1&&& \\ -4&-10&-6&-1&& \\ 5&20&21&8&1&\\ &&\dots&&& \end{matrix} \right] \cr } &=&\left[\begin{matrix} 1&&&& &\\ 2&1&&& &\\ 5&4&1&&& \\ 14&14&6&1&& \\ 42&48&27&8&1&\\ &&\dots&&& \end{matrix} \right] \left[\begin{matrix} 1&&&& &\\ 2&1&&& &\\ 3&4&1&&& \\ 4&10&6&1&& \\ 5&20&21&8&1&\\ &&\dots&&& \end{matrix} \right], \label{4^n} \end{eqnarray} where $MR^{-1}M$ is \seqnum{A053122}. Notice that the entries of $R$ represent restricted {\em bicolored Motzkin paths} \cite{ballsonthelawn}. A bicolored Motzkin path is a path from $(0,0)$ to $(n,k)$ using $U(1,1)$, $D(1,-1)$, $L(1,0)$, or $\barL(1,0)$. Let $\mathcal{M}_{n,k}$ denote the set of all bicolored Motzkin paths of length $n$ and terminal height $k$. (Terminal height is the $y$-coordinate of the final step in the path.) The $(n,k)$-th entry of $R$ is $|\mathcal{M}_{n,k}|$. Using the Lagrange Inversion formula (see p. 38, \cite{Stanley2}), we find that for $n,k\geq 0$, \begin{eqnarray*} |\mathcal{M}_{n,k}|&=&[z^{n+1}]z^{k+1}C^{2(k+1)} \\ &=&\frac{k+1}{n+1}[z^{n-k}](1+z)^{2(n+1)} \\ & =&{ {k+1} \over{n+1} } {{2n+2}\choose{n-k}} \end{eqnarray*} We can see clearly from (\ref{4^n}) that the (dot) product of the first column of $\left({1\over{(1-z)^2}}, {z\over{(1-z)^2}}\right)$ with the $n$-th row of $R$ produces the quantity $4^n$. We can write this more formally as the following identity found in \cite{callan}. \begin{identity} \begin{equation} 4^n=\sum_{k=0}^n{ {{(k+1)^2}\over{n+1}} {{2n+2}\choose{n-k}} } \end{equation} \label{4^n_identity} \end{identity} Now, we present another combinatorial proof of this identity. \begin{proof} To prove the identity, we will combinatorially extend the set of restricted bicolored Motzkin paths of length $n$ to the set of {\em all} paths of length $n$ using $U$, $D$, $L$, $\barL$ (and no other restrictions). Clearly, the total number of the latter paths is $4^n$, giving us the left hand side of (\ref{4^n_identity}). We will present a set of maps $\phi_i$, $i=0,1,2,\ldots k$ so that the right hand side of (\ref{4^n_identity}) is the cardinality of the set $$\bigcup_{k=0}^n\ \bigcup_{Q\in\mathcal{M}_{n,k}}\{\phi_i(Q): 0\leq i\leq k\}.$$ Suppose $Q\in\mathcal{M}_{n,k}$. The {\em last ascent to height $i$} of $Q$ is the last up step (in order from left to right) which starts at height $i-1$ and ends at height $i$. Notice that if we change the last ascent to height $i$ of $Q$ to a down step, we obtain a new path with terminal height $k-2$. Let $\phi_i(Q)$ denote the path obtained by changing each of the last ascents to heights $1, 2, \ldots, i$ to down steps. See Figures \ref{phi map 1} and \ref{phi map 2} for an illustration of this map. \begin{figure}[hbt] \begin{center} \setlength{\unitlength}{.5cm} \begin{picture}(21,4) \put(0,0){\line(1,1){1}} \put(1,1){\line(1,-1){1}} \put(2,0){\thicklines\line(1,0){1}}%* \put(3,0){\line(1,1){1}} \put(3.5,-0.5){$\uparrow$} \put(4,1){\line(1,0){1}} \put(5,1){\line(1,1){1}} \put(6,2){\line(1,-1){1}} \put(7,1){\line(1,1){1}} \put(7.5,0.5){$\uparrow$} \put(8,2){\line(1,1){1}} \put(9,3){\thicklines\line(1,0){1}}%* \put(10,3){\line(1,-1){1}} \put(11,2){\line(1,1){1}} \put(12,3){\line(1,1){1}} \put(13,4){\line(1,-1){1}} \put(14,3){\line(1,-1){1}} \put(15,2){\line(1,1){1}} \put(15.5,1.5){$\uparrow$} \put(16,3){\line(1,1){1}} \put(17,4){\line(1,-1){1}} \put(18,3){\line(1,1){1}} \put(19,4){\line(1,-1){1}} \put(20,3){\line(1,0){1}} \put(0,0){\circle*{.2}} \put(1,1){\circle*{.2}} \put(2,0){\circle*{.2}} \put(3,0){\circle*{.2}} \put(4,1){\circle*{.2}} \put(5,1){\circle*{.2}} \put(6,2){\circle*{.2}} \put(7,1){\circle*{.2}} \put(8,2){\circle*{.2}} \put(9,3){\circle*{.2}} \put(10,3){\circle*{.2}} \put(11,2){\circle*{.2}} \put(12,3){\circle*{.2}} \put(13,4){\circle*{.2}} \put(14,3){\circle*{.2}} \put(15,2){\circle*{.2}} \put(16,3){\circle*{.2}} \put(17,4){\circle*{.2}} \put(18,3){\circle*{.2}} \put(19,4){\circle*{.2}} \put(20,3){\circle*{.2}} \put(21,3){\circle*{.2}} \end{picture} \end{center} \caption{$Q=UD\bar{L}{\bf U}LUD{\bf U}U\bar{L}DUUDD{\bf U}UDUDL$, a restricted bicolored Motzkin path of length $n=21$ and terminal height $k=3$. Last ascents are indicated with a bold $\bf U$ and marked above with an up arrow.} \label{phi map 1} \end{figure} \begin{figure}[hbt] \begin{center} \setlength{\unitlength}{.5cm} \begin{picture}(21,4) \put(0,0){\line(1,1){1}} \put(1,1){\line(1,-1){1}} \put(2,0){\thicklines \line(1,0){1}}%* \put(3,0){\line(1,-1){1}} \put(3.5,-0.25){$\downarrow$} \put(4,-1){\line(1,0){1}} \put(5,-1){\line(1,1){1}} \put(6,0){\line(1,-1){1}} \put(7,-1){\line(1,-1){1}} \put(7.5,-1.25){$\downarrow$} \put(8,-2){\line(1,1){1}} \put(9,-1){\thicklines\line(1,0){1}}%* \put(10,-1){\line(1,-1){1}} \put(11,-2){\line(1,1){1}} \put(12,-1){\line(1,1){1}} \put(13,0){\line(1,-1){1}} \put(14,-1){\line(1,-1){1}} \put(15,-2){\line(1,1){1}} \put(16,-1){\line(1,1){1}} \put(17,0){\line(1,-1){1}} \put(18,-1){\line(1,1){1}} \put(19,0){\line(1,-1){1}} \put(20,-1){\line(1,0){1}} \put(0,0){\circle*{.2}} \put(1,1){\circle*{.2}} \put(2,0){\circle*{.2}} \put(3,0){\circle*{.2}} \put(4,-1){\circle*{.2}} \put(5,-1){\circle*{.2}} \put(6,0){\circle*{.2}} \put(7,-1){\circle*{.2}} \put(8,-2){\circle*{.2}} \put(9,-1){\circle*{.2}} \put(10,-1){\circle*{.2}} \put(11,-2){\circle*{.2}} \put(12,-1){\circle*{.2}} \put(13,0){\circle*{.2}} \put(14,-1){\circle*{.2}} \put(15,-2){\circle*{.2}} \put(16,-1){\circle*{.2}} \put(17,0){\circle*{.2}} \put(18,-1){\circle*{.2}} \put(19,0){\circle*{.2}} \put(20,-1){\circle*{.2}} \put(21,-1){\circle*{.2}} \end{picture} \end{center} \vspace{.5in} \caption{$\phi_2(Q)=UD\bar{L}{\bf D}LUD{\bf D}U\bar{L}DUUDD{U}UDUDL$, the unrestricted bicolored Motzkin path of length $n=21$ and terminal height $j=k-2i=3-2(2)=1$ which is obtained by changing the last ascents to heights 1 and 2 to D's. Premier descents are indicated with a bold $\bf D$ and marked above with a down arrow.} \label{phi map 2} \end{figure} Since $Q$ has terminal height $k$, it contains exactly $k$ last ascents and therefore $\phi_i$ is well-defined as long as $i\leq k$. By replacing the first $i$ last ascents in $Q$ with $D$'s, we ensure that, at some point, the number of $D$'s exceeds the number of preceding $U$'s, so that $\phi_i(Q)$ necessarily goes below the $x$-axis (called unrestricted), eventually ending at height $k-2i$. Notice also that $\phi_i$ is one-to-one. If $Q$ and $Q'$ are restricted paths ending at the same height, then they differ at some step which is not a last ascent, and $\phi_i$ will preserve that difference so that $\phi_i(Q)\neq\phi_i(Q')$. On the other hand, if $Q$ and $Q'$ end at different heights, then $\phi_i(Q)$ and $\phi_i(Q')$ will also end at different heights, so that $\phi_i(Q)\neq\phi_i(Q')$. Because $\phi_i$ is one-to-one, we may conclude that for every bicolored Motzkin path, the collection $\{Q, \phi_1(Q),...,\phi_k(Q)\}$ contains $k+1$ distinct unrestricted paths and for $Q\neq Q'$, the sets $\{Q, \phi_1(Q),...,\phi_k(Q)\}$ and $\{Q', \phi_1(Q'),...,\phi_k(Q')\}$ are disjoint. Hence, the set of all such collections is certainly contained in the set of {\em all} paths of length $n$ using $U$, $D$, $L$, $\barL$. To show that the set $\{Q, \phi_1(Q),...,\phi_k(Q): Q\in\mathcal{M}_{n,k}, 0\leq k\leq n\}$ is indeed equal to the set of {\em all} paths of length $n$ using $U$, $D$, $L$, $\barL$, we need only show that it is possible to take an unrestricted bicolored Motzkin path $P$ and recover its unique preimage $Q$ under $\phi_i$ for some $i$. Let $P$ be an unrestricted bicolored Motzkin path with terminal height $j$. Since $P$ goes below the $x$-axis, it has a set of {\em premier descents below the $x$-axis}, i.e. the first (from left to right) down steps from height $m$ to $m-1$ for $m=0, -1, \ldots$ Suppose $P$ has $i>0$ premier descents below the $x$-axis. Then changing each of the $i$ premier descents to up steps will create a new path $Q$ which stays above the $x$-axis and ends at height $k=j+2i$. What was a premier descent to height $m-1$ below the $x$-axis in $P$ becomes not just an up step located above the $x$-axis, but in fact, it becomes an up step for which the previous number of U's is equal to $-m$ plus the previous number of D's. This is the same as a last ascent to height $-m+1$. It follows then that $\phi_i(Q)=P$. \end{proof} Now there was certainly nothing special about multiplication by the first column of $\left({1\over{(1-z)^2}}, {z\over{(1-z)^2}}\right)$. It is not hard to show that the $m$-th column of $\left({1\over{(1-z)^2}}, {z\over{(1-z)^2}}\right)$ is the sequence ${n\choose m}4^{n-m}$. So one can generalize Identity \ref{4^n_identity} by taking the product of the $m$-th column of $\left({1\over{(1-z)^2}}, {z\over{(1-z)^2}}\right)$ with $R$. Hence, we obtain the following. \begin{identity} $${n \choose m}4^{n-m}=\sum_{k=0}^n{ {{k+1}\over{n+1}} {{k+m+1}\choose{k-m}} {{2n+2}\choose{n-k}} }$$ \label{4^n_generalidentity} \end{identity} \bigskip While the accuracy of Identity \ref{4^n_generalidentity} is guaranteed by Theorem \ref{thetaclass}, the authors would like to see a purely combinatorial proof, perhaps by extending the proof of Identity \ref{4^n_identity}. \bigskip \noindent {\bf Example 2:} Let $$S^*=\left({1\over{1-6z}},{z\over{1-6z}}\right)$$ Notice that the Riordan matrix $S^*$ (\seqnum{A038255}) has the form (\ref{R*}) with $\epsilon=\delta=0$, $b=3$ and $\lambda=2$. Hence, by Theorem \ref{thetaclass}, $S^*$ has pseudo-order 2 and $S^*=SMS^{-1}M$, where $S$ has dot diagram $[ 3,2;1,3,2]$. Solving the recurrence relation given by the dot diagram of $S$, we find that $S=(S(z),zS(z))$ \seqnum{A110440}, where $S(z)$ is the little \Sch generating function (\ref{schgf}). Moreover, $S^{-1}=\left({1\over{1+3z+2z^2}}, {z\over{1+3z+2z^2}}\right)$ and we note that ${1\over{1-3z+2z^2}}$ is the generating function for the Mersenne number sequence $2^n-1$, $n\geq 1$, \seqnum{A000225}. More expressly, we have \begin{eqnarray} S^*&=& \left[\begin{matrix} 1&&&& &\\ 6&1&&& &\\ 36&12&1&&& \\ 216&108&18&1&& \\ 1296&864&216&24&1&\\ &&\dots&&& \end{matrix} \right] \\ &=&\left(S(z),zS(z)\right) \cdot (1,-z) \cdot \left({1\over{1+3z+2z^2}}, {z\over{1+3z+2z^2}}\right) \cdot (1,-z) \cr %&=& \left( { {C^2(z)}\over{\left(1-zC^2(z)\right)^2} }, { {zC^2(z)}\over{\left(1-zC^2(z)\right)^2} } \right) \\ &=&\left(S(z),zS(z)\right) \cdot \left({1\over{1-3z+2z^2}}, {z\over{1-3z+2z^2}}\right) \cr &=&\left[\begin{matrix} 1&&&& &\\ 3&1&&& &\\ 11&6&1&&& \\ 45&31&9&1&& \\ 197&156&60&12&1&\\ &&\dots&&& \end{matrix} \right] \left[\begin{matrix} 1&&&& &\\ 3&1&&& &\\ 7&6&1&&& \\ 15&23&9&1&& \\ 31&72&48&12&1&\\ &&\dots&&& \end{matrix} \right] \label{6^n} \end{eqnarray} The $(n,k)$ entry of $S$, call it $s_{n,k}$, is the number of restricted paths from $(0,0)$ to $(n-1,k-1)$ using $U$, $L$, $\bar{L}$, $\bar{\bar{L}}$, $D$ and $\bar{D}$ (that is, 3 types of level steps and 2 types of down steps). Let us refer to these paths as \Sch paths. {\em Remark.} An interesting observation about the Mersenne array $MS^{-1}M$ \seqnum{A110441} is that the diagonal slices are the even indexed (or numbered) Fibonacci numbers \seqnum{A001906} $\left\{1,3,8,21,\ldots \right\} $. Left multiplying the matrix $S$ by the first column of $MS^{-1}M$, we obtain the following statement. \begin{equation} 6^{n-1}=\sum_{k=1}^n{(2^{k}-1)s_{n,k}} \label{6^n-1} \end{equation} To prove this statement, we will use the same method from Example 1 to extend the set of \Sch paths of length $n$ to the set of unrestricted paths of length $n$ having the same step set. Clearly the cardinality of the latter is $6^n$. Let $Q$ be a \Sch path of length $n$ and terminal height $k$. As before, for all $i$ between $0$ and $k$, we will change the first $i$ last ascents to $D$'s. Now, since we have 2 types of $D$'s in this case, we will say that $\phi_{i,j}(Q)$ is the path obtained by changing $j$ of the first $i$ last ascents to $D$'s and the remaining $i-j$ to $\bar{D}$'s. There are $i \choose j$ ways to do this. Hence, the set of distinct paths generated by $Q$, that is, $\{ \phi_{i,j}(Q): 0\leq j \leq i \leq k \}$, has cardinality \begin{eqnarray*} \sum_{i=0}^k{ \sum_{j=0}^i{i\choose j} }&= &\sum_{i=0}^k{2^i} ={ {1-2^{k+1}}\over{1-2}}=2^{k+1}-1 \end{eqnarray*} Although we know that statement (\ref{6^n-1}) is true, it would be nice to be able to express it explicitly. Fortunately, this can be achieved by first producing a closed formula for $s_{n,k}$. Applying the Lagrange Inversion Formula, we have: \begin{eqnarray} s_{n,k}&=&[z^n]z^kS^k(z) \\ &=& {k\over n}[z^{n-k}]\left(1+3z+2z^2\right)^n \\ &=&{k\over n} \sum_{j=0}^{n-k}{ {n\choose j} {{n-j}\choose{n-k-2j}} 2^j 3^{n-k-2j} } \label{schform} \end{eqnarray} Combining equations (\ref{6^n-1}) and (\ref{schform}), we obtain the following explicit form of the identity: \begin{identity} \begin{equation} 6^n={1\over{n+1}} \sum_{k=0}^{n}{ \sum_{j=0}^{n-k}{ (k+1) {{n+1}\choose j} {{n+1-j}\choose{n-k-2j}} 3^{n-k-2j} \left(2^{k+j+1}-2^j\right) } } \end{equation} \end{identity} We close this section by remarking that an application of Theorem \ref{thetaclass} with $\epsilon=\delta=0$, any nonzero value for $b$ and the same method used in the above examples will produce an identity for $(2b)^n$. \section{A Class of Generalized RNA Triangles} In this section we define another class of pseudo order $2$ elements of the Riordan group. Consider, for $n\geq 1$, the matrix $% D_{n}=\left( g\left( z\right) \left( \frac{1-z}{1-zg\left( z\right) }\right) ^{n},zg\left( z\right) \right),$ where % \begin{equation} g\left( z\right) =\frac{\left( 1-z+z^{2}\right) -\sqrt{% 1-2z-z^{2}-2z^{3}+z^{4}}}{2z^{2}}. \label{rna} \end{equation} Note that $D_{n}=A^{-n}D_{0}A^{n}$, where $D_{0}=\left( g\left( z\right) ,zg\left( z\right) \right) ,$ $A^{n}=\left( \frac{1}{\left( 1-z\right) ^{n}},z\right) $, and $A^{-n}=\left( \left( 1-z\right) ^{n},z\right) $. The matrix $D_{n}$ is of combinatorial interest and the first few cases are explicitly given in Figure \ref{Darrays}. \begin{figure} \begin{center} $D_{0}=\left[ \begin{array}{llllll} 1 & & & & & \\ 1 & 1 & & & & \\ 1 & 2 & 1 & & & \\ 2 & 3 & 3 & 1 & & \\ 4 & 6 & 6 & 4 & 1 & \\ 8 & 13 & 13 & 10 & 5 & 1 \\ & & \cdots & & & \end{array} \right] \qquad D_{1}=\left[ \begin{array}{llllll} 1 & & & & & \\ 1 & 1 & & & & \\ 2 & 2 & 1 & & & \\ 5 & 4 & 3 & 1 & & \\ 12 & 10 & 7 & 4 & 1 & \\ 29 & 25 & 18 & 11 & 5 & 1 \\ & & \cdots & & & \end{array} \right]$ \bigskip $D_{2}=\left[ \begin{array}{llllll} 1 & & & & & \\ 1 & 1 & & & & \\ 3 & 2 & 1 & & & \\ 8 & 5 & 3 & 1 & & \\ 21 & 14 & 8 & 4 & 1 & \\ 55 & 38 & 23 & 12 & 5 & 1 \\ & & \cdots & & & \end{array} \right] $ \end{center} \label{Darrays} \caption{RNA arrays} \end{figure} The matrix $D_{0}=\left( C_{0}\right) ^{-1}PC_{0}$ where $P$ is the Pascal matrix $P=\left( \frac{1}{1-z},\frac{z}{1-z}\right) $, $C_{0}$ is the aerated Catalan matrix defined by% \begin{equation*} C_{0}=\left( C\left( z^{2}\right) ,zC\left( z^{2}\right) \right) =\left( \frac{1-\sqrt{1-4z^{2}}}{2z^{2}},\frac{1-\sqrt{1-4z^{2}}}{2z}\right) , \end{equation*}% and $\left( C_{0}\right) ^{-1}=\left( \frac{1}{1+z^{2}},\frac{z}{1+z^{2}}% \right) .$ $D_{0}$ \seqnum{A097724} has a lattice path interpretation and arises in connection with counting RNA secondary structures from molecular biology. The entries in the leftmost column of $D_{0}$ are the RNA numbers $\left\{ 1,1,1,2,4,8,17,\ldots \right\} $, \seqnum{A004148}, which have a lattice path interpretation \cite{nkwanta2}. Consider counting\textbf{\ }paths which start at the origin $\left( 0,0\right) $ and take unit steps, $N\left( 0,1\right)$, $S\left( 0,-1\right)$, and $E\left( 1,0\right) $ with the following restrictions: 1) no paths pass below the $x$-axis and 2) no S step immediately follows an N step, i.e there are no NS steps. We call this class of paths NES paths. A typical example is denoted by the path NNESSE. If $l_{n,k}$ denotes the number of NES paths of length $n$ and terminal height $k$, then the $(n,k)$ entry of $D_0$ is $l_{n,k}$. Note that the paths that have terminal height $k=0$ are counted by the RNA numbers. There is a one-to-one correspondence between these particular paths and RNA secondary structures of length $n$ \cite{nkwanta2}. The matrix $D_{1}$ \seqnum{A110438} also has a lattice path interpretation. Consider counting\textbf{\ }paths which start at the origin $\left(0,0\right) $ and take unit steps, $N\left( 0,1\right)$, $S\left( 0,-1\right) $, $E\left( 1,0\right)$, and $W\left( -1,0\right)$ with the following restrictions: 1) no paths pass below the $x$-axis, 2) no paths begin with a W step, 3) all W steps remain on the $x$-$axis$, and 4) no S step immediately follows an N step, i.e there are no NS steps. We call this class of paths NESW paths. A typical example is denoted by the path EWEEWNESWN. If $d_{ n,k} $ denotes the number of NESW paths of length $n$ and terminal height $k$, then the $(n,k)$ entry of $D_1$ is $d_{ n,k}.$ Computing the first few paths gives the first few entries of $D_{1}$. By convention $d_{0,0}=1$ and it is obvious $d_{n,n}=1$ since the only way to be at height $n$ after $n$ steps is to always go north. By Riordan group methods, it is easy to show the formation rule of $D_{1}$ is given by the following recurrence relations $d_{0,0}=1,$ $d_{1,0}=1$, and for $n\geq 1$% \begin{equation} d_{n+1,0}=2d_{n,0}+\sum_{j\geq 1}d_{n-j,j}, \label{eq1} \end{equation} for the leftmost column, and for $n>j,$ $n\geq 2,$ and $k\geq 1$ we have% \begin{equation} d_{n+1,k}=d_{n,k-1}+d_{n,k}+\sum_{j\geq 1}d_{n-j,k+j}, \label{eq2} \end{equation}% for the other columns. Note that equation (\ref{eq2}) is valid for entries in $D_0, D_1, D_2, \ldots$, not including the leftmost columns. We want to find the total number of \ NESW paths of length $n$ and connect $% D_{1}$ to the paths by showing the paths satisfy $\left( \text{\ref{eq1}}% \right) $ and $\left( \text{\ref{eq2}}\right) $. To do this we consider the following combinatorial arguments. Since $d_{n,k}$ denotes the number of NESW paths of length $n$ with terminal height $k,$ we consider the following cases to form a $d_{n+1,k}$ path. First, if the last step is N, then there are $d_{n,k-1}$ possibilities to move up to height $k$. If the last step is E, then there are $d_{n,k}$ possibilities to remain at height $k $. If the last step is S, then there are $d_{n-j,k+j}$ possibilities to move down to height $k$ by considering ES$^{j}$ steps. Summing over the cases gives $\left( \text{\ref{eq2}}\right) $. Note for $k>0$ there are no paths with last step W since the W steps remain on the $x$-$axis$. For the leftmost column, if the last step is E , then there are $d_{n,0}$ possibilities. Also if the last step is W, there are $d_{n,0}$ possibilities. If the last step is S then there are $d_{n-j,j}$ possibilities considering ES$^{j}$ steps. Combining these cases gives $% \left( \text{\ref{eq1}}\right) $. There are no paths with last step N for height $k=0$. The boundary condition $d_{n,k}=0$ $\left( k>n\right) $ is trivial since there are no paths of this form. This proves the formation rule and gives $D_{1}$ a NESW lattice path interpretation. To find the total number of NESW paths of length $n$, we multiply by $\left( 1,1,\ldots \right)^{T}$ which has $1/\left( 1-z\right) $ as its generating function. Then by Riordan matrix multiplication and simplifying, the generating function for the total number of all NESW paths is% \begin{eqnarray*} D_{1}\ast \left( 1/\left( 1-z\right) \right) &=&\left( \left( \frac{\sqrt{% 1+z+z^{2}}}{\sqrt{1-3z+z^{2}}}-1\right) \frac{1-z}{2z},zg\left( z\right) \right) \ast \left( 1/\left( 1-z\right) \right) \\ &=&\left( \left( 1-z\right) /\left( 1-3z+z^{2}\right) \right) \\ &=&1+2z+5z^{2}+13z^{3}+34z^{4}+\cdots =\sum_{n\geq 0}F_{2n+1}z^{n}. \end{eqnarray*}% Thus the NESW paths are counted by the odd indexed Fibonacci numbers $\left\{ F_{2n+1}\right\} =\left\{ 1,2,5,13,34,\ldots \right\}$ \seqnum{A001519}. Notice also that the matrix $D_2$ \seqnum{A110439} is related to the Fibonacci numbers. The generating function of the leftmost column of $D_{2}$ gives the even indexed Fibonacci numbers \seqnum{A001906} (plus one), $\left\{1,1,3,8,21,\ldots \right\}$. We now show $D_{0}$ is pseudo order $2$ and generalize that $D_{n}$ also has pseudo-order $2.$ \begin{lemma} The matrix $D_{0}$ has pseudo order $2.$ \end{lemma} \begin{proof} Let $D_{\left( 0,-z\right) }=\left( \left( C_{0}\right)^{-1} P C_{0}\right) _{-z}=\left( g\left( -z\right) ,-zg\left( -z\right) \right) .$ Now using the definitions of Riordan matrix multiplication and pseudo order $% 2$, and the fact $P$ has pseudo-order $2$ we obtain the following:% \begin{equation*} \begin{array}{lll} D_{\left( 0,-z\right) } D_{\left( 0,-z\right) } & = & \left( \left( C_{0}\right) ^{-1} P C_{0}\right) _{-z} \left( \left( C_{0}\right)^{-1}\ P\ C_{0}\right) _{-z} \\ & = & \left( \left( C_{0}\right) ^{-1}\ P\right) _{-z}\ \left( C_{0}\ \left( C_{0}\right) ^{-1}\right) _{-z}\ \left( P\ C_{0}\right) _{-z} \\ & = & \left( \left( C_{0}\right) ^{-1}\right) _{-z}\ \left( P\ P\right) _{-z}\ \left( C_{0}\right) _{-z} \\ & = & \left( \left( C_{0}\right) ^{-1}\ \left( C_{0}\right) \right) _{-z} \\ & = & \left( 1,z\right) .% \end{array}% \end{equation*}% Hence, $D_{\left( 0,-z\right) }$ has order 2 which proves the lemma. \end{proof} \begin{theorem} The matrix $D_{n}$ is pseudo order $2.$ \end{theorem} \begin{proof} Let $D_{\left( n,-z\right) }=\left( A^{-n}\ D_{0}\ A^{n}\right) _{-z}=\left( g\left( -z\right) \left( \frac{1+z}{1+zg\left( -z\right) }% \right) ^{n},-zg\left( -z\right) \right) .$ Now using the definitions of Riordan matrix multiplication and pseudo order $2$, and the fact $% D_{0}$ has pseudo-order $2$ we obtain the following:% \begin{equation*} \begin{array}{lll} D_{\left( n,-z\right) }\ D_{\left( n,-z\right) } & = & \left( A^{-n}\ D_{0}\ A^{n}\right) _{-z}\ \left( A^{-n}\ D_{0}\ A^{n}\right) _{-z} \\ & = & \left( A^{-n}\ D_{0}\right) _{-z}\ \left( A^{n}\ A^{-n}\right) _{-z}\ \left( D_{0}\ A^{n}\right) _{-z} \\ & = & \left( A^{-n}\right) _{-z}\ \left( D_{0}\ D_{0}\right) _{-z}\ \left( A^{n}\right) _{-z} \\ & = & \left( A^{-n}\ \ A^{n}\right) _{-z} \\ & = & \left( 1,z\right) .% \end{array}% \end{equation*}% Hence, $D_{\left( n,-z\right) }$ has order 2 which proves the theorem. \end{proof} While it is true that $D_{n}$ has pseudo-order 2 for all $n \in \mathbb{Z}$ and, moreover, certain cases of $D_n$ have a nice lattice path interpretations, these matrices are distinct from the matrices discussed in Section 2 in that it is not known whether $D_n$ has the form $RMR^{-1}M$ for some $R\in\mathcal{R}$. Nonetheless, $D_n$ is in good company, as there are certainly other interesting combinatorial triangles, such as Aigner's directed animal matrix $(1+zm, z(1+zm))$, where $m(z)$ is defined as in (\ref{motgf}), for which this question is yet unanswered. We close this section by noting that a definitive conclusion for $D_n$ is desirable. If, for example, it were true that $D_0=RMR^{-1}M$ for some $R$, then there would exist some combinatorial decomposition of the RNA numbers \seqnum{A004148}, and similarly for $D_2$, it would be interesting to see what decomposition of the odd Fibonacci numbers were possible by factoring $D_2$ into $R$ and $MR^{-1}M$. If it is not possible to write $D_n$ as $RMR^{-1}M$, one would expect to be able to combinatorially explain why this is the case and reasonably connect $D_n$ with other combinatorial matrices with the same property. Finally, we note that this paper is only concerned with Riordan matrices generated by ordinary generating functions. Considering pseudo-involutions of Riordan matrices generated by exponential generating functions and their factorizations as $RMR^{-1}M$ as well as finding connections to the umbral calculus \cite{barnabei, roman} would be of interest as well. \section{Acknowledgements} The authors wish to thank the referee for valuable comments that improved the presentation of the paper. \begin{thebibliography}{AA} \bibitem{barnabei} M. Barnabei, A. Brini, and G. Nicoletti, Recursive matrices and umbral calculus, {\em J. Algebra} {\bf 75} (1982) 546-573. \bibitem{callan} D. Callan, A combinatorial interpretation of a Catalan numbers identity, {\em Math. Mag.} {\bf 72} (1999), 295--298. \bibitem{cameron} N. Cameron, Random walks, trees and extensions of Riordan group techniques, Ph. D. diss., Howard University, Washington, DC, 2002. \bibitem{ballsonthelawn} C. Mallows, L. Shapiro, Balls on the lawn, {\em J. Integer Seq.} {\bf 2} (1999), Article 99.1.5. \bibitem{merlini} D. Merlini, D. Rogers, R. Sprugnoli, M. C. Verri, On some alternative characterizations of Riordan arrays, {\em Can. J. Math.} {\bf 49} (1997), 301--320. \bibitem{nkwanta1} A. Nkwanta, A Riordan matrix approach to unifying a selected class of combinatorial arrays, Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, {\em Congr. Numer.} {\bf 160} (2003), 33--45. \bibitem{nkwanta2} A. Nkwanta, Lattice paths and RNA secondary structures, {\em DIMACS Ser. Discrete Math. Theoret. Comput. Sci.} {\bf 34} (1997), 137--147. \bibitem{nkwanta3} A. Nkwanta, Lattice paths, generating functions, and the Riordan group, Ph. D. diss., Howard University, Washington, DC, 1997. \bibitem{PW} P. Peart, L. Woodson, Triple factorization of some Riordan matrices, {\em Fibonacci Quart.} {\bf 31} (1993), 121--128. \bibitem{rogers} D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, {\em Discrete Math.} {\bf 22} (1978), 301--310. \bibitem{roman} S. Roman, {\em The Umbral Calculus}, Academic Press, New York, 1984. \bibitem{Shapiro} L. Shapiro, Some open questions about random walks, involutions, limiting distributions, and generating functions, {\it Adv. in Appl. Math.} {\bf 27} (2001), 585--596. \bibitem{Shapiro2} L. Shapiro, Bijections and the Riordan group, {\em Theo. Comp. Sci.} {\bf 307} (2003), 403--413. \bibitem{Riordangroup} L. Shapiro, S. Getu, W. Woan, L. Woodson, The Riordan group, {\em Discrete Appl. Math.} {\bf 34} (1991), 229--239. \bibitem{sprugnoli} R. Sprugnoli, Riordan arrays and combinatorial sums, {\em Discrete Math.} {\bf 132} (1994), 267--290. \bibitem{sprugnoli2} R. Sprugnoli, Riordan arrays and the Abel-Gould identity, {\em Discrete Math.} {\bf 142} (1995), 213--233. \bibitem{Stanley2} R. Stanley, {\em Enumerative Combinatorics, Vol. 2}, Cambridge University Press, Cambridge, 1999. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19. \noindent \emph{Keywords:} Riordan arrays, Catalan numbers, lattice paths, combinatorial identity. \bigskip \hrule \bigskip \noindent Concerned with sequences \seqnum{A000108}, %catalan \seqnum{A000225}, %mersenne \seqnum{A001003}, %schroder \seqnum{A001006}, %motzkin \seqnum{A001519}, %odd fibonacci \seqnum{A001906}, %even fibonacci \seqnum{A004148}, %rna numbers \seqnum{A007318}, %pascal \seqnum{A038231}, %4^n triangle \seqnum{A038255}, %6^n triangle \seqnum{A039598}, %catalan triangle \seqnum{A053122}, %mersenne triangle \seqnum{A097724}, %rna triangle \seqnum{A110438}, %d1 \seqnum{A110439}, %d2 \seqnum{A110440}, and %little schroder triangle \seqnum{A110441}. %mersenne array \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 17 2005; revised version received August 18 2005. Published in {\it Journal of Integer Sequences}, August 23 2005. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .