Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Pattern-avoiding Dyc ...
Conference paper

Pattern-avoiding Dyck paths

Antonio Bernini ORCID (1), Luca Ferrari ORCID (1), Renzo Pinzani (1), Julian West (2)
(1) Dipartimento di Sistemi e Informatica
(2) Heilbronn Institute for Mathematical Research
Download article
Open on HAL
Imported on
November 21, 2016
Published on
December 31, 2012
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Proceedings
DOI
10.46298/dmtcs.2334
License
https://about.hal.science/hal-authorisation-v1
Indicators
909
Views
2420
Downloads

Pattern-avoiding Dyck paths

Antonio Bernini ORCID (1), Luca Ferrari ORCID (1), Renzo Pinzani (1), Julian West (2)
(1) Dipartimento di Sistemi e Informatica
(2) Heilbronn Institute for Mathematical Research
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Dyck path
  • pattern containment relation
  • enumeration
Cited by

Source: OpenCitations

  • Permutation classes and polyomino classes with excluded submatrices

    arXiv (Cornell University)

    Authors : DANIELA BATTAGLINO, MATHILDE BOUVEL, ANDREA FROSINI ORCID, SIMONE RINALDI

    Journal reference : Volume 27, 2015, pp. 157-183

    DOI : 10.1017/s0960129515000250

  • On the sub-permutations of pattern avoiding permutations

    Discrete Mathematics

    Authors : Filippo Disanto ORCID, Thomas Wiehe ORCID

    Journal reference : Volume 337, 2014, pp. 127-141

    DOI : 10.1016/j.disc.2014.06.028

  • Enumerative Results on the Schröder Pattern Poset

    arXiv (Cornell University)

    Authors : Lapo Cioni ORCID, Luca Ferrari ORCID

    Journal reference : Volume , 2017, pp. 56-67

    DOI : 10.1007/978-3-319-58631-1_5

  • Patterns in Shi Tableaux and Dyck Paths

    arXiv (Cornell University)

    Authors : Myrto Kallipoliti ORCID, Robin Sulzgruber, Eleni Tzanaki ORCID

    Journal reference : Volume 39, 2021, pp. 263-289

    DOI : 10.1007/s11083-021-09573-4

  • Restricted Binary Strings and Generalized Fibonacci Numbers

    Florence Research (University of Florence)

    Authors : Antonio Bernini ORCID

    Journal reference : Volume , 2017, pp. 32-43

    DOI : 10.1007/978-3-319-58631-1_3

  • Dyck Paths, Binary Words, and Grassmannian Permutations Avoiding an Increasing Pattern

    Annals of Combinatorics

    Authors : Krishna Menon, Anurag Singh ORCID

    Journal reference : Volume 28, 2023, pp. 871-887

    DOI : 10.1007/s00026-023-00667-x

  • Enumerative Combinatorics of Intervals in the Dyck Pattern Poset

    Order

    Authors : Antonio Bernini ORCID, Matteo Cervetti, Luca Ferrari ORCID, Einar Steingrímsson ORCID

    Journal reference : Volume 38, 2021, pp. 473-487

    DOI : 10.1007/s11083-021-09552-9

  • Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects

    Lecture notes in computer science

    Authors : Andrei Asinowski ORCID, Axel Bacher ORCID, Cyril Banderier ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume , 2018, pp. 195-206

    DOI : 10.1007/978-3-319-77313-1_15

  • The Dyck pattern poset

    Discrete Mathematics

    Authors : Axel Bacher ORCID, Antonio Bernini ORCID, Luca Ferrari ORCID, Benjamin Gunby ORCID, Renzo Pinzani, Julian West

    Journal reference : Volume 321, 2014, pp. 12-23

    DOI : 10.1016/j.disc.2013.12.011
Preview
Loading PDF preview...