\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.3}{22(1)}{2015}

\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
%PACKAGES INTRODUCED BY THE AUTHOR OF THIS PAPER.
\usepackage{enumerate}
\usepackage{url}
\usepackage{amssymb, psfrag,breqn,enumitem}

\usepackage{amssymb,latexsym}
\usepackage{graphicx,psfrag}
\usepackage{fancyhdr}
%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%

\title{\bf Some Enumerations on Non-decreasing Dyck Paths}

\author{\'Eva Czabarka \\
\small Department of Mathematics\\[-0.8ex]
\small University of South Carolina\\[-0.8ex]
\small Columbia, SC, U.S.A.\\
\small\tt czabarka@math.sc.edu\\
\and
 Rigoberto Fl\'orez \thanks{Partially supported by The Citadel Foundation.} \\
\small Department of Mathematics and Computer Science \\[-0.8ex]
\small The Citadel\\[-0.8ex]
\small Charleston, SC, U.S.A.  \\
\small\tt rigo.florez@citadel.edu \\
\and
Leandro Junes\\
\small Department of Mathematics, Computer Science and Information Systems \\[-0.8ex]
\small California University\\[-0.8ex]
\small California, PA, U.S.A.\\
\small\tt junes@calu.edu
}

\date{\dateline{Dec 4, 2013}{Dec 7, 2014}{Jan 2, 2015}\\
\small Mathematics Subject Classifications: 05A15}

\begin{document}

\maketitle

\begin{abstract}
We construct a formal power series on several variables that encodes many statistics on non-decreasing Dyck paths. In particular, we use this formal power series to count peaks, pyramid weights, and indexed sums of pyramid weights for all non-decreasing Dyck paths of length $2n.$ We also show that an indexed sum on pyramid weights depends only on the size and maximum element of the indexing set.

  \bigskip\noindent \textbf{Keywords:} Non-decreasing Dyck paths, Generating functions, pyramid, valley, peak, path weight, Fibonacci numbers.
\end{abstract}

\section {\bf {Introduction}} A {Dyck word} is a word in the letters $X$ and $Y$ with as many $X$'s as $Y$'s
and in which no initial segment has more $Y$'s than $X$'s (see \cite[p.~204]{stanley}).
For example, $X X Y X Y Y$ and  $X X Y X Y Y X Y$ are Dyck words, but $X X Y X Y Y Y X$ is not.
Each Dyck word gives rise to a path (\emph{Dyck path}) in  the $xy$-plane
having only North-East steps and South-East steps (see \cite{Deutschenumeration, Deutschebiyection}).  Dyck paths
start at the origin, end on the $x$-axis, and do not cross the $x$-axis. A \emph{pyramid} of \emph{height}
$h$ is a sub-path corresponding to a sub-word of the form $X^hY^h$. A pyramid is called \emph{maximal}
if its corresponding word is not a proper sub-word of any word of the form $X^hY^h$. The \emph{weight} of a maximal
pyramid is its height and the \emph{path weight} is the sum of the weights of its
maximal pyramids (see \cite{denise}). The \emph{valleys} and \emph{peaks} of a Dyck path $P$ are the local
minima  and local maxima, respectively, of $P.$ We say that a Dyck path $P$ is \emph{non-decreasing} if the
$y$-coordinates of valleys of the path $P$ form a non-decreasing sequence (see \cite{barcucci}).

The concept of non-decreasing Dyck paths was introduced by Barcucci, Del Lungo, Fezzi and Pinzani in
 \cite{barcucci}, and several statistics about them were given  in the mentioned paper. For instance, the authors  counted the number of non-decreasing Dyck paths of length $2n$ to classify the non-decreasing Dyck
paths according their area.  Denise and Simion \cite{denise} provided explicit formulas
for the generating function on Dyck paths according to pyramid weight, length, and number of exterior points.

We provide in this paper a new formal power series on several variables
that encodes both new and some known statistics on non-decreasing Dyck paths.

We use our formal power series to provide a closed
formula for the number of non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks, and any
indexed sum of pyramid weights for all non-decreasing Dyck paths of length $2n$. We show that any
indexed sum depends only on the size and maximal element of the indexing set. We also prove that any
indexed sum is independent of whether we index the pyramids from left to right or right to left.
In particular, we prove that
the sum of the weights of all first pyramids of all non-decreasing Dyck paths of length $2n$ is the same as the
sum of the weights of all last pyramids, and that this sum is the
Fibonacci number $F_{2n}$. We also show that the sum of the weights of all second pyramids is the same
as the sum of the weights of all penultimate pyramids of all non-decreasing Dyck paths of length $2n$,
and that this sum is $F_{2n}-n.$

Our formal power series also provides new proofs for known results. In particular, we use our formal power
series to show that the number of non-decreasing Dyck paths of length $2n$ is $F_{2n-1}$ (see \cite[p.~215]{barcucci}),
and that the sum of the weights of all pyramids in all non-decreasing Dyck paths of length $2n$ is
$\left(2nF_{2n+1}+(2-n)F_{2n}\right)/5$; see \cite{integer3}.


\section {\bf {Preliminaries and Examples}}\label{preliminaries}


\subsection {Two important sequences}
The statistics on non-decreasing Dyck paths provided in this paper (see Section \ref{sec:counting})
are expressed in terms of two sequences. We restate the definitions of these sequences here to avoid
 ambiguities, and provide several identities that will be used throughout the paper. We introduce some notation first. For
 any $n \in \mathbb{N}$, we denote the finite set $\{1,\ldots,n\}$ by $[n].$

The Fibonacci sequence $\{ F_{n} \}_{n \in \mathbb{N}}$ is defined recursively by $F_{n}=F_{n-1}+F_{n-2}$ for all
$n \geq 3$, with initial conditions $F_{1}=F_{2}=1$. The first ten terms of the Fibonacci sequence are:
\[ 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad \ldots \]
The numbers $F_{n}$ can be defined for all $n \in \mathbb{Z}$. If we take $F_{0}:=0$ and $F_{-n}:=(-1)^{n+1}\,F_{n}$
for all $n \in \mathbb{N}$, then it is easy to see that the recursive relation $F_{n}=F_{n-1}+F_{n-2}$ is true for
all integers $n$. We now state several identities on generating functions involving Fibonacci numbers that
will be useful in Section \ref{sec3}.

 \begin{proposition}\label{prop:GeneraFuncFib} Let $\{ F_{n} \}_{n \in \mathbb{Z}}$ be
 the Fibonacci sequence and $z$ be an independent variable. Then,
     \begin{enumerate}
       \item $\displaystyle{\sum_{n=0}^{\infty}F_{2n}\,z^{n} = \frac{z}{1-3\,z+z^2}}$,
       \item $\displaystyle{\sum_{n=0}^{\infty}F_{2n+1}\,z^{n} = \frac{1-z}{1-3\,z+z^2}}$,
       \item $\displaystyle{\sum_{n=1}^{\infty}F_{2n-1}\,z^{n} = \frac{z\,(1-z)}{1-3\,z+z^2}}$,
       \item $\displaystyle{\sum_{n=1}^{\infty}n\,F_{2n}\,z^{n} = \frac{z\,(1-z^2)}{\left(1 -3z+z^2\right)^2}}$,
       \item $\displaystyle{\sum_{n=1}^{\infty}n\,F_{2n+1}\,z^{n} = \frac{z\,(z^2-2 z+2)}{\left(1 -3z+z^2\right)^2}}$.
    \end{enumerate}
 \end{proposition}
\begin{proof} Parts (1) and (2) are proved in Koshy \cite[p.~230]{koshy}.
We prove part (3). Part (2) can be rewritten as
\begin{eqnarray} \label{eqn:zero}
 \displaystyle{\sum_{n=1}^{\infty}F_{2n-1}\,z^{n-1} = \frac{1-z}{1-3\,z+z^2}}.
 \end{eqnarray}
If we multiply by $z$ on both sides of (\ref{eqn:zero}), then we obtain part (3).

If we take the derivative with respect to $z$ and multiply by $z$ on both sides of part (1), then it is easy to see that part (4) holds.

The proof of part (5) is similar to the proof of part (4) and we omit it. \end{proof}
A well-rounded study of the Fibonacci sequence and its many applications in nature and combinatorics can be found in \cite{koshy}.

We now consider the double sequence $\{ C_{d}(n)\}_{n,d \, \in \, \mathbb{Z}_{\geq 0}}$ given by

\begin{equation}\label{eqn:C0}
C_{d}(n)=\sum_{i=0}^{n} \binom {2d+i-1} {i} \, F_{2(n-i)}.
\end{equation}

