\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{pstricks}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

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

\begin{document}

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

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

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

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

\begin{center}
\vskip 1cm{\LARGE\bf Counting Dyck Paths According to the \\
\vskip .02in
Maximum Distance Between Peaks and \\
\vskip .17in 
Valleys} \vskip 1cm
\large Toufik Mansour\\
Department of Mathematics\\
University of Haifa \\
31905 Haifa  \\
Israel\\
\href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il}\\
\ \\
Mark Shattuck\\
Department of Mathematics\\
University of Tennessee \\
Knoxville, TN 37996\\
USA \\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu}\\
\end{center}

\def\DD{\mathcal{D}}
\def\SS{\mathcal{S}}

\vskip .2 in
\begin{abstract}
A \emph{Dyck path} of length $2n$ is a lattice path from $(0,0)$ to
$(2n,0)$ consisting of up-steps $u=(1,1)$ and down-steps $d=(1,-1)$
which never passes below the $x$-axis.  Let $\DD_n$ denote the set of
Dyck paths of length $2n$.  A \emph{peak} is an occurrence of $ud$ (an
upstep immediately followed by a downstep) within a Dyck path, while a
\emph{valley} is an occurrence of $du$.  Here, we compute explicit
formulas for the generating functions which count the members of
$\DD_n$ according to the maximum number of steps between any two peaks,
any two valleys, or a peak and a valley. In addition, we provide closed
expressions for the total value of the corresponding statistics taken
over all of the members of $\DD_n$.  Equivalent statistics on the set
of $231$-avoiding permutations of length $n$ are also described.
\end{abstract}


%%-----------------------------------------------------------------
\section{Introduction}

A {\em Dyck path} of length $2n$ is a lattice path from $(0,0)$ to
$(2n,0)$ consisting of up-steps $u=(1,1)$ and down-steps $d=(1,-1)$ which never
passes below the $x$-axis.  That is, a Dyck path is a word of length $2n$ over the alphabet $\{u,d\}$ in which there are equal numbers of occurrences of the letters $u$ and $d$, with at least as many occurrences of the letter $u$ in any initial segment of the word as the letter $d$.  See Figure 1 below. Let $\DD_n$ denote the set of
Dyck paths of length $2n$.  Dyck paths are well-known combinatorial objects that have been widely studied in the literature. Stanley~\cite{St} presents many structures equivalent
to Dyck paths of length $2n$, all of which are counted by the {\em
Catalan sequence} $c_n=\frac{1}{n+1}\binom{2n}{n}$ (see also A000108 in \cite{sloane}).  Various
statistics have been studied on the set of Dyck paths, such as {\em
area} \cite{D8,F13,M96,W32}, {\em pyramid weight} \cite{D9}, and the number
of {\em udu}'s \cite{S29}. See also \cite{D10,TM,M23} for other related statistics.
\begin{figure}[htp]
\begin{center}
\begin{pspicture}(4.4,1.4)
\psgrid[unit=0.4,subgriddiv=1,griddots=5,gridlabels=7pt](0,0)(11,4)
\psline(0,0)(.8,.8)(1.6,0)(2.4,.8)(3.2,0)(3.6,.4)(4,0)
\end{pspicture}
\end{center}
\caption{The Dyck path $uudduuddud$.}\label{Fig_path1}
\end{figure}

Let $w$ be any word over the alphabet $\{u,d\}$. We say that the Dyck path $P\in\DD_n$ {\em contains} the word $w$ if it can be written as
$P=P'wP''$. In this context, $w$ is said to be the {\em left-most occurrence} (resp., {\em right-most occurrence}) if $P'$ (resp., $P''$) does not contain any occurrences of $w$. For instance, if $P$=u{\bf ud}uu{\bf ud}ddu{\bf ud}dd $\in \DD_7$, then $P$ contains three occurrences of $ud$ indicated in bold. The left-most and right-most occurrences of $ud$ correspond, respectively, to the second and third and to the eleventh and twelfth letters of $P$.

