HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Counting paths on the slit plane

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.
Mots-clés :
Document type :
Conference papers
Domain :

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⟩

Record views