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.
Type de document :
Communication dans un congrès
Gardy, D. & Mokkadem, A. Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities, 2000, Versailles, France, Birkhäuser, pp.101-112, 2000, Trends in Mathematics
Liste complète des métadonnées

https://hal.inria.fr/inria-00099193
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:51:38
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17

Identifiants

  • HAL Id : inria-00099193, version 1

Citation

Mireille Bousquet-Mélou, Gilles Schaeffer. Counting paths on the slit plane. Gardy, D. & Mokkadem, A. Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities, 2000, Versailles, France, Birkhäuser, pp.101-112, 2000, Trends in Mathematics. 〈inria-00099193〉

Partager

Métriques

Consultations de la notice

116