<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

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

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

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

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

\usepackage{psfig}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{amssymb,latexsym,pstcol,pstricks}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Statistics on Dyck Paths
}
\vskip 1cm
\large
Toufik Mansour\\
Department of Mathematics \\
University of Haifa \\
31905 Haifa \\
Israel \\
 \ \\
and \\
 \ \\
Center for Combinatorics\\
LPMC \\
Nan'kai University \\
Tianjin 300071  \\
P. R. China  \\
\href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il} \\
\end{center}

\vskip .2 in
\begin{abstract}
In this paper we consider several statistics on the
set of Dyck paths. Enumeration of Dyck paths according to length and
various other parameters has been studied in several papers.
However, the statistic ``number of $udu$'s" has been considered only
recently. We generalize this statistic and derive an explicit
formula for the number of Dyck paths of length $2n$  according to
the statistic ``number of $uu\cdots udu$'s" (``number of $udud\cdots
udu$'s"). As a consequence, we derive several known results, as well
as many new results.
\end{abstract}

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


%\documentclass[12pt,reqno]{article}

%\usepackage{fullpage}
%\usepackage{amsmath}


%\numberwithin{equation}{section}
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{fact}[theorem]{Fact}
\newtheorem{example}[theorem]{Example}
%\newtheorem{axiom}[theorem]{Axiom}
%\newtheorem{property}[theorem]{Property}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{notation}[theorem]{Notation}
\newenvironment{proof}[1][Proof]{\paragraph*{#1}}{\hspace*{\fill}$\Box$\bigskip}

%\begin{document}

\pagenumbering{arabic}
\def\sof{\hfill\rule{2mm}{2mm}}
\def\ls{\leq}
\def\gs{\geq}
\def\nn{{\bold n}}
\def\ttx{{\left(\frac1{2\sqrt{x}}\right)}}
\def\DD{\mathcal{D}}
\def\SS{\mathcal{S}}
\def\MM{\mathcal{M}}



%===========================================================================
\section{Introduction}
A \emph{lattice path} of length $n$ is a sequence of points
$P_1,P_2,\ldots,P_n$ with $n\geq1$ such that each point $P_i$
belongs to the plane integer lattice and consecutive points $P_i$
and $P_{i+1}$ are connected by a line segment. We will consider
lattice paths in $\mathbb{Z}^2$ whose permitted step types are
up-steps $u=(1,1)$, down-steps $d=(1,-1)$, and horizontal steps
$h=(1,0)$. We will focus on paths that start from the origin and
return to the $x$-axis, and that never pass below the $x$-axis. Let
$\DD_n$ denote the set of such paths, {\em Dyck paths}, of length
$2n$ when only up-steps and down-steps are allowed, and let $\MM_n$
denote the set of such paths, {\em Motzkin paths}, of length $n$
when all the three types are allowed. It is well known that
$|\DD_n|=C_n=\frac{1}{n+1}\binom{2n}{n}$, the $n$-th Catalan number
(see~\cite[A000108]{Sloane}), having ordinary generating function
$C(x)=\frac{1-\sqrt{1-4x}}{2x}$ which satisfies the relation
\begin{equation}\label{eqcatalan}
xC^2(x)-C(x)-1=0,
\end{equation}
and $|\MM_n|=M_n$, the $n$-th Motzkin number
(see~\cite[A001006]{Sloane}), having ordinary generating function
$M(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}$, which satisfies the
relation
\begin{equation}\label{eqmotzkin}
x^2M^2(x)+(x-1)M(x)+1=0.
\end{equation}
Let $D$ be any Dyck path and  $p$ be any word on alphabet $\{u,d\}$.
We say that the Dyck path $D$ occurs $p$ at {\em low level} if $D$
can be decomposed as $D=D'pR$ such that $D'$ is a Dyck path.
Otherwise we say that the Dyck path $D$ occurs $p$ at {\em high
level}.

The enumeration of Dyck paths according to length and various other
parameters has been studied by several authors
\cite{D2}-\cite{MSV13}. However, the statistic ``number of $udu$'s"
has been considered only recently \cite{MSV13,Sun}.

The paper is organized as follows. In Section~2 we consider the
statistic ``the number of $uu\cdots udu$'s" and the statistic ``the
number of $udud\cdots du$'s" in the set of Dyck paths. In Section~3
we consider these statistics at low and high level in the set of
Dyck paths.
%===========================================================================
\section{Enumeration of Dyck paths according to
number of $uu\cdots udu$'s or number of $udud\cdots udu$'s} In
this section we enumerate the number of Dyck paths according to
the length and either the number of $uu\cdots udu$'s or the number
of $udud\cdots udu$'s.

\subsection{Enumeration of Dyck paths according to number of $uu\cdots udu$'s}
Let $\alpha_i(D)$ be the number of occurrences of
$\underbrace{uu\cdots u}_{i}du$ in the Dyck path $D$, see
Table~\ref{tab1}.
\begin{table}[ht]
\begin{tabular}{l|lllllll||l|lllllll}\hline
  $n\backslash\alpha_1$ &amp; $0$ &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$&amp; $5$ &amp;$6$ &amp;  $n\backslash\alpha_2$ &amp; $0$ &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$&amp; $5$ &amp;$6$ \\ \hline
  $1$                   &amp; $1$ &amp;     &amp;     &amp;     &amp;    &amp;     &amp;    &amp;  $1$                   &amp; $1$ &amp;     &amp;     &amp;     &amp;    &amp;     &amp;    \\
  $2$                   &amp; $1$ &amp; $1$ &amp;     &amp;     &amp;    &amp;     &amp;    &amp;  $2$                   &amp; $2$ &amp;     &amp;     &amp;     &amp;    &amp;     &amp;    \\
  $3$                   &amp; $2$ &amp; $2$ &amp; $1$ &amp;     &amp;    &amp;     &amp;    &amp;  $3$                   &amp; $4$ &amp; $1$ &amp;     &amp;     &amp;    &amp;     &amp;    \\
  $4$                   &amp; $4$ &amp; $6$ &amp; $3$ &amp; $1$ &amp;    &amp;     &amp;    &amp;  $4$                   &amp; $10$&amp; $3$ &amp; $1$ &amp;     &amp;    &amp;     &amp;    \\
  $5$                   &amp; $9$ &amp; $16$&amp; $12$&amp; $4$ &amp; $1$&amp;     &amp;    &amp;  $5$                   &amp; $26$&amp; $12$&amp; $3$ &amp; $1$&amp;     &amp;    &amp;\\
  $6$                   &amp; $21$&amp; $45$&amp; $40$&amp; $20$&amp; $5$&amp; $1$ &amp;    &amp; $6$                   &amp; $72$&amp; $41$&amp; $15$&amp; $3$&amp; $1$ &amp;    &amp;\\
  $7$                   &amp; $51$&amp; $126$&amp;$135$&amp;$80$&amp;$30$&amp; $6$  &amp; $1$ &amp;  $7$                   &amp; $206$&amp;$143$&amp;$58$ &amp;$18$&amp;$3$&amp; $1$   &amp;
\end{tabular}
\vspace{10pt} \caption{Number of Dyck paths of length $2n$ according
to the statistics $\alpha_1$ and $\alpha_2$.}\label{tab1}
\end{table}

Define the ordinary generating function for the number of Dyck paths
of length $2n$ according to the statistics
$\alpha_1,\alpha_2,\ldots$ as
$F(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\alpha_j(D)}$.
To study the above ordinary generating function we need the
following notation
$$A_k(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\alpha^k_j(D)},$$
where $\alpha^k_j(D)=\alpha_j\left(\underbrace{uu\cdots
u}_kD\underbrace{dd\cdots d}_k\right)$. These ordinary generating
functions satisfy the following recurrence relations.



\begin{proposition}\label{th11}
For all $k\geq0$,
$$\begin{array}{ll}
A_k(x;q_1,q_2,\ldots)&amp;=1+x(1-q_1q_2\cdots q_{k+1})-x(1-q_1q_2\cdots
q_{k+1})A_0(x;q_1,q_2,\ldots)\\
&amp;+xA_{k+1}(x;q_1,q_2,\ldots)A_0(x;q_1,q_2,\ldots).\end{array}$$
\end{proposition}
\begin{proof}
An equation for the generating function $A_k(x;q_1,q_2,\ldots)$ is
obtained from the ``first return decomposition" of a Dyck paths $D$:
$D=uPdQ$, where $P,Q$ are Dyck paths. Thus, the four possibilities
of $P$ and $Q$ either being empty or nonempty Dyck paths (see
Figure~\ref{fig1}) give contribution
\begin{figure}[ht]
\begin{center}
\begin{pspicture}(1.5,1)
\psline[linewidth=.5pt]{-&gt;}(1,0)\psline[linewidth=.5pt]{-&gt;}(0,.5)
\psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0)
\end{pspicture}
\begin{pspicture}(2.5,1)
\psline[linewidth=.5pt]{-&gt;}(2,0)\psline[linewidth=.5pt]{-&gt;}(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\neq\emptyset$}
\end{pspicture}
\begin{pspicture}(2.5,1)
\psline[linewidth=.5pt]{-&gt;}(2,0)\psline[linewidth=.5pt]{-&gt;}(0,1)
\psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.5,0)(.5,0)(.75,.25)(1,.2)(1.25,.25)(1.5,0)
\rput(1,.45){\tiny$Q\neq\emptyset$}
\end{pspicture}
\begin{pspicture}(3,1)
\psline[linewidth=.5pt]{-&gt;}(3,0)\psline[linewidth=.5pt]{-&gt;}(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)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.5,0)(1.5,0)(1.75,.25)(2,.2)(2.25,.25)(2.5,0)
\rput(.8,.7){\tiny$P\neq\emptyset$}\rput(2.2,.45){\tiny$Q\neq\emptyset$}
\end{pspicture}
\caption{First return decomposition of a Dyck path with nonempty
Dyck paths.}\label{fig1}
\end{center}
\end{figure}
$x$, $x(A_{k+1}(x;q_1,q_2,\ldots)-1)$, $xq_1q_2\cdots
q_{k+1}(A_0(x;q_1,_2,\ldots)-1),$ and
$x(A_{k+1}(x;q_1,q_2,\ldots)-1)(A_0(x;q_1,q_2,\ldots)-1)$,
respectively. Hence, we have the following recurrence relation
$$\begin{array}{ll}A_k(x;q_1,q_2,\ldots)&amp;=1+x(1-q_1q_2\cdots q_{k+1})-x(1-q_1q_2\cdots
q_{k+1})A_0(x;q_1,q_2,\ldots)\\
&amp;+xA_{k+1}(x;q_1,q_2,\ldots)A_0(x;q_1,q_2,\ldots),\end{array}$$ for
all $k\geq0$, as required.
\end{proof}


