Pattern avoiding Dyck paths

Abstract. We introduce the notion of 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 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. Résumé. Nous proposons la notion d’un motif dans le contexte de chemins de treillis, et étudions le cas spécifique des chemins de Dyck. Comme dans le cas des permutations, on obtient une structure de poset sur l’ensemble de tous les chemins de Dyck, que nous appelons l’ensemble des chemins de Dyck partiellement ordonne ́ selon le motif. Étant donne ́ un chemin de Dyck P, nous déterminons une formule pour le nombre de chemins de Dyck couverts par P, ainsi que pour le nombre de chemins de Dyck couvrant P. Nous énumérons ensuite les chemins de Dyck évitant certaines catégories de motif. Enfin, nous proposons une conjecture asymptotique concernant le nombre de chemins de Dyck évitant un motif générique et nous posons quelques problèmes ouverts concernants la structure du poset etudié