Journal of Integer Sequences, Vol. 11 (2008), Article 08.3.5

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


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