A Natural Extension of Catalan Numbers
Noam Solomon and Shay Solomon
Dept. of Mathematics and Computer Science
Ben-Gurion University of the Negev
Beer-Sheva 84105
Israel
Abstract:
A Dyck path is a lattice path in the plane integer lattice Z
× 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 nth Catalan number.
In this paper we find a closed formula, depending on a non-negative
integer t and on two lattice points p1
and p2, for the number
of Dyck paths starting at p1,
ending at p2, and touching the
x-axis exactly t times.
Moreover, we provide explicit expressions for the corresponding
generating function and bivariate generating function.
Full version: pdf,
dvi,
ps,
latex
(Concerned with sequence
A000108.)
Received December 30 2007;
revised version received August 7 2008.
Published in Journal of Integer Sequences, August 7 2008.
Slight revision, August 17 2008.
Return to
Journal of Integer Sequences home page