HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

https://hal.inria.fr/inria-00099193
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:51:38 AM
Last modification on : Monday, December 20, 2021 - 4:50:12 PM

Identifiers

  • HAL Id : inria-00099193, version 1

Citation

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⟩

Share

Metrics

Record views

82