Signature Catalan combinatorics

DOI10.4310/JOC.2019.V10.N4.A6MaRDI QIDQ2317482zbMATH OpenWikidataFDO

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)

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

zbMATH Keywords

Catalan numbersDyck pathsnoncrossing matchingsnoncrossing partitionsparking functionsplanar rooted treespolygon subdivisionsStirling permutations

Mathematics Subject Classification ID

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

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.

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

Cited in

(16)

• On (shape-)Wilf-equivalence for words
• Hopf algebras of parking functions and decorated planar trees
• Enumerating parking completions using join and split
• Poset topology of \(s\)-weak order via SB-labelings
• Generalized \(q,t\)-Catalan numbers
• A generalization of parking functions allowing backward movement
• The \(s\)-weak order and \(s\)-permutahedra
• Rational parking functions and Catalan numbers
• On framed triangulations of flow polytopes, the \(\nu\)-Tamari lattice and Young's lattice
• Hopf dreams and diagonal harmonics
• The s-weak order and s-permutahedra. II: The combinatorial complex of pure intervals
• The \(s\)-weak order and \(s\)-permutahedra. I: Combinatorics and lattice structure
• Combinatorial enumeration of lattice paths by flaws with respect to a linear boundary of rational slope
• Interval and -interval rational parking functions
• Realizing the s-permutahedron via flow polytopes
• Quasisymmetric Schur Q-functions and peak Young quasisymmetric Schur functions

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)