We recall that if $d=0$ and $i \in \{0, \ldots,n \}$, then the binomial coefficients $\binom {2d+i-1} {i}$  are  $\binom {-1} {0}, \binom {0} {1}, \ldots, \binom {n-1} {n}$. Kronenburg \cite[Theorem~2.1]{Kronenburg} extends the definition of binomial coefficients to negative integers. Using Kronenburg's definition we have $\binom {-1} {0}=1$ and $\binom {i-1} {i}=0$ for $i\in \{1,\ldots,n \}$. Thus,
    \begin{equation}\label{eqn:C}
        C_{0}(n)=F_{2n}.
    \end{equation}

The double sequence (\ref{eqn:C0})  can be expressed as a sum of binomial coefficients using Riordan's identity, see \cite[p.~156]{Riordan}, as follows:
\begin{equation}\label{eqn:C1}
\displaystyle{\sum_{j=0}^{k-1} {n-j \choose j} =\sum_{j=1}^{k} F_{2j}{n-j-k \choose k-j}
=\sum_{j=0}^{k-1} F_{2(k-j)}{n-j-2k\choose j}}
\end{equation}
where $F_1=1, F_2=1, F_3=2, \ldots$. Note that Riordan \cite[p.~155]{Riordan} defines Fibonacci numbers as $F_0=1, F_1=1, F_2=2, \ldots$.
 If we take $k=m$ and $n=2m+2d-1$ in (\ref{eqn:C1}), then we obtain that for $d\ge 0$ and $m\ge 1$

\begin{equation}\label{Cdm}
C_d(m)=\sum_{j=0}^{m-1}\binom{2d+j-1}{j}F_{2(m-j)}=\sum_{j=0}^{m-1}\binom{2(m+d)-j-1}{j}.
\end{equation}

 \begin{proposition}\label{prop:ArrayT} Let $n$ and $d$ be non-negative integers. If $z$ is an independent variable, then
   \begin{enumerate}
     \item $\displaystyle{\sum_{n=0}^{\infty}C_{d}(n)\,z^{n}=\frac{z}{(1-z)^{2d}(z^{2}-3z+1)}}$,
     \item $\displaystyle{\sum_{n=d}^{\infty}C_{d-1}(n-d+1)\,z^{n}=\frac{z^{d}}{(1-z)^{2(d-1)}(z^{2}-3z+1)}}$, for $d \geq 1$.
   \end{enumerate}
 \end{proposition}
 \begin{proof} We prove part (1). It is known (see for example \cite[p.~211]{charalambides}) that the generating function of $n$-combinations of $2d$ with repetitions is \[\displaystyle{\sum_{n=0}^{\infty} {2d+n-1 \choose n} \, z^{n}= \frac{1}{(1-z)^{2d}}}. \]
 This and Proposition \ref{prop:GeneraFuncFib} part (1) imply that
 \begin{eqnarray*}
  \displaystyle{\frac{1}{(1-z)^{2d}} \frac{z} {(z^{2}-3z+1)}}&=& \displaystyle{\left(\sum_{n=0}^{\infty} {2d+n-1 \choose n} \, z^{n}\right) \left(\sum_{n=0}^{\infty}F_{2n}\,z^{n}\right)} \\
&=&\displaystyle{ \sum_{n=0}^{\infty} \left(\sum_{i=0}^{n} {2d+i-1 \choose i}F_{2(n-i)}\right) z^n }\\
&=& \displaystyle{\sum_{n=0}^{\infty} C_d (n) \, z^{n}}.
 \end{eqnarray*}
This proves part (1).

We now prove part (2). Since $d \geq 1$, part (1) implies that
\begin{equation}\label{formulaa}
\displaystyle{\sum_{n=0}^{\infty}C_{d-1}(n)}\,z^{n}=\frac{z}{(1-z)^{2(d-1)}(z^{2}-3z+1)}.
\end{equation}
Notice that $C_{d}(0)=0$, therefore multiplying both sides of (\ref{formulaa}) by $z^{d-1}$, we obtain part (2) by changing  the index of summation.
 \end{proof}

\subsection {Dyck Paths}
If a Dyck word $L$ has $n$ $X's$ and $n$ $Y's$, then we say that $L$ has \emph{length} $2n$ or \emph{semi-length} $n$. A \emph{peak} is a sub-word of the form $XY$; a \emph{valley} is a sub-word of the form
$YX$. A \emph{pyramid} of \emph{height} $h$ is a sub-word of the
form $X^hY^h$. A pyramid $\Delta$ is maximal if $\Delta$
is immediately preceded by $Y$ or is immediately followed by $X$. The word $X X (X X Y Y)X Y$ has
the maximal pyramid $X^2Y^2=X X Y Y$ of height  $2$.

A \emph{path} $P$ of length $m$ is an $(m+1)$-tuple of points in
$\mathbb{Z}_{\ge 0}\times \mathbb{Z}_{\ge 0 }$. A \emph{step} in a path $P
= (p_0,p_1, \ldots, p_m)$ is a pair of two consecutive points
$(p_{i},p_{i+1})$ for $i\in \{0, \ldots, m-1\}$. A \emph{North-East} step has the form $(p_i,p_{i+1})=
((i,j),(i+1,j+1))$. Similarly, a \emph{South-East} step has the form
$(p_i,p_{i+1})= ((i,j),(i+1,j-1))$. The \emph{altitude} of $p_{i}= (i,j)$, denoted by $alt(p_i)$, is the
component $j$. We identify a path $P= (p_0,p_1, \ldots, p_m)$ with its broken-line graph obtained by joining $p_{i}$ to $p_{i+1}$ with a line segment for $i \in \{0,\ldots,m-1\}$.

Each Dyck word $L$ gives rise to a path (\emph{Dyck path}) $P_{L}$ having only North-East steps and South-East steps.
Indeed, $X$ corresponds to a North-East step and $Y$ corresponds to  a South-East step. For instance, the Dyck word
$XXYXXYYYXY$ corresponds to the Dyck path depicted in Figure \ref{figure2} part (a).  If a Dyck word $L$ has length
$2n$, then we say that $P_{L}$ has length $2n$. A Dyck path of length $2n$ starts at the origin ($p_{0}=(0,0)$),
ends on the $x$-axis ($p_{2n}=(2n,0)$), and does not cross the $x$-axis. It is easy to see that the correspondence
$L \mapsto P_{L}$ is a bijection between the collection of all Dyck words and the collection of all Dyck paths.
It is known that the number of Dyck paths of length $2n$ is equal to the $n${th}
Catalan number $C_n$ {\cite[Corollary 6.2.3]{stanley}}. For example, the number of Dyck paths
of length $8$ is $C_{4}=14.$

\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=2.4]{DyckWordToDyckPathCombine.pdf}
\end{center}
\caption{A Dyck path of length 10.} \label{figure2}
\end{figure}

A \emph{valley} $v$ of a Dyck path $P= (p_0,p_1, \ldots, p_m)$ is a local minimum of the broken-line graph of $P$
 such that $v \neq p_{0},p_{m}$. Similarly, a \emph{peak} of $P$ is a local maximum of the corresponding broken-line graph of $P$. For the Dyck path in Figure \ref{figure2} part (a), $p_{3}$ and $p_{8}$ are valleys; and $p_{2}, p_{5}$ and $p_{9}$ are peaks.

 A \emph{pyramid} $\Delta$ of a Dyck path $P=(p_0,p_1, \ldots, p_m)$ is a tuple of the form \[(p_{r}, \ldots, p_{r+k},\ldots, p_{r+2k}), \text{ for  } k \in \mathbb{N},\]  where $(p_{r+i},p_{r+i+1})$ is a North-East step for every $i \in
\{0,\ldots,k-1\}$, and $(p_{r+j},p_{r+j+1})$ is a South-East step for every $j \in \{k,\ldots,2k-1\}$. In this case we
 say that $k$ is the \emph{weight} of the pyramid $\Delta$. We identify the pyramid $\Delta=(p_{r}, \ldots, p_{r+k},
 \ldots, p_{r+2k})$ with the simple convex polygon $C(\Delta)$ determined by the points $p_{r}, \ldots, p_{r+k},
 \ldots, p_{r+2k}$. Notice that $C(\Delta)$ is the triangle determined by the three points $p_{r}, p_{r+k}$
 and $p_{r+2k}$. We say that $\Delta$ is a \emph{maximal} pyramid of the Dyck path $P$, if $C(\Delta) \subseteq C(\Delta')$ implies that $C(\Delta)=C(\Delta')$ for any pyramid $\Delta'$ of $P$. For instance, in Figure \ref{figure2} part (b) the pyramids
 $$\Delta_{1}=(p_{1},p_{2},p_{3}), \quad \Delta_{2}=(p_{3},p_{4},p_{5},p_{6},p_{7}) \quad \text{ and } \quad \Delta_{3}=(p_{8},p_{9},p_{10})$$
 (shaded in light grey) are maximal, but
 $\Delta_{4}=(p_{4},p_{5},p_{6})$ (shaded in darker grey) is not a maximal pyramid. The weights of $\Delta_{1}, \Delta_{2}, \Delta_{3}$ and $\Delta_{4}$ are $1,\; 2,\; 1,$ and 1, respectively. The \emph{weight } of a Dyck path $P$ is the sum of the weights of all its maximal pyramids. For example, the weight of the path $P$ depicted in Figure \ref{figure2} part (b) is $1+2+1=4$.

 We label the maximal pyramids of a Dyck path $P$, from left to right, to assign positions such as
 \emph{first pyramid}, \emph{second pyramid}, \ldots, \emph{last pyramid}. For instance,
 $\Delta_{1}, \Delta_{2}$ and $\Delta_{3}$ are the first, second and last pyramids, respectively, of the Dyck
 path depicted in Figure \ref{figure2} part (b). Since $\Delta_{4}$ is not a maximal pyramid, we do not assign a position to it.

 A \emph{lifting step sequence} $M$ of a Dyck path $P=(p_0,p_1, \ldots, p_m)$ is a tuple of the form
 $(p_{r},\ldots, p_{r+s})$, for $s \in \mathbb{Z}_{\geq 0}$, such that
  \begin{enumerate}
       \item there is a maximal pyramid $\Delta=(p_{r+s},\ldots,p_{k})$ such that $\Delta$ is not the
                last pyramid of $P$,
       \item there is no North-East step of $P$ of the form $(p_{r-1},p_{r})$,
       \item  if $s \geq 1$, then $(p_{r+i},p_{r+i+1})$ is a North-East step for every
               $i \in \{0,\ldots,s-1\}$.
  \end{enumerate}
