Enumeration of partial Lukasiewicz paths

Abstract

Łukasiewicz paths are lattice paths in ${\mathbb{N}}^2$ starting at the origin, ending on the $x$-axis, and consisting of steps in the set $\{(1,k),k\ge -1\}$. We give generating function and exact value for the number of $n$-length prefixes (resp. suffixes) of these paths ending at height $k\ge 0$ with a given type of step. We make a similar study for prefixes of height at most $t\ge 0$. Using the explicit forms for the paths of bounded height, we evaluate the average height asymptotically. For fixed $k$ and $n\to \infty$, this quantity behaves as $\sqrt{\pi n}$. Finally we study (in the same way) prefixes of alternate Łukasiewicz paths, i.e., Łukasiewicz paths that do contain two consecutive steps with the same direction.