Enumeration of connected Catalan objects by type

DOI10.1016/J.EJC.2010.10.007zbMATH Open1227.05048arXiv1005.2553OpenAlexW1963809736MaRDI QIDQ616392FDOQ616392

Authors: Brendon Rhoades 

Publication date: 7 January 2011

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

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.

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

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

zbMATH Keywords

symmetric functionsparking functions

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A problem of arrangements
• Parking functions and noncrossing partitions
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• Functional Composition Patterns and Power Series Reversion
• On noncrossing and nonnesting partitions for classical reflection groups
• Title not available (Why is that?)
• Ordered trees and non-crossing partitions
• Multinomial convolution polynomials
• The Shi arrangement and the Ish arrangement
• Nonhomogeneous parking functions and noncrossing partitions
• Faces of a hyperplane arrangement enumerated by ideal dimension, with application to plane, plaids, and Shi
• 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)