In this case we say that the lifting step sequence $M$ has \emph{length} $s$. Figure \ref{figure30} (maximal pyramids are shaded in gray) depicts the lifting step sequences $M_{1}=(p_{0},p_{1},p_{2})$, $M_{2}=(p_{4},p_{5})$ and $M_{3}=(p_{9})$ from a Dyck path of length 16.

\begin{figure} [htbp]
  \begin{center}
    \includegraphics[scale=3]{Lifting_Pyramids2.pdf}
  \end{center}
  \caption{A Dyck path of length 16 and its lifting step sequences.} \label{figure30}
\end{figure}


Let $v_{1}, \ldots, v_{t}$ be all valley points of a
Dyck path $P$. We say that $P$ is \emph{non-decreasing} if
\[alt(v_{1})\le alt(v_{2}) \le \ldots \le alt(v_{t}).\]
That is, a Dyck path is non-decreasing if the $y$-coordinates of the
local minima of the broken-line graph form a non-decreasing sequence. For instance, the Dyck path of
Figure \ref{figure30} is a non-decreasing Dyck path. The collection of all 13 non-decreasing Dyck paths of length eight is depicted in Figure \ref{figure3}. In general, the number of non-decreasing
Dyck paths of length $2n$ is the Fibonacci number $F_{2n - 1}$ \cite[Theorem 2.5]{barcucci}.


\section{Generating Functions} \label{sec3}
In this section we construct a formal power series on several variables that encodes many statistics on non-decreasing Dyck paths. Moreover, we provide an infinite-variable formal power series that encodes paths by  length and pyramid height. We also prove several identities that are used in Theorems \ref{thm:OldResults}, \ref{thm:NewResults1}, and \ref{thm:NewResults2}. That is, these formal power series are the main tools for all the counting results in Section \ref{sec:counting}.


We first construct a formal power series that encodes non-decreasing Dyck paths by the number of peaks and the weight of each of its pyramids. The following discussion leads to this.

We can view any non-decreasing Dyck path as an alternating sequence of pyramids and
lifting steps (the latter may be of zero length and not
contribute to the pyramid-weight). It is clear that any
non-decreasing Dyck-path can be viewed as such a sequence, as the
South-East steps not in any pyramid are simply the last steps that
bring the path back to the $x$-axis. See Figure \ref{figure30}.


\label{pageref1}
It is clear that we have the following conditions: The weight of any pyramid is
at least one. The length of the $i$-th lifting step sequence (the
one that  precedes the $i$-th pyramid) is any nonnegative integer;
except that we know that the last pyramid is not preceded by any lifting
sequence. Thus, a non-decreasing Dyck path $P$ with exactly $s$ peaks can be viewed as a $(2s-1)$-tuple $(m_{1},k_{1},\ldots,m_{s-1},k_{s-1},k_{s})$, where $m_{i} \in \mathbb{Z}_{\geq 0}$ is the length of the $i$-th lifting sequence and  $k_i \in \mathbb{N}$ is the weight of the $i$-th pyramid, see Figure \ref{figure4}. Notice that $s$ is the number of pyramids in the path $P$. It is clear that every path is uniquely determined by its $(2s-1)$-tuple of $k_i$ and $m_i$ numbers.

\begin{figure} [htbp]
  \begin{center}
    \includegraphics[scale=2]{sequnces.pdf}
  \end{center}
  \caption{Four non-decreasing Dyck paths of length 2(6) and their tuples of lifting steps and pyramid weights.} \label{figure4}
\end{figure}

Let $P$ be a non-decreasing Dyck path with exactly $s$ peaks, and let
\[ (m_{1},k_{1},\ldots,m_{s-1},k_{s-1},k_{s})\]
be its $(2s-1)$-tuple of alternating lifting sequences and pyramids weights.  \label{alternating} We associate to $P$ the following term on the variables $z, t_{1}, \ldots, t_{s}$:


\begin{equation}\label{formulaaprime}
term(P)=(z\,t_{s})^{k_s}\prod_{i=1}^{s-1} z^{m_i}(z\,t_{i})^{k_{i}}.
\end{equation}
That is, every pyramid of weight $k_{i}$ in $P$ is associated to $(z\,t_{i})^{k_{i}}$ and every lifting step sequence of length $m_{i}$ in $P$ is associated to $z^{m_{i}}$.

If $P$ has length $2n$, then $2\big(k_s+\sum_{j<s} (k_j+m_j)\big)=2n$. This and the term in (\ref{formulaaprime}) imply that
\begin{equation}\label{formulab}
term(P)=z^n\prod_{j=1}^{s}t_j^{k_j}.
\end{equation}
We denote by $\mathfrak{Q}_{s}$ the collection of all non-decreasing Dyck paths with precisely $s$
peaks of any length $2n$. For instance, if $s=2$, then $\mathfrak{Q}_{2}$ is
the collection of all non-decreasing Dyck paths with exactly 2 peaks of lengths
$4, 6, 8, \ldots.$ Notice that if a non-decreasing Dyck path has $s$ peaks, then its minimum length is $2s.$ A few paths in the infinite collection $\mathfrak{Q}_{2}$ are depicted in Figure \ref{figureTwoPeaks}.


\begin{figure} [htbp]
\begin{center}
\includegraphics[scale=2.2]{Two_Peaks_Together.pdf}
\end{center}
\caption{Three elements of $\mathfrak{Q}_{2}$.} \label{figureTwoPeaks}
\end{figure}

We prove in Theorem \ref{thm:NewResults1} part (1) that the number of non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks is $\binom{n+s-2}{2s-2}$. Thus, $\mathfrak{Q}_{s}$ contains $\binom{n+s-2}{2s-2}$ non-decreasing Dyck paths of length $2n$ for any $n \geq s.$
This shows that $\mathfrak{Q}_{s}$ is an infinite set for any $s \in \mathbb{N}.$


