Signature Catalan combinatorics

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, \dotsc , 2)$ and $s = (k +1, \dotsc , 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.

Keywords

Catalan numbers, planar rooted trees, Dyck paths, noncrossing partitions, noncrossing matchings, polygon subdivisions, Stirling permutations, parking functions

2010 Mathematics Subject Classification

05A19

Full Text (PDF format)

C. Ceballos was supported by the Austrian Science Foundation FWF, grant F 5008-N15, in the framework of the Special Research Program Algorithmic and Enumerative Combinatorics”; he was also partially supported by York University and a Banting Postdoctoral Fellowship of the Government of Canada.

R. S. González D’León was supported during this project by University of Kentucky, York University and Universidad Sergio Arboleda and he is grateful for their support.

Received 10 May 2018

Published 17 July 2019