DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2020.8

More Models of Walks Avoiding a Quadrant

Authors: Mireille Bousquet-Mélou and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bousquetmelou_et_al:LIPIcs.AofA.2020.8,
  author =	{Bousquet-M\'{e}lou, Mireille and Wallner, Michael},
  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 =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.8},
  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}
}

Search Results

Documents authored by Bousquet-Mélou, Mireille

More Models of Walks Avoiding a Quadrant

Abstract

Cite as

Thanks for your feedback!

Could not send message