Modular Catalan numbers

DOI10.1016/J.EJC.2016.11.004MaRDI QIDQ730265zbMATH OpenOpenAlexFDO

Authors Nickolas Hein, Jia Huang

Publication date 27 December 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01688

zbMATH Keywords

\(k\)-associative equivalence classes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: The Catalan number $C_n$ enumerates parenthesizations of $x_0\ast dotsb\ast x_n$ where $\ast$ is a binary operation. We introduce the modular Catalan number $C_{k,n}$ to count equivalence classes of parenthesizations of $x_0\ast dotsb\ast x_n$ when $\ast$ 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 $nge0$ we compute the largest size of $k$-associative equivalence classes and show that the number of classes with this size is a Catalan number.

Recommendations

• Modular Fuss-Catalan numbers
• Catalan numbers, their generalization, and their uses
• Catalan structures and Catalan pairs

Cites work

• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 718850 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 1522340 (Why is no real title available?)
• scientific article; zbMATH DE number 269845 (Why is no real title available?)
• scientific article; zbMATH DE number 5251049 (Why is no real title available?)
• scientific article; zbMATH DE number 2196393 (Why is no real title available?)
• Analytic combinatorics
• Cambrian lattices.
• Catalan Numbers
• Chains of maximum length in the Tamari lattice.
• Equivalence of the two-dimensional directed animal problem to a one- dimensional path problem
• Eulerian Numbers
• From Motzkin to Catalan permutations
• KP line solitons and Tamari lattices
• On noncrossing and nonnesting partitions for classical reflection groups
• Order structure on the algebra of permutations and of planar binary trees
• Pattern avoidance in binary trees
• Restricted 1-3-2 permutations and generalized patterns
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)

Cited in

(13)

• Staircase tilings and \(k\)-Catalan structures
• On the Catalan numbers and some of their identities
• The associative-commutative spectrum of a binary operation
• Cunningham numbers in modular arithmetic
• Associative spectra of graph algebras. I: Foundations, undirected graphs, antiassociative graphs
• The nonassociativity of the double minus operation
• Modular Fuss-Catalan numbers
• Norton algebras of the Hamming graphs via linear characters
• scientific article; zbMATH DE number 5723744 (Why is no real title available?)
• Catalan numbers modulo a prime power
• Enumerating restricted Dyck paths with context free grammars
• Nonassociativity of the Norton algebras of some distance regular graphs
• Stack-sorting with consecutive-pattern-avoiding stacks

Describes a project that uses

Uses Software

• OEIS
• BinaryTrees

This page was built for publication: Modular Catalan numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730265)