Let $w,w'$ be any two words over the alphabet $\{u,d\}$. We say that the Dyck path $P\in\DD_n$ contains the (ordered) pair $(w,w')$ if it can be decomposed as $P=P'wP''w'P'''$. Moreover, we say that $P$ contains the pair $(w,w')$ with distance $r$ if, in the corresponding decomposition $P'wP''w'P'''$, the occurrence of $w$ is left-most, the occurrence of $w'$ is right-most, and the number of letters in $P''$ is exactly $r$.  In this context, we define $d_P(w,w')=r$ whenever such a decomposition $P'wP''w'P'''$ exists and let $d_P(w,w')=0$ otherwise. For instance, if $P=uuduuuddduuddd\in \DD_7$, then $d_P(ud,du)=5$ (the length of $P''$, which is $uuudd$ in this case). We denote the generating function for the number of Dyck paths of length $2n$ according to the statistic $d_P(w,w')$ by $F_{w,w'}(x,q)$, that is,
$$F_{w,w'}(x,q)=\sum_{n\geq0}x^n\sum_{P\in\DD_n}q^{d_P(w,w')}.$$

In this note, we compute $F_{w,w'}(x,q)$ in the case when $w,w' \in \{ud,du\}$.  This yields the generating function for the statistics on $\DD_n$ recording the maximum distance between any two peaks ($ud$'s), any two valleys ($du$'s), or a peak and a valley.  We also provide closed expressions for the total value of these statistics taken over all of the members of $\DD_n$.  Equivalent statistics may be described on the set of $231$-avoiding permutations of length $n$.  In addition, a Catalan number identity, which seems to be new, results from our analysis.

\section{The pair ({\em ud},{\em ud})}

Recall that the generating function for the Catalan sequence $\{c_n\}_{n \geq0}$ is given by
$$\sum_{n\geq0}c_nx^n=\frac{1-\sqrt{1-4x}}{2x},$$
which we will denote simply by $c(x)$.

In this section, we will find an explicit formula for the generating function $F_{ud,ud}(x,q)$. Note that any nonempty Dyck path $P\in\DD_n$ may be decomposed as either $P=uP^{(1)}d$ or
$$\underbrace{uu\cdots u}_{s\mbox{ times}}dP^{(1)}dP^{(2)}\cdots dP^{(s-1)}dP^{(s)}uQ^{(r-1)}\cdots uQ^{(2)}uQ^{(1)}u\underbrace{dd\cdots d}_{r\mbox{ times}},$$
where $P^{(j)}$ and $Q^{(i)}$ are themselves possibly empty Dyck paths (suitably translated) and $r,s>0$. See Figure 2 below.  Rewriting this in terms of generating functions, we have
$$F_{ud,ud}(x,q)=1+xF_{ud,ud}(x,q)+c(xq^2)\sum_{s\geq1}x^sq^{s-1}c^{s-1}(xq^2)\sum_{r\geq1}x^rq^{r-1}c^{r-1}(xq^2),$$
where the $c(xq^2)$ factors account for the number of steps occurring in intermediate Dyck paths  $P^{(i)}$ and $Q^{(j)}$ in the above decomposition.
\begin{figure}[h]
\begin{center}
\begin{pspicture}(2,1)
\psset{xunit=.8,yunit=.8}
\psline[linewidth=.5pt]{->}(1.8,0)\psline[linewidth=.5pt]{->}(0,1)
\psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](1.25,.25)(1.5,0)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25)
\rput(.8,.7){\tiny$P^{(1)}$}
\end{pspicture}
\begin{pspicture}(11,2)
\psset{xunit=.8,yunit=.8}
\psline[linewidth=.5pt]{->}(14,0)\psline[linewidth=.5pt]{->}(0,2)
\psline(0,0)(.22,.22)\psline(.25,.25)(.47,.47)\psline[linestyle=dotted](.47,.47)(.9,.9)
\psline(.93,.93)(1.15,1.15)\psline(1.18,1.18)(1.4,1.4)\psline(1.4,1.4)(1.62,1.18)
\put(1.62,1.18){\put(-.27,-.23){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1,0)(0,0)(.25,.25)(.5,.2)(.75,.25)(1,0)\rput(.55,.5){\tiny$P^{(1)}$}}}
\psline(2.72,1.17)(2.95,.92)
\put(2.72,1.17){\put(-.29,-.43){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1,0)(0,0)(.25,.25)(.5,.2)(.75,.25)(1,0)\rput(.55,.5){\tiny$P^{(2)}$}}}
\psline[linestyle=dotted](4.04,.9)(4.5,.5)
\put(4.52,.5){\put(-.85,-.12){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1,0)(0,0)(.25,.25)(.5,.2)(.75,.25)(1,0)\rput(.55,.5){\tiny$P^{(s-2)}$}}}
\psline(5.62,.48)(5.84,.25)
\put(1.04,-.2){\put(4.52,.5){\put(-.85,-.12){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1,0)(0,0)(.25,.25)(.5,.2)(.75,.25)(1,0)\rput(.55,.5){\tiny$P^{(s-1)}$}}}
\psline(5.62,.48)(5.84,.25)}
\put(2.06,-.38){\put(4.52,.5){\put(-.85,-.12){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1,0)(0,0)(.25,.25)(.5,.2)(.75,.25)(1,0)\rput(.55,.5){\tiny$P^{(s)}$}}}}
\put(6.55,0){
\psline(0,0)(.22,.22)
\put(0,-.03){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25)
\rput(.8,.7){\tiny$Q^{(r-1)}$}}
\put(1,.18){\psline(0,0)(.22,.22)
\put(0,-.03){\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25)}
\rput(.8,.7){\tiny$Q^{(r-2)}$}}\psline[linestyle=dotted](2.56,.55)(2.86,.85)
\put(2.3,.7){\psline(0,0)(.22,.22)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25)
\rput(.8,.7){\tiny$Q^{(1)}$}}}
\psline(12.36,1.1)(12.58,1.32)\psline(12.58,1.32)(12.8,1.1)\psline(12.83,1.07)(13.05,.85)
\psline[linestyle=dotted](13.08,.8)(13.31,.55)
\psline(13.34,.5)(13.56,.25)\psline(13.59,.22)(13.79,0)
\end{pspicture}

\caption{Decomposition of a Dyck path.}\label{f1}
\end{center}
\end{figure}

Hence, we can state the following result.

\begin{proposition}\label{P1}
The generating function $F_{ud,ud}(x,q)$ is given by
$$F_{ud,ud}(x,q)=\frac{1}{1-x}\left(1+\frac{x^2c(xq^2)}{(1-xqc(xq^2))^2}\right).$$
\end{proposition}

One can show that this expression for $F_{ud,ud}(x,q)$ reduces to $c(x)$ when $q=1$ using the fact that $yc^2(y)=c(y)-1$.  Next let us find an explicit formula for the number of Dyck paths $P$ of length $2n$ such that $d_P(ud,ud)=m$. To do so, we expand the generating function $F_{ud,ud}(x,q)$ as follows:
\begin{align*}
F_{ud,ud}(x,q)
&=\sum_{n\geq0}x^n+\frac{x}{1-x}\sum_{j\geq1}jx^jq^{j-1}c^j(xq^2)\\
&=\sum_{n\geq0}x^n+\frac{x}{1-x}\sum_{j\geq1}\sum_{i\geq0}\frac{j^2(2i+j-1)!}{i!(i+j)!}x^{i+j}q^{2i+j-1}\\
&=\sum_{n\geq0}x^n+\sum_{j\geq0}\sum_{i\geq0}\sum_{k\geq0}\frac{(j+1)^2(2i+j)!}{i!(i+j+1)!}x^{i+j+k+2}q^{2i+j},
\end{align*}
where in the second equality, we have used the identity
$$c(y)^j=\sum_{i \geq 0} \frac{j(2i+j-1)!}{i!(i+j)!}y^i, \qquad j \geq 1,$$
which occurs as Equation 2.5.16 in \cite{wilf}.

Collecting the coefficient of $x^nq^m$ in this expansion of $F_{ud,ud}(x,q)$ yields the following result.

\begin{theorem}
The number of Dyck paths $P\in\DD_n$ with $d_P(ud,ud)=m$, $0\leq m\leq 2n-4$, is given by
$$\delta_{m,0}+\sum_{i=\max\{m+2-n,0\}}^{\lfloor m/2\rfloor}\frac{(m+1-2i)^2}{m+1}\binom{m+1}{i}.$$
\end{theorem}

When $n \geq 3$ and $m=2n-4$ in the above theorem, we see that the number of Dyck paths $P$ in $\DD_n$ with $d_P(ud,ud)=2n-4$ is given by $\frac{1}{n-1}\binom{2n-4}{n-2}$, which equals the number of Dyck paths of length $2n-4$.  This agrees with the fact that any Dyck path $P\in\DD_n$ with $d_P(ud,ud)=2n-4$ must be of the form $P=udP'ud$, where $P'$ is any member of $\DD_{n-2}$.

As a consequence of the above result, we obtain the following Catalan number identity, which seems to be new.

\begin{corollary}
For all $n\geq1$,
$$\frac{1}{n+1}\binom{2n}{n}=1+\sum_{m=0}^{2n-4}\frac{\sum\limits_{i=\max\{m+2-n,0\}}^{\lfloor m/2\rfloor}(m+1-2i)^2\binom{m+1}{i}}{m+1}.$$
\end{corollary}

Differentiating the formula for $F_{ud,ud}(x,q)$ in Proposition \ref{P1} above with respect to $q$, and substituting $q=1$, implies that the generating function for $\sum_{P\in\DD_n}d_P(ud,ud)$ is given by $\frac{x^2+2x-1}{(1-x)x^2}-\frac{2x^2+3x-1}{x^2\sqrt{1-4x}}$. Using the fact $\frac{1}{\sqrt{1-4x}}=\sum_{n\geq0}\binom{2n}{n}x^n$ yields the following result.

\begin{corollary}
For all $n\geq1$,
$$\sum_{P\in\DD_n}d_P(ud,ud)=\frac{2(n^2-2n-2)}{(n+2)(n+1)}\binom{2n}{n}+2.$$
\end{corollary}

We conclude this section by considering an equivalent statistic on permutations.  If $\pi=\pi_1\pi_2\cdots\pi_n \in \SS_n$, then $\pi$ is said to be \emph{stack-sortable} if it can be put in the natural order $1,2,\ldots,n$ with the aid of a ``stack" in which each element, starting with the first, is moved to a stack and then to the output.  The stack-sortable permutations are precisely those which have no occurrences of $231$; i.e., there exist no indices $i < j < k$ with $\pi_k < \pi_i < \pi_j$.  The set of such permutations is denoted by $\SS_n(231)$ and has cardinality $c_n$ (see, e.g., \cite{sim}).  As pointed out by West \cite{west}, one can encode a sorting by writing an up-step whenever an element is put on the stack and writing a down-step whenever it is taken off.  For instance, the permutations $123$ and $132$ in $\SS_3(231)$ would be sorted by the sequence of moves encoded by $ududud$ and $uduudd$, respectively.  It may be shown that this encoding yields a $1-1$ correspondence between $\DD_n$ and $\SS_n(231)$, which we will denote by $\alpha$.

The statistic $d_P(ud,ud)$ on $\DD_n$ then translates into a statistic on $\SS_n(231)$ as follows.

\begin{definition}
Given $\pi=\pi_1\pi_2\ldots\pi_n \in \SS_n(231)$, suppose $\pi_\ell=1$ for some index $\ell$ and let $\pi_n=M$.  Define the statistic $r$ on $\SS_n(231)$ by
$$r(\pi) = \begin{cases} n-\ell+M-3, & if \text{~}\text{~}  M>1; \\ 0, & if \text{~}\text{~} M=1. \end{cases}$$
\end{definition}

For example, if $$\lambda = uududduudd \in \DD_5,$$ 
then $\alpha(\lambda)=31254 \in \SS_5(231)$, with $d_{\lambda}(ud,ud)=4=r(\alpha(\lambda))$.  Indeed, one can show the following result.

\begin{proposition}
If $n \geq 1$, then
$$d_{\lambda}(ud,ud)=r(\alpha(\lambda))$$
for all $\lambda \in \DD_n$.
\end{proposition}


\section{The pair ({\em du},{\em du})}

Let us write an equation for the generating function $F_{du,du}(x,q)$. Note that any nonempty Dyck path $P\in\DD_n$ can be decomposed as either

 $\bullet$ $P=uP'd$,

 $\bullet$ $P=\underbrace{uu\cdots u}_{k}\underbrace{dd\cdots d}_{k}P'\underbrace{uu\cdots u}_{k'}\underbrace{dd\cdots d}_{k'}$,

 $\bullet$ $uQ'dP'\underbrace{uu\cdots u}_{k}\underbrace{dd\cdots d}_{k}$,

 $\bullet$ $\underbrace{uu\cdots u}_{k}\underbrace{dd\cdots d}_{k}P'uQ'd$,

 $\bullet$ $uQ'dP'uQ''d$,

\noindent where $k$ and $k'$ are positive, $P'$ is any Dyck path, and $Q',Q''$ are any Dyck paths having at least one valley.

Expressing these cases in terms of generating functions, we obtain
\begin{align*}
F_{du,du}(x,q)&=1+xF_{du,du}(x,q)+\frac{x^2}{q^2(1-x)^2}(c(xq^2)-1+q^2)\\
&+\frac{2x}{1-x}G(x,q)c(xq^2)+q^2G^2(x,q)c(xq^2),
\end{align*}
where $G(x,q)$ is the generating function for the number of Dyck paths $uPd$ of length $2n$, in which $P$ itself is a Dyck path having at least one valley, according to the number of steps between the left-most valley and the last step of the path.  That is,
$$G(x,q)=\sum_{n\geq0}x^n\sum q^{d_{Qud}(du,du)},$$
where the internal sum is over all Dyck paths $Q$ of length $2n$ of the form $Q=uPd$ in which $P$ has at least one valley.

In order to find an explicit formula for the generating function $G(x,q)$, we decompose each Dyck path of the form $uPdud$, where $P$ is a Dyck path having at least one valley, as follows:
$$uPdud=u\underbrace{uu\cdots u}_{k}\underbrace{dd\cdots d}_{\ell}uP^{(1)}dP^{(2)}d\cdots P^{(k-\ell+2)}dud,$$
where $\ell=1,2,\ldots,k$ and each $P^{(j)}$ is a Dyck path. Translating this in terms of generating functions yields
\begin{align}
G(x,q)&=\sum_{k\geq1} x^{k+2}\sum_{\ell=1}^{k}q^{k-\ell+1}c^{k-\ell+2}(xq^2)\notag\\
&=\sum_{k\geq1}x^{k+2}\frac{qc^2(xq^2)-q^{k+1}c^{k+2}(xq^2)}{1-qc(xq^2)}\notag\\
&=\frac{x^3qc^2(xq^2)}{(1-x)(1-qc(xq^2))}-\frac{x^3q^2c^3(xq^2)}{(1-qc(xq^2))(1-xqc(xq^2))}\notag\\
&=\frac{x^3qc^2(xq^2)}{(1-x)(1-xqc(xq^2))}.\label{eqGG}
\end{align}

Substituting this expression for $G(x,q)$ into the one above for $F_{du,du}(x,q)$ yields the following result.

\begin{theorem}
The generating function $F_{du,du}(x,q)$ is given by
$$F_{du,du}(x,q)=\frac{1}{1-x}\left(1+\frac{x^2(q^2-1)}{q^2(1-x)^2}+\left(\frac{x}{q(1-x)}+qG(x,q)\right)^2c(xq^2)\right),$$
where $G(x,q)=\frac{x^3qc^2(xq^2)}{(1-x)(1-xqc(xq^2))}$.
\end{theorem}

Differentiating this formula for $F_{du,du}(x,q)$ with respect to $q$, and substituting $q=1$, yields the following formulas for the total value of $d_P(du,du)$ taken over all of the members of $\DD_n$.

\begin{corollary}
The generating function $\sum_{n \geq 0}\left(\sum_{P\in\DD_n}d_P(du,du)\right)x^n$
is given by
$$\frac{1}{x^2(1-x)^3}\left(10x^4-17x^3+7x^2+2x-1+\frac{6x^5-32x^4+31x^3-5x^2-4x+1}{\sqrt{1-4x}}\right).$$
Moreover, $$\sum_{P\in\DD_n}d_P(du,du)=\sum_{k=3}^n\frac{2(27k^4-151k^3+310k^2-212k-280)}{k(k-1)(k+1)(k+2)}\binom{2k-6}{k-4}\binom{n-k+2}{2}.$$
\end{corollary}

\section{The pairs ({\em ud},{\em du}) and ({\em du},{\em ud})}

First observe that the $d_P(ud,du)$ and $d_P(du,ud)$ statistics are identically distributed on $\DD_n$, upon writing members of $D_n$ in reverse order and replacing  $u$ with $d$ and $d$ with $u$ since this transforms the left-most peak (resp., right-most valley) into the right-most peak (resp., left-most valley).  Thus, we only find the generating function for the former.  To do so, note that any nonempty Dyck path $P\in\DD_n$ can be decomposed as either

$\bullet$ $P=uP'd$,

$\bullet$ $P=\underbrace{uu\cdots u}_{k}dP^{(1)}dP^{(2)}\cdots dP^{(k)}\underbrace{uu\cdots u}_{\ell}\underbrace{dd\cdots d}_{\ell}$,

$\bullet$ $P=\underbrace{uu\cdots u}_{k}dP^{(1)}dP^{(2)}\cdots dP^{(k)}uQd$,

\noindent where $k$ and $\ell$ are positive, $P^{(j)}$, $j=1,2,\ldots,k$, is any Dyck path, and $Q$ is any Dyck path having at least one valley.

Expressing these cases in terms of generating functions (note that we need to distinguish when $k=1$ and $k>1$ in the second decomposition above), we obtain
\begin{align*}
F_{ud,du}(x,q)&=1+xF_{ud,du}(x,q)+\frac{x^2}{1-x}\left(1+\frac{c(xq^2)-1}{q}\right)\\
&+\frac{x^3c^2(xq^2)}{(1-x)(1-xqc(xq^2))}+\frac{xqc(xq^2)}{1-xqc(xq^2)}G(x,q),
\end{align*}
where $G(x,q)$ is the generating function for the number of Dyck paths $uPd$ of length $2n$, in which $P$ itself is a Dyck path having at least one valley, according to the number of steps between the left-most valley and the last step of the path (or, equivalently, according to the number of steps between the right-most valley and the first step of the path). Plugging the expression for $G(x,q)$ given in \eqref{eqGG} into the above equation, and using $yc^2(y)=c(y)-1$, we obtain the following result.

\begin{theorem}
The generating function $F_{ud,du}(x,q)$ is given by
$$\frac{1}{1-x}\left(1+\frac{x^2(q-1)}{q(1-x)}+\frac{x^2c(xq^2)(1-xq)}{q(1-x)(1-xqc(xq^2))^2}\right).$$
\end{theorem}

Note that this expression for $F_{ud,du}(x,q)$ reduces to $c(x)$ when $q=1$. Differentiating the expression with respect to $q$, and substituting $q=1$, yields the following formulas for the total value of $d_P(ud,du)$ taken over all of the members of $\DD_n$.

\begin{corollary}
The generating function $\sum_{n \geq 0}\left(\sum_{P\in\DD_n}d_P(ud,du)\right)x^n$
is given by
$$\frac{2x^4-2x^3+x^2+5x-2}{2x^2(1-x)^2}+\frac{4x^3-2x^2-7x+2}{2x^2(1-x)\sqrt{1-4x}}.$$
Moreover,  $$\sum_{P\in\DD_n}d_P(ud,du)=\sum_{k=3}^{n}\frac{3(3k^4-15k^3+23k^2-11k-2)(2k-2)!(n+1-k)}{(2k-3)(k-1)!(k+2)!}.$$
\end{corollary}

One may also express the $d_P(ud,du)$ statistic on $\DD_n$ in terms of a statistic on $\SS_n(231)$ as in the second section above.

\begin{definition}
Given $\pi=\pi_1\pi_2\cdots\pi_n \in \SS_n(231)$, suppose $\pi_\ell=1$ for some index $\ell$ and let $\pi_n=M$.  Let $m$ denote the index (if it exists) of the right-most entry between $\pi_{\ell}$ and $\pi_n$ in $\pi$ and strictly between $1$ and $M$ in value.  Define the statistic $s$ on $\SS_n(231)$ by
$$s(\pi) = \begin{cases} m-\ell, & if~m~exists; \\ 0, &  otherwise. \end{cases}$$
\end{definition}

For example, if $\pi=216354 \in \SS_6(231)$, then $s(\pi)=4-2=2$.

\begin{definition}
Given $\pi=\pi_1\pi_2\cdots\pi_n \in \SS_n(231)$, suppose $\pi_\ell=1$ for some index $\ell$ and let $\pi_n=M$. Define the statistic $t$ on $\SS_n(231)$ by
$$t(\pi) = \begin{cases} s(\pi)+M-3, & if \text{~}\text{~}  M>2; \\ 0, & if \text{~}\text{~} M=1,2. \end{cases}$$
\end{definition}

For example, if $$\lambda = uudduuduuddd \in \DD_6,$$ then $\alpha(\lambda)=216354 \in \SS_6(231)$, with $d_{\lambda}(ud,du)=3=t(\alpha(\lambda))$.  Indeed, one can show the following result.

\begin{proposition}
If $n \geq 1$, then
$$d_{\lambda}(ud,du)=t(\alpha(\lambda))$$
for all $\lambda \in \DD_n$.
\end{proposition}


%==============================================================================================================
\begin{thebibliography}{99}
\bibitem{D8}
M. Delest and X. G. Viennot, Algebraic languages and polyominoe
enumeration, {\em Theoret. Comput. Sci.} {\bf 34} (1984), 169--206.

\bibitem{D9}
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths,
{\em Discrete Math.} {\bf 187:1-3} (1998), 71--96.

\bibitem{D10}
E. Deutsch, Dyck path enumeration, {\em Discrete Math.} {\bf204}
(1999), 167--202.

\bibitem{F13}
J. M. F\'edou, Grammairs et $q$-\'enum\'eration de polyominos, Ph.D.
Thesis, Universit\'e de Bordeaux I, 1989.

\bibitem{TM}
T. Mansour, Statistics on Dyck paths, {\em J. Integer Seq.} {\bf9:1} (2006), Article 06.1.5.

\bibitem{M96}
D. Merlini, R. Sprugnoli, and M. C. Verri, The area determined by
underdiagonal lattice paths, In Proc. of CAAP'96, {\em Lecture Notes in Comput. Sci.} {\bf1059} (1996), 59--71.

\bibitem{M23}
D. Merlini, R. Sprugnoli, and M. C. Verri, Some statistics on Dyck
paths, {\em J. Statist. Plann. Inference} {\bf 101} (2002),
211--227.

\bibitem{sim}
R. Simion and F. W. Schmidt, Restricted permutations, {\em European J. Combin.} {\bf 6} (1985), 383--406.

\bibitem{sloane}
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,
http://oeis.org.

\bibitem{St}
R. P. Stanley, {\it Enumerative Combinatorics, Vol. 1}, Wadsworth and
Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge
University Press, Cambridge, 1996.

\bibitem{S29}
Y. Sun, The statistic ``number of $udu$'s" in Dyck paths, {\em
Discrete Math.} {\bf 287:1-3} (2004), 177-186.

\bibitem{west}
J. West, Sorting twice through a stack, {\em Theoret. Comput. Sci.} {\bf 117} (1993), 303--313.

\bibitem{wilf}
H. Wilf, {\it generatingfunctionology}, Academic Press, New York,
1990.

\bibitem{W32}
W. Woan, Area of Catalan paths, {\em Discrete Math.} {\bf 226}
(2001), 439--444.
\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } 
Dyck paths, generating functions, statistics, peaks, valleys.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000108}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 8 2011;
revised version received  November 6 2011.
Published in {\it Journal of Integer Sequences}, December 15 2011.

\bigskip
\hrule
\bigskip

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


\end{document}