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élou 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.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2017, 61, pp.242-275. 〈10.1016/j.ejc.2016.10.010〉
Liste complète des métadonnées

Littérature citée [49 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01332175
Contributeur : Frédéric Chyzak <>
Soumis le : mardi 15 novembre 2016 - 13:07:45
Dernière modification le : mercredi 9 mai 2018 - 12:48:06

Fichier

walks.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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. European Journal of Combinatorics, Elsevier, 2017, 61, pp.242-275. 〈10.1016/j.ejc.2016.10.010〉. 〈hal-01332175v2〉

Partager

Métriques

Consultations de la notice

458

Téléchargements de fichiers

140