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

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

\usepackage{amsthm,amssymb}
\usepackage{psfig,epsf}

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

\newcommand{\rk}{{\rm rk}}

\newcommand{\bbox}{\nopagebreak[4] \hfill\rule{2mm}{2mm}}
\newcounter{resno}
\newenvironment{Proof}{{\sc Proof.\ }}{\hfill\bbox\bigskip}
\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo113.eps}
\vskip 1cm

{\LARGE \bf Dyck Paths With No Peaks At Height k }
\vskip 1.5cm

{\large Paul Peart and Wen-Jin Woan} \smallskip \\
Department of Mathematics \\
Howard University \\
Washington, D.C. 20059, USA \medskip \\
Email addresses:  \href{mailto:pp@scs.howard.edu}{pp@scs.howard.edu},
\href{mailto:wwoan@howard.edu}{wwoan@howard.edu} \\
\vskip2.5cm

{\bf Abstract}
\end{center}

{\em A Dyck path of length $2n$ is a path in two-space from $%
(0,0) $ to $(2n,0)$ which uses only steps $(1,1)$ (north-east) and $(1,-1)$
(south-east). Further, a Dyck path does not go below the $x$-axis. A peak on
a Dyck path is a node that is immediately preceded by a north-east step and
immediately followed by a south-east step. A peak is at height $k$ if its $y$%
-coordinate is $k.$ Let $G_k(x)$ be the generating function for the number
of Dyck paths of length $2n$ with no peaks at height $k$ with $k\geq 1.$ It
is known that $G_1(x)$ is the generating function for the Fine numbers
(sequence \htmladdnormallink{A000957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000957} in \cite{OEIS}). In this paper, we derive the recurrence 
\[
G_k(x)=\frac 1{1-xG_{k-1}(x)},\;k\geq 2,\;G_1(x)=\frac 2{1+2x+\sqrt{1-4x}}. 
\]
It is interesting to see that in the case $k=2$ we get $G_2(x)=1+xC(x)$,
where $C(x)$ is the generating function for the ubiquitous Catalan numbers
(\htmladdnormallink{A000108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108}). This means that the number of Dyck paths of length $2n+2,$ $n\geq 0,$
with no peaks at height 2 is the Catalan number $c_n=\frac 1{n+1}\left(
_{\;n}^{2n}\right) .$ We also provide a combinatorial proof for this last
fact by introducing a bijection between the set of all Dyck paths of length $%
2n+2$ with no peaks at height 2 and the set of all Dyck paths of length $2n.$}

\vspace*{+.1in}

\noindent {\em Keywords}: Dyck paths, Catalan number, Fine number, generating function.

\section{Introduction}

In \cite{DE} it was shown that Fine numbers (\htmladdnormallink{A000957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000957}) count Dyck paths with no peaks
at height 1. One of the results of this paper is that the Catalan numbers
(\htmladdnormallink{A000108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108}) count Dyck paths with no peaks at height 2. This provides yet another
combinatorial setting for the Catalan numbers (cf. \cite{GO}, \cite{SH}, \cite{OEIS}, \cite{ST} ).

A Dyck path is a path in two-space which starts at the origin, stays above
the $x$-axis, and allows only steps of $(1,1)$ (i.e. north-east) and $(1,-1)$
(i.e. south-east). A Dyck path ends on the $x$-axis. A Dyck path therefore
has even length with the number of north-east steps equal to the number of
south-east steps. A lattice point on the path is called a peak if it is
immediately preceded by a north-east step and immediately followed by a
south-east step. A peak is at height $k$ if its $y$-coordinate is $k$. Here
are two Dyck paths each of length 10:

