\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\usepackage{bm}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\Sn}{{\mathbb S}}
\newcommand{\Mn}{{\mathbb M}}
\newcommand{\Sk}{{\mathcal S}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\Z}{{\mathbb Z}}

\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}

\begin{center}
\vskip 1cm{\LARGE\bf  Counting Prefixes of Skew Dyck Paths\\
\vskip 1cm}
\large Jean-Luc Baril\\
LIB, Universit{\'e} de Bourgogne\\
B.P. 47 870 \\
21078 Dijon Cedex\\
France    \\
\href{mailto:barjl@u-bourgogne.fr}{\tt barjl@u-bourgogne.fr}\\
\ \\
Jos\'e L. Ram\'{\i}rez and Lina M. Simbaqueba\\
Departamento de Matem\'aticas\\
 Universidad Nacional de Colombia\\
Bogot\'a \\
Colombia\\
\href{mailto:jlramirezr@unal.edu.co}{\tt jlramirezr@unal.edu.co}\\
\href{mailto:lmsimbaquebam@unal.edu.co}{\tt lmsimbaquebam@unal.edu.co}
\end{center}

\vskip .2 in

\begin{abstract}
We  present  enumerative  results  on  prefixes of skew Dyck paths  by
giving  recursive relations, Riordan arrays, and generating functions,
as well as closed formulas to count the total number of these paths
with respect to the length, the height of its endpoint and the number
of left steps.
\end{abstract}

\section{Introduction}

A \emph{skew Dyck path} is a lattice path in the first quadrant of the $xy$-plane that starts at the origin, ends on the $x$-axis, and made of up-steps $U=(1,1)$, down-steps $D=(1,-1)$, and left steps $L=(-1,-1)$ so that up and left steps  do not overlap. We let $|P|$ denote the \emph{length} of the path $P$, i.e., the number of its steps, which is an even non-negative integer. Let $\epsilon$ denote the skew Dyck path of length zero. For example, Figure \ref{figEx1} shows the skew Dyck paths of length $6$, or equivalently of semilength 3. The concept  of skew Dyck path was introduced by Deutsch, Munarini, and Rinaldi \cite{Deutsch}. Some additional results can be found in \cite{Deutsch2, Lu}, where the authors present enumerative results according to different parameters and some bijections with other combinatorial objects, as hex trees, tree-like polyhexes, and 3-Motzkin paths.

We let  $\Sn$ denote the set of all skew Dyck paths,  and let $\Sn_{n}$ denote the set of all skew Dyck paths of semilength $n$. Let $s_n$ be the cardinality of $\Sn_{n}$.
Any nonempty skew Dyck path  $P$ can be uniquely decomposed  either $P=UT_1DT_2$ or $P=UT_3L$, where $T_1,T_2,T_3\in\Sn$  and $T_3\neq \epsilon$.  Figure \ref{deco1} shows  a graphical representation of this decomposition. 
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.8]{deco1.eps}
\caption{Decomposition of a nonempty skew Dyck path.}
\label{deco1}
\end{center}
\end{figure}

This decomposition induces the functional equation $S(x)=1+xS(x)^2+x(S(x)-1)$ for the generating function $S(x):=\sum_{P\in \Sn}x^{|P|/2}=\sum_{n\geq 0} s_nx^n$, and thus  we have 
\begin{align}\label{genS}
S(x)=\frac{1-x-\sqrt{1-6x+5x^2}}{2x}.
\end{align}

The sequence $s_n$  appears in the OEIS as \seqnum{A002212} \cite{OEIS},
and its first few values  
are
$$1, \quad 1, \quad  3, \quad 10, \quad 36, \quad 137, \quad 543, \quad 2219, \quad 9285 , \quad 39587.$$

From the above functional equation, we obtain $S(x)-1=x(S(x)^2+S(x)-1)$, and applying directly the Lagrange inversion Theorem, (see \cite{Gess,Merl} for instance), we deduce the  explicit formulas:
\begin{align*}
s_n&=\sum_{k=1}^n\binom{n-1}{k-1}c_k,\\
s_n&=\sum_{k=1}^n\binom{n-1}{k-1}(-1)^{k-1}5^{n-k}c_k,\\
s_n&=\frac{1}{n}\sum_{k=0}^{\lfloor(n-1)/2\rfloor}\binom{n}{k}\binom{n-k}{k+1}3^{n-2k-1},
\end{align*} 
where $c_n=\frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number, which is the general term of the sequence \seqnum{A000108} in~\cite{OEIS}.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.75]{FigEx1.eps}
\caption{Skew Dyck paths of semilength 3.}
\label{figEx1}
\end{center}
\end{figure}