We now consider a formal power series based on $\mathfrak{Q}_{s}.$ Clearly, $\{ \mathfrak{Q}_{s} \}_{s \in \mathbb{N}}$ partitions the collection of all non-decreasing Dyck paths. For every $s \in \mathbb{N}$, we define a formal power series $Q_s(z;t_1,\ldots,t_s) $ on the variables $z, t_{1}, \ldots, t_{s}$ as follows:
\begin{equation}\label{formulac}
Q_s(z;t_1,\ldots,t_s)=\sum_{P\in \mathfrak{Q}_s}term(P).
\end{equation}
\begin{proposition}\label{prop:FinitePowerSeries}
If $Q_s(z;t_1,\ldots,t_s)$ is defined as in (\ref{formulac}), then
\begin{enumerate}
  \item $\displaystyle{Q_{s}(z;t_1,\ldots,t_{s})=\frac{z^{s}}{(1-z)^{s-1}}\prod_{j=1}^{s}\frac{t_{j}}{1-z\,t_{j}}}$,
  \item $\displaystyle{ Q_{s}(z;t_1,\ldots,t_{s})=\frac{z\,t_{s}}{(1-z)(1-z\,t_{s})} Q_{s-1}(z;t_1,\ldots,t_{s-1})}$, for all $s \geq 2$,
  \item if $q_s(n;k_{1},\ldots,k_{s})$ denotes the number of paths in $\mathfrak{Q}_{s}$ of length $2n$ for which the $i$-th pyramid has weight $k_{i} \in \mathbb{N}$, then
  \[ Q_{s}(z;t_1,\ldots,t_{s})=\sum_{(n;k_{1},\ldots,k_{s})} q_{s}(n;k_{1},\ldots,k_{s})
z^{n}\prod_{j=1}^s t_{j}^{k_{j}},\]
\item for any natural number $s$, $Q_{s}(z;1,\ldots,1)$ is the generating function of the sequence $\left\{ \binom{n+s-2}{2s-2} \right\}_{n \in \mathbb{N}}$.
\end{enumerate}
\end{proposition}
\begin{proof} We prove part (1). Using the definition of $Q_{s}(z;t_1,\ldots,t_{s})$, the term in (\ref{formulaaprime}), and the fact that every $P \in \mathfrak{Q}_{s}$ is uniquely determined by its sequence of $k_{i}$  and $m_{i}$ numbers we get that
\begin{eqnarray*}
Q_s(z;t_1,\ldots,t_s)&=&\sum_{P\in \mathfrak{ Q}_s}term(P)
				      =\sum_{(m_1,\ldots,m_{s-1};k_1,\ldots,k_s)} (zt_s)^{k_s}\prod_{i=1}^{s-1} z^{m_i}(zt_i)^{k_i}\\
                                 &=&\left(\prod_{j=1}^{s-1}\sum_{m_j=0}^{\infty} z^{m_j}\right)\left(\sum_{(k_1,\ldots,k_s)}\prod_{j=1}^{s}(zt_j)^{k_j}\right)\\
                                &=&\left(\prod_{j=1}^{s-1}\frac{1}{1-z}\right)\left(\prod_{j=1}^s\sum_{k_j=1}^{\infty} (zt_j)^{k_j}\right)
                                   =\frac{z^s}{(1-z)^{s-1}}\prod_{j=1}^{s}\frac{t_j}{1-zt_j}.
\end{eqnarray*}
This proves part (1). The proof of part (2) is immediate from part (1).

We now prove part (3). For any $s \in \mathbb{N}$ and any $(s+1)$-tuple $(n,k_{1},\ldots,k_{s}) \in \mathbb{N}^{s+1}$, it is clear that the number of paths $P \in \mathfrak{Q}_{s}$ for which $term(P)=z^n\prod_{j=1}^{s}t_j^{k_j}$ is $q_s(n;k_{1},\ldots,k_{s}).$
%(notice that there are infinitely many $(s+1)$-tuples $(n,k_{1},\ldots,k_{s})$ for which $q_s(n;k_{1},\ldots,k_{s})=0$. For instance, if $\sum_{j \leq s} k_{j} >n$, then $q_s(n;k_{1},\ldots,k_{s})=0$.)
This, the term in (\ref{formulab}) and the definition of $Q_s(z;t_1,\ldots,t_s)$ implies that
\begin{eqnarray*}
Q_s(z;t_1,\ldots,t_s)&=&\sum_{P\in \mathfrak{
Q}_s}term(P)=\sum_{(n;k_1,\ldots,k_s)} q_{s}(n;k_1,\ldots,k_s)
z^n\prod_{j=1}^s t_j^{k_j}.
\end{eqnarray*}
This proves part (3).

We prove part (4). Let $s \in \mathbb{N}$. It is easy to see from part (1) that
\begin{equation}\label{formulad}
Q_s(z,1,\ldots,1)=\frac{z^s}{(1-z)^{2s-1}}.
\end{equation}
From Stanley \cite[p.~544]{stanley1} we know that the generating function of the sequence $\big\{ \binom{n+d-i}{d} \big\}_{n \in \mathbb{N}}$ is $z^{i} / (1-z)^{d+1}$. Therefore, if we take $i=s$ and $d=2s-2$, we obtain the right hand side of (\ref{formulad}). This proves part (4).\end{proof}

We now define an infinite variable formal power series $Q(z;t_1,t_{2},\ldots)$ encoding counts for paths of
length and pyramid height by
\begin{equation}\label{formulae}
Q(z;t_{1},t_{2},\ldots)=\sum_{s=1}^{\infty}Q_{s}(z;t_{1},t_{2},\ldots,t_{s}).
\end{equation}

\begin{proposition}\label{prop:InfinitePowerSeries} Let $R(x,z)$ be the two-variable formal power series $Q(z;x,x,x,\ldots)$. Then,
 \begin{enumerate}
    \item  $R(x,z) = z\,x\,(1-z) / (1-2\,z\,x-z+x\,z^{2})$,
    \vspace{.2cm}

    \item   $R(1,z)$ is the generating function of the sequence $\{F_{2n-1}\}_{n \in \mathbb{N}}$,

    \vspace{.2cm}

    \item  $\displaystyle{\frac{\partial R(x,z)}{\partial x}\Big\vert_{x=1}}$ is the generating function of the sequence $\big\{\frac{1}{5} (2nF_{2n+1}+(2-n)F_{2n})\big\}_{n \in \mathbb{N}}$.
 \end{enumerate}
\end{proposition}
\begin{proof} We prove part (1). Proposition \ref{prop:FinitePowerSeries} part (1), and the generating function in (\ref{formulae}) imply that
 \begin{eqnarray*}
R(x,z)&=&\displaystyle{ Q(z;x,x,x,\ldots)=\sum_{s=1}^{\infty}\frac{z^s\,x^s}{(1-z)^{s-1}(1-z\,x)^{s}}}\\
&=& \displaystyle{ \frac{z\,x}{1-z\,x}\cdot\frac{1}{1-\frac{z\,x}{(1-z)(1-z\,x)}}
=\frac{z\,x\,(1-z)}{(1-z\,x)(1-z)-z\,x}}\\
&=&\frac{z\,x\,(1-z)}{1-2\,z\,x-z+x\,z^2}.
\end{eqnarray*}
This proves part (1).

We now prove part (2). Using part (1) we get that
\[
R(1,z)=\frac{z\,(1-z)}{z^2-3z+1}.
\]
This and Proposition \ref{prop:GeneraFuncFib} part (3) prove part (2).

We prove part (3). Using part (1) it is easy to see that
\begin{eqnarray} \label{eqn:one}
\frac{\partial R(x,z)}{\partial x}\Big\vert_{x=1} = \frac{z(1-z)^2}{(1-3z+z^2)^2}.
\end{eqnarray}
Proposition \ref{prop:GeneraFuncFib} parts (1), (4) and (5) imply that
\begin{eqnarray*}
\sum_{n=1}^{\infty}\frac{2nF_{2n+1}+(2-n)F_{2n}}{5}\,z^{n}&=&\frac{1}{5}\left[ \frac{2\,z\,(z^2-2 z+2)}{\left(1 -3z+z^2\right)^2} + \frac{2\,z}{1-3\,z+z^2} - \frac{z\,(1-z^2)}{\left(1 -3z+z^2\right)^2}\right]\\
&=&\frac{z\,(1-z)^2}{(1-3z+z^2)^2}.
\end{eqnarray*}
This and (\ref{eqn:one}) prove part (3).\end{proof}
If we only want to count paths with at least $l$ peaks, then we define the infinite variable formal power series $Q^{(\ge l)}(z;t_1,t_{2},\ldots)$ by
\begin{equation}\label{formulaf}
Q^{(\ge l)}(z;t_{1},t_{2},\ldots)=\sum_{s=l}^{\infty}Q_{s}(z;t_{1},\ldots,t_{s}).
\end{equation}

We now define a two-variable formal power series that will be used in Theorem \ref{thm:NewResults2}.
Let $m \in \mathbb{N}$ and  ${\mathrm I}= \{i_1,\ldots,i_m\} \subseteq \mathbb{N}$ be such that $1\le i_{1}<\cdots<i_{m}$. We consider the two-variable formal power series $R^{{\mathrm I}}(x,z)$ obtained from $Q^{(\ge i_{m})}(z;t_{1}, t_{2},\ldots)$ by substituting each variable $ t_{1},t_{2}, \ldots $ by either $x$ or $1$, where
\[
t_{l}= \begin{cases}
             x, \text{ if } l \in {\mathrm I},\\
             1, \text { otherwise.}
          \end{cases}
\]
\begin{proposition}\label{prop:InfinitePowerSeriesIndices} Let $m \in \mathbb{N}$ and  ${\mathrm I}= \{i_1,\ldots,i_m\} \subseteq \mathbb{N}$ be such that $1\le i_{1}<\cdots<i_{m}$. Then,
 \begin{enumerate}
    \item  $\displaystyle{R^{{\mathrm I}}(x,z) = \frac{x^{m}\,z^{i_{m}}\,(1-z)^{m+3-2\,i_{m}}}{(1-z\,x)^{m}\,(z^{2}-3\,z+1)}}$,
    \item  $ \displaystyle{\frac{\partial R^{{\mathrm I}}(x,z)}{\partial x}\Big\vert_{x=1}} $is the generating function of the sequence $\big\{m \,C_{i_{m}-1}(n-i_{m}+1)\big\}_{n = i_{m}}^{\infty}$.
  \end{enumerate}