\begin{theorem}\label{th13}
The generating function $F(x;q_1,q_2,\ldots)$ satisfies the
following equation
$$F(x;q_1,q_2,\ldots)=\sum_{m\geq0}x^mF^m(x;q_1,q_2,\ldots)(1+x(1-F(x;q_1,q_2,\ldots))(1-q_1q_2\ldots q_{m+1})).$$
\end{theorem}
\begin{proof}
We simply use the fact $A_0(x;q_1,q_2,\ldots)=F(x;q_1,q_2,\ldots)$
and apply (see Proposition~\ref{th11}) the recurrence relation
$$\begin{array}{ll}
A_k(x;q_1,q_2,\ldots)&amp;=1+x(1-q_1q_2\cdots
q_{k+1})(1-A_0(x;q_1,q_2,\ldots))\\
&amp;\qquad\qquad\qquad+xA_{k+1}(x;q_1,q_2,\ldots)A_0(x;q_1,q_2,\ldots).\end{array}$$
an infinite number of times and in each step we perform some rather
tedious algebraic manipulations.
\end{proof}

\begin{example}
Define $q_1=q$, $q_2=q^{-1}$, and $q_i=1$ for all $i\geq3$. Then
Theorem~\ref{th13} gives that the ordinary generating function
$f(x;q)=F(x;q,q^{-1},1,1,\ldots)$ satisfies
 $$f(x;q)=\frac{1}{1-xf(x;q)}+x(1-f(x;q))(1-q).$$
