\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\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,amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{epsfig}
\usepackage{mathrsfs}


\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
A Natural Extension of Catalan Numbers
}
\vskip 1cm
\large
Noam Solomon and Shay Solomon\footnote{Corresponding author. Tel: +972-8-642-8087; Fax: +972-8-647-7650.} \\
Dept. of Mathematics and Computer Science\\
Ben-Gurion University of the Negev \\
Beer-Sheva 84105 \\
Israel\\
\href{mailto:noams@cs.bgu.ac.il}{\tt noams@cs.bgu.ac.il}\\
\href{mailto:shayso@cs.bgu.ac.il}{\tt shayso@cs.bgu.ac.il}
\end{center}

\vskip .2 in

\begin {abstract}
A Dyck path is a lattice path in the plane integer lattice $\mathbb{Z}
\times \mathbb{Z}$ consisting of steps $(1,1)$ and $(1,-1)$, each
connecting diagonal lattice points, which never passes below the
$x$-axis. The number of all Dyck paths that start at $(0,0)$ and finish
at $(2n,0)$ is also known as the $n$th Catalan number.
In this paper we find a closed formula, depending on a non-negative
integer $t$ and on two lattice points $p_1$ and $p_2$, for the number
of Dyck paths starting at $p_1$, ending at $p_2$, and touching the
$x$-axis exactly $t$ times.
Moreover, we provide explicit expressions for the corresponding
generating function and bivariate generating function.
\end {abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remar}[theorem]{Remark}
\newenvironment{remark}{\begin{remar}\normalfont\quad}{\normalsize\end{remar}}



\newcommand {\ignore} [1] {}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\def \bfm {\bf \boldmath}

\def \AA {{\alpha}}
\def \BB {{\beta}}
\def \CC {{\gamma}}
\def \PP {{\cal P}}
\def \CNF {{\cal C}}

\def \bigd {{B_1}}
\def \smallq {{Small}}
\def \smalld {{Small(n-1)}}
\def \smalla {{Small(n)}}
\def \smm {{Small(m)}}
\def \smmo {{Small(m-1)}}
\def \smn {{Small(n)}}
\def \smno {{Small(n-1)}}
\def\longto{\mathop{\longrightarrow}\limits}


\newtheorem{observation}{Observation}
\newtheorem{fact}{Fact}

\newtheorem{oproof}{Proof is omitted}
\renewcommand{\labelitemi}{$\bullet$}


\newenvironment{fminipage}%
  {\begin{Sbox}\begin{minipage}}%
  {\end{minipage}\end{Sbox}\fbox{\TheSbox}}

\newenvironment{algbox}[0]{\vskip 0.1in
\noindent
\begin{fminipage}{5.29in}
}{
\end{fminipage}
\vskip 0.1in
}
\newenvironment{algsmallbox}[0]{\vskip 0.1in
\noindent
\begin{fminipage}{3.65in}
}{
\end{fminipage}
\vskip 0.1in
}




\section {Introduction}

The \emph{Catalan sequence} is the sequence $\{C_n\}_{n \geq 0} =
\{1,1,2,5,14,42,132,429,\ldots\}$, where $C_n = \frac{1}{n+1} {2n
\choose n}$ is called the $n$th \emph{Catalan number}.  It is
sequence \seqnum{A000108} in Sloane's {\it Encyclopedia of
Integer Sequences}.  The
generating function for the Catalan numbers is given by $C(x) =
\frac{1 - \sqrt{1-4x}}{2x}$. The Catalan numbers
 provide a complete answer
to the problem of counting certain properties of more than 165
different combinatorial structures (see \cite[p.\ 219]{Stanley}
and \cite{Stanleybib}). For convenience, the generalization of
Catalan numbers presented in this paper is translated in terms of
Dyck paths.


\begin{figure}
\begin{center}
\includegraphics{pine3.eps}
\end{center}
\caption{\small (a) A Dyck path of length 12 from $(0,0)$ to $(12,0)$,
having exactly two contact points--the starting point and
the finishing point.
(b) A Dyck path of length 11 from $(1,1)$ to $(12,2)$, having no contact points.}
\label{Dyck}
\end{figure}