\end{proposition}
\begin{proof} We prove part (1). The definition of $R^{{\mathrm I}}(x,z)$, Proposition \ref{prop:FinitePowerSeries} part (1), and the generating function in (\ref{formulaf}) imply that
\begin{eqnarray*}
R^{{\mathrm I}}(x,z) &=& \sum_{s=i_{m}}^{\infty} \left( \frac{z^{s}}{(1-z)^{s-1}}\displaystyle{\prod_{j=1}^{m}\frac{x}{1-z\,x}} \, \displaystyle{\prod_{j=1}^{s-m}\frac{1}{1-z}}  \right)\\
&=& \sum_{s=i_{m}}^{\infty} \left( \frac{z^{s}}{(1-z)^{s-1}}\,\frac{x^{m}}{(1-z\,x)^{m}} \,\frac{1}{(1-z)^{s-m}}  \right)\\
&=&\frac{x^m}{(1-z\,x)^m}\sum_{s=i_m}^{\infty}\frac{z^s}{(1-z)^{2s-m-1}}=\frac{x^{m}\,(1-z)^{m+1}}{(1-z\,x)^{m}}\sum_{s=i_m}^{\infty}\left(\frac{z}{(1-z)^{2}}\right)^{s}\\
&=&\frac{x^{m}\,(1-z)^{m+1}}{(1-z\,x)^{m}}\,\frac{z^{i_{m}}}{(1-z)^{2i_{m}}} \sum_{s=0}^{\infty}\left(\frac{z}{(1-z)^{2}}\right)^{s}\\
&=&\displaystyle{\frac{x^{m}\,(1-z)^{m+1}}{(1-z\,x)^{m}}\,\frac{z^{i_{m}}}{(1-z)^{2i_{m}}}\, \frac{1}{1-\frac{z}{(1-z)^{2}}}}\\
&=&\frac{x^{m}\,z^{i_{m}}\,(1-z)^{m+3-2i_m}}{(1-z\,x)^m(z^2-3z+1)}.
\end{eqnarray*}
This proves part (1).

We now prove part (2). Using part (1) we can see that
\begin{eqnarray*}
\frac{\partial R^{{\mathrm I}}(x,z)}{\partial x}\Big\vert_{x=1} &=&
\frac{mz^{i_m}(1-z)^{3-2i_m}}{(z^2-3z+1)}
+\frac{mz^{i_m+1}(1-z)^{2-2i_m}}{(z^2-3z+1)}\\
&=&m\,\frac{z^{i_m}}{(1-z)^{2(i_m-1)}(z^2-3z+1)}.
\end{eqnarray*}
This and Proposition \ref{prop:ArrayT} part (2) prove part (2). \end{proof}
Corollary \ref{cor:InfinitePowerSeriesIndices} is a straightforward consequence of Proposition \ref{prop:InfinitePowerSeriesIndices} part (1).
\begin{corollary}\label{cor:InfinitePowerSeriesIndices}The formal power series $R^{{\mathrm I}}(x,z)$ depends only on $m$ and $i_{m}$.  It is independent of $i_1,\ldots,i_{m-1}$.
\end{corollary}

\section{Enumerations on non-decreasing Dyck paths} \label{sec:counting}
We give in this section several counting results about non-decreasing Dyck paths. Some of them are known and we prove them here using the same generating function we use to prove the new results. That is, the infinite power series $Q_{s}(z;t_{1},\ldots,t_{s})$ defined in Section \ref{sec3} encodes several statistics for non-decreasing Dyck paths.

We start this section with a technical lemma. We recall that if $s, n, k_{1},\ldots,k_{s} \in \mathbb{N}$, then  $q_s(n;k_{1},\ldots,k_{s})$ denotes the number of paths with exactly $s$ peaks, of length $2n$, for which the $i$-th pyramid has weight $k_{i}$.
  \begin{lemma}\label{lem:technical} Let $n, m, s, i_{1},\ldots, i_{m} \in \mathbb{N}$.
      \begin{enumerate}
         \item If $z,t_{1},t_{2}, \ldots$ are independent variables, then
         \[   Q(z;t_{1},t_{2},\ldots)=\sum_{s=1}^{\infty} \sum_{(n;k_{1},\ldots,k_{s})} q_{s}(n;k_{1},\ldots,k_{s}) z^{n}\prod_{j=1}^s t_{j}^{k_{j}}.   \]
         \item $\sum_{k_{1}, \ldots, k_{s} \in \mathbb{N}} q_{s}(n;k_{1},\ldots,k_{s})$ is the number of non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks.
         \vspace{.2cm}

         \item $ \sum_{s=1}^{\infty} \sum_{k_{1}, \ldots, k_{s} \in \mathbb{N}} \; q_{s}(n;k_{1},\ldots,k_{s})$ is the number of non-decreasing Dyck paths of length $2n$.

          \vspace{.2cm}

         \item $\sum_{s, k_{1}, \ldots, k_{s} \in \mathbb{N}} (k_{1} + \ldots + k_{s}) \, q_{s}(n;k_{1},\ldots,k_{s})$ is the sum of the weights of all pyramids in all non-decreasing Dyck paths of length $2n$.

          \vspace{.2cm}
	 \item If $1\le i_{1}<\cdots<i_{m}$ denote pyramid positions in an arbitrary non-decreasing Dyck path, then
	 $\sum_{s=i_{m}}^{\infty} \sum_{k_{1}, \ldots, k_{s} \in \mathbb{N}} (k_{i_{1}} + \ldots + k_{i_{m}}) \, q_{s}(n;k_{1},\ldots,k_{s}) $ is the sum of the weights of all pyramids in positions $i_{1}, \ldots, i_{m}$ in all non-decreasing Dyck paths of length $2n$, with at least $i_m$ pyramids.
      \end{enumerate}
  \end{lemma}
	    \begin{proof} We first notice that for a fixed natural number $n$, $q_s(n;k_{1},\ldots,k_{s}) \neq 0$ only for a finite number of $(s+1)$-tuples $(s, k_{1}, \ldots, k_{s}) \in \mathbb{N}^{s+1}$. Therefore, all infinite sums in (2)--(5) are finite.

Part (1) is straightforward from Proposition \ref{prop:FinitePowerSeries} part (3) and the power series in (\ref{formulae}).	
			
			We prove part (2). Since $k_{i} \in \mathbb{N}$ ranges over all possible pyramids weights, by the definition of  $q_s(n;k_{1},\ldots,k_{s})$ it is clear that the summation in part (1) counts all non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks. This proves part (2).
				
				We now prove part (3). If $\mathfrak{Q}_{s}^{n}$ denotes the collection of all non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks, then it is clear that $\{ \mathfrak{Q}_{s}^{n} \}_{s \in \mathbb{N}}$ partitions all non-decreasing Dyck paths of length $2n$ (notice that $\mathfrak{Q}_{s}^{n}\neq \emptyset$ only for a finite number of $s$). This and part (2) prove part (3).
				
		We prove part (4). If a non-decreasing Dyck path $P$ has $s$ peaks and its pyramid weights are $k_{1},\ldots,k_{s}$, then the path $P$ total pyramid weight is $k_{1} + \ldots + k_{s}$. Therefore,
		\[(k_{1} + \ldots + k_{s}) \, q_{s}(n;k_{1},\ldots,k_{s})\]
is the sum of the weights of all paths $P$ of length $2n$ with pyramid weights $k_{1},\ldots,k_{s}$. Since $s, k_{1},\ldots,k_{s}$ range in the set of natural numbers, we obtain part (4).
				
We now prove part (5).  If $i_{1},\ldots,i_{m}$ denote pyramid positions in an arbitrary non-decreasing Dyck path $P$ and $k_{i_{1}}, \ldots, k_{i_{m}}$ the corresponding  pyramid weights, then the number of peaks $s$ in $P$ is at least $i_{m}$ and the sum of all pyramid weights coresponding to positions $i_{1},\ldots,i_{m}$ is $k_{i_{1}} + \ldots + k_{i_{m}}$. Therefore, $(k_{i_{1}} + \ldots + k_{i_{m}})  \, q_s(n;k_{1},\ldots,k_{s})$ is the sum of all the pyramid weights $k_{i_{1}}, \ldots, k_{i_{m}}$, in positions $i_{1},\ldots,i_{m}$, of all paths $P$ of length $2n$ with exactly $s \geq i_{m}$ peaks. If we take $s\in \{i_{m}, i_{m}+1, \ldots \}$	and $k_{1}, \ldots, k_{s} \in \mathbb{N}$, then we obtain the sum of the weights of all pyramids in positions $i_{1}, \ldots, i_{m}$ in all non-decreasing Dyck paths of length $2n$. This proves part (5).	\end{proof}