Solving the above equation we get that the ordinary generating
function
$$f(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\alpha_1(D)-\alpha_2(D)}$$
is given by
$$\frac{1+x(1+x)(1-q)-\sqrt{(x(1+x)(1-q)+1)^2-4x(1+x(1-q))^2}}{2x(1+x(1-q))}.$$
In particular, the number of Dyck paths $D$ of length $2n$ such that
$\alpha_1(D)=\alpha_2(D)$ is given by (see \cite[A078481]{Sloane})
$$\frac{1+x+x^2-\sqrt{(1+x+x^2)^2-4x(1+x)^2}}{2x(1+x)}.$$
\end{example}

\begin{example}
Define $q_{2i-1}=q$ and $q_{2i}=q^{-1}$ for all $i\geq1$. Then
Theorem~\ref{th13}  gives 
$$F(x;q,1/q,q,1/q,\ldots)=1+x+xq(F(x;q,1/q,q,1/q,\ldots)-1)+x^2F^3(x;q,1/q,q,\ldots).$$
Then the Lagrange inversion formula (see~\cite{wilf}) gives that
$$\sum_{n\geq1}\sum_{D\in\DD_n}x^nq^{\alpha_1(D)-\alpha_2(D)+\alpha_3(D)-\cdots}=
\sum_{n\geq1}\sum_{j=0}^n\sum_{i=0}^j\binom{n}{j}\binom{i}{j}\binom{3i}{n-1+i-j}q^{j-i}\frac{x^{n+i}}{n}.$$
In particular, the number of Dyck paths $D$ of length $2n$ with
$\sum\limits_{i\geq0}\alpha_{2i+1}(D)=\sum\limits_{i\geq0}\alpha_{2i}(D)$
is given by
$$\sum_{j=0}^{n-1}\frac{1}{n-j}\binom{n-j}{j}\binom{3j}{n-1-j}.$$
\end{example}


\begin{example}\label{exaaa}
Define $q_i=q$ for all $i\geq1$. Then Theorem~\ref{th13} gives that
$$S(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\alpha_1(D)+\alpha_2(D)+\cdots}=\sum_{m\geq0}x^mS^m(x;q)(1+x(1-S(x;q))(1-q^{m+1})),$$
which is equivalent to
$S(x;q)=1+\frac{x}{1-xS(x;q)}-\frac{xq(1-S(x;q))}{1-xqS(x;q)}$.
Differentiating the above equation with respect to $q$ and
substituting $q=1$ with using the fact that $S(x;1)=C(x)$, the
generating function for the Catalan numbers, gives that
$$\sum_{n\geq0}\sum_{D\in\DD_n}(\alpha_1(D)+\alpha_2(D)+\cdots)x^n=
\frac{x^2C^4(x)}{1-xC^2(x)}=\sum_{n\geq2}\binom{2n-1}{n-2}x^2.$$ In
other words, the statistic
$\sum_{D\in\DD_n}\alpha_1(D)+\alpha_2(D)+\cdots$ equals
$\binom{2n-1}{n-2}$, for all $n\geq2$ (see \cite[A002054]{Sloane}).
\end{example}

Denote the ordinary generating function $F(x;q_1,q_2,\ldots)$ with
$q_k=q$ and $q_i=1$ for all $i\neq k$ by $F_k(x;q)$. Fix $k\geq1$,
$q_k=q$ and $q_i=1$ for all $i\neq k$. From the definitions it is
easy to see that $F_k(x;q)=F_{k-1}(x;q)$. Thus,
Proposition~\ref{th11} gives that
$$F_{k-1}(x;q)=1+x(1-q)-x(1-q)F_{0}(x;q)+xF_{k-1}(x;q)F_0(x;q),$$
and
$$F_{j+1}(x;q)=\frac{F_j(x;q)-1}{xF_j(x;q)},$$
for all $j=0,1,\ldots,k-2$. To give an explicit formula for
$F_k(x;q)$ we need the following lemma.

