Solomon, Noam; Solomon, Shay

A natural extension of Catalan numbers

J. Integer Seq. 11(3), Article ID 08.3.5, 12 p., electronic only (2008)

Summary

Summary: A Dyck path is a lattice path in the plane integer lattice Z $\times $ 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.

Mathematics Subject Classification

05A15, 11B83, 11Y55

Keywords/Phrases

Catalan numbers, Dyck paths

Downloads