A prefix of a skew Dyck path is called  \emph{skew meander}. In a way, skew meanders appear as the counterpart of ballot paths (prefixes of Dyck paths \cite{KP}) for skew Dyck paths. The \emph{height} $\alpha(P)$ of a  skew meander $P$ is the $y$-coordinate of the endpoint of the last step of $P$. For example, Figure \ref{figEx1b} shows a  skew meander of length $27$ and height $3$. Let $\Mn$ be the set of all skew meanders, and let $s(n,k)$ denote  the number of skew meanders of length $n$ and height $k$. 

In this paper, we present enumerative results on skew meanders by giving  recursive relations, Riordan arrays,  generating functions, as well as closed formulas to count the total number of skew meanders of a given length with respect to the height and the number of left steps.


\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.75]{Ex3P.eps}
\caption{Skew meander of  length $27$ and height $3$.}
\label{figEx1b}
\end{center}
\end{figure}


\section{Skew meanders via Riordan arrays}
The goal of this section is to study  the distribution of the number of skew meanders of a fixed height.  Let $\Sk=[s(n,k)]_{n, k\geq 0}$ denote the matrix where $s(n,k)$ is the number of skew meanders of length $n$ and height $k$. 
The first few rows of the matrix $\Sk$ are
\newcommand\scalemath[2]{\scalebox{#1}{\mbox{\ensuremath{\displaystyle #2}}}}
$$\Sk=\left(
\scalemath{0.6}{
\begin{array}{cccccccccc}
 1 &  &  &  &  &  & &  &  &  \\
 0 & 1 &  &  &  &  &  & &  &   \\
 1 & 0 & 1 &  &  &  &  &  & &   \\
 0 & 2 & 0 & 1 &  &  &  &  &  &  \\
 3 & 0 & 3 & 0 & 1 &  &  &  &  &   \\
 0 & \bm{\textcolor{red}{6}} & 0 & 4 & 0 & 1 &  &  &  &   \\
 10 & 0 & 10 & 0 & 5 & 0 & 1 &  &  &  \\
 0 & 21 & 0 & 15 & 0 & 6 & 0 & 1 &  &  \\
 36 & 0 & 37 & 0 & 21 & 0 & 7 & 0 & 1 &  \\
 0 & 79 & 0 & 59 & 0 & 28 & 0 & 8 & 0 & 1 \\
  & \vdots &  &  & \vdots &  & &  & \vdots &  \\
\end{array}
}
\right).$$
The sequence $(s(n,1))_{n\geq1}$ corresponds to the sequence \seqnum{A033321} that counts skew Dyck paths of semilength $n$ with a down-step $D$. Figure \ref{figEx3} shows  the six skew meanders  of length $5$ and height $1$ corresponding to the  bold red entry in the above matrix.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.8]{Prefixes.eps}
\caption{The six skew meanders of length 5 and height 1.}
\label{figEx3}
\end{center}
\end{figure}



We will prove that the matrix $\Sk$ is a Riordan array. So, let us give some background on Riordan arrays \cite{Riordan}. 
We will say that an infinite column vector $(a_0,a_1,\dots)^T$ has generating function $f(x)$ if $f(x)=\sum_{n\ge0} a_nx^n$, and we  index rows and columns starting at $0$. A {\em Riordan array} is an infinite lower triangular matrix whose $k$-th column has generating function
$g(x)f(x)^k$ for all $k \ge 0$, for some formal power series  $g(x)$ and $f(x)$, with $g(0) \neq 0$, $f(0)=0$, and $f'(0)\neq 0$. Such a Riordan array is denoted by  $(g(x),f(x))$.
If we multiply this matrix by a column vector  $(c_0, c_1, \dots)^T$ having generating function $h(x)$, then the resulting column
vector has generating function $g(x)h(f(x))$. This property is known as the fundamental theorem of Riordan arrays, or as the summation property.

The product of two Riordan arrays $(g(x),f(x))$ and $(h(x),l(x))$ is defined by
\begin{equation}\label{eq:product} (g(x),f(x))*(h(x),l(x))=\left(g(x)h(f(x)), l(f(x))\right). \end{equation}
Under the operation $``*"$, the set of all Riordan arrays is a group  \cite{Riordan}. The identity element is $I=(1,x)$, and the inverse of $(g(x),f(x))$ is
 \begin{equation}\label{invRiordan}
 (g(x), f(x))^{-1}=\left(1/\left(g\circ \overline{f}\right)(x), \overline{f}(x)\right),
\end{equation}
  where $\overline{f}(x)$ denotes the compositional inverse of $f(x)$.
  
\bigskip

Recall  that for a skew meander $P$,  $\alpha(P)$ is the height  of $P$, $|P|$ is the length of $P$. For a non-negative integer $k$, we introduce the generating function
\begin{equation*}\label{GFRXY}
H_k(x):=\sum_{P\in \Mn, \, \alpha(P)=k} x^{|P|}= \sum_{n\geq 0}s(n,k)x^n.
\end{equation*}
It is clear that  $H_0(x)=S(x^2)$.

\begin{theorem}\label{thm1}
The matrix $\Sk = [s(n, k)]_{n, k\geq 0}$ is a Riordan array  given by
\begin{align}\label{TeoRior1}
\Sk=\left(S(x^2), \frac{x}{1-x^2S(x^2)}\right),
\end{align}
where $S(x)=(1-x-\sqrt{1-6x+5x^2})/2x.$
\end{theorem}
\begin{proof}
Obviously, skew meanders of height zero are skew Dyck paths, and a skew meander $P$ of height $k\geq 1$ can be decomposed either $P=UP_1$ or $U Q D P_2$, where $P_1$ (resp. $P_2$) is a skew meander of height $k-1$ (resp. $k$), and $Q$ is a skew Dyck path in $\Sn$. Figure~\ref{fig2} illustrates the two cases.
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.7]{Fig2.eps}
\caption{Decomposition of a  skew meander of height at least one .}
\label{fig2}
\end{center}
\end{figure}
Using the symbolic method (see~\cite{flajolet}), we obtain the functional equation
$$H_k(x)=xH_{k-1}(x) + x^2S(x^2)H_k(x), \quad k\geq 1,$$
anchored with $H_0(x)=S(x^2)$. Then $H_k(x)=xH_{k-1}(x)/(1-x^2S(x^2)),$ and by iterating this  expression we deduce for $k\geq 0$, 
$$H_k(x)=\left(\frac{x}{1-x^2S(x^2)}\right)^kS(x^2).$$
From the definition of Riordan array we obtain the desired result.
\end{proof}