\begin{lemma}\label{lem11}
For all $j=0,1,\ldots,k-1$,
$$F_j(x;q)=\frac{\sqrt{x}U_j\ttx
F_0(x;q)-U_{j-1}\ttx}{\sqrt{x}\left[\sqrt{x}U_{j-1}\ttx
F_0(x;q)-U_{j-2}\ttx\right]},$$ where $U_j(t)$ is the $j$-th
Chebyshev polynomial of the second kind.
\end{lemma}
\begin{proof}
We proceed by induction on $j$. The result is true for $j=0$. For
$j\geq0$ we have that
$F_{j+1}(x;q)=\frac{F_{j}(x;q)-1}{xF_{j}(x;q)}$. Thus, by the
induction hypothesis for $j$ we obtain that the ordinary generating
function $F_{j+1}(x;q)$ equals
$$\frac{\sqrt{x}U_j\ttx
F_0(x;q)-U_{j-1}\ttx-\sqrt{x}\left[\sqrt{x}U_{j-1}\ttx
F_0(x;q)-U_{j-2}\ttx\right]}{x\left[\sqrt{x}U_j\ttx
F_0(x;q)-U_{j-1}\ttx\right]},$$ which is
$$\frac{\sqrt{x}\left[\frac{1}{\sqrt{x}}U_j\ttx-U_{j-1}\ttx
\right]F_0(x;q)-\left[\frac{1}{\sqrt{x}}U_{j-1}\ttx-U_{j-2}\ttx\right]}{\sqrt{x}\left[\sqrt{x}U_j\ttx
F_0(x;q)-U_{j-1}\ttx\right]}.$$ Using the recurrence relation
$U_m(t)=2tU_{m-1}(t)-U_{m-2}(t)$ twice we get
$$\frac{\sqrt{x}U_{j+1}\ttx F_0(x;q)-U_{j}\ttx}{\sqrt{x}\left[\sqrt{x}U_j\ttx
F_0(x;q)-U_{j-1}\ttx\right]},$$ as claimed.
\end{proof}

Now we are ready to give an explicit formula for the ordinary
generating function $F_k(x;q)$.

\begin{theorem}\label{th12}
Let
$$\begin{array}{l}
\alpha(x;q)=x^2(1-q)U_{k-2}\ttx-x\sqrt{x}U_{k-1}\ttx,\\
\beta(x;q)=x\sqrt{x}(1-q)\left[U_{k-3}\ttx+\sqrt{x}U_{k-2}\ttx\right]-\sqrt{x}U_{k-1}\ttx,\\
\gamma(x;q)=\sqrt{x}(1+x(1-q))U_{k-3}\ttx-U_{k-2}\ttx.
\end{array}$$
Then the ordinary generating function $F_k(x;q)$ is given by
$$\frac{\gamma(x;q)}{\beta(x;q)}
C\left(\frac{\alpha(x;q)\gamma(x;q)}{\beta^2(x;q)}\right),$$ where
$U_j(t)$ is the $j$-th Chebyshev polynomial of the second kind and
$C(x)$ is the ordinary generating function for the Catalan numbers.
\end{theorem}
\begin{proof}
The generating function $F_0(x;q)$ satisfies the following equation
$$F_{k-1}(x;q)=1+x(1-q)-x(1-q)F_{0}(x;q)+xF_{k-1}(x;q)F_0(x;q).$$
Using Lemma~\ref{lem11} for $j=k-1$ we get
$$F_{k-1}(x;q)=\frac{\sqrt{x}U_{k-1}\ttx
F_0(x;q)-U_{k-2}\ttx}{\sqrt{x}\left[\sqrt{x}U_{k-2}\ttx
F_0(x;q)-U_{k-3}\ttx\right]}.$$ Substituting the expression for
$F_{k-1}(x;q)$ in the above equation and using the recurrence
relation $U_m(t)=2tU_{m-1}(t)-U_{m-2}(t)$ we obtain
        $$\alpha(x;q)F_0^2(x;q)-\beta(x;q)F_0(x;q)+\gamma(x;q)=0.$$
Hence, by solving the above equation we get the desired result.
\end{proof}

For example, Theorem~\ref{th12} for $k=1$ gives
$F_1(x;q)=C\left(\frac{x}{1+x(1-q)}\right)$ (see~\cite[Equations~2.2
and 2.3]{Sun}). In particular, $F_1(x;0)=C(x/(1+x))$. This result
can be generalized by using Theorem~\ref{th12} with $q=0$.

\begin{corollary}
The ordinary generating function for the number of Dyck paths of
length $2n$ that avoid $\underbrace{uu\cdots u}_{k}du$ is given by
$$\frac{U_{k}\ttx+\sqrt{x}U_{k-1}\ttx}{(1+x)U_{k}\ttx}
C\left(\frac{xU_{k}\ttx+x\sqrt{x}U_{k-1}\ttx}{(1+x)^2U_{k}\ttx}\right),$$
where $U_j(t)$ is the $j$-th Chebyshev polynomial of the second kind
and $C(x)$ is the ordinary generating function for the Catalan
numbers.
\end{corollary}