\[
\begin{array}{ccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  \\ 
&amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  \\ 
&amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  \\ 
\times &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ
\end{array}
\]

\[
\begin{array}{ccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  \\ 
&amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  \\ 
&amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  \\ 
\times &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ
\end{array}
\]

\noindent The first path has one peak at height 2 and two peaks at height 3.
It has no peaks at height 1. The second path has one peak at height 1 and
two at height 3. It has no peaks at height 2. Reference \cite{DE} contains much
information about Dyck paths. It is known that the number of Dyck paths of
length $2n$ is $c_n,$ the $n^{th}$ Catalan number, given by 
\[
c_n=\frac 1{n+1}\left( _{\;n}^{2n}\right) . 
\]
We will prove that the number of these paths with no peaks at height 2 is $%
c_{n-1}$ . It is known \cite{DE} that the number of these paths with no peaks at
height 1 is $f_n,$ the $n^{th}$ Fine number with generating function 
\[
F(x)=\frac 1{1-x^2C^2(x)}=1+x^2+2x^3+6x^4+18x^5+57x^6+186x^7+O\left(
x^8\right) 
\]
where $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function for the
Catalan numbers. See \cite{DE}, \cite{DS}, and \cite{FI} for further information about the
Fine numbers. Theorem 2 below contains a proof that the Fine numbers count
Dyck paths with no peaks at height 1. In Theorem 1, we obtain the recurrence 
\[
G_k(x)=\frac 1{1-xG_{k-1}(x)}\;,\;k\geq 2, 
\]
where $G_k(x)$ is the generating function for the number of Dyck paths of
length $2n$ with no peaks at height $k.$ In Section 3 we introduce a
bijection between the set of all Dyck paths of length $2n$ and the set of
all Dyck paths of length $2n+2$ with no peaks at height 2. This bijection
provides a combinatorial proof that $G_2(x)=1+xC(x).$

\section{Theorems}

We will use the fact that 
\[
F(x)=\sum\limits_{n\geq 0}f_nx^n=\frac{C(x)}{1+xC(x)}.\qquad \qquad \qquad
\qquad \qquad \qquad \qquad \qquad 
\]
Theorem 1: Let $G_m(x)=\sum\limits_{n\geq 0}g(m,n)x^n$ be the generating
function for Dyck paths of length $2n$ with no peaks at height $m$, $m\geq 1$%
. Then 
\[
G_m(x)=\frac 1{1-xG_{m-1}(x)}\quad ;\quad m\geq 2\;.
\]

\begin{Proof}
The set of all Dyck paths of length $2n$ , $n\geq 0,$ with
no peaks at height $m$ consists of the trivial path ( the origin) and paths
with general form shown in the diagram.

\[
\begin{array}{ccc}
&amp; A &amp;  \\ 
\times &amp;  &amp; B
\end{array}
\]

It starts with a north-east step followed by a segment labeled $A$ which
represents any Dyck path of length $2k$, $0\leq k\leq n-1$ , with no peaks
at height $m-1$. $A$ is followed by a south-east step followed by a segment
labeled $B$ which represents any Dyck path of length $2n-2-2k$ with no peaks
at height $m$. Therefore 
\[
g(m,0)=1,\,g(m,n)=\sum\limits_{k=0}^{n-1}g(m-1,k)g(m,n-1-k)=\left[
x^{n-1}\right] \{G_{m-1}(x)G_m(x)\}.
\]
\[
i.e.\quad g(m,0)=1,\quad g(m,n)=\left[ x^n\right]
\{xG_{m-1}(x)G_m(x)\}\;;\quad n\geq 1,
\]
where $[x^k]$ denotes ''coefficient of $x^k$ in ''. That is, 
\[
G_m(x)=1+x\,G_{m-1}(x)G_m(x)\;,
\]
or equivalently,
\[
G_m(x)=\frac 1{1-xG_{m-1}(x)}
\]
\end{Proof}

Theorem 2: The number of Dyck paths of length $2n$ with no peaks at height 1
is the Fine number $f_n$ for $n\geq 0$ .\\ 
\begin{Proof}
With the
notation of Theorem 1, we will prove that 
\[
G_1=\sum\limits_{n=0}^\infty g(1,n)x^n=\frac 1{1-x^2C^2}
\]
Obviously, $g(1,0)=1$ and $g(1,1)=0.$ For $n\geq 2$ , a Dyck path of length $%
2n$ with no peaks at height 1 has the form of the diagram in the proof of
Theorem 1 with A any Dyck path of length $2k,$ $1\leq k\leq n-1$ , and B a
Dyck path of length $2n-2k-2$ with no peaks at height 1. Therefore, for $%
n\geq 2$ , we have 
\begin{eqnarray*}
g(1,n)
&amp;=&amp;\sum\limits_{k=1}^{n-1}c_k\,g(1,n-k-1)=[x^{n-1}]\{C(x)G_1(x)\}-g(1,n-1) \\
&amp;=&amp;[x^n]\{xC(x)G_1(x)\}-g(1,n-1)
\end{eqnarray*}
Therefore 
\begin{eqnarray*}
G_1(x) &amp;=&amp;1+\sum\limits_{n\geq 2}g(1,n)x^n=1+xC(x)G_1(x)-x-xG_1(x)+x \\
&amp;=&amp;1+xG_1(x)\left( C(x)-1\right) =1+xG_1(x)xC^2(x)
\end{eqnarray*}

\noindent That is, \ 
\[
G_1(x)=\frac 1{1-x^2C^2(x)}
\]
\end{Proof}
\\Theorem 3: The number of Dyck paths of length $2n$ with no peaks at height
2 is the Catalan number $c_{n-1}$ , for $n\geq 1.$

\begin{Proof}
From Theorem 1, 
\[
G_2(x)=\frac 1{1-xG_1(x)}=\frac 1{1-x\frac{C(x)}{1+xC(x)}}=1+xC(x)
\]
\end{Proof}
\\Remark: In \cite{DE} it was shown that 
\[
\frac{f_{n-1}}{c_n}\rightarrow \frac 19\quad as\quad n\rightarrow \infty 
\]
Therefore 
\[
\frac{f_n}{c_n}\rightarrow \frac 49\quad as\quad n\rightarrow \infty 
\]
Since 
\[
\frac{c_{n-1}}{c_n}\rightarrow \frac 14\quad as\quad n\rightarrow \infty 
\]
we see that, for sufficiently large $n$, approximately $\frac 49$ of the
Dyck paths of length $2n$ have no peaks at height 1, while approximately $%
\frac 14$ have no peaks at height 2.\\Remark: $G_3(x)=\frac 2{2-3x+x\sqrt{%
\left( 1-4x\right) }}=1+x+2x^2+4x^3+9x^4+22x^5+58x^6$

$\qquad \qquad \qquad \qquad \qquad \;+163x^7+483x^8+1494x^9+O\left(
x^{10}\right) $ (sequence \htmladdnormallink{A059019}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059019} in \cite{OEIS} ).

\section{A bijection between two Catalan families}

We end with a bijection between the two Catalan families mentioned in this
paper. Let ${\bf {\rm \Phi }}$\ be the set of all Dyck paths of length $2n$
and let ${\bf {\rm \Psi }}$\ be the set of all Dyck paths of length $2n+2$
with no peaks at height 2. We define a bijection between ${\bf {\rm \Phi }}$%
\ and ${\bf {\rm \Psi }}$\ as follows. First, starting with a Dyck path\ $P$
from\ ${\bf {\rm \Phi }}$, we obtain a Dyck path $\widehat{P}$ from ${\bf 
{\rm \Psi }}$\ using the following steps.

\begin{description}
\item  (1) Attach a Dyck path of length 2 to the left of $P$ to produce $%
P^{*}.$

\item  (2) Let $S^{*}$ be a maximal sub-Dyck path of $P^{*}$ with $S^{*}$
having no peaks at height 1. To each such $S^{*}$ add a north-east step at
the beginning and a south-east step at the end to produce sub-Dyck path $%
\widetilde{S}$. This step produces a Dyck path $\widetilde{P}.$

\item  (3) From $\widetilde{P}$ eliminate each Dyck path of length 2 that is
to the immediate left of each $\widetilde{S}$. We now have a unique element $%
\widehat{P}$ of\ ${\bf {\rm \Psi }}$.\medskip\ 
\end{description}

To obtain $P$ from $\widehat{P}$ , we reverse the steps as follows:

\begin{description}
\item  (1) Let $\widehat{S}$ be a sub-Dyck path of $\widehat{P}$ between two
consecutive points on the $x$-axis with $\widehat{S}$ having no peaks at
height 1. To each $\widehat{S}$ add a Dyck path of length 2 immediately to
the left. This step produces a Dyck path $\widetilde{P}$ .

\item  (2) Let $\widetilde{S}$ be a maximal sub-Dyck path of $\widetilde{P}$
. From each such $\widetilde{S}$ remove the left-most north-east step and
the right-most south-east step to produce a sub-Dyck path $S^{*}$. This step
produces a Dyck path $P^{*}$ of length 2n+2.

\item  (3) From $P^{*}$ , remove the left-most Dyck path of length 2 to
produce $P.$
\end{description}

For example, we obtain a Dyck path of length 18 with no peaks at height 2
starting with a Dyck path of length 16 as follows:

\[
P= 
\begin{array}{ccccccccccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
&amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp; 
&amp;  \\ 
&amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp; 
&amp;  &amp;  \\ 
\times &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; 
\end{array}
\]

\[
P^{*}= 
\begin{array}{ccccccccccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  \\ 
&amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp; 
&amp;  \\ 
&amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp; 
&amp; \circ &amp;  \\ 
\times &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; 
\circ
\end{array}
\]

$\ $%
\[
\widetilde{P}= 
\begin{array}{ccccccccccccccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp; 
\\ 
&amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; 
\circ &amp;  &amp;  &amp;  \\ 
&amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp; 
&amp; \circ &amp;  &amp;  \\ 
&amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp; 
&amp;  &amp;  &amp;  &amp; \circ &amp;  \\ 
\times &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; 
&amp;  &amp;  &amp;  &amp; \circ
\end{array}
\]

\[
\widehat{P}= 
\begin{array}{ccccccccccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  \\ 
&amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; 
&amp;  \\ 
&amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp; 
&amp;  \\ 
&amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  \\ 
\times &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ
\end{array}
\]

It is now easy to show that the Catalan numbers count paralellogram
polynominoes ( or Fat Path Pairs ) with no columns at height 2 (see \cite{ST}, p.
257).

\begin{thebibliography}{20}

\bibitem{DE}
E. Deutsch. \ {\it Dyck Path Enumeration}. Discrete Math. 204
(1999), no. 1-3, 167-202.

\bibitem{DS}
E. Deutsch \&amp; L. W. Shapiro. {\it Fine Numbers}. Preprint.

\bibitem{FI}
T. Fine. \ {\it Extrapolation when very little is known about the
source}. Information and Control\ 16 (1970) 331-359.

\bibitem{GO}
H. W. Gould. {\it Bell \&amp; Catalan Numbers:} Research Bibliography
of Two Special Number Sequences, 6th ed. Morgantown, WV: Math Monongliae,
1985.

\bibitem{SH}
L. W. Shapiro. {\it A Catalan Triangle}. Discrete Math. 14 (1976)
83-90.

\bibitem{OEIS}
N. J. A. Sloane,
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim$njas/sequences/
}{http://www.research.att.com/~njas/sequences/}.

\bibitem{ST}
R. P. Stanley. {\it Enumerative Combinatorics}. Vol. 2. Cambridge
University Press, 1999.

\end{thebibliography}

\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Concerned with sequences
\htmladdnormallink{A000108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108},
\htmladdnormallink{A000957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000957},
\htmladdnormallink{A059019}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059019},
\htmladdnormallink{A059027}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059027}.)
}

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent

Received October 16, 2000; revised version received February 8, 2001;
published in Journal of Integer Sequences, May 12, 2001.

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}

\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home
page}{http://www.research.att.com/~njas/sequences/JIS/}.

\centerline{\rule{6.5in}{.01in}}

\end{document}

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