Processing math: 100%

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 pathsConference paper

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 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 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 369 times.
This article's PDF has been downloaded 949 times.