The Dyck pattern poset. (English) Zbl 1281.05009
Summary: 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.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
Online Encyclopedia of Integer Sequences:
Number of Dyck paths of semilength n avoiding the pattern U^(n-1) D^(n-1).Array read by antidiagonals upwards: T(n,k) (n>=1, k>=0) = number of Dyck paths of semilength k avoiding the pattern U^(n-1) D U D^(n-1).
Triangle read by rows: T(n,k) (n >= 1, k >= 0) = number of Dyck paths of semilength k avoiding the pattern U^n D^n.
References:
| [1] | Bernini, A.; Ferrari, L.; Pinzani, R.; West, J., Pattern avoiding Dyck paths, Discrete Math. Theor. Comput. Sci. Proc., AS, 683-694 (2013) · Zbl 1294.05004 |
| [2] | Björner, A., The Möbius function of subword order, (Invariant Theory and Tableaux (Minneapolis, MN, 1988). Invariant Theory and Tableaux (Minneapolis, MN, 1988), IMA Vol. Math. Appl., vol. 19 (1990), Springer: Springer New York), 118-124 · Zbl 0706.06007 |
| [4] | Choffrut, C.; Karhumäki, J., Combinatorics of words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages (1997), Springer), 329-438 · Zbl 0866.68057 |
| [5] | Dairyko, M.; Pudwell, L.; Tyner, S.; Wynn, C., Non-contiguous pattern avoidance in binary trees, Electron. J. Combin., 19, 3, #P22 (2012) · Zbl 1252.05086 |
| [6] | Giraudo, S., Balanced binary trees in the Tamari lattice, Discrete Math. Theor. Comput. Sci. Proc., AN, 725-736 (2010) · Zbl 1373.05038 |
| [7] | Goyt, A., Avoidance of partitions of a three element set, Adv. Appl. Math., 41, 95-114 (2008) · Zbl 1139.05003 |
| [8] | Higman, G., Ordering by divisibility in abstract algebras, Proc. Lond. Math. Soc., 3, 326-336 (1952) · Zbl 0047.03402 |
| [9] | Klazar, M., On \(a b a b\)-free and \(a b b a\)-free sets partitions, European J. Combin., 17, 53-68 (1996) · Zbl 0840.05004 |
| [10] | Knuth, D., The Art of Computer Programming, Vol. 1 (1968), Addison Wesley: Addison Wesley Boston · Zbl 0191.17903 |
| [11] | Rowland, E., Pattern avoidance in binary trees, J. Combin. Theory Ser. A, 117, 741-758 (2010) · Zbl 1221.05058 |
| [12] | Sagan, B. E., Pattern avoidance in set partitions, Ars Combin., 94, 79-96 (2010) · Zbl 1240.05018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
