\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}
& & & & & \circ & & \circ & & & \\
& & \circ & & \circ & & \circ & & \circ & & \\
& \circ & & \circ & & & & & & \circ & \\
\times & & & & & & & & & & \circ
\end{array}
\]
\[
\begin{array}{ccccccccccc}
& & & & & \circ & & \circ & & & \\
& & & & \circ & & \circ & & \circ & & \\
& \circ & & \circ & & & & & & \circ & \\
\times & & \circ & & & & & & & & \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}
& A & \\
\times & & 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)
&=&\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) \\
&=&[x^n]\{xC(x)G_1(x)\}-g(1,n-1)
\end{eqnarray*}
Therefore
\begin{eqnarray*}
G_1(x) &=&1+\sum\limits_{n\geq 2}g(1,n)x^n=1+xC(x)G_1(x)-x-xG_1(x)+x \\
&=&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}
& & & & & & & & & & & & & & & & & & \\
& & & & & & & & & & & \circ & & \circ & & & & & \\
& & \circ & & \circ & & & & & & \circ & & \circ & & \circ & & &
& \\
& \circ & & \circ & & \circ & & \circ & & \circ & & & & & & \circ &
& & \\
\times & & & & & & \circ & & \circ & & & & & & & & \circ & &
\end{array}
\]
\[
P^{*}=
\begin{array}{ccccccccccccccccccc}
& & & & & & & & & & & & & & & & & & \\
& & & & & & & & & & & & & \circ & & \circ & & & \\
& & & & \circ & & \circ & & & & & & \circ & & \circ & & \circ &
& \\
& \circ & & \circ & & \circ & & \circ & & \circ & & \circ & & & & &
& \circ & \\
\times & & \circ & & & & & & \circ & & \circ & & & & & & & &
\circ
\end{array}
\]
$\ $%
\[
\widetilde{P}=
\begin{array}{ccccccccccccccccccccccc}
& & & & & & & & & & & & & & & & \circ & & \circ & & & &
\\
& & & & & \circ & & \circ & & & & & & & & \circ & & \circ & &
\circ & & & \\
& & & & \circ & & \circ & & \circ & & & & & & \circ & & & & &
& \circ & & \\
& \circ & & \circ & & & & & & \circ & & \circ & & \circ & & & &
& & & & \circ & \\
\times & & \circ & & & & & & & & \circ & & \circ & & & & & &
& & & & \circ
\end{array}
\]
\[
\widehat{P}=
\begin{array}{ccccccccccccccccccc}
& & & & & & & & & & & & \circ & & \circ & & & & \\
& & & \circ & & \circ & & & & & & \circ & & \circ & & \circ & &
& \\
& & \circ & & \circ & & \circ & & & & \circ & & & & & & \circ &
& \\
& \circ & & & & & & \circ & & \circ & & & & & & & & \circ & \\
\times & & & & & & & & \circ & & & & & & & & & & \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 \& 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 \& 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}