Modular Catalan numbers

DOI10.1016/J.EJC.2016.11.004zbMATH Open1352.05015arXiv1508.01688OpenAlexW2962862310MaRDI QIDQ730265FDOQ730265

Nickolas Hein, Jia Huang

Publication date: 27 December 2016

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

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 $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.

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)

Cites Work

• Pattern avoidance in binary trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• Cambrian lattices.
• Title not available (Why is that?)
• On noncrossing and nonnesting partitions for classical reflection groups
• Order structure on the algebra of permutations and of planar binary trees
• Title not available (Why is that?)
• Catalan Numbers
• Eulerian Numbers
• From Motzkin to Catalan permutations
• Restricted 1-3-2 permutations and generalized patterns
• Title not available (Why is that?)
• KP line solitons and Tamari lattices
• Chains of maximum length in the Tamari lattice
• Title not available (Why is that?)
• Equivalence of the two-dimensional directed animal problem to a one- dimensional path problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (13)

• Title not available (Why is that?)
• Enumerating Restricted Dyck Paths with Context-Free Grammars
• Variations of the Catalan numbers from some nonassociative binary operations
• On the Catalan numbers and some of their identities
• The associative-commutative spectrum of a binary operation
• Norton algebras of the Hamming graphs via linear characters
• Nonassociativity of the Norton algebras of some distance regular graphs
• Associative spectra of graph algebras. I: Foundations, undirected graphs, antiassociative graphs
• Cunningham numbers in modular arithmetic
• Modular Fuss-Catalan numbers
• Catalan numbers modulo a prime power
• Stack-sorting with consecutive-pattern-avoiding stacks
• The Nonassociativity of the Double Minus Operation

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)