Counting paths on the slit plane
Résumé
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.