\begin{corollary}\label{Riordan:corollary}  
The generating function for the total number of  skew meanders of length $n$ is given by
\begin{align*}
\sum_{n\geq 0}\sum_{k=0}^ns(n,k)x^n=
\frac{-2 + x + 4 x^2 + x^3 +(2 + x) \sqrt{1 - 6 x^2 + 5 x^4}}{2 x (1 - 2 x - x^2)}.
\end{align*}
\end{corollary}
\begin{proof}
Multiplying the right-hand side of the equality \eqref{TeoRior1} by the vector $(1,1,1,\dots)^T$, which has generating function $1/(1-x)$, and using  the summation property, the resulting vector has generating function
$$\left(S(x^2), \frac{x}{1-x^2S(x^2)}\right)  \frac{1}{1-x}=\frac{S(x^2)}{1-\frac{x}{1-x^2S(x^2)}}=\frac{S(x^2)}{1-x-x^2S(x^2)}.$$
After simplification we obtain the desired result.
\end{proof}
The total number of skew meanders of length $n$, for $0\leq n \leq 10$ are 
$$1, \quad 1, \quad 2, \quad 3, \quad 7, \quad 11, \quad 26, \quad 43, \quad 102, \quad 175, \quad 416.$$



In Theorem \ref{exp1}, we will give  a combinatorial formula for $s(n,k)$ involving binomial coefficients and the entries of the Catalan triangle introduced by Shapiro  \cite{Shapiro} in the context of  lattice paths on $\Z\times \Z$. It is defined by the matrix $[B(n,k)]_{n, k\geq 1}=[\frac{k}{n}\binom{2n}{n-k}]_{n, k\geq 1}$.  For convenience, we extend this triangle by adding a row and column of indice zero by setting  $B(0,0)=1$, $B(0,k)=B(k,0)=0$ if $k>0$. So, the first few rows are
$$\mathcal{B}:=[B(n,k)]_{n, k\geq 0}=\left(
\begin{array}{cccccccc}
 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\
 0 & 5 & 4 & 1 & 0 & 0 & 0 & 0 \\
 0 & 14 & 14 & 6 & 1 & 0 & 0 & 0 \\
 0 & 42 & 48 & 27 & 8 & 1 & 0 & 0 \\
 0 & 132 & 165 & 110 & 44 & 10 & 1 &
   0 \\
 0 & 429 & 572 & 429 & 208 & 65 & 12
   & 1 \\
     \vdots &  &  & \vdots &  &  & \vdots &  
\end{array}
\right),$$
which correspond to  array \seqnum{A039598} in \cite{OEIS}. From the generating function of the columns of $\B$,  see \cite{WoanShapiroRog}, we prove that the matrix $[B(n,k)]_{n, k\geq 0}$ is the  Riordan array  
$\B=\left(1, xC(x)^2\right),$ 
 where $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function of the Catalan numbers $c_n=\frac{1}{n+1}{2n \choose n}$. 
