Rational Parking Functions and Catalan Numbers

By Drew Armstrong, Nicholas A. Loehr, Gregory S. Warrington. 2014

95 citations recorded by the source corpus.

The “classical” parking functions, counted by the Cayley number (n+1)n−1, carry a natural permutation representation of the symmetric group Sn in which the number of orbits is the Catalan number $${\frac{1}{n+1} \left( \begin{array}{ll} 2n \\ n \end{array} \right)}$$1n+1(2nn). 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 ba−1, carry a permutation representation of Sa in which the number of orbits is the “rational” Catalan number $${\frac{1}{a+b} \left( \begin{array}{ll} a+b \\ a \end{array} \right)}$$1a+ba+ba. First, we compute the Frobenius characteristic of the Sa-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 $${\frac{1}{[a+b]_{q}} {{\left[ \begin{array}{ll} a+b \\ a \end{array} \right]}_{q}}}$$1[a+b]qa+baq and for the q-binomial coefficients $${{{\left[ \begin{array}{ll} n \\ k \end{array} \right]}_{q}}}$$nkq. 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.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/24150681f71f08157111c3899db55acdcdcb0de6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Jeffrey B. Remmel

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Compositional (km,kn)-Shuffle Conjectures (2014, background): “For more on the coprime case, see [1].”
The Delta Conjecture (2015, background): “As mentioned in Equation 4 of [ALW14], the number of Dyck paths with exactly ci vertical runs of length i for each i is 1 n+ 1 ( n+ 1 c1, c2, .”