Journal of Combinatorics

Volume 10 (2019)

Number 4

Special Issue in Memory of Jeff Remmel, Part 2 of 2

Guest Editor: Nicholas A. Loehr

Signature Catalan combinatorics

Pages: 725 – 773

DOI: http://dx.doi.org/10.4310/JOC.2019.v10.n4.a6

Authors

Cesar Ceballos (Faculty of Mathematics, University of Vienna, Austria)

Rafael S. González D’León (Escuela de Ciencias Exactas e Ingeniería, Universidad Sergio Arboleda, Bogotá, Colombia)

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, \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

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