\documentclass{SLC_rigo} %Style here adapted to include the package algorithm.sty (as other order of packages would bug the compilation).
\articlenumber{6}
%%This is the final version, as published in August 2023.
%History of the versions:
%Initial submission 20/08/2021:  https://doi.org/10.48550/arXiv.2108.08299
%Last author's revision: 07/08/2023
%Editors revision: 07/08/2023 
%Publication: August 2023

\pdfminorversion=7 %to avoid a warning due to figures generated with an older pdf standard.
\makeatletter
\providecommand*{\toclevel@unnumbered}{0}
\makeatother

\usepackage{enumerate}

\newcommand{\D}{{\mathcal D}}
\newcommand{\area}{{\texttt{area}}}
\newcommand{\Q}{{\mathcal Q}}
\usepackage{tikz}

\author[R.~Fl\'orez]{Rigoberto Fl\'orez\textsuperscript{1}\protect\orcid{0000-0002-3644-9358}}
\address{\textsuperscript{1}Department of Mathematical Sciences, The Citadel, Charleston, SC, U.S.A.;\newline \website{https://www.rigoflorez.com/}}

\author[T.~Mansour]{Toufik Mansour\textsuperscript{2}\protect\orcid{0000-0001-8028-2391}}
\address{\textsuperscript{2}Department of Mathematics, University of Haifa, 3498838 Haifa, Israel;\newline  \website{https://math.haifa.ac.il/toufik/}}

\author[J.L.~Ram\'irez]{Jos\'e L. Ram\'{\i}rez\textsuperscript{3}\protect\orcid{0000-0002-8028-9312}}
\address{\textsuperscript{3}Departamento de Matem\'aticas, Universidad Nacional de Colombia, Bogot\'a, Colombia;\newline  \website{https://sites.google.com/site/ramirezrjl/}}

\author[F.A.~Velandia]{Fabio A. Velandia\textsuperscript{4}\protect\orcid{0000-0002-9542-0782}}
\address{\textsuperscript{4}Departamento de Matem\'aticas, Universidad Nacional de Colombia, Bogot\'a, Colombia;\newline  \website{https://orcid.org/0000-0002-9542-0782}}

\author[D.~Villamizar]{Diego Villamizar\textsuperscript{5}\protect\orcid{0000-0002-7759-9483}}
\address{\textsuperscript{5}Escuela de Ciencias Exactas e Ingenier\'ia, Universidad Sergio Arboleda, Bogot\'a, Colombia; \website{https://sites.google.com/view/dvillami/}}


\title[Restricted Dyck paths on valleys sequence]{Restricted Dyck paths on valleys sequence}

\abstract{In this paper we study a subfamily of a classic lattice path, the \emph{Dyck paths}, called \emph{restricted $d$-Dyck} paths, in short $d$-Dyck.
A valley of a Dyck path $P$ is a local minimum of $P$; if the difference between the heights of two consecutive valleys (from left to right) is at
least $d$, we say that $P$ is a restricted $d$-Dyck path. The \emph{area} of a Dyck path is the sum of the absolute values of $y$-components
of all points in the path. We find the number of peaks and the area of all paths of a given length in the set of $d$-Dyck paths. We give a 
bivariate generating function to count the number of the $d$-Dyck paths with respect to the semi-length and number of peaks. After that, 
we analyze in detail the case $d=-1$. Among other things, we give both the generating function and a recursive relation for the total area.}

\keywords{Dyck path, $d$-Dyck path, generating function}
 
\begin{document}
\maketitle
\section{Introduction}

A classic concept, the \emph{Dyck paths}, has been widely studied. Recently, a subfamily of these paths, non-decreasing Dyck paths, has received a certain
level of interest. It is because of some statistics are given by linear combinations of Fibonacci numbers and Lucas numbers. In this paper we keep
studying a generalization of the non-decreasing Dyck paths. Other generalizations of non-decreasing Dyck paths have been given for Motzkin paths and for \L{}ukasiewicz paths ~\cite{RigoJoseLuis,RigoJoseLuisRational}.

We now give some definitions that we use in this paper. 
A 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 consists of (the same number of) North-East steps $U:=(1,1)$ and South-East steps $D:=(1,-1)$. 
The \emph{semi-length} of a path is the total number of $U$'s that the path has. \pagebreak 

A \emph{valley} (\emph{peak}) is a subpath of the form $DU$
($UD$) and the \emph{valley vertex} of $DU$ is the lowest point (a local minimum) of $DU$. The \emph{level} of a valley is the $y$-component of its valley vertex. Following ~\cite{FloRamVelVilPolyominoes, FloRamVelVil} we define the \emph{valley vertices vector} of a Dyck path $P$ as the vector
$\nu=(\nu_1, \nu_2, \dots, \nu_k)$ formed by all $y$-coordinates (listed from left to right) of all valley vertices of $P$. 

For a fixed $d \in \mathbb{Z}$,
a Dyck path $P$ is called \emph{restricted $d$-Dyck} or \emph{$d$-Dyck} (for simplicity), if either $P$ has at most one valley, or if its valley vertex
vector $\nu$ satisfies that $\nu_{i+1}-\nu_i\geq d$, where $1\le i <k$. The set of all $d$-Dyck paths of semi-length $n$ is denoted $\D_{d}(n)$, where 
$r_d(n)$ denotes its cardinality, and the set of all $d$-Dyck paths is denoted by $\D_{d}$.

The first well-known example of these paths is the set of $0$-Dyck paths; in the literature, 
see~\cite{barcucci,CZ,CZ2,DeutscheProdinger, ElizaldeFlorezRamirez,FlorezJose}, this family is known as non-decreasing Dyck paths. The whole family of Dyck paths can
be seen as a limit of $d$-Dyck and it occurs when $d\to -\infty$. Another example, from Figure~\ref{Example} we observe that $\nu=(0,1,0,3,4,3,2)$ and that
$\nu_{i+1}-\nu_i\ge -1$, for $i=1, \dots, 6$, so the figure depicts a $(-1)$-Dyck path of length 28 (or semi-length 14).

\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=0.9]{Example1}
\end{center}\label{Example}
\caption{A $(-1)$-Dyck path of length 28.} 
\end{figure}

The recurrence relations and/or the generating functions for $d$-Dyck when $d\ge 0$ have different behavior than the case $d< 0$. 
For example, generating functions accounting for the number of valleys, the number of peaks, and the area, for $d$-Dyck when $d\ge 0$, 
are all rational for all variables (see~\cite{barcucci,CZ,CZ2,ElizaldeFlorezRamirez,FlorezJose,FloRamVelVilPolyominoes, FloRamVelVil}).
However, when we analyze in this paper several aspects for $d< 0$ (the number of paths, the area of the paths, and the number of peaks) 
we find that the generating functions are all algebraic (non-rational). 

In this paper we give a bivariate generating function to count the number of paths 
in $\D_{d}(n)$, for $d\le 0$, with respect to the number of peaks and semi-length. We also give a relationship between the total number of 
$d$-Dyck paths and the Catalan numbers. Additionally, we give an explicit symbolic expression for the generating function with respect to the 
semi-length. For the particular case $d=-1$ we give a combinatorial expression and a recursive relation for the total number of paths. 
We also analyze the asymptotic behavior for the sequence $r_{-1}(n)$. 

It is well known that there are many bijections between Dyck paths and other combinatorial objects, we are wondering if there are other bijections 
between $d$-Dyck paths for $d<-1$ and other object of combinatorics. 

The \emph{area} of a Dyck path $P$ is the sum of the values of $y$-components of all points in the path. That is, the area of $P$, denoted by $\area(P)$, 
 corresponds to the surface area under $P$ and above of the $x$-axis. For example, if $P$ is the path in Figure~\ref{Example}, then 
 $\area(P)=70$. We use generating functions and recursive relations to analyze the distribution of the area of all paths in $\D_{-1}(n)$.
 \clearpage 
 
The problem of enumerating the area in directed lattice paths, in a general setting, was solved by Banderier and Gittenberger~\cite{BanGit}, building
on the enumerative and asymptotics results from~\cite{BanFla}, where Dyck, Motzkin, and \L{}ukasiewicz paths are particular cases.

A summary of notation used throughout the paper appears in Table~\ref{tab:notation} in the appendix.


 \section{Number of \texorpdfstring{$d$}{d}-Dyck paths and Peaks Statistic}
Given a family of lattice paths, a classic question is how many lattice paths are there of certain length, and a second classic question is
how many peaks are there depending on the length of the path. These questions have been completely answered, for instance, for Dyck paths~\cite{Deutschenumeration}, $d$-Dyck paths for $d\ge 0$~\cite{barcucci, FloRamVelVil}, and Motzkin paths~\cite{sapounakis} among others. 
In this section we give a bivariate generating function according to the semi-length and the number of peaks of the $d$-Dyck paths with $d< 0$. 

Given a $d$-Dyck path $P$, we denote the semi-length of $P$ by $\ell(P)$ and denote the number of peaks of $P$ by $\rho(P)$. So, the 
bivariate generating function to count the number of paths and peaks of $d$-Dyck paths is defined by
 \begin{align*}
 L_d(x, y):=\sum_{P\in \D_d}x^{\ell(P)}y^{\rho(P)}.
 \end{align*}

 \subsection{Some facts known when \texorpdfstring{$d\geq 0$}{d>0}}
These results can be found in~\cite{FloRamVelVil}.
\begin{itemize}
\item
If $d\geq 0$, then the generating function $F_d(x, y)$ is given by 
 \begin{align*}
 L_d(x, y)=1 + \frac{xy(1-2x+x^2+xy-x^{d+1}y)}{(1-x)(1-2x+x^2-x^{d+1}y)}.
 \end{align*}
\item If $d\geq 1$,
\begin{align*}
r_d(n)=\sum_{k=0}^{\lfloor\frac{n+d-2}{d}\rfloor}\binom{n-(d-1)(k-1)}{2k}.
\end{align*}
\item If $n> d$, then we have the recursive relation
\begin{align*}
r_d(n)=2r_d(n-1)-r_d(n-2)+r_d(n-d-1),
\end{align*}
with the initial values $r_d(n)=\binom n2 +1$, for $0\leq n \leq d$.

\item Let $p_d(n,k)$ be the number of $d$-Dyck paths of semi-length $n$, having exactly $k$ peaks.
If $d\geq 0$, then
\begin{align*}
p_d(n,k)=\binom{n+k-d(k-2)-2}{2(k-1)}.
\end{align*}
For the whole set of Dyck paths, the number $p_{-\infty}(n,k)$, is given by the Narayana numbers $N(n,k)=\frac{1}{n}\binom nk \binom{n}{k-1}$.
\end{itemize}

\subsection{Peaks statistic for \texorpdfstring{$d$}{d} a negative integer} For the remaining part of the paper we consider only the case $d<0$ and use $e$ to
denote $|d|$. A \emph{pyramid} of semi-length $h\ge1$ is a subpath of the form $X^hY^h$; it is \emph{maximal}, denote by $\Delta_h$, if it can not be 
extended to a pyramid $X^{h+1}Y^{h+1}$. 

\begin{theorem}\label{mainGF} If $d$ is a negative integer and $e:=|d|$, then
the generating function $L_e(x, y)$ satisfies the functional equation
\begin{equation}\label{eqSys1}
 L_e(x,y)= xy+xL_e(x,y)+xS_e(x,y)L_e(x,y), 
\end{equation}
where $S_e(x)$ satisfies the algebraic equation
\[
(1-xS_e(x,y))^e(y+(1-y)xS_e(x,y))-S_e(x,y)(1-xS_e(x,y))^{e+1}-\frac{x^{e+2}y}{1-x}S_e(x,y)=0.
\]
\end{theorem}

\begin{proof} We start this proof by introducing some notation. The set $\Q_{d,i} \subseteq \D_{d}$ denotes the family of non-empty paths
where the last valley is at level $i$. We consider the generating function
\[Q_i^{(e)}(x,y):=\sum_{P\in \Q_{d,i}}x^{\ell(P)}y^{\rho(P)}.\]
It is convenient to consider the sum over the $Q^{(e)}_i(x,y)$. We also consider the generating function, with respect to the lengths and peaks, that counts 
the $d$-Dyck paths that have either no valleys or the last valley is at level less than $e$. That is, 
\begin{equation}\label{defSe}
S_e(x,y)=\frac{y}{1-x}+\sum _{j=0}^{e-1}Q^{(e)}_j(x,y).
\end{equation}
 A path $P$ can be uniquely decomposed as either
$UD, UTD$, or $UQDT$ (by considering the first return decomposition), where $T\in\D_{d}$ and $Q$ is either a pyramid or is a path in $\cup_{i=0}^{e-1}\Q_{d,i}$ 
(see Figure~\ref{Fig3}, for a graphical representation of this decomposition). Notice that $\nu_{i+1}-\nu_i\geq d$ and the decomposition $UQDT$ ensures that 
 $Q$ holds as in the former line.

\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=0.8]{Deco1}
\end{center}
\caption{Decomposition of a $d$-Dyck path.} \label{Fig3}
\end{figure}

 From the symbolic method we obtain the functional equation
\[ L_e(x,y)= xy+xL_e(x,y)+xS_e(x,y)L_e(x,y).\]
Now we are going to obtain a system of equations for the generating functions $Q_i(x,y)$. Let $Q$ be a path in the set $\Q_{d,i}$. If $i=0$, then the path 
$Q$ can be decomposed uniquely as either
$UQ'D\Delta$ or $UQ'DR$, where $\Delta$ is a pyramid, $R$ is a path in $\Q_{d,0}$, and $Q'$ is either a pyramid or $Q'\in \cup_{i=0}^{e-1}\Q_{d,i}$.
Therefore, we have the functional equation
\[Q_0^{(e)}(x,y)=xS_e(x,y)\frac{xy}{1-x}+xS_e(x,y)Q_0^{(e)}(x,y).\]
For $i>0$, any path $Q$ can be decomposed uniquely in one of these two forms $UR_1D$ or $UQDR_2$,
where $R_1\in \Q_{d,i-1}, R_2 \in \Q_{d,i}$, and $Q$ is either a pyramid or $Q\in \cup_{i=0}^{e-1}\Q_{d,i}$.
So, we have the functional equation
\begin{align}
\label{eqSys2aa}
Q_i^{(e)}(x,y)=xQ_{i-1}^{(e)}(x,y)+xS_e(x,y)Q_i^{(e)}(x,y).
\end{align}
Summarizing the discussion above, we obtain the system of equations:
\begin{align}
\label{eqSys2}
\begin{cases}
Q_0^{(e)}(x,y)&=xS_e(x,y)\frac{xy}{1-x}+xS_e(x,y)Q_0^{(e)}(x,y)\\
 Q_1^{(e)}(x,y) &=xQ_0^{(e)}(x,y)+xS_e(x,y)Q_1^{(e)}(x,y)\\
 &\ \vdots\\
 Q_i^{(e)}(x,y)&=xQ_{i-1}^{(e)}(x,y)+xS_e(x,y)Q_i^{(e)}(x,y)\\
 &\ \vdots \\
 Q_{e-1}^{(e)}(x,y)&=xQ_{e-2}^{(e)}(x,y)+xS_e(x,y)Q_{e-1}^{(e)}(x,y).
 \end{cases}
 \end{align}
Summing up the equations in~\eqref{eqSys2}, we obtain that
\begin{align*}
\sum_{j=0}^{e-1}Q_j^{(e)}(x,y)=xS_e(x,y)\left(\sum_{j=0}^{e-1}Q_j^{(e)}(x,y)+\frac{xy}{1-x}\right)+x\sum_{j=0}^{e-2}Q_j^{(e)}(x,y).
\end{align*}
From this and~\eqref{defSe} we have
\begin{multline}\label{eqSex}
 S_e(x,y)-\frac{y}{1-x}=x\left (S_e(x,y)-\frac{y}{1-x}-Q_{e-1}^{(e)}(x,y)\right)\\+xS_e(x,y)\left(S_e(x,y)-\frac{y}{1-x}\right )+\frac{x^2y}{1-x}S_e(x,y).
\end{multline}
Iterating~\eqref{eqSys2aa}, we have $Q_i^{(e)}(x,y)$, with $i\geq 0$, can be expressed as 
\begin{align}\label{FunEcQ}
Q_i^{(e)}(x,y)=\frac{x^{i+2}yS_e(x,y)}{(1-x)(1-xS_e(x,y))^{i+1}}.
\end{align}
Substituting~\eqref{FunEcQ} into~\eqref{eqSex} we obtain the desired functional equation.
\end{proof}
Solving~\eqref{eqSex} for $S_e(x,y)$ we have
\begin{align}\label{FunEcS}
S_e(x,y)=\frac{1-x+xy-\sqrt{1-2x+x^2-2xy-2x^2y+x^2y^2+4x^2Q_{e-1}^{(e)}(x,y)}}{2x}.
\end{align}
We observe that substituting~\eqref{FunEcS} into~\eqref{eqSys1}, we have
\begin{eqnarray*}
L_e(x,y)&=&\dfrac{xy}{1-x-xS_e(x,y)}\\
&=&\dfrac{xy}{1-x-\dfrac{1-x+xy-\sqrt{1-2x+x^2-2xy-2x^2y+x^2y^2+4x^2Q_{e-1}^{(e)}(x,y)}}{2}}.
\end{eqnarray*}
Since $S_e(x,y)$ is a power series and by~\eqref{FunEcQ}, we obtain that $Q_{e-1}^{(e)}(x,y)\rightarrow0$ as $e\rightarrow\infty$, where here we assumed that $|x|<1$ (for details on convergence of generating functions; see~\cite[p.~731]{flajolet}). Therefore,
\begin{align*}
\lim_{e\to \infty} L_e(x,y)=\frac{1-x-xy-\sqrt{1 - 2 x + x^2 - 2 x y - 2 x^2 y + x^2 y^2}}{2x}.
\end{align*}
This last generating function is the distribution of the Narayana sequence. This corroborates with the fact that the restricted $(-\infty)$-Dyck paths coincide 
with the non-empty Dyck paths.

 \begin{theorem}
 If $1\leq k \leq |d|+3$, then the $k$-th coefficient of the generating function $L_e(x,1)$ coincides with the Catalan number $C_k=\frac{1}{k+1}\binom{2k}{k}$.
 \end{theorem}
\begin{proof} We first observe that the shortest Dyck path that contains a forbidden sequence of valleys is $P=U^{e+2}DUD^{e+2}UD$ (clearly,
$\ell (P)=e+4$) with $e=|d|$. Therefore, if $d<0$, then $r_d(n)=C_n$, for $n=1, 2, \dots, |d|+3$.
\end{proof}
The first few values for the sequence $r_d(n)$, for $d\in \{-1, -2, -3, -4\}$ are
\begin{align*}
\{r_{-1}(n)\}_{n\geq 1}&=\{\textbf{1}, \, \textbf{2}, \, \textbf{5}, \, \textbf{14}, \, 41, \, 123, \, 375, \, 1157, \, 3603, \dots \}, \\
\{r_{-2}(n)\}_{n\geq 1}&=\{\textbf{1}, \, \textbf{2}, \, \textbf{5}, \, \textbf{14}, \, \textbf{42}, \, 131, \, 419, \, 1365, \, 4511, \dots \}, \\
\{r_{-3}(n)\}_{n\geq 1}&=\{\textbf{1}, \, \textbf{2}, \, \textbf{5}, \, \textbf{14}, \, \textbf{42}, \, \textbf{132}, \, 428, \, 1419, \, 4785, \dots \}, \\
\{r_{-4}(n)\}_{n\geq 1}&=\{\textbf{1}, \, \textbf{2}, \, \textbf{5},\, \textbf{14}, \, \textbf{42},\, \textbf{132}, \, \textbf{429}, \, 1429, \, 4850, \dots \}.
\end{align*}
For example, there are $41$ $(-1)$-Dyck paths out of the $42$ Dyck paths of length $10$. Figure~\ref{DyckF} depicts the only Dyck path of length 
$10$ that is not a $(-1)$-Dyck path.

\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=1.3]{DyckF}
\end{center}
\caption{The only Dyck path of length 10 that is not a $(-1)$-Dyck path.} \label{DyckF}
\end{figure}

Recall that $d$ is a negative integer and that $e:=|d|$. Then by Theorem~\ref{mainGF}, we have
\begin{align*}
(L_e(x,y)+y)^e&\left(xL^2_e(x,y)+(xy+x-1)L_e(x,y)+xy\right)\\
&-\frac{x}{1-x}((1-x)L_e(x,y)-xy)(L_e(x,y))^{e+1}=0.
\end{align*}
This implies that 
\begin{multline*}
\sum_{j=2}^{e+1}x\binom{e}{j-2}y^{e+2-j}(L_e(x,y))^j+\sum_{j=1}^{e+1}(xy+x-1)\binom{e}{j-1}y^{e+1-j}(L_e(x,y))^j\\
+\sum_{j=0}^ex\binom{e}{j}y^{e+1-j}(L_e(x,y))^j+\frac{x^2y}{1-x}(L_e(x,y))^{e+1}=0.
\end{multline*}
Hence, by taking $y=1$ and collecting powers of $L_e(x,1)$, we have
\begin{align*}
L_e(x,1)=Z\left(a_0+\sum_{j=2}^{e+1}a_j(x)(L_e(x,1))^j\right),
\end{align*}
where $Z=1$, and
\begin{align*}
a_0&=\frac{x}{1-(e+2)x},\\
a_j&=\frac{1}{1-(e+2)x}\left(x\binom{e+2}{j}-\binom{e}{j-1}\right),\quad j=2,3,\ldots,e,\\
a_{e+1}&=\frac{(e+2)x(1-x)-1+x(1+x)}{(1-x)(1-(e+2)x)}.
\end{align*}
Hence, by the Lagrange inversion formula, we expand the generating function $L_e(x,1)$ as a power series in $Z$ to obtain 
\begin{align*}
L_e(x,1)&=\sum_{n\geq1}\frac{[Z^{n-1}]}{n}
\sum_{i_0+i_2+i_3+\cdots+i_{e+1}=n}\frac{n!}{i_0!i_2!\cdots i_{e+1}!}a_0^{i_0}Z^{2i_2+\cdots+(e+1)i_{e+1}}\prod_{j=2}^{e+1}a_j^{i_j},
\end{align*}
that leads to the following result.
\begin{theorem}\label{thLfe}
We have 
\begin{align*}
L_e(x,1)&=\sum_{n\geq1}\frac{\sum_{2i_2+\cdots+(e+1)i_{e+1}=n-1}\binom{n}{i_2,\ldots,i_{e+1}}x^{n-i_2-\cdots-i_{e+1}}t^{i_{e+1}}\prod_{j=2}^{e}\left(x\binom{e+2}{j}-\binom{e}{j-1}\right)^{i_j}}{n(1-(e+2)x)^n},
\end{align*}
where 
\[ \binom{n}{i_2,\ldots,i_{e+1}}=\frac{n!}{i_2!\cdots i_{e+1}!(n-i_2-\cdots-i_{e+1})!} \text{ and } t=\frac{(e+2)x(1-x)-1+x(1+x)}{1-x}.\]
\end{theorem}
For example, Theorem~\ref{thLfe} with $e=2$ gives
\[ L_2(x,1)=\sum_{n\geq1}\frac{\sum_{2i_2+3i_3=n-1}\binom{n}{i_2,i_3}x^{n-i_2-i_3} (6x-2)^{i_2}(\frac{-3x^2+5x-1}{1-x})^{i_3}}{n(1-4x)^n}.\]
Thus, 
\begin{multline*}L_2(x,1)=\frac{x}{1-4x}+\frac{x^2(6x-2)}{(1-4x)^3}+\frac{x^3t}{(1-4x)^4}+
\frac{2x^3(6x-2)^2}{(1-4x)^5} +\frac{5x^4t(6x-2)}{(1-4x)^6}\\
+\frac{5x^4(6x-2)^3+3x^5t^2}{(1-4x)^7}+\frac{21x^5 (6 x - 2)^2 t}{(1 - 4 x)^8} + \frac{28x^6 (-2 + 6 x)t^2 + 14 x^5 (-2 + 6 x)^4}{(1 - 4 x)^9} +\cdots,
\end{multline*}
where $t=(-3x^2+5x-1)/(1-x)$.

\section{Some results for the case \texorpdfstring{$d=-1$}{d=-1}}
In this section we keep analyzing the bivariate generating function given in the previous section for the particular case $d=-1$. For this case, 
we provide more detailed results. We denote by $\Q$ the set of all non-empty paths in
$\D_{-1}$ having at least one valley, where the last valley is at ground level. We denote by $\Q_n$ the subset of $\Q$ formed by all paths of
semi-length $n$ and denote by $q_n$ the cardinality of $\Q_n$. For simplicity, when $d=-1$ (or $e=1$) we use $L(x,y)$ instead of $L_{1}(x,y)$. 
As a consequence of Theorem~\ref{mainGF}, taking $d=-1$, we obtain this theorem.

\begin{theorem}\label{teodnegativo}
 The bivariate generating function $L(x,y)$ is given by
 \begin{align*}
 L(x,y)= \frac{(x-1)y\left(1-x(2+y) - \sqrt{(1-x-2xy-2x^2y+x^2y^2-x^3y^2)/(1-x)} \right)}{2(1-2x+x^2-2xy+x^2y)}.
\end{align*} 
\end{theorem}
Notice that a path $Q\in\Q$ can be uniquely decomposed as either
$U\Delta DU\Delta'D$, $\, U\Delta DR$, $\,UR_1 DR_2$, or $\,URDU\Delta D$,
where $\Delta, \Delta'$ are pyramids, and $R, R_1, R_2\in \Q$ (see Figure~\ref{Fig4} for a graphical representation of this decomposition).
\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=0.51]{Fig4}
\end{center}
\caption{Decomposition of a $(-1)$-Dyck path in $\Q$.} \label{Fig4}
\end{figure}

Therefore, if 
\[Q(x,y):=\sum_{Q\in \Q}x^{\ell(Q)}y^{\rho(P)},\]
then 
\begin{align*}
 Q(x, y)&= x^2\left(\frac{y}{1-x}\right)^2+ x\left(\frac{y}{1-x}\right)Q(x, y) + x(Q(x,y))^2 + x^2\left(\frac{y}{1-x}\right)Q(x,y).
\end{align*}
Solving the equation above for $Q(x,y)$, we find that
\begin{align}\label{gFunQ}
Q(x, y)=\frac{1-x-xy-x^2y -\sqrt{(1-x)(1 - x - 2 x y -2 x^2 y + x^2y^2 - x^3y^2)}}{2(1-x)x}.
\end{align}
Expressing $L(x,y)$ as a series expansion we obtain these first few terms: 
\begin{multline*}
L(x,y)=x y+x^2 \left(y^2+y\right)+x^3 \left(y^3+3 y^2+y\right)+x^4 \left(y^4+\textbf{6}y^3+6 y^2+y\right)\\
+x^5 \left(y^5+10 y^4+19 y^3+10 y^2+y\right)+x^6\left(y^6+15 y^5+46 y^4+45 y^3+15 y^2+y\right)+\cdots.
\end{multline*}
Figure~\ref{Eje1} depicts all six paths in $\D_{-1}(4)$ with exactly 3 peaks. Notice that this is the coefficient of $x^4y^3$, in boldface type, in the above series.
\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=0.85]{Eje1}
\end{center}
\caption{All six paths in $\D_{-1}(4)$ with exactly 3 peaks.} \label{Eje1}
\end{figure}

The generating function for the $(-1)$-Dyck paths is given by
\begin{equation}\label{LxForD1}
L(x):=L(x,1)=\frac{-1 + 4 x - 3 x^2 + \sqrt{1 - 4 x + 2 x^2 + x^4}}{2 (1 - 4 x + 2 x^2)}.
\end{equation}
Thus,
\begin{equation*}
L(x)=x+2 x^2+5 x^3+14 x^4+41 x^5+123 x^6+375 x^7+1157 x^8+\cdots.
\end{equation*}

For the sake of simplicity, if there is not ambiguity, for the remaining part of the paper we use $r(n)$ instead of $r_{-1}(n)$. 
Our interest here is to give a combinatorial formula for this sequence.
First of all, we give some preliminary results. Let $b(n)$ be the number of $(-1)$-Dyck paths of semi-length $n$ that either have no valleys or the last valley is at ground level. Note that $b(n)-1$ is the $n$-th coefficient of the generating function $Q(x,1)$; see~\eqref{gFunQ}, or equivalently 
\begin{align*}
\sum_{n\geq 0}b(n)x^n&=Q(x,1) + \frac{1}{1-x}=\frac{1-x^2-\sqrt{1-4x+2x^2+x^4}}{2(1-x)x}\\
&=1+x+2 x^2+4 x^3+9 x^4+22 x^5+57 x^6+154 x^7+429 x^8+\cdots.
\end{align*}

This generating function coincides with the generating function of the number of Dyck paths of semi-length $n$ that avoid the subpath $UUDU$. From Proposition 5 of~\cite{Sap}
 and~\cite[p.~10]{barry} we conclude the following proposition.

\begin{proposition}
\label{propbn}
For all $n\geq 0$ we have
\begin{align*}
b(n)=1+\sum_{j=0}^{\lfloor\frac{n-1}{2}\rfloor}\frac{(-1)^j}{n-j}\binom{n-j}{j}\binom{2n-3j}{n-j+1}=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\sum_{j=0}^{n-k}\binom{n-k}{j}N(j,k),
\end{align*}
where $N(n,k)=\frac{1}{n}\binom nk \binom{n}{k-1}$ are the Narayana numbers, with $N(0,0)=1$. 
\end{proposition}

We tried to find a combinatorial proof of the previous proposition. However, we were not able to do it. This remark summarizes our observations 
toward a potential proof. It will be interesting to see such a combinatorial proof.

\begin{remark} 
\label{rem1}
Let $\mathcal{B}(n)=\mathcal{Q}_n\cup \{\Delta _n\}$ denote the set of $(-1)$-Dyck paths having either no valleys or the last valley 
is at ground level. That is, $b(n)=|\mathcal{B}(n)|$. A South-East step in $P\in \mathcal{B}(n)$, satisfies one of these two conditions.
\begin{itemize} 
\item The step belongs to a pyramid.
\item The step is part of a valley, say for example, the $m$-th valley, 
such that $\nu _{m}-\nu _{m -1}=-1$. In this case, the valley with height $\nu _{m}$ is called $(-1)$-\textit{valley}. 
\end{itemize}

\pagebreak
 
We denote by $\mathcal{B}_{j,k}(n)$ the set of paths in $\mathcal{B}(n)$ with exactly $j$ valleys, 
where $k$ of them are $(-1)$-valley. Now, a path $P\in \mathcal{B}_{j,k}(n)$ can be decomposed as
\begin{align*}
P=U^{s_0}\Delta _{t_1}U^{s_1}\Delta _{t_2}D^{r_1}U^{s_2}\cdots \Delta _{t_{j-1}}D^{r_{j-2}}U^{s_{j-1}}\Delta _{t_{j}}D^{r_{j-1}}\Delta _{t_{j+1}},
\end{align*}
where $r_i\in \{0,1\}$, $t_i\geq 1$, $s_i\geq 0$, and with the additional property that there are exactly $k$ indices $i$ for which $r_i=1$. 

There are $n-k$ 
South-East steps that belong to one of the $j+1$ pyramids in the path. So, we can represent the possible choices of the $t_i$ as an integer composition of 
$n-k$ into $j+1$ parts in $\binom{n-k-1}{j+1-1}=\binom{n-k-1}{j}$ ways. This means that setting $t_i=1$ for all $i$, in the spirit of Proposition~\ref{propbn}, 
the Narayana numbers $N(j,k+1)$ should correspond to the number of $(-1)$-Dyck paths of semi-length $j+1+k$ containing exactly $j$ valleys and $k\leq j-1$ $(-1)$-valleys where the last valley is at ground level. That is $|\mathcal{B}_{j,k}(j+k+1)|=N(j,k+1)$ for $j>0$.

\end{remark}

\begin{theorem} The total number of paths in $\D_{-1}(n)$ is given by
\begin{align*}
r(n)=\sum_{k=0}^n\sum_{i=0}^{n-k-1}\binom{n-k-1}{i}q^{(i)}(k),
\end{align*}
where
\begin{align*}
q^{(i)}(n)=\sum_{n_1+n_2+\cdots+n_i=n}b(n_1)b(n_2)\cdots b(n_i).
\end{align*}
\end{theorem}
\begin{proof}
Recall that $\ell(P)$ denotes the semi-length of a path $P$. 
Let us denote by $\mathcal{Q}^{(i)}(n)$ the set of $i$-tuples $(P_1,\ldots ,P_i)$ of paths $P_j\in \mathcal{B} =\bigcup _{m\geq 0}\mathcal{B}(m)$, 
such that $\ell \left (P_1\right )+\cdots+\ell \left (P_i\right )=n$. It is clear that $\left |\mathcal{Q}^{(i)}(n)\right |=q^{(i)}(n)$. Note that the empty path $\lambda \in \mathcal{B}$. Let $\mathcal{C}_{i}(n)$ be the set of integer compositions of $n$ with $i$ parts. The cardinality of this set is given by the binomial coefficient $\binom{n -1}{i-1}$.\\
Let $\mathcal{QC}(n)$ be the set of $(2i+1)$-tuples $(c_1,P_1,\dots, c_i,P_i,c_{i+1})$ such that the element \linebreak $((P_1,\dots ,P_i),(c_1,\dots ,c_{i+1}))$ is in 
$ \mathcal{Q}^{(i)}(j)\times \mathcal{C}_{i+1}(n-j)$. (Note that $\mathcal{QC}(n)$ is isomorphic to 
$\bigcup _{i,j}( \mathcal{Q}^{(i)}(j)\times \mathcal{C}_{i+1}(n-j))$.) We now consider the function 
\begin{align*}\varphi :\mathcal{QC}(n)\longrightarrow \mathcal{D}_{-1}(n),
\end{align*}
defined by 
\begin{equation*}
\varphi \left (\left(c_1,P_1,c_2,P_2,\dots ,c_i,P_i,c_{i+1}\right )\right )=U^{c_1}M_1U^{c_2}\cdots M_iU^{c_{i+1}}D^{g},\end{equation*}
where the integer $g\geq c_{i+1}$ is the number of necessary down-steps to reach the $x$-axis, and $M_j$ is given by 
\begin{align*}M_j=\begin{cases}
D^{c_j},& \text{ if } P_j=\lambda; \\
P_j,& \text{ if } P_j=\Delta;\\
P_jD,& \text{ otherwise}.
\end{cases}\end{align*}
 Figure~\ref{fig:exBij} depicts two examples on the application of the function $\varphi$. 
\pagebreak

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=1.06]{ExBijDb}
 \caption{Function $\varphi$ applied to the vectors $(c_1,\Delta ,c_2,\lambda ,c_3)$ and $(c_1,P_1,c_2)$.}
 \label{fig:exBij}
\end{figure}
For the remaining part of this proof we use $\Delta _0=\lambda$. 
We define  $\phi$ from $\mathcal{D}_{-1}(n)$ to $ \mathcal{QC}(n)$ via the Algorithm~\ref{ReverseFunction} below. 
\begin{algorithm}[bh]
\begin{enumerate}[(1) ]
\item \label{AlgStep1} Let $i=1$.
 \item \label{AlgStep2} If there are $(-1)$-valleys, go to step (3), else, the path is non-decreasing, and 
 for some  integers $s_m\geq 0$, $g\geq 0$, and $t_m>0$,
 it can be decomposed as
 \begin{align*}P = U^{s_0}\Delta _{t_1}U^{s_1}\Delta _{t_2}\cdots U^{s_{j-1}}\Delta_{t_j}\Delta _{t_{j+1}}D^g.
 \end{align*}
 \begin{itemize}
 \item If no valleys, that is $j=s_0=g=0$, then \textbf{return} the vector $(t_1)$. 
 \item If there is just one valley, that is $j=1$, set
 \begin{align*}
 (s_0',t_1')=\begin{cases}(s_0,t_1),& \text{ if } s_0>0;\\
 (t_1,0),& \text{otherwise};
 \end{cases}
 \end{align*} 
 and then \textbf{return} the vector $(s_0',\Delta _{t'_1},t_2)$.
 \item In the general case, set 
 \begin{align*}
 (s_m',t_{m+1}')=\begin{cases}(s_m,t_{m+1}),& \text{ if }s_m>0;\\
   (t_{m+1},0),&\text{otherwise};
 \end{cases}
 \end{align*}
for $m<j$ and then \textbf{return} the vector $(s_0',\Delta _{t_1'},s_1',\dots ,\Delta _{t_j'},t_{j+1}).$
 \end{itemize}
 
 \item \label{AlgStep3} Find the \textbf{rightmost} occurrence of an $(-1)$-valley, that is, a subpath of the form $D\Delta _k{\color{red}{D}}U$, 
 with $k>0$. Denote the height of this valley as $h_i$. Decompose the path $P$ as $P=\widetilde{P}_0P_i{\color{red}{D}}\widetilde{P}_1$, where $P_i$ is the maximal subpath that is a Dyck path to 
 the left of the aforementioned $(-1)$-valley. Notice that $P_i$ ends on $D\Delta _k$ and so, it belongs to $\mathcal{B}$. Let $\hat{P}_0=\widetilde{P}_0D^{h_i+1}$ and $\hat{P}_1=\widetilde{P}_1D^{-h_i}$, where $D^{-r}$ means deleting the last $r$ South-East steps of the path. By assumption, the path 
 $\hat{P}_1$ is non-decreasing: go to step (\ref{AlgStep2}) using $\hat{P}_1$ and call the returned tuple $\tau _1$. Increase the value of $i$ by one and go to step (\ref{AlgStep2}) with the path $\hat{P}_0$ and call the returning tuple $\tau _0$. \textbf{Return } $(\tau _0,P_i,\tau _1)$.
