Article ID Journal Published Year Pages File Type
10118393 European Journal of Combinatorics 2005 11 Pages PDF
Abstract
The Catalan numbers occur ubiquitously in combinatorics. R. Stanley's book Enumerative Combinatorics 2 (1999) and its addendum (http://www-math.mit.edu/~rstan/ec/catadd.pdf) list over 95 collections of objects counted by the Catalan numbers. We augment this list with two additional collections of permutations that are enumerated by the Catalan numbers. Furthermore, we show that the generating function for either collection, relative to the classical coinversion and major index statistics, is precisely the q,t-Catalan sequence of Garsia and Haiman. This is proved by exhibiting weight-preserving bijections between the given collections and the set of Dyck paths. The bijections are based on encodings of Dyck paths and permutations as sequences of partitions.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,