Cyril Banderier ; Bernhard Gittenberger - Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area

dmtcs:3481 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities - https://doi.org/10.46298/dmtcs.3481
Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the AreaArticle

Authors: Cyril Banderier ORCID1; Bernhard Gittenberger 2

  • 1 Laboratoire d'Informatique de Paris-Nord
  • 2 Institut für Diskrete Mathematik und Geometrie [Wien]

This paper tackles the enumeration and asymptotics of the area below directed lattice paths (walks on $\mathbb{N}$ with a finite set of jumps). It is a nice surprise (obtained via the "kernel method'') that the generating functions of the moments of the area are algebraic functions, expressible as symmetric functions in terms of the roots of the kernel. For a large class of walks, we give full asymptotics for the average area of excursions ("discrete'' reflected Brownian bridge) and meanders ("discrete'' reflected Brownian motion). We show that drift is not playing any role in the first case. We also generalise previous works related to the number of points below a path and to the area between a path and a line of rational slope.


Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Section: Proceedings
Published on: January 1, 2006
Imported on: May 10, 2017
Keywords: algebraic function,kernel method,generating function,analytic combinatorics,Lattice path,singularity analysis,Brownian Excursion,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

7 Documents citing this article

Consultation statistics

This page has been seen 359 times.
This article's PDF has been downloaded 767 times.