It is well known that $C(x)$ satisfies the functional equation $C(x)=xC(x)^2+1$. So, if we set $B(x):=C(x)-1$, then $B(x)=x(B(x)+1)^2=x\Phi(B(x)),$ where $\Phi(z)=(z+1)^2$.  Moreover,
$$[x^n]B(x)^k=[x^n](C(x)-1)^k=[x^n](xC(x)^2)^k=B(n,k).$$
From the Lagrange inversion theorem (see for instance \cite{Merl}), we 
have 
$$B(n,k)=[x^n](B(x))^k=\frac{k}{n}[z^{n-k}](z+1)^{2n}=\frac{k}{n}\binom{2n}{n-k},$$ which proves that $\mathcal{B}$ is the Riordan array $(1,xC(x)^2)$.

 
 
\begin{theorem}\label{exp1}
For $n, k\geq 0$, if $n+k\equiv \modd{0} {2}$, then
$$s(n,k)=\sum_{j=0}^{\frac{n-k}{2}}\sum_{i=0}^{j+1}\sum_{\ell=0}^{\frac{n-k}{2}-j}\binom{j+k-1}{j}\binom{j+1}{i}\binom{\frac{n-k}{2}-j-1}{\ell-1}B(\ell,i),$$
 and $s(n,k)=0$ otherwise. 
\end{theorem}
\begin{proof}
Let $U(x):=S(x)-1$, where $S(x)$ is the generating function defined in \eqref{genS}. Note that $U(x)=x(U(x)^2+3U(x)+1)=x\Phi(U(x)),$ where $\Phi(z)=z^2+3z+1$. From the  Lagrange inversion theorem, we deduce
\begin{align*}
u_n^{(k)}:&=[x^n]U(x)^k=\frac{k}{n}[z^{n-k}]\Phi(z)^n=\frac{k}{n}[z^{n-k}](z^2+3z+1)^n\\
&=\frac{k}{n}[z^{n-k}]((z+1)^2+z)^n=\frac{k}{n}[z^{n-k}]\sum_{i=0}^n\binom ni (z+1)^{2i}z^{n-i} 
\end{align*}
\begin{align*}
&=\sum_{i=0}^n\binom ni \frac{k}{n}[z^{i-k}] (z+1)^{2i}=\sum_{i=1}^n\binom{n-1}{i-1} \frac{k}{i}[z^{i-k}] (z+1)^{2i}\\
&=\sum_{i=0}^n\binom{n-1}{i-1}B(i,k).
\end{align*}
If we set $g_n^{(k)}:=[x^n]S(x^2)^k=(U(x^2)+1)^k$, then it is cleat that 
$$g_n^{(k)}=\begin{cases}
\sum_{i=0}^k\binom ki u_{n/2}^{(i)}, & \text{if} \ n  \equiv \modd{0} {2};\\
0, & \text{otherwise}.
\end{cases}$$
Now, by definition of a Riordan array, we have 
\begin{align*}
s(n,k)&=[x^n]S(x^2)\frac{x^k}{(1-x^2S(x^2))^k}\\
&=[x^{n-k}]\sum_{j\geq 0}\binom{j+k-1}{j}S(x^2)^{j+1}x^{2j}\\
&=\sum_{j\geq 0}\binom{j+k-1}{j} [x^{n-k-2j}]S(x^2)^{j+1}\\
&=\sum_{j=0}^{\lfloor\frac{n-k}{2}\rfloor}\binom{j+k-1}{j}g_{n-k-2j}^{(j+1)},
\end{align*}
which provides the desired result. 
\end{proof}
By considering different expansions of the expression $(z^2+3z+1)^n$, and using similar proofs as for Theorem~\ref{exp1}, we obtain the following two corollaries.
\begin{corollary}
For $n, k\geq 0$, if $n+k\equiv \modd{0} {2}$, then
$$s(n,k)=\sum_{j=0}^{\frac{n-k}{2}}\sum_{i=0}^{\frac{n-k}{2}-j}\binom{j+k-1}{j}\binom{\frac{n-k}{2}-j-1}{i-1}\binom{j+2i+1}{i}\frac{j+1}{j+2i+1},$$
and $s(n,k)=0$ otherwise. 
\end{corollary}

\begin{corollary}
For $n, k\geq 0$, if  $n+k\equiv \modd{0} {2}$, then
$$s(n,k)=\sum_{j=0}^{\frac{n-k}{2}}\sum_{i=0}^{j+1}\binom{j+k-1}{j}\binom{j+1}{i}t_{\frac{n-k}{2}-j}^{(i)},$$
where $t_0^{(0)}=1, t_n^{(k)}=0 \mbox{ if } n=0, k\neq 0, \mbox{ and } t_n^{(k)}=\sum_{i=0}^{\lfloor \frac{n-k}{2}\rfloor}\frac{k}{n}\binom ni \binom{n-i}{k+i}3^{n-k-2i} \mbox{ otherwise.}$
Moreover,  $s(n,k)=0$ if $n+k\equiv \modd{1} {2}$. 
\end{corollary}


\section{A recurrence relation for $s(n,k)$}

