2026-07-22T13:20:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12038 2024-03-06T10:49:14Z ddc:004 open_access

More Models of Walks Avoiding a Quadrant Bousquet-Mélou, Mireille Wallner, Michael Enumerative combinatorics lattice paths non-convex cones algebraic series D-finite series 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mireille Bousquet-Mélou and Michael Wallner 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.8 urn:nbn:de:0030-drops-120383 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode