Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane

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 $19 \times 4$ combinatorially meaningful specializations only four are algebraic functions.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Frédéric Chyzak <>
Submitted on : Wednesday, June 15, 2016 - 1:13:00 PM
Last modification on : Wednesday, May 9, 2018 - 12:48:06 PM


Files produced by the author(s)


  • HAL Id : hal-01332175, version 1
  • ARXIV : 1606.02982


Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, Lucien Pech. Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane. 2016. ⟨hal-01332175v1⟩



Record views


Files downloads