2016/06/09 by Alin Bostan, Frédéric Chyzak, Bostan, Alin +7 · 3 citations
Mathematics · #05A15 #11J89 (Secondary) #14N10 #33C05 #33F10 #68W30 (Primary) #97N80 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Stochastic processes and statistical mechanics #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1606.02982
openalex publication_date 2016/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study nearest-neighbors walks on the two-dimensional square lattice, that\nis, models of walks on \ℤ2 defined by a fixed step set that is a\nsubset of the non-zero vectors with coordinates 0, 1 or -1. We concern\nourselves with the enumeration of such walks starting at the origin and\nconstrained to remain in the quarter plane \ℕ2, counted by their\nlength and by the position of their ending point. Bousquet-M 'elou and Mishna\n[Contemp. Math., pp. 1--39, Amer. Math. Soc., 2010] identified 19 models of\nwalks that possess a D-finite generating function; linear differential\nequations have then been guessed in these cases by Bostan and Kauers [FPSAC\n2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201--215, 2009]. We give\nhere the first proof that these equations are indeed satisfied by the\ncorresponding generating functions. As a first corollary, we prove that all\nthese 19 generating functions can be expressed in terms of Gauss'\nhypergeometric functions that are intimately related to elliptic integrals. As\na second corollary, we show that all the 19 generating functions are\ntranscendental, and that among their 19 \× 4 combinatorially meaningful\nspecializations only four are algebraic functions.\n