• Mathematics of computing → Generating functions
  • Mathematics of computing → Distribution functions
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Grammars and context-free languages
Cyril Banderier
Université Paris 13, LIPN, UMR CNRS 7030, France
Marie-Louise Lackner
Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, TU Wien, Austria
Michael Wallner
Université de Bordeaux, LaBRI, UMR CNRS 5800, France; Institute for Discrete Mathematics and Geometry, TU Wien, Austria

Abstract. In this article, we revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener - Hopf formulas, thus capturing joint distributions. We also show that each of the fundamental families of symmetric polynomials corresponds to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).

This work was initiated during the sojourn of Marie-Louise Lackner and Michael Wallner at the University of Paris Nord, via a Franco-Austrian "Amadeus" project and via a MathStic funding. The subsequent part of this collaboration was funded by the Erwin Schrödinger Fellowship of the Austrian Science Fund (FWF): J 4162-N35.