Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.8
URN: urn:nbn:de:0030-drops-120383
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12038/
Bousquet-Mélou, Mireille ; Wallner, Michael
More Models of Walks Avoiding a Quadrant
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{bousquetmlou_et_al:LIPIcs:2020:12038,
author = {Mireille Bousquet-M{\'e}lou and Michael Wallner},
title = {{More Models of Walks Avoiding a Quadrant}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Michael Drmota and Clemens Heuberger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12038},
URN = {urn:nbn:de:0030-drops-120383},
doi = {10.4230/LIPIcs.AofA.2020.8},
annote = {Keywords: Enumerative combinatorics, lattice paths, non-convex cones, algebraic series, D-finite series}
}
| Keywords: | Enumerative combinatorics, lattice paths, non-convex cones, algebraic series, D-finite series | |
| Seminar: | 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 10.06.2020 |