Both statements in Theorem \ref{thm:OldResults} are known. Indeed, Theorem \ref{thm:OldResults} part (1) is proved in \cite[p.~215]{barcucci}
using a recursive description of non-decreasing Dyck paths that allows them to deduce a functional equation from which a generating function can be obtained, and Theorem \ref{thm:OldResults} part (2) is in \cite{integer3} without a proof. We provide new proofs for both statements in Theorem \ref{thm:OldResults} using the generating function $R(x,z)$ defined in Section \ref{sec3}. We also provide new combinatorial proofs for both statements.

\begin{theorem} \label{thm:OldResults} If $n \in \mathbb{N}$, then
		\begin{enumerate}
			\item the number of non-decreasing Dyck paths of length $2n$ is $F_{2n-1}$,
	                \item the sum of the weights of all pyramids in all non-decreasing Dyck paths of length $2n$ is
	                \[ \displaystyle{\frac{2nF_{2n+1}+(2-n)F_{2n}}{5}}.\]
		\end{enumerate}		
\end{theorem}

\begin{proof}
  Lemma \ref{lem:technical} part (1) and the definition of $R(x,z)$ imply that
    \begin{eqnarray} \label{eqn:two}
        R(x,z) =\sum_{s=1}^{\infty} \sum_{(n;k_{1},\ldots,k_{s})} q_{s}(n;k_{1},\ldots,k_{s})
z^{n}\, x^{k_{1}+\ldots + k_{s}}.
    \end{eqnarray}
  \begin{description}[font=\normalfont\itshape]
      \item[Generating function proof of part (1).] Proposition \ref{prop:InfinitePowerSeries} part (2) and (\ref{eqn:two}) imply that
    \[
       R(1,z) = \sum_{n=1}^{\infty} \sum_{s=1}^{\infty}  \sum_{(k_{1},\ldots,k_{s})} q_{s}(n;k_{1},\ldots,k_{s})\,z^{n} = \sum_{n=1}^{\infty} F_{2n-1} \,z^{n}.
   \]
This and Lemma \ref{lem:technical} part (3) prove part (1).

     \item[Combinatorial proof of part (1).] We denote by $\mathfrak{Q}^{n}$ the set of all non-decreasing
Dyck paths of length $2n$ and $d_{n}=\left\vert{\mathfrak{Q}^{n}}\right\vert $. The set $\mathfrak{Q}^{n}$ can be partitioned into two disjoint sets $\mathcal{A}_n$
and $\mathcal{B}_n$, where $\mathcal{A}_n$ contains those paths that have at least one valley of height $0$, and
$\mathcal{B}_n=\mathfrak{Q}^{n}\setminus\mathcal{A}_n$. Since the paths are non-decreasing, $\mathcal{A}_n$
contains those paths that have at least two peaks, and the first pyramid has a lifting step of size $0$.
By removing the first and last step from the paths in $\mathcal{B}_n$ we can map
$\mathcal{B}_n$ into $\mathfrak{Q}^{n-1}$ bijectively. Moreover, $\mathcal{A}_n=\bigcup_{j=1}^{n-1}\mathcal{C}_{n,j}$
where $\mathcal{C}_{n,j}$ contains those paths whose first valley point is at $(2j,0)$. By removing the path until
the first valley point from all the paths in $\mathcal{C}_{n,j}$,
we can map $\mathcal{C}_{n,j}$ into $\mathfrak{Q}^{n-j}$ bijectively. Thus,

\begin{equation}\label{recurrence}
d_n=d_{n-1}+\sum_{j=1}^{n-1}d_{n-j}.
\end{equation}

It is clear that $d_1=1$. Since $\{ d_{n} \}_{n \in \mathbb{N}}$ and
$\{ F_{2n-1} \}_{n \in \mathbb{N}}$ satisfy the same recursion
(\ref{recurrence}), $d_{n}=F_{2n-1}.$

     \item[Generating function proof of part (2).] It is easy to see from (\ref{eqn:two}) and Proposition \ref{prop:InfinitePowerSeries} part (3) that
     \begin{eqnarray*}
       \displaystyle{\frac{\partial R(x,z)}{\partial x}\Big\vert_{x=1}} &=& \sum_{n=1}^{\infty} \sum_{s=1}^{\infty}  \sum_{(k_{1},\ldots,k_{s})} (k_{1}+\ldots + k_{s})\,q_{s}(n;k_{1},\ldots,k_{s})\,z^{n}\\
                                                                                 &=& \sum_{n=1}^{\infty} \frac{1}{5}(2nF_{2n+1}+(2-n)F_{2n}) \,z^{n}.
     \end{eqnarray*}
This and Lemma \ref{lem:technical} part (4) prove part (2).
\item[Combinatorial proof of part (2).] We denote by $w_n$ the sum of the weights of all the paths in $\mathfrak{Q}^{n}$ and use the same notation as
in the combinatorial proof of part (1). It is clear that the sum of the weights of the paths in $\mathcal{C}_{n,j}$ is $w_{n-j}+jd_{n-j}=w_{n-j}+jF_{2(n-j)-1}$. It is also easy to see that the paths in $\mathcal{B}_n$
and the corresponding paths in $\mathfrak{Q}^{n-1}$ have the same weight
with the exception of the path in $\mathcal{B}_n$ with a single pyramid.
Therefore, the sum of the weights of the paths in $\mathcal{B}_n$ is $1+w_{n-1}$. Thus,
\begin{equation}\label{recurrence2}
w_n=w_{n-1}+1+\sum_{j=1}^{n-1}(w_{n-j}+jF_{2(n-j)-1}).
\end{equation}
The proof can be finished showing that the sequence $\{(2nF_{2n+1}+(2-n)F_{2n})/5\}_{n \in \mathbb{N}}$ satisfies the recursion (\ref{recurrence2}). We skip this as it is not very enlightening.\qedhere
\end{description}
\end{proof}

Antoine Vella \cite[p.~8, Cor.~2.2]{vella} proves a similar result to Theorem \ref{thm:NewResults1} part (1) for valleys,
but the refinement in terms of peaks, although deducible from his work \cite[pp.~7--8]{vella}, is not made explicit in his
 thesis. Therefore, we include a proof of Theorem \ref{thm:NewResults1} part (1) using the generating function
 $Q_{s}(z;t_{1},\ldots,t_{s})$ defined in Section \ref{sec3}. We also provide combinatorial proofs of
 Theorem \ref{thm:NewResults1} parts (1) and (2).

\begin{theorem} \label{thm:NewResults1} Let $n \in \mathbb{N}$ and fix a natural number $ s \in [n].$ Therefore,
  \begin{enumerate}
     \item the number of non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks is $\binom{n+s-2}{2s-2}$,
     \item for any $j \in [s]$ the sum of the weights of
the pyramids in the $j$-th position amongst all non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks
is the same as the average pyramid weight among these paths, and it is given by
$\binom{n+s-1}{n-s}$.
  \end{enumerate}

\end{theorem}
\begin{proof} We first give a generating function proof of part (1).
   \begin{description}[font=\normalfont\itshape]
  \item[Generating function proof of part (1).] Proposition \ref{prop:FinitePowerSeries} parts (3) and (4) imply that
    \[
      Q_{s}(z;1,\ldots,1) = \sum_{n=1}^{\infty} \sum_{(k_{1},\ldots,k_{s})} q_{s}(n;k_{1},\ldots,k_{s})
\,z^{n}= \sum_{n=1}^{\infty} \binom{n+s-2}{2s-2} \,z^{n}.
    \]
This and Lemma \ref{lem:technical} part (2) proves part (1).
  \item[Combinatorial proof of part (1).] We denote the number of non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks by $D(n,s)$. By our earlier discussion in Section \ref{sec3}  page \pageref{alternating}, we have that
\[D(n,s)=\big\vert\{(m_1,k_1,\ldots,m_{s-1},k_{s-1},k_s): m_i\ge 0, k_i\in \mathbb{N},\sum k_i+\sum m_i=n
\}\big\vert.\]

We now consider the sequence $\ell_1,\ldots,\ell_{2s-2}$ defined as follows:
\[
\ell_i=
\begin{cases}
i + \sum_{j\le i} (m_j+k_j), &\text{if } i\text{ is even,}\\
i+m_i+\sum_{j<i}(m_j+k_j), &\text{if } i\text{ is odd.}\\
\end{cases}
\]
It is clear from the definition that
$$\ell_1=m_1+1>0, \quad \ell_{2i}=\ell_{2i-1}+1+m_i>\ell_{2i-1}, \quad \ell_{2i}=\ell_{2i-1}+k_i>\ell_{2i-1}$$
and
$$\ell_{2s-2}=s-1+\sum_{i\le s-1}(m_i+k_i)=s-1+n-k_s\le n+s-2.$$
Thus, the sequence $\ell_1,\ldots,\ell_{2s-2}$ is a strictly increasing sequence from the set
$[n+s-2]$. That is, it can be identified by a $2(s-1)$-element subset of
the $(n+s-2)$-element set. Moreover, given such a set, the $(2s-1)$-tuple $(m_1,\ldots,k_s)$
can be uniquely reconstructed. This proves part (1) combinatorially.

  \item[Combinatorial proof of part (2).] We fix $j\in [s]$ and a permutation $\pi_j:[s] \rightarrow [s]$ such that $\pi_j(1)=j$. We also define the map $f_j$ by
  \[f_j(m_1,k_1,\ldots,m_{s-1}k_{s-1},k_s)=(m_1,k_{\pi_j(1)},m_2,k_{\pi_j(2)},\ldots, m_{s-1},k_{\pi_j(s-1)}, k_{\pi_j(s)}).\]
The map $f_j$ clearly defines a bijection from the collection of
all $(2s-1)$-tuple characterizations of all non-decreasing Dyck paths of
length $2n$ with exactly $s$ peaks into themselves, see Section \ref{sec3} page \pageref{alternating}. Moreover, if the $j$-th pyramid of
a path $P$ has weight $w$, then the function $f_j$ maps the $(2s-1)$-tuple characterization of $P$ into the
$(2s-1)$-tuple characterization of a path $P'$ whose first pyramid has weight $w$. This shows that the sum of the
weights of the $j$-th pyramids amongst all non-decreasing Dyck paths of length $2n$ with exactly $s$ peaks is the same
 regardless of the value of $j$, and it is the
average peak weight $W(s,n)$ amongst these paths. Thus, we only need to show that the sum of the
 weights of the $s$-th pyramids in these paths is $\binom{n+s-1}{2s-1}$.

From the combinatorial proof of part (1) we see that any sequence $\ell_1,\ldots,\ell_{2s-2}$ such that
$1\le\ell_1<\ldots<\ell_{2s-2}\le n+s-2$ determines a non-decreasing Dyck path of length
$2n$ with exactly $s$ peaks with last pyramid weight $k_s=n+s-1-\ell_{2s-2}$. We now assign to any such
$(2s-2)$-tuple/$(2s-2)$-subsets the set of $k_s$ many $(2s-1)$-sets
$\{\ell_1,\ldots,\ell_{2s-2},p: \ell_{2s-2}<p\le n+s-1\}$.
It is easy to see that any non-decreasing Dyck path of length $2n$ with exactly $s$ peaks with last pyramid weight
$k_s$ has exactly $k_s$ many different $(2s-1)$-subsets of $[n+s-1]$ assigned to it, every such subset gets assigned
to some path, and different paths do not get the same subsets assigned. Therefore, the sum of the weight of the $s$-th
pyramids in these paths is the number of $(2s-1)$-subsets of the set $[n+s-1]$, which is $\binom{n+s-1}{2s-1}=\binom{n+s-1}{n-s}$. This proves part (2). \qedhere
 \end{description} \end{proof}

\begin{theorem} \label{thm:NewResults2} Let $n, m, i_{1},\ldots, i_{m}$ be elements of $\mathbb{N}$. If $ i_{1}<\cdots<i_{m}$ denote pyramid positions in an arbitrary non-decreasing Dyck path, then the sum of the weights of all pyramids in positions $i_{1}, \ldots, i_{m}$ in all non-decreasing Dyck paths of length $2n$ with at least $i_{m}$ pyramids is $m \,C_{i_{m}-1}(n-i_{m}+1)$.
\end{theorem}
\begin{proof}
\begin{description}[font=\normalfont\itshape]
  \item[Generating function proof.]Proposition \ref{prop:FinitePowerSeries} part (3), the generating function in (\ref{formulaf}) and the definition of $R^{{\mathrm I}}(x,z)$ imply that
    \begin{eqnarray}\label{eqn:three}
       R^{{\mathrm I}}(x,z)=\sum_{s=i_{m}}^{\infty} \sum_{(n;k_{1},\ldots,k_{s})} q_{s}(n;k_{1},\ldots,k_{s})
z^{n}\, x^{k_{i_{1}}+\ldots + k_{i_{m}}}.
    \end{eqnarray}
It is clear that if a non-decreasing Dyck path $P$  has at least $i_{m}$ pyramids, then the length of $P$ is at least $2\,i_{m}$. Thus, if $s \geq i_{m}$, then
\[ q_{s}(1;k_{1},\ldots,k_{s}) = q_{s}(2;k_{1},\ldots,k_{s}) = \ldots = q_{s}(i_{m}-1;k_{1},\ldots,k_{s}) = 0, \]
 for any  $(k_{1},\ldots,k_{s}) \in \mathbb{N}$. This, (\ref{eqn:three}) and Proposition \ref{prop:InfinitePowerSeriesIndices} part (2) imply that
\begin{eqnarray*}
       \displaystyle{\frac{\partial R^{{\mathrm I}}(x,z)}{\partial x}\Big\vert_{x=1}} &=& \sum_{n=1}^{\infty}  \sum_{s=i_{m}}^{\infty}  \sum_{(k_{1},\ldots,k_{s})} (k_{i_{1}} + \ldots + k_{i_{m}}) \,q_{s}(n;k_{1},\ldots,k_{s})\,z^{n}\\
       												&=& \sum_{n=i_{m}}^{\infty}  \sum_{s=i_{m}}^{\infty}  \sum_{(k_{1},\ldots,k_{s})} (k_{i_{1}} + \ldots + k_{i_{m}}) \,q_{s}(n;k_{1},\ldots,k_{s})\,z^{n}\\
                                                                                 &=& \sum_{n=i_{m}}^{\infty} m \,C_{i_{m}-1}(n-i_{m}+1)\,z^{n}.
     \end{eqnarray*}
This and Lemma \ref{lem:technical} part (5) proves the Theorem.
\item[Combinatorial proof.]It follows from Theorem~\ref{thm:NewResults1} part (2) that the quantity we seek is
\begin{equation*}
m\sum_{s=i_m}^n \binom{n+s-1}{n-s}=m\sum_{j=0}^{n-i_m}\binom{2n-j-1}{j}.
\end{equation*}
We are done by equation (\ref{Cdm}).\qedhere
\end{description}
\end{proof}

The conclusion of Theorem \ref{thm:NewResults2} depends only on $n, m$ and the largest element of $\{i_{1},\ldots, i_{m}\}$. We make this explicit in Corollary \ref{cor:first}.

    \begin{corollary}\label{cor:first}Let $n \in \mathbb{N}$. If $I$ is a finite non-empty subset of $\mathbb{N}$ denoting pyramid position in an arbitrary non-decreasing Dyck path, then the sum of the weights of all pyramids in positions determined by $I$ in all non-decreasing Dyck paths of length $2n$ with at least  max$(I)$ pyramids depends only on $n, \left| I\right|$ and max$(I)$. Moreover, this sum is $\left| I\right| \,C_{max(I)-1}(n-(I)+1)$.
  \end{corollary}


The pyramid positions in Theorem \ref{thm:NewResults2} and Corollary \ref{cor:first} come from numbering the pyramids from left to right. We could have also chosen to number the pyramids from right to left. We introduce some notation.

We say that a pyramid $\Delta$ is in the \emph{$i$--LR position} of a path $P$, if $\Delta$ is labeled with the number $i$ when the numbering of the pyramids of $P$ is done left to right. In this case, we say that $\Delta$ is the $i$--LR pyramid. Similarly, we say that a pyramid $\Delta$ is in the \emph{$i$--RL position} of a path $P$. If $\Delta$ is labeled with the number $i$ when the numbering of the pyramids of $P$ is done right to left. In this case, we say that $\Delta$ is the $i$--RL pyramid. See Figure \ref{figure5}.

\begin{figure} [htbp]
\begin{center}
\includegraphics[width=75mm]{LR_Positions.pdf}
\includegraphics[width=75mm]{RL_Positions.pdf}
\end{center}
\caption{LR and RL pyramid positions for a path $P$.} \label{figure5}
\end{figure}


Notice that all the results from Proposition \ref{prop:FinitePowerSeries}  to Corollary \ref{cor:first} are for pyramids in LR positions.

\begin{theorem}\label{thm:LRtoRL} If $n,i \in \mathbb{N}$, then the sum of the weights of all pyramids in the $i$--LR position of all non-decreasing Dyck paths of length $2n$ is the same as the sum of the weights of all pyramids in the $i$--RL position.  Moreover, this sum is $C_{i-1}(n-i+1)$.
\end{theorem}


\begin{proof} Theorem \ref{thm:NewResults2} with $m=1$ and $i_{m}=i$
proves that the sum of the weights of all pyramids in the $i$--LR position of all non-decreasing Dyck paths of length $2n$ with at least $i$ pyramids is $C_{i-1}(n-i+1)$. Since a path with less than $i$ pyramids will contribute zero to this sum, we can drop the condition ``with at least $i$ pyramids" in the previous statement.

