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.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.683-694, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229675
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:44
Dernière modification le : mardi 7 mars 2017 - 15:23:07
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:35:50

Fichier

dmAS0158.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229675, version 1

Collections

Citation

Antonio Bernini, Luca Ferrari, Renzo Pinzani, Julian West. Pattern-avoiding Dyck paths. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.683-694, 2013, DMTCS Proceedings. 〈hal-01229675〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

256