TY - JOUR
T1 - Modular Catalan numbers
AU - Hein, Nickolas
AU - Huang, Jia
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2017/3/1
Y1 - 2017/3/1
N2 - The Catalan number Cn enumerates parenthesizations of x0∗⋯∗xn where ∗ is a binary operation. We introduce the modular Catalan number Ck,n to count equivalence classes of parenthesizations of x0∗⋯∗xn when ∗ satisfies a k-associative law generalizing the usual associativity. This leads to a study of restricted families of Catalan objects enumerated by Ck,n with emphasis on binary trees, plane trees, and Dyck paths, each avoiding certain patterns. We give closed formulas for Ck,n with two different proofs. For each n≥0 we compute the largest size of k-associative equivalence classes and show that the number of classes with this size is a Catalan number.
AB - The Catalan number Cn enumerates parenthesizations of x0∗⋯∗xn where ∗ is a binary operation. We introduce the modular Catalan number Ck,n to count equivalence classes of parenthesizations of x0∗⋯∗xn when ∗ satisfies a k-associative law generalizing the usual associativity. This leads to a study of restricted families of Catalan objects enumerated by Ck,n with emphasis on binary trees, plane trees, and Dyck paths, each avoiding certain patterns. We give closed formulas for Ck,n with two different proofs. For each n≥0 we compute the largest size of k-associative equivalence classes and show that the number of classes with this size is a Catalan number.
UR - http://www.scopus.com/inward/record.url?scp=85002835525&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85002835525&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2016.11.004
DO - 10.1016/j.ejc.2016.11.004
M3 - Article
AN - SCOPUS:85002835525
SN - 0195-6698
VL - 61
SP - 197
EP - 218
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -