Skip to Main content Skip to Navigation
Conference papers

Counting paths on the slit plane

Mireille Bousquet-Mélou 1 Gilles Schaeffer 2
2 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present a method, based on functional equations, to enumerate paths on the square lattice that avoid a given half-line. The corresponding generating functions are algebraic, and sometimes remarkably simple: for instance, the number of paths of length $2n+1$ going from $(0,0)$ to $(1,0)$ and avoiding the nonpositive horizontal axis (except at their starting point) is $C_{2n+1}$, the $(2n+1)$th Catalan number. More generally, we enumerate exactly paths of length $n$ starting from $(0,0)$ and avoiding the nonpositive horizontal axis, regardless of their endpoint: the asymptotic number of such paths is $4^n n^{-1/4}$ (up to an explicit multiplicative constant). We also obtain limit laws for the coordinates of their endpoint: in particular, the average abscissa of their endpoint grows like $\sqrt n$ (up to an explicit multiplicative constant), which shows that these paths are strongly repelled from the origin. We derive from our results the distribution of the abscissa where a random walk, starting from a given point, hits for the first time a given half-line.
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:51:38 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM


  • HAL Id : inria-00099193, version 1


Mireille Bousquet-Mélou, Gilles Schaeffer. Counting paths on the slit plane. Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities, 2000, Versailles, France, pp.101-112. ⟨inria-00099193⟩



Record views