For instance, the ordinary generating function for the number of
Dyck paths of length $2n$ that avoid $uudu$ is given by
$\frac{1}{1-x^2} C\left(\frac{x}{(1-x)(1+x)^2}\right)$
(see~\cite[A105633]{Sloane}).

%========================
\subsection{Enumeration of Dyck paths according to number of $ud\cdots udu$'s}
Let $\beta_i(D)$ be the number of occurrences of
$\underbrace{udud\cdots ud}_{i}u$ in the Dyck path $D$, see
Table~\ref{tab2}. Clearly, $\beta_1(D)=\alpha_1(D)$.
\begin{table}[ht]
\begin{center}
\begin{tabular}{l|lllllll}\hline
  $n\backslash\beta_2$ &amp; $0$ &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$&amp; $5$ &amp;$6$ \\ \hline
  $1$                   &amp; $1$ &amp;     &amp;     &amp;     &amp;    &amp;     &amp;\\
  $2$                   &amp; $2$ &amp;     &amp;     &amp;     &amp;    &amp;     &amp;\\
  $3$                   &amp; $4$ &amp; $1$ &amp;     &amp;     &amp;    &amp;     &amp;\\
  $4$                   &amp; $11$&amp; $2$ &amp; $1$ &amp;     &amp;    &amp;     &amp;\\
  $5$                   &amp; $31$&amp; $8$ &amp;  $2$&amp; $1$ &amp;     &amp;    &amp;\\
  $6$                   &amp; $92$&amp; $28$&amp; $9$ &amp; $2$ &amp; $1$ &amp;    &amp;\\
  $7$                   &amp; $283$&amp;$99$&amp;$34$ &amp;$10$ &amp;$2$  &amp; $1$&amp;\\
\end{tabular}
\vspace{10pt} \caption{Number of Dyck paths of length $2n$ according
the statistic $\beta_2$.}\label{tab2}
\end{center}
\end{table}
Define the ordinary generating function for the number of Dyck paths
of length $2n$ according to the statistics $\beta_1,\beta_2,\ldots$
as
$$G(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\beta_j(D)}.$$
To study the above ordinary generating function we need the
following notation
$$B_k(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\beta^k_j(D)},$$
where $\beta^k_j(D)=\beta_j\left(\underbrace{ud\cdots ud}_k
D\right)$. These ordinary generating functions satisfy the following
recurrence relations.


\begin{proposition}\label{th21}
For all $k\geq0$,
$$\begin{array}{l}
B_k(x;q_1,q_2,\ldots)=\prod\limits_{i=1}^{k}q_i^{k-i}+x\prod\limits_{i=1}^{k+1}q_i^{k+1-i}
(B_0(x;q_1,q_2,\ldots)-1)B_0(x;q_1,q_2,\ldots)\\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+xB_{k+1}(x;q_1,q_2,\ldots).\end{array}$$
\end{proposition}
\begin{proof}
An equation for the generating function $B_k(x;q_1,q_2,\ldots)$ is
obtained from the ``first return decomposition" of a Dyck paths $D$:
$D=uPdQ$, where $P$ and $Q$ are Dyck paths. Then each Dyck path $D$
that starts with $\underbrace{udud\ldots ud}_k$ can be decomposed as
either $D=\underbrace{udud\ldots ud}_k$, $D=\underbrace{udud\ldots
ud}_kuPdQ$ with $P$ a nonempty Dyck path, or
$D=\underbrace{udud\ldots ud}_{k+1}Q$ (see Figure~\ref{fig2} for
$k=2$).
\begin{figure}[ht]
\begin{center}
\begin{pspicture}(2,1)
\psline[linewidth=.5pt]{-&gt;}(1.5,0)\psline[linewidth=.5pt]{-&gt;}(0,.5)
\psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0)
\psline[linewidth=1pt](0.5,0)(.75,.25)\psline[linewidth=1pt](.75,.25)(1,0)
\end{pspicture}
\begin{pspicture}(4.5,1)
\psline[linewidth=.5pt]{-&gt;}(4,0)\psline[linewidth=.5pt]{-&gt;}(0,1)
\psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0)
\psline[linewidth=1pt](0.5,0)(.75,.25)\psline[linewidth=1pt](.75,.25)(1,0)
\psline[linewidth=1pt](1,0)(1.25,.25)\psline[linewidth=1pt](2.25,.25)(2.5,0)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.25,.25)(1.25,.25)(1.5,.5)(1.75,.45)(2,.5)(2.25,.25)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](3.5,0)(2.5,0)(2.75,.25)(3,.2)(3.25,.25)(3.5,0)
\rput(1.8,.7){\tiny$P\neq\emptyset$}\rput(3,.45){\tiny$Q$}
\end{pspicture}
\begin{pspicture}(4.5,1)
\psline[linewidth=.5pt]{-&gt;}(4,0)\psline[linewidth=.5pt]{-&gt;}(0,1)
\psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0)
\psline[linewidth=1pt](0.5,0)(.75,.25)\psline[linewidth=1pt](.75,.25)(1,0)
\psline[linewidth=1pt](1,0)(1.25,.25)\psline[linewidth=1pt](1.25,.25)(1.5,0)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.5,0)(1.5,0)(1.75,.25)(2,.2)(2.25,.25)(2.5,0)
\rput(2,.45){\tiny$Q$}
\end{pspicture}
\caption{First return decomposition of a Dyck path according the
statistic $ududu$.}\label{fig2}
\end{center}
\end{figure}
Thus, the ordinary generating function $B_k(x;q_1,q_2,\ldots)$ is
given by
$$\begin{array}{l}
\prod\limits_{i=1}^{k}q_i^{k-i}+x\prod\limits_{i=1}^{k+1}q_i^{k+1-i}
(B_0(x;q_1,q_2,\ldots)-1)B_0(x;q_1,q_2,\ldots)+xB_{k+1}(x;q_1,q_2,\ldots),\end{array}$$
for all $k\geq0$, as required.
\end{proof}