In this part, we will provide a recurrence relation for $s(n,k)$. For this, we consider the matrix $\Sk_2:=[s(2n-k,k)]_{n,k \geq 0}=[\widetilde{s}(n,k)]_{n,k \geq 0}$,  which is a compression of $\Sk$ obtained by deleting some zeros. The first few rows of the matrix $\Sk_2$  are
$$\Sk_2=[\widetilde{s}(n,k)]_{n,k \geq 0}=\left(
\begin{array}{cccccccc}
 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\
 10 & 6 & 3 & 1 & 0 & 0 & 0 & 0 \\
 36 & 21 & 10 & 4 & 1 & 0 & 0 & 0 \\
 137 & 79 & 37 & 15 & 5 & 1 & 0 & 0 \\
 543 & 311 & 145 & 59 & 21 & 6 & 1 & 0 \\
 2219 & 1265 & 589 & 241 & 88 & 28 & 7 & 1 \\
   & \vdots &  &  & \vdots &  &  & \vdots \\
\end{array}
\right).$$

From  the summation property for Riordan arrays (see Theorem~\ref{thm1}), we obtain directly the following corollary.
\begin{corollary}\label{coro:D2} The matrix $\Sk_2$ is a Riordan array given by
$\Sk_2=\left(S(x), \frac{x}{1-xS(x)}\right),$ and the generating function $S_2(x)$ for the row sums of the matrix $\Sk_2$ is given by
\begin{align*}
S_2(x)&:=\sum_{n\geq 0}s_2(n)x^n=\sum_{n\geq 0}\sum_{k=0}^n\widetilde{s}(n,k)x^n=
\frac{1- 2x - \sqrt{1 - 6 x + 5 x^2}}{x}\\
&=1 + 2 x + 6 x^2 + 20 x^3 + 72 x^4 + 274 x^5 + 1086 x^6 + 4438 x^7 + 18570 x^8 + \cdots
\end{align*}
\end{corollary}
The generating function $S_2(x)$ satisfies $S_2(x)=2S(x)-1$, and  $s_2(n)$  corresponds to the general term of the sequence \seqnum{A122737} which has a combinatorial interpretation using special polyominoes (bi-wall directed polygons).  

A plane figure is a \emph{polyomino} if it is a union of finitely many cells and the interior  is connected. A polyomino $P$ is a \emph{polygon} if $P$ has a connected border, and this border is a closed self-avoiding walk. We say that  $P$ is \emph{directed} if each of its cells can be reached  from its bottom left-hand corner by a path which is contained in the polyomino and uses only north and east steps.  Let $c$ be the bottom left-hand corner of $P$. A \emph{clockwise tour} of $P$ is  a closed walk which,  starting at $c$, goes along the boundary of $P$ (in the clockwise direction), and ends when the corner $c$ is reached again.  A \emph{bi-wall directed polygon} is a directed polygon  such that  its  clockwise tour satisfies that once the first left step has been made, up steps occur never more \cite{Feretic}.  For example, Figure \ref{biwall} shows a  bi-wall directed polygon of perimeter $66$. The sequence $s_2(n)$ counts the number of  bi-wall directed polygons with perimeter $2(n+2)$. We wonder how the bijective proof of this result will appear.

\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.6]{biwall.eps}
\caption{Bi-wall directed polyomino of perimeter $66$.}
\label{biwall}
\end{center}
\end{figure}

Notice that, due to the relation $S_2(x)=2S(x)-1$, bi-wall directed polygons of perimeter $2(n+2)$ are in one-to-one correspondence with special directed polygons of perimeter $2(2n+1)$ having a clockwise tour that can be decomposed either $N P S \overline{P}$ or $P E \overline{P} W$ where $N$ (resp. $S$, $E$, $W$) are the north- (resp. south-, east-, west-) steps, and $P$ is obtained from a skew Dyck path $Q$ of semilength $n$ by replacing $U$ with $N$, $D$ with $E$, and $L$ with $W$,   and $\overline{P}$ is obtained from $Q$ by reading $Q$ from right to left and by replacing $U$ with $W$, $D$ with $S$, and $L$ with $E$. For instance, from the skew Dyck path $P=UDUUDL$ we generate two directed polygons $\textcolor{red}{N}NENNES\textcolor{red}{S}ESWWSW$ and $NENNES\textcolor{red}{E}ESWWSW\textcolor{red}{W}$ illustrated in Figure~\ref{sympoly}. Finding a constructive bijection between this class of polyominoes and bi-wall directed polygons remains an interesting open question.


\begin{figure}[H]
\begin{center}
\includegraphics[scale=1]{Fig4.eps}
\caption{Construction of two directed polygons of perimeter $14$ from a skew Dyck path of length $6$.}
\label{sympoly}
\end{center}
\end{figure}

