We define a family of maps on lattice paths, called sweep maps, that assign levels to each step in the path and sort steps according to their level. Surprisingly, although sweep maps act by sorting, they appear to be bijective in general. The sweep m
aps give concise combinatorial formulas for the q,t-Catalan numbers, the higher q,t-Catalan numbers, the q,t-square numbers, and many more general polynomials connected to the nabla operator and rational Catalan combinatorics. We prove that many algorithms that have appeared in the literature (including maps studied by Andrews, Egge, Gorsky, Haglund, Hanusa, Jones, Killpatrick, Krattenthaler, Kremer, Orsina, Mazin, Papi, Vaille, and the present authors) are all special cases of the sweep maps or their inverses. The sweep maps provide a very simple unifying framework for understanding all of these algorithms. We explain how inversion of the sweep map (which is an open problem in general) can be solved in known special cases by finding a bounce path for the lattice paths under consideration. We also define a generalized sweep map acting on words over arbitrary alphabets with arbitrary weights, which is also conjectured to be bijective.
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 nth Catalan number. In this paper, we will generalize this setup to
rational parking functions indexed by a pair (a,b) of coprime positive integers. We show that these parking functions, which are counted by b^(a-1), carry a permutation representation of S_a in which the number of orbits is a rational Catalan number. We compute the Frobenius characteristic of the S_a-module of (a,b)-parking functions. Next we propose a combinatorial formula for a q-analogue of the rational Catalan numbers and relate this formula to a new combinatorial model for q-binomial coefficients. Finally, we discuss q,t-analogues of rational Catalan numbers and parking functions (generalizing the shuffle conjecture for the classical case) and present several conjectures.
For each skew shape we define a nonhomogeneous symmetric function, generalizing a construction of Pak and Postnikov. In two special cases, we show that the coefficients of this function when expanded in the complete homogeneous basis are given in ter
ms of the (reduced) type of $k$-divisible noncrossing partitions. Our work extends Haimans notion of a parking function symmetric function.