\begin{theorem}\label{th22}
The generating function $G(x;q_1,q_2,\ldots)$ is given by
$$G(x;q_1,q_2,\ldots)=C\left(\frac{x\sum_{m\geq0}x^m\prod_{i=1}^{m+1}q_i^{m+1-i}}{1+x\sum_{m\geq0}x^m\prod_{i=1}^{m+1}q_i^{m+1-i}}\right),$$
where $C(x)$ is the generating function for the Catalan numbers.
\end{theorem}
\begin{proof}
We simply use the fact that
$B_0(x;q_1,q_2,\ldots)=G(x;q_1,q_2,\ldots)$ and apply the recurrence
relation
$$\begin{array}{ll}
B_k(x;q_1,q_2,\ldots)&amp;=\prod\limits_{i=1}^{k}q_i^{k-i}+x\prod\limits_{i=1}^{k+1}q_i^{k+1-i}
(B_0(x;q_1,q_2,\ldots)-1)B_0(x;q_1,q_2,\ldots)\\
&amp;+xB_{k+1}(x;q_1,q_2,\ldots)\end{array}$$ an infinite number of
times and in each step we perform some rather tedious algebraic
manipulations.
\end{proof}

\begin{example}
Let $q_{2i-1}=q$ and $q_{2i}=q^{-1}$ for all $i\geq1$. Then
Theorem~\ref{th22} gives that
$$\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_1(D)-\beta_2(D)+\cdots}=
C\left(\frac{x(1+xq)}{1+x}\right)$$ which is equivalent to
$$\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_1(D)-\beta_2(D)+\cdots}=
1+\sum_{n\geq1}x^n\sum_{i=0}^{n+1}\sum_{j=0}^{i+1}C_i\binom{i+1}{j}\binom{n-1-j}{i}q^j.$$
In particular, the ordinary generating function for the number of
Dyck paths $D$ of length $2n$ with
\begin{equation}\label{sbb}
\sum_{i\geq1}\beta_{2i-1}(D)=\sum_{i\geq1}\beta_{2i}(D)
\end{equation} is given by $C(x/(1+x))=M(x)$, that is, the number of Dyck
paths $D$ of length $2n$ with (\ref{sbb}) is given by $M_n$, the
$n$-th Mozkin number.
\end{example}

\begin{example}
Let $q_i=q$ for all $i\geq1$. Then, similar to Example~\ref{exaaa},
we obtain from Theorem~\ref{th22} that
$$\sum_{D\in\DD_n}(\beta_1(D)+\beta_2(D)+\cdots)=\sum_{j=0}^{n-2}\binom{2j+2}{j},$$
for all $n\geq2$.
\end{example}

Denote the ordinary generating function $G(x;q_1,q_2,\ldots)$ with
$q_k=q$ and $q_i=1$ for all $i\neq k$ by $G_k(x;q)$. For example, if
$q_1=q$ and $q_i=1$, $i=2,3,\ldots$, then Theorem~\ref{th22} gives
$G_1(x;q)=C\left(\frac{x}{1+x(1-q)}\right)$ (see~\cite[Equations~2.2
and 2.3]{Sun}). In general, if $q_k=q$ and $q_i=1$ for all $i \neq
k$, then Theorem~\ref{th12} gives an explicit formula for the
ordinary generating function $G_k(x;q)$.

\begin{corollary}\label{th23}
The ordinary generating function for the Dyck paths of length $2n$
according to the statistic $\beta_k$ is given by
$$G_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_k}=
C\left(\frac{x(1-xq-x^k(1-q))}{1-xq-x^{k+1}(1-q)}\right),$$ where
$C(x)$ is the generating function for the Catalan numbers.
\end{corollary}

For instance, Corollary~\ref{th23} for $k=2$ and $q=0$ gives that
the ordinary generating function for the number of Dyck paths of
length $2n$ that avoid $UDUDU$ is given by
$$C\left(\frac{x(1-x^2)}{1-x^3}\right)=1+\sum_{n\geq1}x^n\left(\sum_{i=1}^n\sum_{j=0}^{(n-m)/2}
(-1)^{\frac{n-m+j}{3}}\binom{m}{j}\binom{\frac{n+2m-2j}{3}-1}{m-1}C_m\right).$$

\section{Enumeration of Dyck paths according to number of $uu\ldots udu$'s or
number of $udud\ldots udu$'s at low and high levels}
%We say that a $\underbrace{uu\ldots u}_kdu$ ($\underbrace{udud\ldots
%ud}_ku$) is at low (resp. high) level if its peak is at level $k$
%exactly (resp. greater than level $k$).
In this section we consider the following statistics on Dyck paths:
number of low (high) level $uu\ldots udu$'s or number of low (high)
level $udud\ldots udu$'s (for the case $k=1$, see \cite[Section
3]{Sun}).