Rogers \cite{Rogers} observed that every element $d_{n+1,k+1}$ of a
Riordan array  (not belonging to $0$ row or $0$ column) can be expressed as a fixed linear combination
of the elements in the preceding row. The \emph{$A$-sequence} is defined to be the sequence coefficients of this linear combination. Similarly, Merlini et al.\  \cite{Merlini}  introduced the \emph{$Z$-sequence}, which characterizes the elements in column $0$,  except for the element $d_{0,0}$.  Therefore,
the $A$-sequence, the $Z$-sequence and the element $d_{0,0}$ completely characterize a Riordan array. We summarize this characterization in the following theorem.




\begin{theorem}[\cite{Merlini, HeS}] \label{Mer1}
An infinite lower triangular array $\mathcal{D}=\left[d_{n,k}\right]_{n,k\geq 0}=(g(x), f(x))$ is a Riordan array if and only if  $d_{0,0}\neq 0$
and there exist two sequences $(a_0, a_1, a_2, \dots)$, with $a_0\neq 0$, and  $(z_0, z_1, z_2, \dots)$ (called the $A$-sequence and the $Z$-sequence, respectively), such that
\begin{align*}
d_{n+1,k+1}&=a_0d_{n,k} + a_1d_{n,k+1} + a_2d_{n,k+2} +\cdots & \text{for } n, k\ge0,  \\
d_{n+1,0}&=z_0d_{n,0} + z_1d_{n,1} + z_2d_{n,2} +\cdots & \text{for } n\ge0,
\end{align*}
or equivalently
$$g(x)=\frac{d_{0,0}}{1-xZ(f(x))} \quad \text{and} \quad f(x)=x(A(f(x))),$$
where $A(x)$ and $Z(x)$ are the generating functions of the $A$-sequence and $Z$-sequence, respectively.
\end{theorem}


Below we describe the $A$-sequence and $Z$-sequence for the Riordan array $\Sk_2$.
\begin{theorem}\label{AZSeq}
For $n, k\geq 0$, we have  
\begin{align*}
\widetilde{s}(n+1,k+1)&=\widetilde{s}(n,k)+\widetilde{s}(n,k+1)+\sum_{i\geq 2}2^{i-2} \, \widetilde{s}(n,k+i),
\end{align*}
Moreover, for $n\geq 0$
\begin{align*}
\widetilde{s}(n+1,0)&=\widetilde{s}(n,0)+\sum_{i\geq 1}(2^{i-1}+1)\widetilde{s}(n,i),
\end{align*}
with the initial value $\widetilde{s}(0,0)=1$.
\end{theorem}
\begin{proof}
From Theorem  \ref{Mer1} and Corollary  \ref{coro:D2}, the generating function of the $A$-sequence is
$$A(x)=\frac{x}{\overline{f}(x)}=\frac{x}{\frac{x(1-2x)}{1-x-x^2}}=\frac{1-x-x^2}{1-2x}=1+x+x^2+2x^3+4x^4+8x^5+\cdots.$$
The generating function of the $Z$-sequence of $\Sk_2$ is  
$$Z(x)=\frac{1}{\overline{f}(x)}\left(1-\frac{d_{0,0}}{g(\overline{f}(x))}\right)=\frac{1-x-x^2}{(1 - x)(1 - 2x)}=1 + 2 x + 3 x^2 + 5 x^3 + 9 x^4 + 17 x^5 + 33 x^6+\cdots.$$
Combining the above relations, we obtain the following corollaries. 
\end{proof}

\begin{corollary}\label{AZSeq2}
For any  integers $n, k\geq 0$, we have the following relations 
\begin{align*}
s(n,k)&=s(n-1,k-1)+s(n-2,k)+\sum_{i=2}^{\lfloor \frac{n-1}{2}\rfloor}2^{i-2} \,s(n-i-1,k+i-1),\\
s(n,0)&=s(n-2,0)+\sum_{i=1}^{\lfloor \frac{n-1}{2}\rfloor}(2^{i-1}+1) s(n-i-2,i).
\end{align*}
with $s(0,0)=1=s(1,1)$, $s(1,0)=0$, and $s(n,k)=0$ for $n<k$.
\end{corollary}


\begin{corollary}\label{AZSeq2b}
For any  integers $n, k\geq 2$, we have the following relation
\begin{align*}
s(n+1,k-1)-2s(n,k)&=s(n,k-2)-s(n-1,k-1)-s(n-2,k).
\end{align*}
\end{corollary}


\section{The number of left steps}

In this section, we provide a close form for the number $a_h(n,m)$ of skew  meanders of length $n$, height $h$, and with exactly $m$ left steps $L=(-1,-1)$.  Let $\ell(P)$ denote the number of left steps in a path $P$. Given a non-negative integer $h$, we let $\Mn_h$ denote the set of skew meanders of height $h$. We are interested in the bivariate generating function 
$$L_h(x,y):=\sum_{P\in \Mn_h}x^{|P|}y^{\ell(P)}=\sum_{n, m \geq 0}a_h(n,m)x^ny^m.$$

