Name
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. We also compute the generating function of Dyck paths avoiding any single pattern in a recursive fashion, from which we deduce the exact enumeration of such a class of paths. Finally, we describe the asymptotic behavior of the sequence counting Dyck paths avoiding a generic pattern, we prove that the Dyck pattern poset is a well-ordering and we propose a list of open problems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.disc.2013.12.011 | Discrete Mathematics |
Keywords | Field | DocType |
dyck pattern poset,specific case,poset structure,generating function,asymptotic behavior,dyck path,generic pattern,pattern-avoiding dyck path,exact enumeration,single pattern,pattern,poset,asymptotic | Discrete mathematics,Generating function,Combinatorics,Lattice (order),Enumeration,Permutation,Dyck language,Asymptotic analysis,Recursion,Mathematics,Partially ordered set | Journal |
Volume | ISSN | Citations |
321 | 0012-365X | 3 |
PageRank | References | Authors |
0.52 | 5 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Axel Bacher | 1 | 21 | 4.82 |
| Antonio Bernini | 2 | 34 | 7.68 |
| Luca Ferrari | 3 | 47 | 10.50 |
| Benjamin Gunby | 4 | 3 | 0.52 |
| Renzo Pinzani | 5 | 341 | 67.45 |
| Julian West | 6 | 3 | 0.52 |