Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Analytic Combinatori ...
Conference paper

Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area

Cyril Banderier ORCID (1), Bernhard Gittenberger (2)
(1) Laboratoire d'Informatique de Paris-Nord
(2) Institut für Diskrete Mathematik und Geometrie [Wien]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2005
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Proceedings
DOI
10.46298/dmtcs.3481
License
https://about.hal.science/hal-authorisation-v1
Indicators
785
Views
2270
Downloads

Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area

Cyril Banderier ORCID (1), Bernhard Gittenberger (2)
(1) Laboratoire d'Informatique de Paris-Nord
(2) Institut für Diskrete Mathematik und Geometrie [Wien]
Abstract
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.
Keywords
  • [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]
  • Brownian Excursion
  • singularity analysis
  • Lattice path
  • analytic combinatorics
  • generating function
  • kernel method
  • algebraic function
Cited by

Source: OpenCitations

  • Generating functions for a lattice path model introduced by Deutsch

    Special Matrices

    Authors : Helmut Prodinger ORCID

    Journal reference : Volume 9, 2021, pp. 217-225

    DOI : 10.1515/spma-2020-0133
  • Enumeration of S-Motzkin paths from left to right and from right to left: a kernel method approach

    Pure mathematics and applications

    Authors : Helmut Prodinger ORCID

    Journal reference : Volume 29, 2020, pp. 28-38

    DOI : 10.1515/puma-2015-0039
  • On directed lattice paths with vertical steps

    Discrete Mathematics

    Authors : Maciej Dziemiańczuk ORCID

    Journal reference : Volume 339, 2015, pp. 1116-1139

    DOI : 10.1016/j.disc.2015.11.001
  • Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects

    Lecture notes in computer science

    Authors : Andrei Asinowski ORCID, Axel Bacher ORCID, Cyril Banderier ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume , 2018, pp. 195-206

    DOI : 10.1007/978-3-319-77313-1_15
  • Skew Dyck paths, area, and superdiagonal bargraphs

    Journal of Statistical Planning and Inference

    Authors : Emeric Deutsch ORCID, Emanuele Munarini ORCID, Simone Rinaldi

    Journal reference : Volume 140, 2009, pp. 1550-1562

    DOI : 10.1016/j.jspi.2009.12.013
  • On some problems about ternary paths: a linear algebra approach

    Rocky Mountain Journal of Mathematics

    Authors : Helmut Prodinger ORCID

    Journal reference : Volume 51, 2021, pp.

    DOI : 10.1216/rmj.2021.51.709
  • The Kernel Method for Lattice Paths Below a Line of Rational Slope

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Cyril Banderier ORCID, Michael Wallner ORCID

    Journal reference : Volume , 2019, pp. 119-154

    DOI : 10.1007/978-3-030-11102-1_7
Preview
Loading PDF preview...