\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}