ALCOMFT-TR-01-188

Cyril Banderier and Philippe Flajolet
Basic Analytic Combinatorics of Directed Lattice Paths
INRIA. Work package 4. December 2001.

Abstract: This paper develops a unified enumerative and asymptotic theory of directed 2-dimensional lattice paths in half-planes and quarter-planes. The lattice paths are specified by a finite set of rules that are both time and space homogeneous, and have a privileged direction of increase. (They are then essentially 1-dimensional objects.) The theory relies on a specific ``kernel method'' that provides an important decomposition of the algebraic generating functions involved, as well as on a generic study of singularities of an associated algebraic curve. Consequences are precise computable estimates for the number of lattice paths of a given length under various constraints (bridges, excursions, meanders) as well as a characterization of the limit laws associated to several basic parameters of paths.

Postscript file: ALCOMFT-TR-01-188.ps.gz (575 kb).