×

The complete generating function for Gessel walks is algebraic. (English) Zbl 1206.05013

Summary: Gessel walks are lattice walks in the quarter-plane \(\mathbb{N}^2\) which start at the origin \((0,0)\in \mathbb{N}^2\) and consist only of steps chosen from the set \(\{\leftarrow , \swarrow , \nearrow , \rightarrow \}\). We prove that if \(g(n;i,j)\) denotes the number of Gessel walks of length \(n\) which end at the point \((i,j)\in \mathbb{N}^2\), then the trivariate generating series \(G(t;x,y) = \sum _{n,i,j\geq 0} g(n;i,j)x^i y^j t^n\) is an algebraic function.

MSC:

05A15 Exact enumeration problems, generating functions
14N10 Enumerative problems (combinatorial problems) in algebraic geometry
33F10 Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.)
68W30 Symbolic computation and algebraic computation
33C05 Classical hypergeometric functions, \({}_2F_1\)
97N80 Mathematical software, computer programs (educational aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bernhard Beckermann and George Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl. 15 (1994), no. 3, 804 – 823. · Zbl 0805.65008 · doi:10.1137/S0895479892230031
[2] Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235 – 265. Computational algebra and number theory (London, 1993). · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125
[3] Alin Bostan, Philippe Flajolet, Bruno Salvy, and Éric Schost, Fast computation of special resultants, J. Symbolic Comput. 41 (2006), no. 1, 1 – 29. · Zbl 1121.13037 · doi:10.1016/j.jsc.2005.07.001
[4] A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic – supplementary material, http://www.risc.jku.at/people/mkauers/gessel/. · Zbl 1206.05013
[5] A. Bostan and M. Kauers, Automatic classification of restricted lattice walks, Proceedings of FPSAC’09, 2009, pp. 201-215. · Zbl 1391.05026
[6] Mireille Bousquet-Mélou, Walks in the quarter plane: Kreweras’ algebraic model, Ann. Appl. Probab. 15 (2005), no. 2, 1451 – 1491. · Zbl 1064.05010 · doi:10.1214/105051605000000052
[7] M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, preprint, to appear in “Algorithmic Probability and Combinatorics”, special volume of the Contemporary Mathematics series of the Amer. Math. Soc., available at http://arxiv.org/abs/0810.4387, 2008. · Zbl 1209.05008
[8] Mireille Bousquet-Mélou and Marko Petkovšek, Walks confined in a quadrant are not always D-finite, Theoret. Comput. Sci. 307 (2003), no. 2, 257 – 276. Random generation of combinatorial objects and bijective combinatorics. · Zbl 1070.68112 · doi:10.1016/S0304-3975(03)00219-6
[9] F. Chyzak, Fonctions holonomes en calcul formel, Ph.D. thesis, École polytechnique, 1998.
[10] Bernard Dwork, Differential operators with nilpotent \?-curvature, Amer. J. Math. 112 (1990), no. 5, 749 – 786. · Zbl 0718.12007 · doi:10.2307/2374806
[11] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. · Zbl 0936.11069
[12] Ira M. Gessel, A probabilistic method for lattice path enumeration, J. Statist. Plann. Inference 14 (1986), no. 1, 49 – 58. · Zbl 0602.05006 · doi:10.1016/0378-3758(86)90009-1
[13] D. Yu. Grigor\(^{\prime}\)ev, Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. Symbolic Comput. 10 (1990), no. 1, 7 – 37. · Zbl 0728.68067 · doi:10.1016/S0747-7171(08)80034-X
[14] Manuel Kauers, Christoph Koutschan, and Doron Zeilberger, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA 106 (2009), no. 28, 11502 – 11505. · Zbl 1203.05010 · doi:10.1073/pnas.0901678106
[15] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0895.68055
[16] C. Koutschan, Advanced applications of the holonomic systems approach, Ph.D. thesis, RISC-Linz, 2009. · Zbl 1344.68301
[17] G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers, Cahiers du B.U.R.O. 6 (1965), 5-105.
[18] C. Mallinger, Algorithmic manipulations and transformations of univariate holonomic functions and sequences, Master’s thesis, RISC-Linz, August 1996.
[19] John McDonald, Fiber polytopes and fractional power series, J. Pure Appl. Algebra 104 (1995), no. 2, 213 – 233. · Zbl 0842.52009 · doi:10.1016/0022-4049(94)00129-5
[20] Marni Mishna and Andrew Rechnitzer, Two non-holonomic lattice walks in the quarter plane, Theoret. Comput. Sci. 410 (2009), no. 38-40, 3616 – 3630. · Zbl 1228.05038 · doi:10.1016/j.tcs.2009.04.008
[21] M. Petkovšek and H. Wilf, On a conjecture of Ira Gessel, preprint, available on line at http:// arxiv.org/abs/0807.3202, 2008.
[22] Marius van der Put, Grothendieck’s conjecture for the Risch equation \?’=\?\?+\?, Indag. Math. (N.S.) 12 (2001), no. 1, 113 – 124. · Zbl 1004.12005 · doi:10.1016/S0019-3577(01)80009-4
[23] B. Salvy and P. Zimmermann, Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM T. Math. Software 20 (1994), no. 2, 163-177. · Zbl 0888.65010
[24] H. A. Schwarz, Über diejenigen Fälle, in welchen die Gaußische hypergeometrische Reihe einer algebraische Funktion ihres vierten Elementes darstellt, J. Reine Angew. Math. 75 (1873), 292-335.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.