\begin{theorem}\label{lem1}
The generating function $L_h(x,y)$ is given by the equations
\begin{align*}
L_0(x,y)=\frac{1-x^2y-\sqrt{1 - 4 x^2 - 2 x^2 y + 4 x^4 y + x^4 y}}{2x},
\end{align*}
and for $h\geq 1$, we have  
$$L_h(x,y)=\frac{x^{h}L_0(x,y)}{(1-x^2L_0(x,y))^{h}}.$$
\end{theorem}
\begin{proof}
From the decomposition given in Figure \ref{deco1}, we obtain the functional equation
$$L_{0}(x,y)=1+x^2L_{0}(x,y)^2+x^2y(L_{0}(x,y)-1).$$
Solving for $L_{0}(x,y)$, we have the first  equation. If $h\geq 1$, then from the decomposition given in Figure \ref{fig2} we have 
$$L_{h}(x,y)=xL_{h-1}(x,y)+x^2L_{0}(x,y)L_{h}(x,y).$$
Therefore
$$L_{h}(x,y)=\frac{xL_{h-1}(x,y)}{1-x^2L_0(x,y)}=\cdots=\frac{x^{h}L_0(x,y)}{(1-x^2L_0(x,y))^{h}}.$$
\end{proof}

Let $a^{(j)}(n,m)$ be the coefficient of $x^ny^m$ in the generating function $L_0(x,y)^j$.
\begin{lemma}\label{lem2}
For $n, j\geq 1$, $n \equiv \modd{0} {2}$, and  $0\leq m \leq n/2-1$ we have 
\begin{align*}
a^{(j)}(n,m)=\sum_{i=0}^j\frac{i}{n/2-m}\binom{j}{i}\binom{n/2-1}{m}\binom{2(n/2-m)}{n/2-m-i},
\end{align*}
with the initial values $a^{(j)}(0,0)=1$. Moreover, for $n\equiv \modd{1} {2}$, $a^{(j)}(n,m)=0$. \end{lemma}
\begin{proof}
If  $f(x,y)=L_0(x^{1/2},y)-1$, then from Theorem \ref{lem1} we have 
$$f(x,y)=x(f(x,y)^2+(2+y)f(x,y)+1)=x\Phi(f(x,y)),$$
where  $\Phi(z)=z^2+(2+y)z+1$. From the  Lagrange inversion theorem, we deduce
\begin{align*}
f^{(k)}(n,m)&:=[x^ny^m]f(x,y)^k=\frac{k}{n}[z^{n-k}y^m]\Phi(z)^n\\
&=\frac{k}{n}[z^{n-k}y^m](z^2+(2+y)z+1)=\binom{n-1}{m}B(n-m,k).
\end{align*}
Since $B(n,k)=\frac{k}{n}\binom{2n}{n-k}$, we obtain
$$f^{(k)}(n,m)=\frac{k}{n-m}\binom{n-1}{m}\binom{2(n-m)}{n-m-k}.$$
If $n$ is even then
\begin{align*}
a^{(j)}(n,m)&=[x^ny^m](f(x^2,y)+1)^j=[x^ny^m]\sum_{i= 0}^j\binom{j}{i}f(x^2,y)^i\\
&=\sum_{i=0}^j\frac{i}{n/2-m}\binom{j}{i}\binom{n/2-1}{m}\binom{2(n/2-m)}{n/2-m-i}.
\end{align*}
Moreover, if $n$ is odd this sequence is equal to zero.
\end{proof}

The summand on the right side   
of $a^{(j)}(2n,m)$ is denoted by $F(j,i)$, that is
$$F(j,i):=\frac{i}{n-m}\binom{j}{i}\binom{n-1}{m}\binom{2(n-m)}{n-m-i}.$$

By Zeilberger's creative telescoping method (cf.\ \cite{ABZ}) $F(j,i)$ satisfies the relation
\begin{align}\label{rel1}
(1 + j) (j - 2 m + 2 n)F(j,i) - j (1 + j - m + n) F(j+1,i)=G(j,i+1)-G(j,i),
\end{align}
with the certificate 
$$R(j,i)=\frac{(-1 + i) (1 + j) (i - m + n)}{1 - i + j}.$$
That is, $R(j,i)=F(j,i)/G(j,i)$ is a rational function in both variables.
Summing both sides of \eqref{rel1} with respect to $i$ and after simplification we obtain the following result.

\begin{proposition}\label{lem3}
For $0\leq m \leq n-1$
$$a^{(j)}(2n,m)=\frac{j}{2(n-m+j)}\binom{n-1}{m}\binom{2(n-m)}{n-m}\frac{(2 m - 2 n -j+1)_j}{(m - n -j+1)_j},$$
where $(x)_n:=x(x+1)\cdots(x+n-1)$ and $(x)_0=1$.
\end{proposition}



