Antonio Bernini ; Luca Ferrari ; Renzo Pinzani ; Julian West - Pattern-avoiding Dyck paths

dmtcs:2334 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2334
Pattern-avoiding Dyck pathsArticle

Authors: Antonio Bernini ORCID1; Luca Ferrari ORCID1; Renzo Pinzani 1; Julian West 2

  • 1 Dipartimento di Sistemi e Informatica
  • 2 Heilbronn Institute for Mathematical Research

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.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: Dyck path,pattern containment relation,enumeration,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

8 Documents citing this article

Consultation statistics

This page has been seen 308 times.
This article's PDF has been downloaded 859 times.