Rational Parking Functions and Catalan Numbers

摘要

The "classical" parking functions, counted by the Cayley number (n+1) (n-1), carry a natural permutation representation of the symmetric group S (n) in which the number of orbits is the Catalan number . In this paper, we will generalize this setup to "rational" parking functions indexed by a pair (a, b) of coprime positive integers. These parking functions, which are counted by b (a-1), carry a permutation representation of S (a) in which the number of orbits is the "rational" Catalan number . First, we compute the Frobenius characteristic of the S (a) -module of (a, b)-parking functions, giving explicit expansions of this symmetric function in the complete homogeneous basis, the power-sum basis, and the Schur basis. Second, we study q-analogues of the rational Catalan numbers, conjecturing new combinatorial formulas for the rational q-Catalan numbers and for the q-binomial coefficients . We give a bijective explanation of the division by [a+b] (q) that proves the equivalence of these two conjectures. Third, we present combinatorial definitions for q, t-analogues of rational Catalan numbers and parking functions, generalizing the Shuffle Conjecture for the classical case. We present several conjectures regarding the joint symmetry and t = 1/q specializations of these polynomials. An appendix computes these polynomials explicitly for small values of a and b.