A \emph{Dyck path} is a lattice path in the integer lattice
$\mathbb{Z} \times \mathbb{Z}$ consisting of rise-steps $(1,1)$ and
fall-steps $(1,-1)$ that connect diagonal lattice points, which
never goes below the $x$-axis. (See Figure \ref{Dyck} for an
illustration.) Let $D((i,j), (i',j'))$ denote the set of all Dyck
paths that start at $(i,j)$ and finish at $(i',j')$. The number of
steps in any such Dyck path equals $i'-i$. Notice that  $\vert
D((i,j),(i',j'))\vert = 0$ iff at least one of the following
conditions holds:
\begin {itemize}
\item $i > i'$.
\item $j'-j > i'-i$.
\item $j'-j \ne i'-i \pmod 2$.
\item $j' < 0$ or $j <0$.
\end {itemize}
Otherwise, as a corollary of the Ballot theorem (cf.~\cite[p.\ 73]{Feller}), we get that
\begin {equation}
\label{simp}
\vert D((i,j),(i',j')) \vert=
{i'-i \choose \frac{i'-i+\vert j' - j \vert}{2}} -
{i'-i \choose \frac{i'-i+ j' + j + 2}{2}}.
\end {equation}
The number of Dyck paths that start at $(0,0)$ and finish at
$(2n,0)$ is also known as the $n$th Catalan number $C_n$.

There is an extensive literature on Dyck paths, often disguised by
means of similar combinatorial objects as Catalan numbers, Motzkin
paths, Schr\"{o}der paths, staircase walks,
Ballot-numbers, and more. We mention here but a limited number of
examples of previous work.


The notion of a peak on a Dyck path
 was introduced by Deutsch in \cite{Deutsch}, where it is shown that the
 number of Dyck paths of length $2n$ starting and ending on the $x$-axis
with no peaks at height 1 is given by the $n$th Fine number $F_n$,
  $\{F_n\}_{n \geq 0} = \{1,0,1,2,6,18,57,\ldots\}$.
In \cite{PW}, a complete answer for the number of
Dyck paths in $D((0,0),(2n,0))$ with no peaks at
height $k$ is given.
Further, an explicit expression for the generating
function for the number of Dyck paths in $D((0,0),(2n,0))$ with
exactly $r$ peaks at height $k$ is provided \cite{Mansour}.

Connections between Dyck paths and
pattern-avoiding permutations have been a subject of ongoing research.
Among various works in this context is the work of Knuth \cite{Knuth},
where it is shown that $S_n(312)$ satisfy the
Catalan recurrence, and the works of Bandlow and Killpatrick \cite{BK},
Krattenthaler \cite{Kr}, and Mansour et al.\ \cite{MDD}, where
bijections between
Dyck paths and permutations that avoid certain patterns of size three are presented.

The close relationship between lattice paths and queueing theory models
has been extensively studied.
The seminal papers by Mohanty \cite{Moh99} and Flajolet and Guillemin \cite{FG00}
offer lattice path perspectives for the Karlin-McGregor theory of
birth-death processes,
which is closely related to various queueing theory models.
The book by Fayolle et al.\ on random walks in the plane
integer lattice \cite{FIM99} is historically motivated by such queueing theory
questions \cite{FI79}.
In \cite{MMSKS95}, a combinatorial technique based on lattice path counting
is applied to derive the transient solution of the
$M/M/c$ queueing model, and in
\cite{BKM97} this result is extended
to (almost) arbitrary birth-death processes.
In \cite{AODW95}, equilibrium probability distributions of the queue length in the
$M/M/1$, $M/E_k/1$ and $E_l/E_k/1$ queueing models are presented,
based on the generating function for the number of minimal lattice paths.
In \cite{DM}, service times of customers in the $M/M/1$ queueing model
are analyzed, and it is shown that a family of polynomial generating sequence associated
with Dyck paths of length $2n$ provide the correlation function of the successive services
in a busy period with $n+1$ customers.

Brak and Essam \cite{BE2} considered the case of $k \geq 1$
non-intersecting Dyck paths that start and finish on the $x$-axis.
For the particular case of $k=1$, the \emph{contact polynomial}
defined as $P_n(x):=\sum_{t=2}^{n+1} |D_t((0,0),(2n,0))| x^{t}$ is
proved\footnote{In \cite {BE2}, a combinatorial proof for $P_n(C(x))
= \sum_{\ell=0}^{\infty}C_{n+\ell}x^{\ell}$ is provided. However,
this result had already been proved analytically in an earlier work
\cite{BE1}.}
 to satisfy $P_n(C(x)) = \sum_{\ell=0}^{\infty}C_{n+\ell}x^{\ell}$.
Via a bijection between \emph{bi-colored} Dyck paths and plain Dyck
paths, the analogue of the Chu-Vandemonde summation formula for Dyck
paths is derived.


In this paper we study ``generalized" Dyck paths,
 starting and ending at arbitrary points in the non-negative half-plane,
``touching" the $x$-axis any \emph{predetermined} number of times,
and never passing below the $x$-axis. We say that a Dyck path $P$
\emph{touches} the $x$-axis $t$ times, if exactly $t$ points on $P$
have zero as their $y$ coordinate. Following \cite{BE2}, any point
of $P$ that intersects the $x$-axis is called a \emph{contact}.
Denote the set of all Dyck paths starting at $(i,j)$, ending at
$(i',j')$, and touching the $x$-axis exactly $t$ times by
$D_t((i,j), (i',j'))$. We have $D((i,j),(i',j')) = \bigcup_{t \in
\mathbb{N}} D_t((i,j), (i',j'))$. Notice that
$$|D_0((0,1),(2n,1))| = |D((0,0),(2n,0))| = C_n.$$
More generally, we have $|D_0((i,j),(i',j'))|
=|D((i,j-1),(i',j'-1))|$. In the sequel, we henceforth concentrate
on Dyck paths that touch the $x$-axis \emph{at least once}.


\subsection {Main Results}
Our main contribution is the following theorem, for which we provide
a simple combinatorial proof.
\begin {theorem} \label{Main}
For any pair of lattice points $(i,j)$ and $(i',j')$, and for any
integer $t \geq 1$,
\begin{equation*} \vert
D_t((i,j),(i',j'))\vert = \left\{ \begin{array}{ll}
     0,                          & \mbox{if $j<0$ or $j'<0$};\\ \\
    \vert D((i,j+t-2),(i'-t,0)) \vert,                    & \mbox{if
$j'=0$};\\ \\
\vert D((i,j+t-1),(i'-t,j'-1)) \vert -    \\
\vert D((i,j+t-2),(i'-t,j'-2)) \vert,  & \mbox{if $j'>0$} .\
    \end{array}
   \right.
\end{equation*}
In the degenerate case $t+ \vert j \vert + \vert j' \vert + \vert
i'-i \vert = 1$, $\vert D_t((i,j),(i',j')) \vert = 1$.
\end {theorem}


We also find an explicit expression for the corresponding generating
function.

\begin {theorem} \label{generating}
For any non-negative integers $j,j'$ and $t$, with $t \ge 1$,
$$D_t^{j,j'}(x) ~:=~ \sum_{n \ge 0} d_t^{j,j'}(n)x^n ~=~ \frac{(1-\sqrt{1-4x^2})^{t+j+j'-1}}
{2^{(t+j+j'-1)}\cdot {x^{(j+j')}}},$$ where $D_t^{j,j'}(x)$ is the
generating function of the sequence $d_t^{j,j'}(n) := \vert
D_t((0,j),(n,j')) \vert$.
\end {theorem}

We derive the bivariate generating function as an easy consequence
of Theorem \ref{generating}.
\begin {corollary}
For any non-negative integers $j$ and $j'$, $$\Phi^{j,j'}(x,y) ~:=~
\sum_{t \ge 1,n \ge 0} d_{j,j'}(n,t)x^n y^t ~=~ \frac {y
(1-\sqrt{1-4x^2})^{j+j'}} {2^{(j+j'-1)} x^{(j+j')}(y\cdot
\sqrt{1-4x^2}+2-y)},$$ where $\Phi^{j,j'}(x,y)$ is the bivariate
generating function of the sequence $d_{j,j'}(n,t) := \vert
D_t((0,j),(n,j')) \vert$.
\end {corollary}


\subsection{Minor Results}
\begin {itemize}
\item By Theorem \ref{Main} and (\ref{simp}), we determine the
coefficients of the contact polynomial, as follows:
\begin{eqnarray*}
P_n(x) &:=&\sum_{t=2}^{n+1} |D_t((0,0),(2n,0))| x^{t} ~=~
\sum_{t=2}^{n+1} |D((0,0),(2n-t,t-2))| x^{t} \\ &=&\sum_{t=2}^{n+1}
\left[{2n-t \choose n-1} - {2n-t \choose n}\right] x^{t} ~=~
\sum_{t=2}^{n+1} \frac{t-1}{n-t+1} {2n-t \choose n} x^t.
\end {eqnarray*}
\item The following formula, which is the analogue of the Chu-Vandemonde summation formula
for Dyck paths, was proved in \cite{BE2}:
\begin {equation} \label{chu}
 \frac {1}{n+b+1} {2n+2b \choose n+b}
 ~=~\sum_{m=1}^{n} \frac{m}{n} {2n -m-1 \choose n-1} \frac{m+1}{b+m+1} {2b+m \choose b},
 \forall b \ge 0, n \ge 1
\end {equation}
In Section \ref{ana}, we provide a simple proof for (\ref{chu})
using different techniques that involve our new knowledge on the
contact polynomial and an interesting identity from \cite{BE1}.
\end {itemize}


\subsection{Notation and Basic Facts}
Consider some infinite sequence $\{s_n\}_{n \geq 0}:=
\{s_0,s_1,s_2,\ldots\}$. It is common to denote the $n$th element $s_n$
also as $s(n)$ and the entire sequence
$\{s_n\}_{n \geq 0}$ also as $s$. For $n < 0$, define $s_n := 0$.
For any integer $m$, define $s[m]$
as the sequence $\{s_m,s_{m+1},\ldots\}$, namely, $s[m]_n = s_{n+m}$
if $n \ge 0$, and 0 otherwise. We define $\mathcal H(s)$ as the
sequence $\{s_0,0,s_{1},0,s_2,0\ldots\}$, namely, $\mathcal H(s)_n =
s_{\frac n 2}$ if $n$ is even, and 0 otherwise. We define $s^k$ to
be the result of applying $k$ convolutions of $s$ with itself, that
is, $s^k:= s * s \ldots * s$.

\begin {fact}
For any sequences
 of non-negative integers $s$ and $t$ with generating
functions $S(x)$ and $T(x)$, respectively, we have
\begin {itemize}
    \item
    The generating function of their convolution $s * t$ is $S(x) \cdot T(x)$.
    \item
    The generating function of  $s[m]$ is\footnote{In the sequel, whenever a shifted
sequence $s[m]$ with a positive integer $m$ is used, $S(x)$ will
always be divisible by $x^m$. Thus the notation $S(x)\cdot x^{-m}$
is unambiguous .} $S(x)\cdot x^{-m}$.

    \item
    The generating function of $\mathcal H(s)$ is
    $S(x^2)$.
    \item
    The generating function of $s^k$ is $S(x)^k$.
\end {itemize}
\end {fact}

We will use the following observation in the sequel (often
implicitly):
\begin {observation} \label{implicit}
For any integers $i,i',j,j'$ and $t$, with $t \geq 1$, there are
natural bijections between
\begin {itemize}
\item $D_t((i,j),(i',j'))$ and $D_t((0,j),(i'-i,j'))$.
\item $D_t((i,j),(i',j'))$ and $D_t((i,j'),(i',j))$.
\end {itemize}
\end {observation}


\section {Proof of Theorem \ref{Main}}
\label {Mai} This section is organized as follows.
We start with an investigation of Dyck paths that touch the $x$-axis
exactly once (Section \ref{Sux}). Then, we show that there is a
bijection
 between the set of Dyck paths
that touch the $x$-axis any predetermined number of times and the
set of Dyck paths that touch it just once (Section \ref{Main1}).
Equipped with appropriate tools, we conclude with a simple proof of
Theorem \ref{Main} (Section
\ref{proo}).

\begin{remark} Observe that there is a natural bijection between
$$D_t((i,j),(i',0))$$ and
$$D_{t-1}((i,j),(i'-1,1)),$$ implying that the
case $j'=0$ of Theorem \ref{Main} may be deduced directly from the
case $j'>0$. Nevertheless, we provide an alternative proof for the
case $j'=0$, independent of the case $j'>0$.
\end {remark}


\subsection {Touching the $x$-Axis Just Once} \label{Sux}
In this section we restrict our attention to Dyck paths that touch
the $x$-axis once.
\begin {lemma} \label {lemma2}
For any integers $i,j$ and $i'$, such that $j > 0$,
$$\vert D_1((i,j),(i',0)) \vert = \vert D((i,j-1),(i'-1,0)) \vert.$$
\end {lemma}
\begin {proof}
For any Dyck path $P$ in $D_1((i,j),(i',0))$, its last move is a
fall-step, connecting $(i'-1,1)$ and $(i',0)$. Omitting this last
move from $P$ yields a Dyck path of length $i'-1$ that finishes at
$(i'-1,1)$, never passing below $y=1$. This naturally induces a
bijection between
 $D_1((i,j),(i',0))$ and $D_0((i,j),(i'-1,1))$.
The proof is concluded by observing that $|D_0((i,j),(i'-1,1))| =
\vert D((i,j-1),(i'-1,0)) \vert$.
 \end {proof}
\begin {lemma} \label{Aux}
For any integers $i,j,i'$ and $j'$, such that $j \ge 0$ and $j' >0$,
$$\vert D_1((i,j),(i',j')) \vert = \vert D((i,j),(i'-1,j'-1)) \vert
- \vert D((i,j-1),(i'-1,j'-2)) \vert.$$
\end {lemma}
\begin {proof}
We first claim that there is a bijection between
$$D_1((i,j),(i',j'))$$ and $$S:= \bigcup_{k>0} D_k((i,j),(i'-1,j'-1)).$$
\begin{figure}
\begin{center}
\input{lemmm32.pstex_t}
\end{center}
\caption{\small The Dyck path $P$ on the left
is in $D_1((0,1),(9,2))$, having $(1,0)$ as a
unique contact point. The Dyck path $f(P)$ on the right
is in $D_3((0,1),(8,1))$, having in
addition to $(1,0)$ also $(3,0)$ and $(5,0)$ as contact points.}
\label{lemm3}
\end{figure}
To see this, consider the following map $f$, taking a Dyck path $P$
in $D_1((i,j),(i',j'))$ and sending it to the one obtained from it
by omitting the step which occurs immediately after reaching the contact
point. (See Figure \ref{lemm3} for an illustration.) Clearly, $f(P)$
touches the $x$-axis at least once, starts at $(i,j)$, and finishes
at $(i'-1,j'-1)$; that is, $f(P) \in \bigcup_{k >0}
D_k((i,j),(i'-1,j'-1))$. It is easy to verify that $f$ is bijective,
as required.

Observe that
$$S = D((i,j),(i'-1,j'-1)) \setminus
D_0((i,j),(i'-1,j'-1))$$ and $$\vert D_0((i,j),(i'-1,j'-1))\vert =
\vert D((i,j-1),(i'-1,j'-2)) \vert,$$ and we are done.
\end {proof}


\subsection{The General Case} \label {Main1}
We use the next statement in the special case $\ell = t-1$ for
proving Theorem \ref{Main}.
\begin {proposition}
\label{mprop} For any integers $i,j,i',j',\ell$,
such that $j,j' \ge 0, t \ge 1$ and $0 \le \ell \le t-1$, there is a bijection between
$D_t((i,j),(i',j'))$ and $D_{t-\ell}((i,j+\ell),(i'-\ell,j'))$.
\end {proposition}
\begin {proof}
We construct a bijection $f: D_t((i,j),(i',j')) \rightarrow
D_{t-\ell}((i,j+\ell),(i'-\ell,j'))$. Let $P$ be some path in
$D_t((i,j),(i',j'))$. Denote the $t$ contact points of $P$, from
left to right, by $p_1,\ldots,p_t$, and let $U_i$ be the step in $P$
which occurs immediately after reaching $p_i$, for each $1 \leq i
\leq \ell$. As $P$ does not pass below the $x$-axis, the $U_i$'s are
all rise-steps. Consider the Dyck path $P'$ obtained from $P$ by
omitting these $\ell$ rise-steps and define $f(P)$ as the one
obtained from it by a shift of all the points in it, $\ell$ units up.
(See Figure \ref{general} for an illustration in the case
$\ell=t-1$.)



\begin{figure}
\begin{center}
\input{proppp.pstex_t}
\end{center}
\caption{\small The Dyck path $P$ at the top is in $D_4((0,1),(13,2))$, and has four contact
points: $p_1 = (3,0)$, $p_2 = (5,0)$, $p_3 = (7,0)$ and $p_4 =
(11,0)$. The path $P'$ at the middle part of the figure is a diagonal lattice path of length 10 from $(0,1)$
to $(10,-1)$, obtained from $P$ by omitting the three rise-steps
$U_1$, $U_2$ and $U_3$. The Dyck path $f(P)$ at the bottom is in $D_1((0,4),(10,2))$, having one
contact point--$(8,0).$} \label{general}
\end{figure}

Observe that $f(P)$ starts at $(i,j+\ell)$, finishes at
$(i'-\ell,j')$, touches the $x$-axis exactly $t-\ell$ times, and
never passes below the $x$-axis. Hence, $f(P) \in
D_{t-\ell}((i,j+\ell),(i'-\ell,j'))$.
To show that $f$ is bijective, we construct its inverse.
Take some Dyck path $Q$ in
$D_{t-\ell}((i,j+\ell),(i'-\ell,j'))$. Let $Q'$ be the Dyck path
obtained from $Q$ by a shift of all points in it, $\ell$ units down.
Let $q_1$ be the left-most point in $Q'$ that touches the $x$-axis
and define $q_i$ as the left-most point in $Q'$ with $y$-coordinate
$1-i$,
for each $2 \leq i \leq \ell$.
We define $f^{-1}(Q)$ to be the Dyck path obtained from $Q'$ by
inserting a rise-step $U_i$ immediately after reaching  $q_i$, for
each $1 \leq i \leq \ell$. It is easy to verify that $f^{-1}(Q) \in
D_t((i,j),(i',j'))$ and $f(f^{-1}(Q)) = Q$. The proposition follows.
\end {proof}

\subsection {Proof of Theorem \ref{Main}} \label{proo}
Suppose first that $t+ \vert j \vert + \vert j' \vert + \vert i'-i
\vert > 1$. The result is immediate if either $j <0$ or $j'<0$. We
henceforth assume that $j, j' \geq 0$. \\Setting $\ell = t-1$ in
Proposition \ref{mprop}, we find that
$$\vert D_t((i,j),(i',j') \vert
= \vert D_1((i,j+t-1),(i'-t+1,j') \vert.$$
We distinguish the two
following cases:

$\\$\emph{Case 1:} $j'=0$. We need to show that
$$\vert D_1((i,j+t-1),(i'-t+1,0)) \vert = \vert D((i,j+t-2),(i'-t,0))
\vert.$$
If $j+t-1 > 0$, then this equation follows from Lemma
\ref{lemma2}. Otherwise $t=1,j=j'=0$, and so, $\vert i' - i \vert > 0$. It is
easy to verify that both hand sides of the equation
vanish in the latter case.

$\\$\emph{Case 2:} $j'
> 0$. By Lemma \ref{Aux}, we have $$\vert D_1((i,j+t-1),(i'-t+1,j'))
\vert = \vert D((i,j+t-1),(i'-t,j'-1)) \vert - \vert
D((i,j+t-2),(i'-t,j'-2)) \vert.$$

In the degenerate case $t+ \vert j \vert + \vert j' \vert + \vert
i'-i \vert = 1$, we have $t=1, j=j'=0,$ and $i'=i$. The result in
this case follows from the fact that $D_1((i,0),(i,0))$ is comprised
of a single Dyck path of length zero that starts and finishes at $(i,0)$.

\section {Proof of Theorem \ref{generating}}
\label {gen} Define $\phi(n,k) := \vert D_{k+2}((0,0),(n,0)) \vert$,
for any non-negative integers $n$ and $k$, and let $a_n := \phi(n,0)$. It is easy to verify that
for odd values of $n$, $a_n = 0$, whereas for even values of $n$,
$a_n = c_{\frac{n}{2} -1}$, except for $n=0$, where $a_0 = 0$.
Equivalently, we have $a_n = \mathcal H(C[-1])_n$.
Thus, the generating function for the sequence $a$ is given by $A(x) = \frac
{1-\sqrt{1-4x^2}} 2$.

We use Lemmas \ref{cl1}
and \ref{mprop2} to prove Theorem \ref{generating}.

\begin {lemma}
\label{cl1} For any non-negative integers $n$ and $k$, $\phi(n,k) =
a^{k+1}(n)$.
\end {lemma}

\begin {proof}
We construct a bijection
$$g: D_{k+2}((0,0),(n,0)) \rightarrow \bigoplus_{\{1\le n_i \in \N \vert n =
\sum_{i=1}^{k+1} n_i\}} \prod_{i=1}^{k+1} D_2((0,0),(n_i,0)).$$
Let $P$ be some path in $D_{k+2}((0,0),(n,0))$. Denote the $k+2$
contact points of $P$, from left to right, by $p_1 = (x_1,0),\ldots,p_{k+2}=(x_{k+2},0)$.
(Note that $x_1=0,x_{k+2} = n.$) Those
points define a partition of $P$ into consecutive sub-paths, namely,
for each $1\leq i \leq k+1$,
we define $S_i$ to be the sub-path of $P$ between $p_i$ and
$p_{i+1}$. For each $1 \leq i \le k+1$,
define $n_i = x_{i+1}-x_{i}$, and let $S'_i$ be the Dyck path in $D_2((0,0),(n_i,0))$
obtained from $S_i$ by a shift of all points in it, $x_i$ units left.
(See Figure \ref{partition} for an illustration.)
We define $g(P)$ as $\prod_{i=1}^{k+1} S'_i$.
Clearly, this map is bijective (the inverse is given by the concatenation of all sub-paths $\{S'_i\}$ in their
respective order). This implies that both sets have the same
cardinality, that is, \begin{equation} \label{ending} \phi(n,k) ~=
\sum_{\{1\le n_i \in \N \vert n = \sum_{i=1}^{k+1} n_i\}}
\prod_{i=1}^{k+1} \vert D_2((0,0),(n_i,0)) \vert ~= \sum_{\{1\le n_i
\in \N \vert n = \sum_{i=1}^{k+1} n_i\}} \prod_{i=1}^{k+1} a_{n_i}.
\end {equation} Since $a_0 = 0$, the right-hand side of (\ref{ending})
is equal to $\sum_{\{0\le n_i \in \N \vert n = \sum_{i=1}^{k+1}
n_i\}} \prod_{i=1}^{k+1} a_{n_i}$. But the latter term is precisely
$a^{k+1}(n)$, which completes the proof.
\end {proof}

\begin{figure}
\begin{center}
\input{jintlem3.pstex_t}
\end{center}
\caption{\small (a) The Dyck path $P$ is in $D_3((0,0),(10,0))$, and has three contact
points: $p_1 = (0,0)$, $p_2 = (4,0)$ and $p_3 = (10,0)$. (b)
A partition of $P$ according to its contact points into two consecutive sub-paths $S_1$
and $S_2$, where $S_1$ is in $D_2((0,0),(4,0))$ and $S_2$ is in $D_2((4,0),(10,0))$.
(c) The Dyck path $S'_1$ (respectively, $S'_2$) is obtained from $S_1$ (resp., $S_2$) by a shift
of all points in it, $x_1 = 0$ (resp., $x_2 = 4$) units left.} \label{partition}
\end{figure}



The following statement implies that the problem of finding the
number of Dyck paths that start and finish at points with
\emph{arbitrary} $y$-coordinates is equivalent to the problem of
finding the number of Dyck paths that start and finish on the
$x$-axis. It follows as a simple corollary of Proposition
\ref{mprop} and Observation \ref{implicit}.
\begin {lemma}
\label{mprop2} For any integers $i,i',j,j'$ and $t$,
such that $j,j' \ge 0$ and  $t \geq 1$, there is a bijection between $D_t((i,j),(i',j'))$ and
$D_{t+j+j'}((i,0),(i'+j+j',0)).$
\end {lemma}


To complete the proof of Theorem \ref{generating}, we distinguish the two following
cases: \\\emph{Case 1: $t+j+j'=1$.} In this case $t=1, j=j'=0$,
and so, $d_j^{j,j'}(n) = d_1^{0,0}(n) = |D_{1}((0,0),(n,0))|$. By Theorem
\ref{Main}, $d_1^{0,0}(n) = 0$ for all $n > 0$, and $d_1^{0,0}(0) =
1$. It follows that $$D_1^{0,0}(x) ~=~ \sum_{n \ge 0}d_1^{0,0}(n)x^n ~=~ 1 ~=~
\frac{(1-\sqrt{1-4x^2})^{t+j+j'-1}} {2^{(t+j+j'-1)}\cdot
{x^{(j+j')}}}.$$
\\\emph{Case 2: $t+j+j' \ge 2$.}
By Lemma \ref{mprop2}, we have $$d_t^{j,j'}(n) =|D_t((0,j),(n,j'))| =
|D_{t+j+j'}((0,0),(n+j+j',0))| =
    \phi(n+j+j',{t+j+j'-2}).$$
By Lemma \ref{cl1}, we deduce that $$d_t^{j,j'}(n) =
\phi(n+j+j',{t+j+j'-2}) = a^{t+j+j'-1}(n+j+j')=
a^{t+j+j'-1}[j+j'](n).$$ Therefore, $$D_t^{j,j'}(x) ~=~ \sum_{n \ge 0}d_t^{j,j'}(n)x^n ~=~
\frac
{A(x)^{t+j+j'-1}} {x^{(j+j')}} ~=~
\frac{(1-\sqrt{1-4x^2})^{t+j+j'-1}} {2^{(t+j+j'-1)}\cdot
{x^{(j+j')}}}.$$

\section {Chu-Vandemonde Summation Formula}
\label {ana} In this section we provide a simple proof for the
analogue of the Chu-Vandemonde summation formula for Dyck paths,
which was already obtained by different techniques in \cite[p.\ 4, Eq.\ (18)]{BE2}
Refer to \cite{Gould} for similar
results.

Following \cite{BE2}, we define $B_{p,q} := |D((0,0),(p,q))|$, for
any non-negative integers $p$ and $q$. By Theorem \ref{Main} and the
second part of Observation \ref{implicit}, the equation $$P_n(x) =\sum_{t=2}^{n+1}
|D_t((0,0),(2n,0))| x^{t} = \sum_{t=2}^{n+1} |D((0,t-2),(2n-t,0))|
x^{t} = \sum_{t=2}^{n+1} B_{2n-t,t-2} x^{t}$$ holds. In \cite{BE2,BE1}, it
is proved that $P_n(C(x)) = \sum_{b=0}^\infty C_{n+b} x^b$.
We obtain the following identity:
\begin {equation}
\label{stam}
\begin{array}{ll}
    \sum_{b=0}^\infty C_{n+b} x^b ~=~ \sum_{t=2}^{n+1} B_{2n-t,t-2}
    (\frac {1-\sqrt{1-4x}} {2x})^t
    ~=~ \sum_{t=2}^{n+1} B_{2n-t,t-2}  \frac {(\frac {1-\sqrt{1-4x}}
    {2})^t} {x^t}
    ~=~ \cr\cr  \sum_{t=2}^{n+1} B_{2n-t,t-2} \sum_{m=0}^\infty
    a^t(2m+2t)x^m ~=~ \sum_{b=0}^{\infty} (\sum_{t=2}^{n+1}
     B_{2n-t,t-2} \cdot a^t(2b+2t))x^b.
\end{array}
\end {equation}


By Lemma \ref{cl1} and Theorem \ref{Main}, we have $$a^t(2b+2t)=
|D_{t+1}((0,0),(2b+2t,0))| = |D((0,t-1),(2b+t-1,0))| =
B_{2b+t-1,t-1}.$$ Equating coefficients in (\ref{stam}) yields
\begin {equation*}
 C_{n+b} ~=~ \sum_{t=2}^{n+1} B_{2n-t,t-2}B_{2b+t-1,t-1}~=~\sum_{m=1}^{n} B_{2n-m-1,m-1}B_{2b+m,m}, \forall b \ge
 0
\end {equation*}


or equivalently,
\begin {equation*}
 \frac {1}{n+b+1} {2n+2b \choose n+b}
 ~=~ \sum_{m=1}^{n} \frac{m}{n} {2n -m-1 \choose n-1} \frac{m+1}{b+m+1} {2b+m \choose b},
 \forall b \ge 0, n \ge 1
\end {equation*}

which is the analogue of the Chu-Vandemonde formula for Dyck paths.

\begin{thebibliography}{24}
\bibitem{AODW95}
I. Arizono, H. Ohta, S. J. Deutsch,  and C. Wang,
An analysis of the $E_l/E_k/1$
queueing system by restricted minimal lattice paths,
{\em J. Operational Research Society} {\bf 46} (1995), 245--253.

\bibitem{BK}
J. Bandlow and K. Killpatrick,\\
\href{http://www.combinatorics.org/Volume_8/Abstracts/v8i1r40.html}{An area-to-inv bijection between Dyck
paths and $312$-avoiding permutations}, {\em Electron. J. Combin.} {\bf 8} (1)
(2001), Article \#R40.

\bibitem{BKM97}
W. B\"{o}hm, A. Krinik, and S. G. Mohanty, The combinatorics of birth-death
processes and applications to queues, {\em Queueing Syst.} {\bf 26}
(1997), 255--267.

\bibitem{BE2}
R. Brak and J. W. Essam,
\href{http://www.combinatorics.org/Volume_10/Abstracts/v10i1r35.html}{Bicoloured Dyck paths and the contact
polynomial for $n$} non-intersecting paths in a half-plane lattice,
{\em Electron. J. Combin.} {\bf 10} (2003), Article \#R35.

\bibitem{BE1}
R. Brak, J. W. Essam, and A. Owczarek, New results for directed vesicles
and chains near an attractive wall, {\em J. Stat. Phys.} {\bf 93} (1998),
155--192.

\bibitem{DM}
M. Draief and J. Mairesse,
Services within a busy period of an $M/M/1$ queue and
Dyck paths, {\em Queueing Syst.} {\bf 49} (2005), 73--84.

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

\bibitem{FI79}
G. Fayolle and R. Iasnogorodski, Two coupled processors: the reduction to
a Riemann-Hilbert problem, {\em Probab. Theory Related Fields} {\bf 47}
(1979), 325--351.

\bibitem{FIM99}
G. Fayolle, R. Iasnogorodski, and V. Malyshev,
{\em Random Walks in the Quarter-Plane},
Springer,  1999.

\bibitem{Feller}
W. Feller, {\em An Introduction to Probability Theory and
its Applications}, Volume 1, Wiley, 1967.

\bibitem{FG00}
P. Flajolet and F. Guillemin,
The formal theory of birth-and-death processes, lattice path combinatorics,
and continued fractions, {\em Adv. Appl. Probab.} {\bf 32} (2000), 750--778.

\bibitem{Gould}
H. Gould, Some generalizations of Vandermonde convolution, {\em Amer.
Math. Monthly} {\bf 63} (1956), 84--91.

\bibitem{Knuth}
D. E. Knuth, {\em The Art of Computer Programming}, Volume 1,
Addison-Wesley, 1973.

\bibitem{Kr}
C. Krattenthaler, Permutations with restricted patterns and Dyck
paths, {\em Adv. Appl. Math.} {\bf 27} (2001), 510--530.

\bibitem{Mansour}
T. Mansour, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Mansour/mansour6.html}{Counting peaks at height $k$ in a Dyck path},
{\em J. Integer Seq.} {\bf 5} (2002), Article 02.1.1.

\bibitem{MDD}
T. Mansour, E. Y. P. Deng, and R. R. X. Du, Dyck paths and restricted
permutations, {\em Discrete Appl. Math.} {\bf 154} (2006),
1593--1605.

\bibitem{Moh99}
S. G. Mohanty, Combinatorial aspects of some random walks, in
P. Revesz and B. Toth, eds., {\em Random Walks},
J\'{a}nos Bolyai Mathematical Society, Budapest, 1999, pp. 259--273.

\bibitem{MMSKS95}
K. Muto, H. Miyazaki, Y. Seki, Y. Kimura, Y. Shibata, Lattice path counting and $M/M/c$ queueing systems, {\em Queueing Syst.} {\bf 19} (1995),
193--214.

%\bibitem{OF85}
%H. Ohta, M. Furukawa, An application of the number of lattice paths
%to the theory of queues, {J. of the Oper. Res. Soc.} {36(12)} (1985) 1117-1124.

\bibitem{PW}
P. Peart and W. J. Woan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/PEART/pwatjis2.html}{Dyck paths with no peaks at height $k$}, {\em J.
Integer Seq.} {\bf 4} (2001), Article 01.1.3.

%\bibitem{SA02}
%K. Sen, M. Agarwal, Lattice paths combinatorics applied to transient queue
%length distribution of $C_2/M/1$ queues and busy period analysis of bulk
%queues $C_2^b/M/1$, {J. of Stat. Planning and Inference} {100(2)} (2002) 365-397.

\bibitem{Stanleybib}
R. Stanley, Catalan Addendum, 2008. Available via\\
\href{http://www-math.mit.edu/~rstan/ec/catadd.pdf}{\tt http://www-math.mit.edu/$\sim$rstan/ec/catadd.pdf}.

\bibitem{Stanley}
R. Stanley, {\em Enumerative Combinatorics}, Volume 1, Wadsworth and
Brooks/Cole, 1986.
\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 11B83, 11Y55.

\noindent \emph{Keywords: } Catalan numbers, Dyck paths.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 30 2007;
revised version received  August 7 2008.
Published in {\it Journal of Integer Sequences}, August 7 2008.
Slight revision, August 17 2008.

\bigskip
\hrule
\bigskip

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


\end{document}