Signature Catalan combinatorics

DOI10.4310/JOC.2019.V10.N4.A6zbMATH Open1417.05003arXiv1805.03863WikidataQ127463773 ScholiaQ127463773MaRDI QIDQ2317482FDOQ2317482

Authors: Cesar Ceballos, Rafael S. González D'León 

Publication date: 12 August 2019

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

Abstract: The Catalan numbers constitute one of the most important sequences in combinatorics. Catalan objects have been generalized in various directions, including the classical Fuss-Catalan objects and the rational Catalan generalization of Armstrong-Rhoades-Williams. We propose a wider generalization of these families indexed by a composition $s$ which is motivated by the combinatorics of planar rooted trees; when $s=(2,\mathrm{...},2)$ and $s=(k+1,\mathrm{...},k+1)$ we recover the classical Catalan and Fuss-Catalan combinatorics, respectively. Furthermore, to each pair $(a,b)$ of relatively prime numbers we can associate a signature that recovers the combinatorics of rational Catalan objects. We present explicit bijections between the resulting $s$-Catalan objects, and a fundamental recurrence that generalizes the fundamental recurrence of the classical Catalan numbers. Our framework allows us to define signature generalizations of parking functions which coincide with the generalized parking functions studied by Pitman-Stanley and Yan, as well as generalizations of permutations which coincide with the notion of Stirling multipermutations introduced by Gessel-Stanley. Some of our constructions differ from the ones of Armstrong-Rhoades-Williams, however as a byproduct of our extension, we obtain the additional notions of rational permutations and rational trees.

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

Recommendations

• Rational parking functions and Catalan numbers
• Combinatorial properties of Catalan pairs
• Catalan pairs: a relational-theoretic approach to Catalan numbers
• Generalized Catalan numbers from hypergraphs
• Permutation statistics and the \(q,t\)-Catalan sequence

zbMATH Keywords

Catalan numbersDyck pathsparking functionsStirling permutationsnoncrossing partitionsplanar rooted treesnoncrossing matchingspolygon subdivisions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial identities, bijective combinatorics (05A19)

Cited In (12)

• Rational parking functions and Catalan numbers
• Enumerating parking completions using join and split
• The \(s\)-weak order and \(s\)-permutahedra
• Hopf algebras of parking functions and decorated planar trees
• Generalized \(q,t\)-Catalan numbers
• The \(s\)-weak order and \(s\)-permutahedra. II: The combinatorial complex of pure intervals
• On (shape-)Wilf-equivalence for words
• A generalization of parking functions allowing backward movement
• Hopf dreams and diagonal harmonics
• The \(s\)-weak order and \(s\)-permutahedra. I: Combinatorics and lattice structure
• On framed triangulations of flow polytopes, the \(\nu\)-Tamari lattice and Young's lattice
• Poset topology of \(s\)-weak order via SB-labelings

This page was built for publication: Signature Catalan combinatorics

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