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

Cyril Banderier 1 Bernhard Gittenberger 2
1 LIPN - 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 : algebraic function kernel method generating function analytic combinatorics Lattice path singularity analysis Brownian Excursion
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.345-356, 2006, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01184683
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:22:37
Dernière modification le : jeudi 11 janvier 2018 - 06:17:32
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 10:44:19

Fichier

dmAG0126.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184683, version 1

Collections

UNIV-PARIS13 | INSMI | LIPN | USPC | TDS-MACS

Citation

Cyril Banderier, Bernhard Gittenberger. Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.345-356, 2006, DMTCS Proceedings. 〈hal-01184683〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

218

Contact


archive-ouverte@inria.fr