Hypergeometric expressions for generating functions of walks with small steps in the quarter plane

DOI10.1016/J.EJC.2016.10.010zbMATH Open1352.05013arXiv1606.02982OpenAlexW2962868185MaRDI QIDQ730269

Author name not available (Why is that?)

Publication date: 27 December 2016

Published in: (Search for Journal in Brave)

Abstract: We study nearest-neighbors walks on the two-dimensional square lattice, that is, models of walks on $mathbb{Z}^2$ defined by a fixed step set that is a subset of the non-zero vectors with coordinates 0, 1 or $-1$. We concern ourselves with the enumeration of such walks starting at the origin and constrained to remain in the quarter plane $mathbb{N}^2$, counted by their length and by the position of their ending point. Bousquet-M'elou and Mishna [Contemp. Math., pp. 1--39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a D-finite generating function; linear differential equations have then been guessed in these cases by Bostan and Kauers [FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201--215, 2009]. We give here the first proof that these equations are indeed satisfied by the corresponding generating functions. As a first corollary, we prove that all these 19 generating functions can be expressed in terms of Gauss' hypergeometric functions that are intimately related to elliptic integrals. As a second corollary, we show that all the 19 generating functions are transcendental, and that among their $19imes4$ combinatorially meaningful specializations only four are algebraic functions.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Hypergeometric expressions for generating functions of walks with small steps in the quarter plane

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