\end{enumerate}
\caption{Function $\phi$}
\label{ReverseFunction}
\end{algorithm}
\pagebreak

We now give an example of the application of the Algorithm~\ref{ReverseFunction}. Consider, for instance, the path given in Figure~\ref{fig:expro}. 
First of all, search for the rightmost $(-1)$-valley (in the first case, it is denoted by dashed circle after $P_1$), they are decorated by a red circle around them, 
the algorithm applied to $\hat{P}_1=UD$ (where $\widetilde{P}_1=UDD$) gives $\tau _1=(1)$. We extract the path $P_1$ and we locate the next $(-1)$-valley, the right part on this instance, 
given by $UDUDU$, corresponds to $\tau _1=(1,\lambda,1,\lambda,1)$, and the left part of $P_2$ corresponds to $(1,\Delta _1,1)$, and so the whole path is 
encoded by the vector $(1,\Delta _1,1,P_2,1,\lambda,1,\lambda,1,P_1,1)$.

\begin{figure}[H]
 \centering
 \includegraphics[scale=0.95]{phiInverse}
 \caption{Example inverse function.}
 \label{fig:expro}
\end{figure}
\noindent Using these decompositions, we show by induction that $\phi\circ \varphi |_{\mathcal{QC}_k(n)}=id_{\mathcal{QC}_k(n)}$ and 
$\varphi\circ \phi |_{\mathcal{B}_k(n)}=id_{\mathcal{B}_k(n)}$ for every $k\geq 0$. These equalities and the functionality of $\phi$, 
given by choosing the paths $P_i$ in a \textbf{maximal} way, imply that $\varphi$ is a bijection and $\phi$ is its inverse.\\
Let $S(k)$ be the statement 
\begin{align*}\phi\circ \varphi |_{\mathcal{QC}_k(n)}=id_{\mathcal{QC}_k(n)} \text{\quad and \quad } \varphi\circ \phi |_{\mathcal{B}_k(n)}=id_{\mathcal{B}_k(n)}.
\end{align*}
For the basis step, $S(0)$, first notice that if $P\in \mathcal{B}_0(n)$, then the Algorithm~\ref{ReverseFunction} Part~\eqref{AlgStep2} 
guarantees that $\phi (P)$ contains only paths of the form $\Delta _t$ for $t\geq 0$. On the other hand, $\varphi $ returns a path without 
$(-1)$-valley when given a tuple $\tau \in \mathcal{QC}_0(n)$ by definition of the $M_j$'s, 
and so the functions and their compositions are well defined when restricted to 
$\mathcal{B}_0(n)$ and $\mathcal{QC}_0(n)$. Let $P=U^{s_0}\Delta _{t_1}\cdots \Delta _{t_i}\Delta_{t_{i+1}}D^g \in \mathcal{B}_0(n)$, 
using Algorithm 1 we get $\phi (P)=(s_0',\Delta _{t_1'},\dots ,\Delta _{t_i'},t_{i+1} )$. 
\clearpage

Now, we have
\[\varphi (\phi (P))=\varphi (s_0',\Delta _{t_1'},\dots ,\Delta _{t_i'},t_{i+1})=U^{s_0'}M_1\cdots M_iU^{t_{i+1}}D^{g'},\] with 
$M_m=D^{s'_{m-1}}=D^{t_m}$ if $t'_m=0$ and $s_{m-1}'=t_m$, or $M_m=\Delta _{t'_m}=\Delta _{t_m}$ if $s_{m-1}>0$, for $1\leq m\leq i$. 
This gives $\varphi (\phi(P))=P$.\\
Let $\tau = (c_1,\Delta _{t_1},\dots ,c_i,\Delta _{t_i},c_{i+1})$ with $c_m>0$ and $t_m\geq 0$, then 
\begin{equation*}
\varphi (\tau )=U^{c_1}M_1\cdots U^{c_i}M_iU^{c_{i+1}}D^g,\end{equation*}
where
\[M_m=\begin{cases}D^{c_m},& \text{ if }t_m=0;\\ \Delta _{t_m}, & \text{otherwise;} \end{cases}\]
and let $1\leq x_1<x_2<\cdots <x_q\leq i$ be such that $t_{x_m}=0$, that is the paths $\Delta_{t_{x_m}}$ in $\tau$ that are of the form 
$\Delta _0=\lambda$. Notice that $c_m>0$ and the definition of $M_m$ imply that either $U^{c_m}M_{m}=\Delta _{c_m}$ exactly for $t_m=0$ or $U^{c_m}\Delta _{t_m}$ for $t_m>0$, which allows us to decompose $\varphi (\tau)$ as 
\begin{align*}
\varphi(\tau )=\left (U^{c_1}\Delta _{t_1}\cdots U^{c_{x_1-1}}\Delta _{t_{x_1-1}}\right )U^0\Delta _{c_{x_1}}\cdots U^0\Delta _{c_{x_q}}\left (U^{c_{x_q+1}}\Delta _{t_{x_q+1}}\cdots \Delta _{t_i}\right )\Delta _{c_{i+1}}D^{g-c_{i+1}},
\end{align*}
where every pyramid in the decomposition is non-empty and so the decomposition is unique. We now have that $\phi (\varphi (\tau ))=(c_1,\Delta _{t_1},\dots ,c_{x_1-1},\Delta _{t_{x_i-1}},c_{x_1},\lambda ,\dots ,c_{x_q},\lambda ,\dots,c_{i+1})=\tau$.\\
For the inductive step $S(k)$, we assume that we have the desired equalities for $\ell <k$. Notice that any tuple $\tau \in \mathcal{QC}_k(n)$ 
can be decomposed as $\tau =(\tau _0,P_1,\tau _1)$ with $\tau _0$ containing $\ell <k$ paths that are not pyramids, $P_1\neq \Delta _t$ for any 
$t\geq 0$, and $\tau _1 \in \mathcal{QC}_0(n')$. Notice, further, that 
\begin{align*}
\varphi ((\tau _0,P_1,\tau _1))=\varphi (\tau _0)D^{-}P_1D\varphi (\tau _1)D^{g_2},
\end{align*}
where $\varphi (\tau _0)D^{-}$ means deleting the South-East steps suffix of $\varphi (\tau _0)$. By the recursive step in the 
Algorithm~\ref{ReverseFunction}, we have that $\phi (\varphi (\tau ))=\tau$ by using the inductive hypothesis. Analogously, we can decompose a path as 
in the recursive step of Algorithm~\ref{ReverseFunction}, and the inductive hypothesis give $\varphi (\phi (P))=P$.
\end{proof}

Proposition~\ref{NumberPathQn} is a direct consequence of the decomposition given in the proof of Theorem~\ref{teodnegativo}. The first result follows
from Figure~\ref{Fig4} and the second result uses the first part of this proposition and the decomposition $UTD$, $U\Delta DT,$ or $UQDT$ as given in the proof
of Theorem~\ref{teodnegativo}.

\begin{proposition}\label{NumberPathQn} If $n>1$, then these hold
\begin{enumerate}
\item If $q_n=|\Q_n|$, then 
 \begin{align*}
 q_n=2 q_{n-1}+q_{n-2}+q_{n-3}+\sum _{i=2}^{n-4} q_{i} (q_{n-i-1}-q_{n-i-2})+1,
 \end{align*}
for $n>3$, with the initial values $q_1=0$, $q_2=1$, and $q_3=3$.

\item If $r(n)=|\D_{d}(n)|$, then 
\begin{align*}
r(n)=3 r(n-1)-r(n-2)+q_{n-2}+\sum _{i=2}^{n-3} q_{i} (r(n-i-1)-r(n-i-2)), 
\end{align*}
for $n>3$, with the initial values $r(1)=1$, $r(2)=2$, and $r(3)=5$.
\end{enumerate}
\end{proposition}

The generating function of the sequence $r(n)$ is algebraic of order two, then $r(n)$ satisfies a recurrence relation with polynomial coefficients; see~\cite[Proposition 4]{Ban}. This can be automatically solved with implementation of Kauers in \emph{Mathematica}~\cite{Kau}. In particular we obtain that $r(n)$ satisfies the recurrence relation:
 \begin{multline*}
 2nr(n) - 4nr(n+1) + (12 + 5 n)r(n+2) - 4(15 + 4 n)r(n+3) \\
 + 10(9 + 2 n)r(n+4) - 2(21 + 4 n)r(n+5) + (6 + n)r(n+6)=0, \quad \text{ with } n \geq 6
 \end{multline*}
and the initial values $r(0)=0, r(1)=1, r(2)=2, r(3)=5, r(4)=14$, and $r(5)=41$.

In Theorem~\ref{AsymptoticApproximationr(n)} we give an asymptotic approximation for the sequence $r(n)$. To accomplish this goal, we use the singularity 
analysis method to find the asymptotes of the coefficients of a generating function (see, for example,~\cite{flajolet} for the details).

We recall that in literature $f_n \sim g_n$ means that $f_n$ and $g_n$ are asymptotic equivalent. That is, $f_n/g_n \to 1$ as $n \to \infty$. 

\begin{theorem} \label{AsymptoticApproximationr(n)} If $\rho$ is the smallest real positive root of $1 - 4 x + 2 x^2 + x^4$, then 
the number of $(-1)$-Dyck paths has this asymptotic approximation
\begin{align*}
r(n)\sim \frac{\rho^{-n}}{\sqrt{n^3\pi}}\cdot \dfrac{\sqrt{\rho(4-4\rho-4\rho^3)}}{4(-1+4\rho-2\rho^2)},
\end{align*}
where $\rho$ is called the dominant singularity of the generating function $L(x)$.
\end{theorem}

\begin{proof}
 From a symbolic computation we find that
\begin{align*}
\rho=\frac{1}{3} \left(-1-\frac{4\ 2^{2/3}}{\sqrt[3]{13+3 \sqrt{33}}}+\sqrt[3]{2 \left(13+3
 \sqrt{33}\right)}\right)\approx 0.295598.
 \end{align*}

From the expression given in~\eqref{LxForD1} for $L(x)$ we have
\[
L(x)=\frac{-1+4x-3x^2}{2 (1 - 4 x + 2 x^2)} + \frac{\sqrt{1 - 4 x + 2 x^2 + x^4}}{2 (1 - 4 x + 2 x^2)}
\sim (\rho-x)^{1/2} \frac{\sqrt{\rho(4-4\rho-4\rho^3)}}{2(1-4\rho+2\rho^2)} \ \  \text{ as } x\to \rho^-.
\]
Therefore,
\begin{equation*}
r(n)\sim \frac{n^{-1/2-1}}{\rho^n(-2\sqrt{\pi})} \frac{\sqrt{\rho(4-4\rho-4\rho^3)}}{2(1-4\rho+2\rho^2)}= \frac{\rho^{-n}}{\sqrt{n^3\pi}}
\frac{\sqrt{\rho(4-4\rho-4\rho^3)}}{4(-1+4\rho-2\rho^2)}. \qedhere
\end{equation*}
\end{proof}

\section{The area of the \texorpdfstring{$(-1)$}{(-1)}-Dyck paths}

In this section we use generating functions and recursive relations to analyze the distribution of the area of the paths in the set of restricted
$(-1)$-Dyck paths. We recall that the \emph{area} of a Dyck path is the sum of the absolute values of $y$-components of all points in the path.
We use $\area(P)$ to denote the area
of a path $P$. From Figure~\ref{Example} on Page \pageref{Example}, we can see that $\area(P)=70$. We use $a(n)$
to denote the total area of all paths in $\D_{-1}(n)$. In Theorem~\ref{GFAreaDDyckPath} we give a generating function for the sequence $a(n)$.
We now introduce a bivariate generating function depending on this previous parameter and $\ell(P)$ (the semi-length of $P$). So,
 \begin{align*}
 A(x, q):=\sum_{P\in \D_{-1}}x^{\ell(P)}q^{\area(P)}.
 \end{align*}
Let $\Q \subset \D_{-1}(n)$ be the set formed by all paths having at least one valley, where
the last valley is at ground level; let $\Q_n\subset \Q$ be the set formed by all paths of semi-length $n$, and let $q_n=|\Q_n|$.

\begin{theorem}\label{GFAreaDDyckPath}
The generating function for the sequence $a(n)$ is given by
\begin{align*}
V(x)&=\sum_{n\geq 0} a(n)x^n=\frac{b(x) - c(x)\sqrt{1-4x+2x^2+x^4}}{(1- x)^2 (1 - 4 x + 2 x^2)^3 (1 - 3 x - x^2 - x^3)},
\end{align*}
where
\begin{align*}
b(x)&=2 x - 23 x^2 + 107 x^3 - 262 x^4 + 359 x^5 - 256 x^6 + 82 x^7 -
 5 x^8 - 10 x^9 + 6 x^{10},\\
c(x)&=x - 10 x^2 + 41 x^3 - 89 x^4 + 108 x^5 - 73 x^6 + 18 x^7 + 2 x^8.
 \end{align*}
\end{theorem}

\begin{proof}
From the decomposition $UD, \, UTD, \, U\Delta DT,$ or $UQDT$ given in the proof of Theorem~\ref{teodnegativo} we obtain the functional equation
\begin{align}\label{eqA1}
A(x,q)=xq+xqA(xq^2,q)+ E(x,q)A(x,q) + xqB(xq^2,q)A(x,q),
\end{align}
where $E(x,q):=\sum_{j\geq 1}x^jq^{j^2}$ and $B(x,q):=\sum_{P\in \Q}x^{\ell(P)}q^{\area(P)}$.
Note that $E(x,q)$ corresponds to the generating function that counts the total number of non-empty pyramids in the given decomposition.\\
From the decomposition given in Figure~\ref{Fig4}, we obtain the functional equation
\begin{align}\label{eqB1}
B(x,q)=E(x,q)^2+E(x,q)B(x,q)+xqB(q^2x,q)B(x,q) + xqB(q^2x,q)E(x,q).
\end{align}
Let $M(x)$ be the generating function of the total area of the $(-1)$-Dyck paths in $\Q$. From the definition of $A(x,q)$ we have
 \begin{align*}
 V(x)=\left.\frac{\partial A(x,q)}{\partial q}\right|_{q=1}.
 \end{align*}
Substituting $x$ by $xq^2$ in~\eqref{eqB1}, and then differentiating with respect to $q$ and taking $q=1$, we obtain
\begin{multline}\label{eqW}
W(x):=\left.\frac{\partial B(xq^2,q)}{\partial q}\right|_{q=1}=\frac{2(3-x)x^2}{(1-x)^4}+\frac{(3-x)x}{(1-x)^3}Q(x) + \frac{x}{1-x}\left(W(x) + 2x \frac{\partial Q(x)}{\partial x}\right)\\ 
+ 3xQ(x)^2 + x Q(x)\left(W(x) + 4x \frac{\partial Q(x)}{\partial x} \right) + xQ(x)\left(W(x)+ 2x\frac{\partial Q(x)}{\partial x}\right) \\
 + \frac{3x^2}{1-x}Q(x) + \frac{x^2}{1-x}\left(W(x) + 4x \frac{\partial Q(x)}{\partial x} \right) + \frac{x^2(3-x)}{(1-x)^3}Q(x),
\end{multline}
 where $Q(x):=Q(x,1)$ and $Q(x,y)$ is the generating function given in~\eqref{gFunQ} on Page \pageref{gFunQ}.

Now, differentiating~\eqref{eqA1} with respect to $q$ and then taking $q=1$ we obtain,
 \begin{multline}\label{eqA2}
V(x)=x + xL(x) + x\left(V(x) + 2x\frac{\partial L(x)}{\partial x}\right) + \frac{x(x+1)}{(1-x)^3}L(x)\\+\frac{x}{1-x}V(x) + xQ(x)L(x) + x W(x) L(x) + xQ(x)V(x).
\end{multline}
Solving~\eqref{eqW} for $W(x)$ and substituting into~\eqref{eqA2} and then solving the resulting expression for $V(x)$ we obtain the desired result.
\end{proof}

The first few values of the series of $V(x)$ are
 \begin{align*}
V(x)= \sum_{n\geq 1}a(n)x^n
 &=x + 6 x^2 + 29 x^3 + 130 x^4 + 547 x^5 + 2198 x^6 + 8551 x^7 % + 32508 x^8 
 + \cdots.
\end{align*}

We now give a recursive relation for $a(n)$. Again for the sake of simplicity, the proof here is based on a geometric decomposition of the paths. So, we avoid some details. However, in~\cite{FlorezMansourRamirez} there are detailed proofs of Proposition~\ref{AreaPart1} and Theorem~\ref{AreaPart2}. We recall that $q_n=|\Q_n|$ and that for simplicity we use $r(n)$ instead of $r_{-1}(n)$. 

The following two results may follow as a direct application of~\eqref{eqB1}. However, we include here a different combinatorial proof. 

\begin{proposition}\label{AreaPart1} If $A_n$ with $n\ge 1$ is the total area of all paths in $\Q_n$, then 
 \begin{multline*}A_n=2 A_{n-1}+A_{n-2}+2 A_{n-3}+q_{n}-q_{n-1}+2n q_{n-2} +2(n-5) q_{n-3}+4 n^2-14 n+13+\\
 \sum _{i=2}^{n-4} 2(A_{i}+i q_{i} +i(i+1)) (q_{n-i-1}-q_{n-i-2}), \quad \text{with } n>4,
\end{multline*}
and the initial values $A_1=0$, $A_2=2$, $A_3=13$, and $A_4=58$.

\end{proposition}

\begin{proof}
From Figure~\ref{Fig4} we know that a path in $\Q_{n}$ can be decomposed in one of these four cases; $\Delta_i\Delta_{n-i}$, $\Delta_iQ$, $XQY\Delta_{i}$, $XQ^{\prime}YQ$ where $Q, Q^{\prime} \in \Q$

\textbf{Case 1}. The area of $\Delta_i\Delta_{n-i}$ is $i^2+(n-i)^2$. Since for a fixed $i \in \{1, 2, \dots, n-1\}$, there is exactly one path of the form 
$\Delta_i\Delta_{n-i}$ in $\Q_{n}$, we have that the total area of this type of paths is $\sum_{i=1}^{n-1} (i^2+(n-i)^2)=n(n-1) (2 n-1)/3$.

\textbf{Case 2}. The area of $P_i:=\Delta_iQ$ is $i^2+A_{n-i}$. Since for every $i \in \{1,2, \dots, n-2\}$ there are $q_{n-i}$ paths of the form $P_i$, 
we have that the total area of all paths of the form $P_i$ is given by $i^2 q_{n-i}+A_{i}$. Therefore, the total area of this type of paths is 
$\sum_{i=1}^{n-2} i^2 q_{n-i}+\sum_{j=2}^{n-1}A_{j}$.

\textbf{Case 3}. For a fixed $i$, the area of a path of the form $XQ^{\prime}YQ^{\prime\prime}$ is given by $2i+1+A_i+A_{n-i-1}$, where $Q^{\prime} \in \Q_{i}$, 
$Q^{\prime\prime} \in \Q_{n-i-1}$ and $i \in \{2, 3, \dots, n-3\}$. Note that for a fixed $i$ and a fixed $Q \in \Q_{n-i-1}$ there $q_i$ paths of the form $XQ^{\prime}YQ$ with $Q \in \Q_{i}$. This implies that for a fixed 
$i \in \{2, 3, \dots, n-3\}$ the total area of this type of paths is $A_{n-i-1} q_{i} +(2i+1) q_{i} q_{n-i-1} + A_i q_{n-i-1}$. We conclude for $i$ varying from $2$ to $n-3$, we obtain that the total area of this type of paths is 
\[\sum_{i=2}^{n-3} A_{n-i-1} q_{i}+\sum_{i=2}^{n-3} ((2i+1) q_{i} q_{n-i-1}+A_i q_{n-i-1}).\]

\textbf{Case 4}. The area of $H_i:=XQ_{\ell}Y\Delta_{i}$ is given by area of $\Delta_{i}$ (which is $i^2$) plus the area of $XQ_{\ell}Y$ 
(this is given by $A_{\ell}$, the area of $Q_{\ell}$, plus $2i+1$ which is the area of the trapezoid generated by $X$ and $Y$). Since for every 
$i \in \{1,2, \dots, n-3\}$ there are $q_{n-i-1}$ paths of the form $H_i$ with $Q \in \Q_{n-i}$, we conclude that the total area of this type of paths is 
\begin{align*}
\sum_{i=1}^{n-3} i^2 q_{n-i-1}+\sum_{i=2}^{n-2} ((2i+1) q_{i} + A_i).
\end{align*}
Adding the results from Cases 1-4, we obtain that the recursive relation for the area $A_n$ is given by
\begin{multline*}
A_n=\sum _{i=1}^{n-1} \left(i^2+(n-i)^2\right)+\sum _{i=1}^{n-2} i^2 q_{n-i}+\sum _{i=2}^{n-1} A_{i}+\sum _{i=2}^{n-3} (2 i+1) q_{i} q_{n-(i+1)}+\sum _{i=2}^{n-3} A_{i} q_{n-(i+1)}+\\
\sum _{i=2}^{n-3} A_{i} q_{n-(i+1)}+\sum _{i=2}^{n-2} A_{i}+\sum _{i=1}^{n-3} i^2 q_{n-(i+1)}+\sum _{i=2}^{n-2} (2 i+1) q_{i}.
\end{multline*}
Subtracting $A_n$ from $A_{n+1}$ and simplifying we have
 \begin{multline*}A_n=2 A_{n-1}+A_{n-2}+2 A_{n-3}+(2 n-5) q_{n-3}+(2 n-4) q_{n-2}+q_{n-1}+4 n^2-14 n+15+\\
 \sum _{i=2}^{n-4} (2 A_{i}+(2 i+1) q_{i}) (q_{n-i-1}-q_{n-i-2})+\sum _{i=2}^{n-3} \left(2 i^2-2 i+1\right) (q_{n-i}-q_{n-i-1}).
\end{multline*}
We now rearrange this expression to obtain $q_n$ (see the expression within brackets) given in Proposition~\ref{NumberPathQn}

 \begin{multline*} A_n=2 A_{n-1}+A_{n-2}+2 A_{n-3}+(2 n-6) q_{n-3}+(2 n-4) q_{n-2}-q_{n-1}+4 n^2-14 n+13+\\
 \sum _{i=2}^{n-4} 2( A_{i}+ i q_{i}) (q_{n-i-1}-q_{n-i-2})+\sum _{i=2}^{n-3} 2\left( i^2- i\right) (q_{n-i}-q_{n-i-1}) \\
+[2 q_{n-1}+q_{n-2}+q_{n-3} +\sum _{i=2}^{n-4} q_{i} (q_{-i+n-1}-q_{-i+n-2})+1].
\end{multline*}
After some simplifications we obtain the desired recursive relation.
\end{proof}

The proof of the following theorem is similar to the proof of Proposition~\ref{AreaPart1}. We recall that 
 $r(i)=|\D_{-1}(i)|$ and $q_{j}=|\Q_{j}|$. 

\begin{theorem} \label{AreaPart2} If $a(n)$ is the total area of all paths in $\D_{-1}(n)$, for $n\ge 1$, then $a(n)$ satisfies the recursive relation 
\begin{multline*}
a(n)=3 a(n-1)-a(n-2)+A_{n-2}+2(n-1) q_{n-2}+2 n r(n-1)+2(3-n) r(n-2)\\
-4 r(n-3)+(n-1)^2+ \sum _{i=3}^{n-2} q_{i-1} (a(n-i)-a(n-i-1))\\
+\sum _{i=3}^{n-2} \left(A_{i-1}+(2 i-1) q_{i-1}+i^2\right) (r(n-i)-r(n-i-1)).
\end{multline*}
\end{theorem}
 
\begin{proof} First of all, we note that a path in $\D_{-1}(n)$ can be decomposed as $XQ_1Y$, $\Delta_iQ_{n-i}$, and $XQ^{\prime}YD$, where $Q_{j}, D \in \D_{-1}$, and $Q^{\prime} \in \Q_{j}$.
This decomposition gives these three cases to consider. 

\textbf{Case 1}. The area of $XQY$ is $(2n-1)+ a(n-1)$, where $a(n-1)$ is the area of $Q \in \D_{-1}(n-1)$ and $2n-1$ is the are of the trapezoid generated by $X$ and $Y$. This gives that the total area of all paths of the form $XQY$ with $Q \in \D_{-1}(n-1)$ is $(2n-1)r(n-1)+ a(n-1)$.

\textbf{Case 2}. The area of $K_i:=X^iY^iQ_{\ell}$ is $i^2+a(n-i)$, where $Q_{\ell}\in \D_{-1}(n-i)$. Since for a fixed $i \in \{1,2, \dots, n-1\}$ 
there are $r(n-i)$ paths of form $K_i$, we conclude that the total area of all these paths is 
$\sum_{i=1}^{n-1} i^2 r(n-i)+a(n-i)$.

\textbf{Case 3}. The area of $M_i:=XQ^{\prime}YD$ is $((2i+1) + A_i+ a(n-i-1)$, where $Q^{\prime} \in \Q_{i}$ and $D \in\D_{-1}(n-i-1)$. 
Note that for a given path $D \in\D_{-1}(n-i-1)$, there are as many paths of the form $XQ^{\prime}YD$ as paths in $\Q_{i}$. It is easy to see that for a fixed $i \in \{2, 3, \dots, n-2\}$ there are $r(n-i-1)$ subpaths of the form $XQ^{\prime}Y$. Note that $X$ and $Y$ give rise
to a trapezoid, where the two parallel sides have lengths $2i$ and $2i+2$, giving rise to an area of $2i+1$. So, the contribution to the area given by
the first subpaths of the form $XQ^{\prime}Y$ is equal to the area of the trapezoids plus the area of all paths of the form $Q^{\prime}$ (these are on top of
the trapezoids). Thus, the area of a trapezoid multiplied by the total number of the paths of the form $Q^{\prime}$ plus the area of all paths of the form
$Q^{\prime}$ and then all of these multiplied by the total number of paths of the form $D$. Thus, the contribution to the area given by the first subpaths
of the form $XQ^{\prime}Y$ (overall paths of the form $M_i$ for a fixed $i$), is $((2i+1) q_{i} r(n-i-1) + A_i r(n-i-1))$.\\
We conclude that the total area of this type of paths is 
\begin{align*}
\sum_{i=2}^{n-2} A_{i} r(n-i-1)+\sum_{i=2}^{n-2} (2i+1) q_{i} r(n-i-1).
\end{align*}
Adding the results from Cases 1-3, we obtain that the recursive relation for the area $a(n)$ is given by
\begin{multline*} a(n)=a(n-1)+(2 n-1) r(n-1)+ \sum _{i=1}^{n-1} i^2 r(n-i)+\sum _{i=1}^{n-1} a(n-i) \\
+\sum _{i=2}^{n-2} q_{i} a(n-i-1)+\sum _{i=2}^{n-2} A_{i} r(n-i-1)+\sum _{i=2}^{n-2} (2i+1) q_{i} r(n-i-1).
\end{multline*}
Subtracting $a(n)$ from $a(n+1)$ and simplifying we have
\begin{multline*}
a(n)=3 a(n-1)-a(n-2)+A_{n-2}+2(n-1) q_{n-2}+(2 n-1) r(n-1)+(3-2 n) r(n-2)+(n-1)^2\\
+\sum _{i=3}^{n-2} q_{i-1} (a(n-i)-a(n-i-1))+\sum _{i=3}^{n-2} A_{i-1} (r(n-i)-r(n-i-1))\\
+\sum _{i=3}^{n-2} (2 i-1) q_{i-1} (r(n-i)-r(n-i-1))+\sum _{i=1}^{n-2} i^2 (r(n-i)-r(n-i-1)).
\end{multline*}
After some other simplifications we have that
\begin{multline*}
a(n)=3 a(n-1)-a(n-2)+A_{n-2}+2(n-1) q_{n-2}+2 n r(n-1) \\ 
+2(3-n) r(n-2)-4 r(n-3)+(n-1)^2+\sum _{i=3}^{n-2} q_{i-1} (a(n-i)-a(n-i-1))\\
+\sum _{i=3}^{n-2} \left(A_{i-1}+(2 i-1) q_{i-1}+i^2\right) (r(n-i)-r(n-i-1)).
\end{multline*}
This completes the proof.
\end{proof}

Notice that the total area of the Dyck paths (cf.~\cite{Woan}) is given by $4^n-\binom{2n+1}{n}$.

\section{Appendix. Notation table}

\begin{table}[H]
\begin{center}
\begin{tabular}{|l|c|} \hline
Concept & Notation \\ \hline
Set restricted $d$-Dyck paths  & $\D_{d}$ \\
Set restricted $d$-Dyck paths of length $n$ & $\D_n$ \\
Cardinality of $\D_{d}(n)$  & $r_d(n)$ \\
Cardinality of $\D_{-1}(n)$  & $r_{-1}(n)$ or $r(n)$ \\
Area of a path $P$ & \area(P)\\
Semi-length of $P$  & $\ell(P)$\\
Number of peaks of $P$  & $\rho(P)$\\
Number of paths in $\D_{d}(n)$ having exactly $k$ peaks. & $p_d(n,k)$ \\
Paths with the last valley at level $i$ &$\Q_{d,i}$\\
General pyramid & $\Delta$ \\
Pyramid $(XY)^k$ & $\Delta_k$\\
\hline
\end{tabular}
\end{center}
\caption{Summary of notation.} \label{tab:notation}
\end{table}

\subsection*{Acknowledgments}
The authors are grateful to the referees and the editor for the helpful suggestions and comments.
The first author was partially supported by The Citadel Foundation.
The third author was partially supported by Universidad Nacional de Colombia. The last author thanks the ANTA group at Aalto University where part of the presented work was written.
\smallskip

\bibliographystyle{SLC} 
\bibliography{Florez}
\end{document}