\subsection{Enumeration of Dyck paths according to number of
$uu\ldots udu$'s at low and high levels} Let $\gamma_k$ (resp.
$\gamma'_k$) be the number of occurrences of $\underbrace{uu\ldots
u}_kdu$ at low (resp. high) level. Denote the ordinary generating
function for the number of Dyck paths of length $2n$ according to
the statistics $\gamma_k$ (resp. $\gamma'_k$) by
$$L_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\gamma_k(D)}\quad
\left(\mbox{resp.}\,\,
H_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\gamma'_k(D)}\right).$$


\begin{theorem}\label{th31}
Let $k\geq2$. Then the number of Dyck paths of length $2n$ with
$\gamma_k=m$ is given by
$$\sum_{j\geq0}(-1)^j\frac{(m+j)(k+1)+1}{2n+1-(m+j)(k+1)}\binom{m+j}{j}\binom{2n+1-(m+j)(k+1)}{n+1}.$$
\end{theorem}
\begin{proof}
Consider any Dyck path $D=uPdQ$, where $P$ and $Q$ are Dyck paths.
So $D$ contains $a_k:=\underbrace{uu\ldots u}_kdu$ if either $P$
starts with $a_{k-1}$ or $Q$ contains $a_{k}$ (see
Figure~\ref{fig3}).
\begin{figure}[ht]
\begin{center}
\begin{pspicture}(3,1)
\psline[linewidth=.5pt]{-&gt;}(3,0)\psline[linewidth=.5pt]{-&gt;}(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)
\psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.5,0)(1.5,0)(1.75,.25)(2,.2)(2.25,.25)(2.5,0)
\rput(.8,.7){\tiny$P$}\rput(2,.45){\tiny$Q$}
\end{pspicture}
\caption{First return decomposition of a Dyck path.}\label{fig3}
\end{center}
\end{figure}
Thus, $L_k(x;q)=1+xt_1(x;q)L_k(x;q)$, where
$t_j(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\gamma_k\left(\underbrace{uu\ldots
u}\nolimits_jD\underbrace{dd\ldots d}\nolimits_j\right)}$ for all
$j=1,2,\ldots k-1$. Again, using the first return decomposition of a
Dyck path we obtain that the ordinary generating function $t_j(x;q)$
equals $1+xt_{j+1}(x;q)C(x)$, where $C(x)$ is the ordinary
generating function for the Catalan numbers and $j=1,2,\ldots,k-2$.
In addition, $t_{k-1}(x;q)=1+x+xC(x)(C(x)-1)+xq(C(x)-1)$. Therefore,
it is easy to check that
$$t_1(x;q)=(xC(x))^{k-2}t_{k-1}(x;q)+\sum_{j=0}^{k-3}(xC(x))^j.$$
This implies that the ordinary generating function $L_k(x;q)$ is
given by
$$L_k(x;q)=\frac{1}{1-x\left(\frac{1-(xC(x))^{k-2}}{1-xC(x)}+(xC(x))^{k-2}t_1(x;q))\right)}.$$
By using the identity $C(x)=\frac{1}{1-xC(x)}$ (see
(\ref{eqcatalan})) we arrive at
$$L_k(x;q)=\frac{C(x)}{1+(1-q)(xC(x))^{k+1}}=\sum_{m\geq0}\frac{x^{m(k+1)}C^{m(k+1)+1}(x)}
{(1+(xC(x))^{k+1})^{m+1}},$$ which is equivalent to
$$L_k(x;q)=\sum_{m\geq0}\sum_{j\geq0}(-1)^j\binom{m+j}{j}x^{(m+j)(k+1)}C^{(m+j)(k+1)+1}(x).$$
On other hand, by applying the Lagrange inversion formula in
\cite{wilf}, we get that
$$C^k(x)=\sum_{n\geq 0}\frac{k}{2n+k}\binom{2n+k}{n}x^n.$$
Hence, the $x^nq^m$ coefficient in the ordinary generating function
$L_k(x;q)$ is given by
$$\sum_{j\geq0}(-1)^j\frac{(m+j)(k+1)+1}{2n+1-(m+j)(k+1)}\binom{m+j}{j}\binom{2n+1-(m+j)(k+1)}{n+1},$$
as required.
\end{proof}
For example, Theorem~\ref{th31} for $k=2$ (for the case $k=1$
see~\cite[Theorem~3.1]{Sun}) gives that the number of Dyck paths of
length $2n$ having $\gamma_2=m$ is given by
$$\sum_{j\geq0}(-1)^j\frac{3(m+j)+1}{2n+1-3(m+j)}\binom{m+j}{j}\binom{2n+1-3(m+j)}{n+1}.$$

\begin{theorem}\label{th32}
The ordinary generating function for the number of Dyck paths of
length $2n$ according to the statistic $\gamma'_k$ is given by
$$H_k(x;q)=\frac{1}{1-x\dfrac{1-x^k(1-q)F_k^{k-1}(x;q)(F_k(x;q)-1)}{1-xF_k(x;q)}},$$
where the explicit formula for the ordinary generating function
$F_k(x;q)$ is given by Theorem~\ref{th12}.
\end{theorem}
\begin{proof}
Again (see Theorem~\ref{th31}), by using the first return
decomposition of a Dyck path $D$ ($D=uPdQ$ where $P$ and $Q$ are
Dyck paths, see Figure~\ref{fig3}), we obtain that the ordinary
generating function $H_k(x;q)$ satisfies
$H_k(x;q)=1+xt_1(x;q)H_k(x;q)$, where $t_j(x;q)$ satisfies the
recurrence relation $t_j(x;q)=1+xt_{j+1}(x;q)F_k(x;q)$, for
$j=1,2,\ldots k$, and
$t_{k}(x;q)=1+x+x(t_k(x;q)-1)F_k(x;q)+xq(F_k(x;q)-1)$. Solving the
above system of equations we get the desired result.
\end{proof}

