On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane

zbMATH Open1284.05018arXiv1004.1733MaRDI QIDQ3099298FDOQ3099298

Kilian Raschel, Guy Fayolle

Publication date: 1 December 2011

Abstract: In two recent works cite{BMM,BK}, it has been shown that the counting generating functions (CGF) for the 23 walks with small steps confined in a quadrant and associated with a finite group of birational transformations are holonomic, and even algebraic in 4 cases -- in particular for the so-called Gessel's walk. It turns out that the type of functional equations satisfied by these CGF appeared in a probabilistic context almost 40 years ago. Then a method of resolution was proposed in cite{FIM}, involving at once algebraic tools and a reduction to boundary value problems. Recently this method has been developed in a combinatorics framework in cite{Ra}, where a thorough study of the explicit expressions for the CGF is proposed. The aim of this paper is to derive the nature of the bivariate CGF by a direct use of some general theorems given in cite{FIM}.

Full work available at URL: https://arxiv.org/abs/1004.1733

Recommendations

• Counting Walks in the Quarter Plane
• New steps in walks with small steps in the quarter plane: series expressions for the generating functions
• Classifying lattice walks restricted to the quarter plane
• On the functions counting walks with small steps in the quarter plane
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane

zbMATH Keywords

generating functionautomorphismquarter-planeuniversal coveringWeierstrass elliptic functionspiecewise homogeneous lattice walk

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable (30D05) Compact Riemann surfaces and uniformization (30F10)

Cited In (24)

• Counting Walks in the Quarter Plane
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
• The quasi-holonomic ansatz and restricted lattice walks
• Combinatorics meets potential theory
• Algebraic systems of generating functions and return probabilities for random walks
• Non-D-finite excursions in the quarter plane
• On 3-dimensional lattice walks confined to the positive octant
• Random walks in the quarter plane, discrete harmonic functions and conformal mappings
• Two non-holonomic lattice walks in the quarter plane
• Classifying lattice walks restricted to the quarter plane
• An elementary solution of Gessel's walks in the quadrant
• On the nature of the generating series of walks in the quarter plane
• On the algebraic area of lattice walks and the Hofstadter model
• An upper bound and finiteness criteria for the Galois group of weighted walks with rational coefficients in the quarter plane
• On the functions counting walks with small steps in the quarter plane
• On the nature of four models of symmetric walks avoiding a quadrant
• New steps in walks with small steps in the quarter plane: series expressions for the generating functions
• Enumeration of walks with small steps avoiding a quadrant
• The six-vertex model on random planar maps revisited
• Quadrant walks starting outside the quadrant
• The generating function of Kreweras walks with interacting boundaries is not algebraic
• Walks in the quarter plane: Analytic approach and applications
• Counting walks in a quadrant: a unified approach via boundary value problems
• A human proof of Gessel's lattice path conjecture

This page was built for publication: On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3099298)