Modular Catalan Numbers
Preprint
Abstract
The Catalan number $C_n$ enumerates parenthesizations of $x_0*\dotsb*x_n$ where $*$ is a binary operation. We introduce the modular Catalan number $C_{k,n}$ to count equivalence classes of parenthesizations of $x_0*\dotsb*x_n$ when $*$ satisfies a $k$-associative law generalizing the usual associativity. This leads to a study of restricted families of Catalan objects enumerated by $C_{k,n}$ with emphasis on binary trees, plane trees, and Dyck paths, each avoiding certain patterns. We give closed formulas for $C_{k,n}$ with two different proofs. For each $n\ge0$ we compute the largest size of $k$-associative equivalence classes and show that the number of classes with this size is a Catalan number.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Chains of maximum length in the Tamari latticeProceedings of the American Mathematical Society, 2014
- KP line solitons and Tamari latticesJournal of Physics A: Mathematical and Theoretical, 2010
- Pattern avoidance in binary treesJournal of Combinatorial Theory, Series A, 2010
- Cambrian latticesAdvances in Mathematics, 2006
- Restricted 1-3-2 Permutations and Generalized PatternsAnnals of Combinatorics, 2002
- Order Structure on the Algebra of Permutations and of Planar Binary TreesJournal of Algebraic Combinatorics, 2002
- From Motzkin to Catalan permutationsDiscrete Mathematics, 2000
- On Noncrossing and Nonnesting Partitions for Classical Reflection GroupsThe Electronic Journal of Combinatorics, 1998
- Polyominoes and polygons1994
- Equivalence of the two-dimensional directed animal problem to a one-dimensional path problemAdvances in Applied Mathematics, 1988