Pattern-avoiding Dyck paths
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 patter...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2013-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2334/pdf |
| _version_ | 1797270262513664000 |
|---|---|
| author | Antonio Bernini Luca Ferrari Renzo Pinzani Julian West |
| author_facet | Antonio Bernini Luca Ferrari Renzo Pinzani Julian West |
| author_sort | Antonio Bernini |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:01:28Z |
| format | Article |
| id | doaj.art-23eb304926ea4322b75884eb88860f8e |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:28Z |
| publishDate | 2013-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-23eb304926ea4322b75884eb88860f8e2024-03-07T14:52:36ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502013-01-01DMTCS Proceedings vol. AS,...Proceedings10.46298/dmtcs.23342334Pattern-avoiding Dyck pathsAntonio Bernini0https://orcid.org/0000-0002-5363-7756Luca Ferrari1https://orcid.org/0000-0001-8096-6865Renzo Pinzani2Julian West3Dipartimento di Sistemi e InformaticaDipartimento di Sistemi e InformaticaDipartimento di Sistemi e InformaticaHeilbronn Institute for Mathematical ResearchWe 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.https://dmtcs.episciences.org/2334/pdfdyck pathpattern containment relationenumeration[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Antonio Bernini Luca Ferrari Renzo Pinzani Julian West Pattern-avoiding Dyck paths Discrete Mathematics & Theoretical Computer Science dyck path pattern containment relation enumeration [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Pattern-avoiding Dyck paths |
| title_full | Pattern-avoiding Dyck paths |
| title_fullStr | Pattern-avoiding Dyck paths |
| title_full_unstemmed | Pattern-avoiding Dyck paths |
| title_short | Pattern-avoiding Dyck paths |
| title_sort | pattern avoiding dyck paths |
| topic | dyck path pattern containment relation enumeration [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2334/pdf |
| work_keys_str_mv | AT antoniobernini patternavoidingdyckpaths AT lucaferrari patternavoidingdyckpaths AT renzopinzani patternavoidingdyckpaths AT julianwest patternavoidingdyckpaths |