Explicit Formulas for Enumeration of Lattice Paths: Basketball and the Kernel Method

摘要

This article deals with the enumeration of directed lattice walks on theintegers with any finite set of steps, starting at a given altitude $j$ andending at a given altitude $k$, with additional constraints such as, forexample, to never attain altitude $0$ in-between. We first discuss the case ofwalks on the integers with steps $-h, dots, -1, +1, dots, +h$. The case $h=1$is equivalent to the classical Dyck paths, for which many ways of gettingexplicit formulas involving Catalan-like numbers are known. The case $h=2$corresponds to "basketball" walks, which we treat in full detail. Then we moveon to the more general case of walks with any finite set of steps, alsoallowing some weights/probabilities associated with each step. We show how amethod of wide applicability, the so-called "kernel method", leads to explicitformulas for the number of walks of length $n$, for any $h$, in terms of nestedsums of binomials. We finally relate some special cases to other combinatorialproblems, or to problems arising in queuing theory.