License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12038/
Bousquet-Mélou, Mireille ;
Wallner, Michael
More Models of Walks Avoiding a Quadrant
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 |
Collection: |
|
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 |