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.
The random chemistry algorithm of Kauffman can be used to determine an unknown subset S of a fixed set V. The algorithm proceeds by zeroing in on S through a succession of nested subsets V=V_0,V_1,...,V_m=S. In Kauffmans original algorithm, the size
of each V_i is chosen to be half the size of V_{i-1}. In this paper we determine the optimal sequence of sizes so as to minimize the expected run time of the algorithm.
The game of memory is played with a deck of n pairs of cards. The cards in each pair are identical. The deck is shuffled and the cards laid face down. A move consists of flipping over first one card then another. The cards are removed from play if th
ey match. Otherwise, they are flipped back over and the next move commences. A game ends when all pairs have been matched. We determine that, when the game is played optimally, as n tends to infinity: 1) The expected number of moves is (3 - 2 ln 2)n + 7/8 - 2 ln 2 (approximately 1.61 n), 2) The expected number of times two matching cards are unwittingly flipped over is ln 2, and 3) The expected number of flips until two matching cards have been seen is asymptotically sqrt{pi n}.
We introduce explicit combinatorial interpretations for the coefficients in some of the transition matrices relating to skew Hall-Littlewood polynomials P_lambda/mu(x;t) and Hiverts quasisymmetric Hall-Littlewood polynomials G_gamma(x;t). More specif
ically, we provide: 1) the G-expansions of the Hall-Littlewood polynomials P_lambda, the monomial quasisymmetric polynomials M_alpha, the quasisymmetric Schur polynomials S_alpha, and the peak quasisymmetric functions K_alpha; 2) an expansion of P_lambda/mu in terms of the F_alphas. The F-expansion of P_lambda/mu is facilitated by introducing starred tableaux.
Every word has a shape determined by its image under the Robinson-Schensted-Knuth correspondence. We show that when a word w contains a separable (i.e., 3142- and 2413-avoiding) permutation sigma as a pattern, the shape of w contains the shape of sig
ma. As an application, we exhibit lower bounds for the lengths of supersequences of sets containing separable permutations.
We study equivalence classes relating to the Kazhdan-Lusztig mu(x,w) coefficients in order to help explain the scarcity of distinct values. Each class is conjectured to contain a crosshatch pair. We also compute the values attained by mu(x,w) for the permutation groups S_10 and S_11.
We conjecture a combinatorial formula for the monomial expansion of the image of any Schur function under the Bergeron-Garsia nabla operator. The formula involves nested labeled Dyck paths weighted by area and a suitable diagonal inversion statistic.
Our model includes as special cases many previous conjectures connecting the nabla operator to quantum lattice paths. The combinatorics of the inverse Kostka matrix leads to an elementary proof of our proposed formula when q=1. We also outline a possible approach for proving all the extant nabla conjectures that reduces everything to the construction of sign-reversing involutions on explicit collections of signed, weighted objects.
