Geodesic
Pattern-avoiding Dyck paths
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2013_special_264_a18,
     author = {Bernini, Antonio and Ferrari, Luca and Pinzani, Renzo and West, Julian},
     title = {Pattern-avoiding {Dyck} paths},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)},
     year = {2013},
     doi = {10.46298/dmtcs.2334},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2334/}
}
TY  - JOUR
AU  - Bernini, Antonio
AU  - Ferrari, Luca
AU  - Pinzani, Renzo
AU  - West, Julian
TI  - Pattern-avoiding Dyck paths
JO  - Discrete mathematics & theoretical computer science
PY  - 2013
VL  - DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2334/
DO  - 10.46298/dmtcs.2334
LA  - en
ID  - DMTCS_2013_special_264_a18
ER  - 
%0 Journal Article
%A Bernini, Antonio
%A Ferrari, Luca
%A Pinzani, Renzo
%A West, Julian
%T Pattern-avoiding Dyck paths
%J Discrete mathematics & theoretical computer science
%D 2013
%V DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2334/
%R 10.46298/dmtcs.2334
%G en
%F DMTCS_2013_special_264_a18
Bernini, Antonio; Ferrari, Luca; Pinzani, Renzo; West, Julian. Pattern-avoiding Dyck paths. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013). doi : 10.46298/dmtcs.2334. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2334/

Cité par Sources :