\begin{theorem}
For $n, m, h\geq 0$ we have
$$a_{h}(n,m)=\sum_{j=0}^{\frac{n-h}{2}}\binom{j+h-1}{j}a^{(j+1)}(n-h-2j,m).$$
\end{theorem}
\begin{proof}
For $h\geq 1$ we have from Theorem \ref{lem1}  that
\begin{align*}
a_h(n,m)&=[x^ny^m]\frac{x^{h}L_0(x,y)}{(1-x^2L_0(x,y))^{h}}\\
&=[x^{n-h-2j}y^m]\sum_{j\geq 0}\binom{j+h-1}{j}L_0(x,y)^{j+1}
\\
&=\sum_{j\geq 0}\binom{j+h-1}{j}a^{(j+1)}(n-h-2j,m).
\end{align*}
\end{proof}

Figure \ref{biwall2} shows the skew meanders corresponding to $a_3(11,2)=12$.
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.6]{Fig3.eps}
\caption{The  skew meanders of length 11, height 3, with exactly 2 left steps.}
\label{biwall2}
\end{center}
\end{figure}


\begin{thebibliography}{99}

\bibitem{Deutsch} E.~Deutsch, E.~Munarini, and S.~Rinaldi, Skew Dyck paths, \emph{J. Statist. Plann. Inference} \textbf{140} (2010), 2191--2203. 

\bibitem{Deutsch2} E.~Deutsch, E.~Munarini, and S.~Rinaldi, Skew Dyck paths, area, and superdiagonal bargraphs,  \emph{J. Statist. Plann. Inference}  \textbf{140} (2010), 1550--1526. 

\bibitem{Feretic} S.~Feretic, Generating functions for bi-wall directed
polygons, in S. Rinaldi and S. G. Mohanty, eds., {\it Seventh Int. Conf. on
Lattice Path Combinatorics and Applications}, 2010, pp.~147--151.

\bibitem{flajolet} P.~Flajolet and R.~Sedgewick,  \emph{Analytic Combinatorics}, Cambridge University Press,  2009.

\bibitem{Gess} I.~M.~Gessel, Lagrange inversion, \emph{J. Combin. Theory Ser. A} \textbf{144} (2016), 212--224.

\bibitem{KP} P.~Kirschenhofer and H.~Prodinger, Return statistics of simple random walks, \emph{J. Statist. Plann. Inference}  {\bf 54} (1996), 67--74.


\bibitem{HeS} T.-X.~He and R.~Sprugnoli, Sequence characterization of Riordan arrays, \emph{Discrete  Math.}  {\bf 309} (2009), 3962--3974.

\bibitem{Lu} Q.~L.~Lu, Skew Motzkin paths, \emph{Acta Math. Sin. (Engl. Ser.)} \textbf{33} (2017), 657--667.

\bibitem{Merlini}  D.~Merlini, D.~G.~Rogers, R.~Sprugnoli, and M.~C.~Verri, On some alternative characterizations of Riordan arrays, \emph{Canadian J. Math.} {\bf 49} (1997), 301--320.

\bibitem{Merl} D.~Merlini, R.~Sprugnoli, and M.~C.~Verri, Lagrange inversion: when and how, \emph{Acta Appl. Math}, {\bf 94} (2006), 233--249.

\bibitem{ABZ} M.~Petko\v{v}sek, H.~Wilf, and D.~Zeilberger, \emph{A=B}, A. K. Peters, Ltd. 1996.

\bibitem{Rogers} D.~G.~Rogers, Pascal triangles, Catalan numbers and renewal arrays, \emph{Discrete Math.} {\bf 22} (1978), 301--310.

\bibitem{Shapiro} L.~Shapiro, A Catalan triangle,  \emph{Discrete Math.} {\bf 14} (1976), 83--90.

\bibitem{Riordan} L.~W.~Shapiro, S.~Getu, W.~Woan, and L.~Woodson, The Riordan group,  \emph{Discrete Appl. Math.} {\bf 34} (1991) 229--239.

\bibitem{OEIS} N.~J.~A.~Sloane et al., The On-Line Encyclopedia of
Integer Sequences, 2021. Available at \url{https://oeis.org/}.

\bibitem{WoanShapiroRog} W.-J.~Woan, L.~Shapiro, and D.~G.~Rogers, The Catalan numbers, the Lebesgue integral, and $4^{n-2}$, \emph{Amer. Math. Monthly} \textbf{104} (1997), 926--931.


\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A19.

\noindent \emph{Keywords:}
skew Dyck path, generating function, Lagrange inversion, Riordan array.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A002212},
\seqnum{A033321},
\seqnum{A039598}, and
\seqnum{A122737}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 18 2021;
revised version received  July 28 2021.
Published in {\it Journal of Integer Sequences}, August 4 2021.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
