Enumeration of connected Catalan objects by type

DOI10.1016/J.EJC.2010.10.007MaRDI QIDQ616392zbMATH OpenOpenAlexFDO

Authors Brendon Rhoades

Publication date 7 January 2011

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

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

zbMATH Keywords

symmetric functionsparking functions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18)

Abstract: Noncrossing set partitions, nonnesting set partitions, Dyck paths, and rooted plane trees are four classes of Catalan objects which carry a notion of type. There exists a product formula which enumerates these objects according to type. We define a notion of `connectivity' for these objects and prove an analogous product formula which counts connected objects by type. Our proof of this product formula is combinatorial and bijective. We extend this to a product formula which counts objects with a fixed type and number of connected components. We relate our product formulas to symmetric functions arising from parking functions. We close by presenting an alternative proof of our product formulas communicated to us by Christian Krattenthaler which uses generating functions and Lagrange inversion.

Recommendations

• On trees and noncrossing partitions
• On the structure of the lattice of noncrossing partitions
• A bijection between noncrossing and nonnesting partitions of types \(A\) and \(B\)
• A bijection between noncrossing and nonnesting partitions of types A and B
• Parking functions of types A and B

Cites work

• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• A problem of arrangements
• Faces of a hyperplane arrangement enumerated by ideal dimension, with application to plane, plaids, and Shi
• Functional Composition Patterns and Power Series Reversion
• Multinomial convolution polynomials
• Nonhomogeneous parking functions and noncrossing partitions
• On noncrossing and nonnesting partitions for classical reflection groups
• Ordered trees and non-crossing partitions
• Parking functions and noncrossing partitions
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• The Shi arrangement and the Ish arrangement
• The cycle lemma and some applications

Cited in

(4)

• Asymptotics for generating functions of the Fuss-Catalan numbers
• The Shi arrangement and the Ish arrangement
• Chung-Feller property of Schröder objects
• Enumeration of Fuss-Catalan paths by type and blocks

This page was built for publication: Enumeration of connected Catalan objects by type

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