Theorems \ref{th31} and \ref{th32} give the following result. For
$\gamma'_1=0$, we obtain that the number of Dyck paths of length
$2n$ is given by the $n$-th Motzkin number (see
\cite[Equation~3.6]{Sun}). For $\gamma'_2=0$, we obtain that the
ordinary generating function for the number of Dyck paths of length
$2n$  is given by
$$\frac{2x^3+x^2-5x+3-(2x+1)\sqrt{x^4-2x^3-5x^2-2x+1}}{2(x^5+x^4+4x^3+5x^2-4x+1)}.$$

\subsection{Enumeration of Dyck paths according to number of
$ud\ldots udu$'s at low and high levels} Let $\delta_k$ (resp.
$\delta'_k$) be the number of occurrences of $\underbrace{udud\ldots
ud}_ku$ at low (resp. high) level. Denote the ordinary generating
function for the number of Dyck paths of length $2n$ according to
the statistics $\delta_k$ (resp. $\delta'_k$) by
$$L'_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\delta_k(D)}\quad
\left(\mbox{resp.}\,\,
H'_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\delta'_k(D)}\right).$$
Using the same techniques as in the previous subsection we obtain
the following results.

\begin{theorem}\label{th41}
Let $k\geq1$. Then the ordinary generating function for the number
of Dyck paths of length $2n$ according to the statistic $\delta_k$
is given by
$$L'_k(x;q)=\frac{1-x^{k+1}-xq(1-x^k)}{1-x^{k+1}-x(1-x^k)C(x)-xq(1-x^k-x(1-x^{k-1})C(x))}.$$
Moreover, the ordinary generating function for the number of Dyck
paths of length $2n$ with $\delta_k=m$ is
$$\frac{x^{m+k}(1-x)^2C(x)(1-x^k-x(1-x^{k-1})C(x))^{m-1}}{(1-x^{k+1}-x(1-x^k)C(x))^{m+1}}$$
when $m\geq1$, and $\frac{1-x^{k+1}}{1-x^{k+1}-x(1-x^k)C(x)}$ when
$m=0$.
\end{theorem}

For example, the number of Dyck paths of length $2n$ having
$\delta_1=0$ is given by $\frac{1+x}{1+x-xC(x)}$
(see~\cite[Page~5]{Sun}), and having $\delta_2=0$ is given by
$\frac{1+x+x^2}{1+x+x^2-x(1+x)C(x)}$.

To enumerate the number of Dyck paths of length $2n$ according to
the statistic $\delta'_k$ we use the first return decomposition of a
Dyck path  and Corollary~\ref{th23}. Thus we obtain the following
result.

\begin{theorem}\label{th42}
Let $k\geq1$. Then the ordinary generating function for the number
of Dyck paths of length $2n$ according to the statistic $\delta'_k$
is given by
$$H'_k(x;q)=\frac{1}{1-xG_k(x;q)},$$
where
$$G_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_k}=
C\left(\frac{x(1-xq-x^k(1-q))}{1-xq-x^{k+1}(1-q)}\right).$$
\end{theorem}

For example, the ordinary generating function for the number of Dyck
paths of length $2n$ having $\delta'_1=0$ is given by $M(x)$
(see~\cite[Equation~3.6]{Sun}).
%===========================================================================
\begin{thebibliography}{2}
\bibitem{D2}
E.~Deutsch, Dyck path enumeration, {\em Discr. Math.} {\bf 204}
(1999), 167--202.

\bibitem{K9}
G. Kreweras, Joint distribution of three descriptive parameters of
bridges, {\em Combinatoire \'Enum\'erative}, {\em Proc. (Montr\'eal,
Que., 1985/Qu\'ebec, Que., 1985), Lec. Notes in Math.} {\bf 1234}
(1986), 177--191.

\bibitem{KM10}
G. Kreweras and P. Moszkowski, A new enumerative property of the
Narayana numbers, {\em J. Statist. Plann. and Infer.} {\bf 14}
(1986), 63--67.

\bibitem{KP11}
G. Kreweras and Y. Poupard, Subdivision des nombres de Narayana
suivant deux param\'etres suppl\'ementaires, {\em Europ. J. Combin.}
{\bf 7} (1986), 141--149.

\bibitem{M}
T. Mansour, Counting peaks at height $k$ in a Dyck path, {\em
Journal of Integer Sequences} {\bf 5} (2002), Article 02.1.1.

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

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

\bibitem{Sloane}
N. J. A.~Sloane and S.~Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, New York (1995).

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

\bibitem{wilf}
H. Wilf, {\it Generatingfunctionology}, Academic Press, New York,
1990.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
05A05, 05A15, 42C05.\\


\noindent  {\it Keywords}: Chebyshev polynomials, Dyck paths,
Generating functions.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A001006}, \seqnum{A002054},
\seqnum{A078481}, and \seqnum{A105633}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 2 2005;
revised version received January 16 2006.  
Published in {\it Journal of Integer Sequences}, January 17 2006.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>