Skip to Main content Skip to Navigation
Conference papers

Pattern-avoiding Dyck paths

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229675
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:19:44 AM
Last modification on : Wednesday, April 15, 2020 - 9:56:11 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:35:50 AM

File

dmAS0158.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229675, version 1

Collections

Citation

Antonio Bernini, Luca Ferrari, Renzo Pinzani, Julian West. Pattern-avoiding Dyck paths. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.683-694. ⟨hal-01229675⟩

Share

Metrics

Record views

136

Files downloads

1276