• Medientyp: E-Artikel
  • Titel: Pattern-avoiding Dyck paths
  • Beteiligte: Bernini, Antonio; Ferrari, Luca; Pinzani, Renzo; West, Julian
  • Erschienen: Centre pour la Communication Scientifique Directe (CCSD), 2013
  • Erschienen in: Discrete Mathematics & Theoretical Computer Science
  • Sprache: Englisch
  • DOI: 10.46298/dmtcs.2334
  • ISSN: 1365-8050
  • Schlagwörter: Discrete Mathematics and Combinatorics ; General Computer Science ; Theoretical Computer Science
  • Entstehung:
  • Anmerkungen:
  • Beschreibung: <jats:p xml:lang="en">We introduce the notion of $\textit{pattern}$ in the context of lattice paths, and investigate it in the specific case of Dyck paths. Similarly to the case of permutations, the pattern-containment relation defines a poset structure on the set of all Dyck paths, which we call the $\textit{Dyck pattern poset}$. Given a Dyck path $P$, we determine a formula for the number of Dyck paths covered by $P$, as well as for the number of Dyck paths covering $P$. We then address some typical pattern-avoidance issues, enumerating some classes of pattern-avoiding Dyck paths. Finally, we offer a conjecture concerning the asymptotic behavior of the sequence counting Dyck paths avoiding a generic pattern and we pose a series of open problems regarding the structure of the Dyck pattern poset.</jats:p>