LIPIcs.AofA.2020.8.pdf
- Filesize: 0.53 MB
- 14 pages
Document
More Models of Walks Avoiding a Quadrant
Authors
Michael Wallner 
-
Part of:
Volume:
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-10
File
Document Identifiers
Author Details
Acknowledgements
We thank our referees for their careful reading.
Cite As Get BibTex
Mireille Bousquet-Mélou and Michael Wallner. More Models of Walks Avoiding a Quadrant. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.AofA.2020.8
Abstract
We continue the enumeration of plane lattice paths avoiding the negative quadrant initiated by the first author in [Bousquet-Mélou, 2016]. We solve in detail a new case, the king walks, where all 8 nearest neighbour steps are allowed. As in the two cases solved in [Bousquet-Mélou, 2016], the associated generating function is proved to differ from a simple, explicit D-finite series (related to the enumeration of walks confined to the first quadrant) by an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou, 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We also explain why we expect the observed algebraicity phenomenon to persist for 4 more models, for which the quadrant problem is solvable using the reflection principle.
Subject Classification
ACM Subject Classification
- Theory of computation → Random walks and Markov chains
- Mathematics of computing → Enumeration
- Mathematics of computing → Generating functions
- Mathematics of computing → Computations on polynomials
Keywords
- Enumerative combinatorics
- lattice paths
- non-convex cones
- algebraic series
- D-finite series
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- M. Bousquet-Mélou. Square lattice walks avoiding a quadrant. J. Combin. Theory Ser. A, 144:37-79, 2016. URL: https://doi.org/10.1016/j.jcta.2016.06.010.
- M. Bousquet-Mélou and A. Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Combin. Theory Ser. B, 96:623-672, 2006. URL: https://doi.org/10.1016/j.jctb.2005.12.003.
- M. Bousquet-Mélou and M. Mishna. Walks with small steps in the quarter plane. In Algorithmic probability and combinatorics, volume 520 of Contemp. Math., pages 1-39. Amer. Math. Soc., Providence, RI, 2010. URL: https://doi.org/10.1090/conm/520/10252.
- D. Denisov and V. Wachtel. Random walks in cones. Ann. Probab., 43(3):992-1044, 2015. URL: https://doi.org/10.1214/13-AOP867.
-
G. Fayolle, R. Iasnogorodski, and V. Malyshev. Random walks in the quarter-plane: Algebraic methods, boundary value problems and applications, volume 40 of Applications of Mathematics. Springer-Verlag, Berlin, 1999.
- I. Gessel. A factorization for formal Laurent series and lattice path enumeration. J. Combin. Theory Ser. A, 28(3):321-337, 1980. URL: https://doi.org/10.1016/0097-3165(80)90074-6.
- I. M. Gessel and D. Zeilberger. Random walk in a Weyl chamber. Proc. Amer. Math. Soc., 115(1):27-31, 1992. URL: https://doi.org/10.1090/S0002-9939-1992-1092920-8.
- L. Lipshitz. The diagonal of a D-finite power series is D-finite. J. Algebra, 113(2):373-378, 1988. URL: https://doi.org/10.1016/0021-8693(88)90166-4.
- L. Lipshitz. D-finite power series. J. Algebra, 122:353-373, 1989. URL: https://doi.org/10.1016/0021-8693(89)90222-6.
- M. Mishna and A. Rechnitzer. Two non-holonomic lattice walks in the quarter plane. Theoret. Comput. Sci., 410(38-40):3616-3630, 2009. URL: https://doi.org/10.1016/j.tcs.2009.04.008.
- S. Mustapha. Non-D-finite walks in a three-quadrant cone. Ann. Comb., 23(1):143-158, 2019. URL: https://doi.org/10.1007/s00026-019-00413-2.
- K. Raschel. Counting walks in a quadrant: a unified approach via boundary value problems. J. Eur. Math. Soc. (JEMS), 14(3):749-777, 2012. URL: https://doi.org/10.4171/JEMS/317.
- K. Raschel and A. Trotignon. On walks avoiding a quadrant. Electron. J. Combin., 26(3):Paper 3.31, 34, 2019. URL: https://doi.org/10.37236/8019.
- B. Salvy and P. Zimmermann. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, 20(2):163-177, 1994. URL: https://doi.org/10.1145/178365.178368.