Multivariate Analogues of Catalan Numbers, Parking Functions, and their Extensions


Nicholas Anthony Loehr

This document is concerned with the Catalan numbers and their generalizations. The Catalan numbers, which occur ubiquitously in combinatorics, are also connected to certain problems in representation theory, symmetric function theory, the theory of Macdonald polynomials, algebraic geometry, and Lie algebras. Garsia and Haiman introduced a bivariate analogue of the Catalan numbers, called the $q,t$-Catalan sequence, in this setting. This sequence counts multiplicities of the sign character in a certain doubly graded $S_n$-module called the diagonal harmonics module. Several classical $q$-analogues of the Catalan numbers can be obtained from this sequence by suitable specializations. Haglund and Haiman separately proposed combinatorial interpretations for this $q,t$-Catalan sequence by defining two statistics on Dyck paths. Garsia and Haglund later proved the correctness of these interpretations. Haglund, Haiman, and Loehr proposed similar statistics on labelled Dyck paths, which are conjectured to give the Hilbert series of the diagonal harmonics module.

In this thesis, we introduce and analyze several conjectured combinatorial interpretations for the ``higher'' $q,t$-Catalan sequences of Garsia and Haiman. These interpretations involve pairs of statistics for unlabelled lattice paths staying inside certain triangles. Trivariate generating functions for these paths are also discussed. These constructions are then generalized to lattice paths lying in certain trapezoids. We study several five-variable generating functions for these paths and derive their combinatorial properties.

Next, we consider multivariate generating functions for labelled lattice paths (parking functions) staying within various shapes. In the case of triangles, we obtain a conjectured combinatorial interpretation for the Hilbert series of higher-order analogues of the diagonal harmonics module.

Finally, we present some miscellaneous results connected to the various Catalan sequences. In particular, we give a determinantal formula for the Carlitz-Riordan numbers that $q$-count Dyck paths by area. We also give several ways to define the bivariate sequence $C_n(q,t)$ in terms of classical permutation statistics. We discuss the connection between the multivariate Catalan sequences and a remarkable partition identity of M. Haiman. We conclude by summarizing some open problems suggested by the various combinatorial constructs considered here.

UCSD > Mathematics > Thesis Archive