If we decide to number pyramids from right to left (using RL labeling of pyramids), then using a similar argument as in Section \ref{sec3} page \pageref{pageref1}, every non-decreasing Dyck path $P$ with exactly $s$ peaks is uniquely determined by its alternating sequence of pyramids and lifting steps
\[ (m_{s},k_{s},\ldots,m_{2},k_{2},k_{1}),\]
where $k_{i} \in \mathbb{N}$ and $m_{i} \in \mathbb{Z}_{\geq 0}$ are the $i$--RL pyramid weight and the length of the $i$--RL lifting sequence, respectively. If we associate to $P$ the following term on the variables $z, t_{1}, \ldots, t_{s}$:
\[term(P)=(z\,t_{1})^{k_1}\prod_{i=2}^{s} z^{m_i}(z\,t_{i})^{k_{i}},\]
then it is easy to see that all results from Proposition \ref{prop:FinitePowerSeries}  to Corollary \ref{cor:first}  are still true for RL labeling of pyramids. Therefore, if we apply the RL version of  Theorem \ref{thm:NewResults2} with $m=1$ and $i_{m}=i$, then we obtain that the sum of the weights of all pyramids in the $i$--RL position of all non-decreasing Dyck paths of length $2n$ is $C_{i-1}(n-i+1)$. This proves the Theorem. \end{proof}

\begin{corollary}\label{cor:second} If $n \in \mathbb{N}$, then,
    \begin{enumerate}
    \item the sum of the weights of all first pyramids of all non-decreasing Dyck paths of length $2n$ is the same as the sum of the weights of all last pyramids. Moreover, this sum is $F_{2n}$,
    \item the sum of the weights of all second pyramids of all non-decreasing Dyck paths of length $2n$ is the same as the sum of the weights of all penultimate pyramids. Moreover, this sum is $F_{2n}-n$.
        \end{enumerate}
  \end{corollary}

\begin{proof}
We prove part (1). Theorem \ref{thm:LRtoRL} with $i=1$ shows that the sum of the weights of all first pyramids is the same as the sum of the weights of all last pyramids of all non-decreasing Dyck paths of length $2n$, and this  sum is $C_{0}(n)$. We know that $C_{0}(n)=F_{2n}$, see (\ref{eqn:C}). This proves part (1).

We now prove part (2). Theorem \ref{thm:LRtoRL} with $i=2$ shows that the sum of the weights of all second pyramids is the same as the sum of the weights of penultimate pyramids of all non-decreasing Dyck paths of length $2n$, and this sum is $C_{1}(n-1)$.

We prove that $C_{1}(n-1)=F_{2n} -n$.
If we take the derivative with respect to $z$, and multiply by $z$ on both sides of $\sum_{n=0}^{\infty} z^{n}=1/(1-z)$, then we obtain
   \[
     \sum_{n=1}^{\infty} n \, z^{n} =\frac{z}{(1-z)^2}.
    \]
This, Proposition \ref{prop:GeneraFuncFib} part (1) and Proposition \ref{prop:ArrayT} part (2) with $d=2$ imply that
   \begin{eqnarray*}
   \sum_{n=2}^{\infty} \left(F_{2n} -n \right)\, z^{n}  &=&\sum_{n=1}^{\infty} \left(F_{2n} -n \right)\, z^{n} \\
                                                                               &=& \frac{z}{1-3\,z+z^2} - \frac{z}{(1-z)^2}= \frac{z^{2}}{(1-z)^{2} \left(z^{2}-3 z+1\right)}\\
                                                                               &=&\sum_{n=2}^{\infty} C_{1}(n-1) \,z^{n}.		
    \end{eqnarray*}
Therefore, $F_{2n} -n=C_{1}(n-1)$. This proves part (2).   \end{proof}

If we drop the condition ``with at least $i_{m}$ pyramids" from Theorem \ref{thm:NewResults2}, then we obtain a new counting result. We introduce some notation first. If $A$ is a collection of pyramids, then we denote by $w(A)$ the sum of the weights of all pyramids in $A$.

\begin{corollary}\label{cor:NewResults3} Let $n, m, i_{1},\ldots, i_{m}$ be elements of $\mathbb{N}$. If $ i_{1}<\cdots<i_{m}$ denote pyramid positions in an arbitrary non-decreasing Dyck path, then the sum of the weights of all pyramids in positions $i_{1}, \ldots, i_{m}$ in all non-decreasing Dyck paths of length $2n$ is $\sum_{k=1}^{m} C_{i_{k}-1}(n-i_{k}+1)$.
\end{corollary}

\begin{proof} If we denote by $\mathcal{P}_{n}^{i}$ the collection of all pyramids in the $i$--position of all non-decreasing Dyck paths of length $2n$, then it is clear that $\{ \mathcal{P}_{n}^{i} \}_{i=1}^{\infty}$ partitions the collection of all pyramids in all non-decreasing Dyck paths of length $2n$. Therefore, the sum of the weights of all pyramids in positions $i_{1}, \ldots, i_{m}$ in all non-decreasing Dyck paths of length $2n$ is
   \begin{eqnarray} \label{eqn:last}
          \sum_{k=1}^{m} w(\mathcal{P}_{n}^{i_{k}}).
   \end{eqnarray}
Theorem \ref{thm:LRtoRL} shows that $w(\mathcal{P}_{n}^{i})=C_{i-1}(n-i+1)$. This and (\ref{eqn:last}) prove the Theorem. \end{proof}

\section{Remarks}
It can be proved that $F_{2(n-i)}$ is the number of non-decreasing Dyck paths of length $2n$
where the weight of the last pyramid  is exactly $i$. We do not include the proof here, but it will appear in a future work by the same authors.

\section{Figure of all non-decreasing Dyck paths of Length 8}
We give all non-decreasing Dyck paths of length 8. This figure was made with the help of \emph{Mathematica}$^{\text{\textregistered}}$.

\begin{figure} [htbp]
\begin{center}
\includegraphics[width=49mm]{Dyck_Path1.pdf}
\includegraphics[width=49mm]{Dyck_Path2.pdf}
\includegraphics[width=49mm]{Dyck_Path3.pdf}
\includegraphics[width=49mm]{Dyck_Path4.pdf}
\includegraphics[width=49mm]{Dyck_Path5.pdf}
\includegraphics[width=49mm]{Dyck_Path6.pdf}
\includegraphics[width=49mm]{Dyck_Path7.pdf}
\includegraphics[width=49mm]{Dyck_Path8.pdf}
\includegraphics[width=49mm]{Dyck_Path9.pdf}
\includegraphics[width=49mm]{Dyck_Path10.pdf}
\includegraphics[width=49mm]{Dyck_Path11.pdf}
\includegraphics[width=49mm]{Dyck_Path12.pdf}
\includegraphics[width=49mm]{Dyck_Path13.pdf}
\end{center}
\caption{All non-decreasing Dyck paths of length 8.} \label{figure3}
\end{figure}

\begin{thebibliography}{10}
\bibitem{barcucci} E.~Barcucci, A.~Del Lungo, S.~Fezzi, and R.~Pinzani,
Nondecreasing Dyck paths and q-Fibonacci numbers,
\emph{Discrete Math.} 170 (1997), no. 1--3, 211--217.

\bibitem{charalambides} C.~Charalambides, \emph{Enumerative Combinatorics},
Chapman and Hall/CRC, Boca Raton, FL, 2002.

\bibitem{denise} A.~Denise and R.~Simion,
Two combinatorial statistics on Dyck paths,
\emph{Discrete Math.} 137 (1995), no. 1--3, 155--176.

\bibitem{Deutschenumeration} E.~Deutsch,
Dyck path enumeration,
\emph{Discrete Math.} 204 (1999), no. 1--3, 167--202.

\bibitem{Deutschebiyection} E.~Deutsch,
A bijection on Dyck paths and its consequences,
\emph{Discrete Math.} 179 (1998), no. 1--3, 253--256.

\bibitem{koshy} T.~Koshy,
\emph{Fibonacci and lucas numbers with applications},
Wiley-Interscience, New York, 2001.

\bibitem{Kronenburg} M.~Kronenburg,
The binomial coefficient for negative arguments,
May 18 2011. \url{http://arxiv.org/abs/1105.3689/}.

\bibitem{Riordan} J.~Riordan, \emph{Combinatorial Identities},
John Wiley \& Sons, New York-London-Sydney 1968.

\bibitem{stanley1} R.~Stanley, \emph{Enumerative Combinatorics: Vol.\ 1},
Cambridge University Press, Cambridge, 1997.

\bibitem{stanley} R.~Stanley, \emph{Enumerative Combinatorics: Vol.\  2},
Cambridge University Press, Cambridge, 1999.

\bibitem{integer3} The On-Line Encyclopedia of Integer
Sequences, Sep 13 2011.
\url{http://oeis.org/A030267}.

\bibitem{vella} A.~Vella, \emph{Pattern avoidance in cyclically ordered structures},
Department of Mathematics, Chalmers University of Technology and G\"{o}teborg University, 2003.


\end{thebibliography}

\end{document} 
