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.
Pattern-avoiding Dyck paths / Antonio Bernini; Luca Ferrari; Renzo Pinzani; Julian West. - In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. - ISSN 1365-8050. - ELETTRONICO. - AS:(2013), pp. 683-694. (Intervento presentato al convegno Formal Power Series and Algebraic Combinatorics 2013 tenutosi a Paris, France nel 24-28 giugno 2013).
Pattern-avoiding Dyck paths
BERNINI, ANTONIO;FERRARI, LUCA;PINZANI, RENZO;
2013
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.File | Dimensione | Formato | |
---|---|---|---|
bernini_ferrari_pinzani_west.pdf
accesso aperto
Descrizione: articolo principale
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
388.54 kB
Formato
Adobe PDF
|
388.54 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.