1 Search Results for "Bousquet-Mélou, Mireille"

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-dev.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}
}
  • Refine by Author
  • 1 Bousquet-Mélou, Mireille
  • 1 Wallner, Michael

  • Refine by Classification
  • 1 Mathematics of computing → Computations on polynomials
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Generating functions
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 D-finite series
  • 1 Enumerative combinatorics
  • 1 algebraic series
  • 1 lattice paths
  • 1 non-convex cones

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact