New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
A combinatorial model for the Macdonald polynomials

Edited by Richard V. Kadison, University of Pennsylvania, Philadelphia, PA, and approved October 1, 2004 (received for review July 30, 2004)
Abstract
We introduce a polynomial C̃ _{μ}[Z; q, t], depending on a set of variables Z = z _{1}, z _{2},..., a partition μ, and two extra parameters q, t. The definition of C̃ _{μ} involves a pair of statistics (maj(σ, μ), inv(σ, μ)) on words σ of positive integers, and the coefficients of the z _{i} are manifestly in . We conjecture that C̃ _{μ}[Z; q, t] is none other than the modified Macdonald polynomial H̃ _{μ}[Z; q, t]. We further introduce a general family of polynomials F _{T}[Z; q, S], where T is an arbitrary set of squares in the first quadrant of the xy plane, and S is an arbitrary subset of T. The coefficients of the F _{T}[Z; q, S] are in , and C̃ _{μ}[Z; q, t] is a sum of certain F _{T}[Z; q, S] times nonnegative powers of t. We prove F _{T}[Z; q, S] is symmetric in the z _{i} and satisfies other properties consistent with the conjecture. We also show how the coefficient of a monomial in F _{T}[Z; q, S] can be expressed recursively. maple calculations indicate the F _{T}[Z; q, S] are Schurpositive, and we present a combinatorial conjecture for their Schur coefficients when the set T is a partition with at most three columns.
I refer the reader to chapter 1 of ref. 1 or chapter 7 of ref. 2 for basic facts about symmetric functions. Given a sequence μ = (μ_{1}, μ_{2},...) of nonincreasing, nonnegative integers with ∑_{i} μ_{i} = n, we say μ is a partition of n, denoted by eitherμ = n or μ ⊢ n. By adding or subtracting parts of size 0 if necessary, we will always assume partitions of n have exactly n parts. We let η(μ) = ∑_{i}(i  1)μ_{i}, and if λ is another partition, set K̃ _{λ,μ}(q, t) = t ^{η(μ)} K _{λ,μ}(q, 1/t), where K _{λ,μ}(q, t) is Macdonald's q, tKostka polynomial (ref. 1, p. 354). We call H̃ _{μ}[Z; q, t] = ∑_{λ⊢μ} s _{λ} K̃ _{λ,μ}(q, t) the modified Macdonald polynomial, where s _{λ} = s _{λ}[Z] is the Schur function and the sum is over all λ ⊢μ. The H̃ _{μ}[Z; q, t] can be easily transformed by a plethystic substitution into Macdonald's original symmetric functions P _{μ}[Z; q, t]. Macdonald defined the P _{μ} in terms of orthogonality with respect to a scalar product, and conjectured . (ref. 1, p. 355). [From their definition, all one can infer is that the K _{λ,μ}(q, t) are rational functions in q, t.] He also posed the problem of finding a combinatorial rule to describe these polynomials.
Garsia and Haiman (3) introduced an S _{n} module V(μ) for each μ ⊢ n, and posed the n! conjecture, which says that dim_{Q} V(μ) equals n!, where dim is the dimension as a vector space. This was proved in 2000 by Haiman (4). It had previously been shown (5) that the n! conjecture implies that the coefficient of q^{i}t ^{j} in K̃ _{λ,μ}(q, t) equals the multiplicity of the irreducible S _{n} character χ^{λ} in the character of a submodule V(μ)^{(i,j)} of V(μ). Macdonald's conjecture that follows. No purely combinatorial description of the K̃ _{λ,μ}(q, t) is known.
We assign (row,column) coordinates to lattice squares in the first quadrant by switching the (x, y) coordinates of the lower left corner of the square, so the lowerleft square has coordinates (0, 0), the square above it (1, 0), etc.. For a square w, we call the first coordinate of w the row value of w, denoted row (w), and the second coordinate of w the column value of w, denoted col(w). Given μ ⊢ n, we let μ also stand for the Ferrers diagram of μ (French convention), consisting of the set of n squares with coordinates (i, j), with 0 ≤ i ≤ n  1, 0 ≤ j ≤ μ_{i}  1.
Let T be a finite set of squares in the first quadrant. A subset of T consisting of all those w ∈ T with a given row value is called a row of T, and a subset of squares of T consisting of all those w ∈ T with a given column value is called a column of T. Furthermore, we let T(i) denote the ith square of T encountered if we read across rows from left to right, starting with the squares of largest row value and working downward. Given a square w ∈ T, define the leg of w, denoted leg(w), to be the number of squares in T that are strictly above and in the same column as w, and the arm of w, denoted arm(w), to be the number of squares in T strictly to the right and in the same row as w. Also, if w has coordinates (i, j), we let south(w) denote the square with coordinates (i  1, j).
A word σ of positive integers is a linear sequence σ_{1}σ_{2}···σ_{n}, with σ_{i} ≥ 1. If the letter i occurs α_{i} times in σ, for each i ≥ 1, we say σ has content α, denoted content(σ) = α. We call a pair (σ, T), where σ is a word of positive integers and T is a set of squares in the first quadrant, a filling. We represent (σ, T) geometrically by placing σ_{i} in square T(i), for 1 ≤ i ≤ n. For w ∈ T, we let w(σ) denote the element of σ placed in square w. A descent of (σ, T) is a square w ∈ T, with south(w) ∈ T and w(σ) > south(w)(σ).
Let Des(σ, T) denote the set of all descents of (σ, T). For partitions μ, define a generalized major index statistic maj(σ, μ) via
An inversion of (σ, T) is a pair of squares (a, b) with a, b ∈ T, a(σ) > b(σ), and either
Let Inv(σ, T) denote the set of all inversions of (σ, T), and define the inversion statistic inv(σ, T) via
whereS denotes the cardinality of a set S. For example, if (σ, μ) is the filling on the right in Fig. 1, then representing squares by their coordinates,
so maj(σ, μ) = 3 + 1 + 3 = 7, inv(σ, μ) = 5  (2 + 0 + 1) = 2.
For any word σ, as is customary we define the descent set Des(σ) to be {i: σ_{i} > σ_{i+1}}. Note that, if 1^{n} denotes a column of n cells, then
is the usual major index statistic on the word σ, while
is the usual inversion statistic.
For μ ⊢ n, define
where is the “weight” of σ and the sum is over all words σ of n positive integers.
Conjecture 1. For all partitions μ,
I have verified Conjecture 1 by using maple forμ ≤ 9. I thank A. Ulyanov (University of Warwick, Coventry, United Kingdom) for also verifying it forμ = 10 andμ = 11.
Given a set T of squares and a subset S ⊆ T, define
Let T̂ = {w ∈ T: south(w) ∈ T}. Note that Des(σ, T) ⊆ T̂ for all σ. In Symmetry we prove the following.
Theorem 1. For all S, T, F _{T}[Z; q, S] is a symmetric function in the z _{i}. Given S ⊆ μ, let
It follows from Theorem 1 that C̃ _{μ}[Z; q, t] is symmetric in the z _{i}, since by the definition of maj(σ, μ),
A symmetric function f(z _{1}, z _{2},...), homogeneous of degree n, is uniquely defined by the coefficients of its monomials in z _{1},..., z _{n} only. Thus one consequence of the symmetry of C̃ _{μ}[Z; q, t] is that we can restrict the infinite sum over σ in Eq. 8 to only those σ satisfying 1 ≤ σ_{i} ≤ n for 1 ≤ i ≤ n, and work with the finite set of variables Z = {z _{1}, z _{2},..., z _{n}}. For the remainder of the article we will make this assumption.
Remark 1: The definition of Inv(σ, μ) is motivated by the “dinv” statistic that occurs in a conjectured formula (ref. 6, conjecture 3.1.2) for the character of the space of diagonal harmonics. In fact, that formula can be recast as a sum of certain F _{T}[Z; q, T̂] times nonnegative powers of t and q.
Definition 1: Given a word σ of content (γ_{1}, γ_{2},···), construct a permutation σ′, the standardization of σ, by replacing the γ_{1} 1s in σ by the numbers 1,..., γ_{1}, the γ_{2} 2s in σ by the numbers γ_{1} + 1,..., γ_{1} + γ_{2}, etc., in such a way that, for i < j, σ_{i} ≤ σ_{j} if and only if . For example, if σ = 224123114 then σ′ = 458167239.
Remark 2: At first glance it might seem that inv(σ, T) could be negative. However, given a square μ ∈ Des(σ, T), then for each square v in the same row as u and to the right of u, either σ(u) > σ(v), or σ(v) > σ(south(u)), or both. Assume for the moment that σ has distinct entries. If we adopt the convention that for a square w ∉ T, σ(w) = ∞, it follows that inv(σ, T) equals the number of triples of squares u, v, w, where v ∈ T is the same row as u, with u strictly to the left of v, south(u) = w, and if we draw a circle through u, v, w, and read the σ values of u, v, w in counterclockwise order around the circle, starting at the smallest value, then the three values form a strictly increasing sequence (in particular, at least two of u, v, w are in T). If σ has repeated entries, then inv(σ, T) = inv(σ′, T) is given by applying the above rule to σ′.
In Shuffles we include some results related to the expansion of C̃ _{μ}[Z; q, t] into quasisymmetric functions. Special Values contains a discussion of the various special cases of our conjecture that we can prove, and in A Recursive Formulation we show how the coefficient of a monomial symmetric function in the F _{T}[Z; q, S]s can be expressed recursively.
maple calculations indicate the F _{T}[Z; q, S] have the following interesting property.
Conjecture 2. For all S, T, F _{T}[Z; q, S] is Schur positive.
In particular, Conjecture 2 is true for all S, T with T ⊆ μ for some partition μ withμ ≤ 8 and has also been checked for many selected choices of T withT ∈ {9, 10}. At this time we are unable to present a combinatorial prediction for the Schur coefficients for general S, T, but in Conjectures Involving Schur Coefficients we introduce an elegant conjecture for the Schur coefficients of F _{μ}[Z; q, S], and hence for the K̃ _{λ,μ}(q, t), whenever μ has at most three columns.
Symmetry
Lemma 1 below can be easily obtained from corollary 5.2.4 in ref. 6 (by letting each μ_{i} there be a single square, and choosing the offsets s _{i} appropriately). For any two sets A, B, we let A  B = {a ∈ A, a ∉ B}.
Definition 2: Let β_{1} < β_{2}···< β_{n} be real numbers. Define a βinversion of a function f: {1,..., n} → {1, 2} to be a pair i, j such that 0 < β_{j}  β_{i} < 1 and f(i) > f(j). Let inv_{β}(f) denote the number of βinversions and set
Lemma 1. With the definitions above, we have G _{β}(z _{1}, z _{2}; q) = G _{β}(z _{2}, z _{1}; q) for all β.
Proof of Theorem 1: Given S, T let , so A _{T} is symmetric in the z _{i} if and only if F _{T} is, and
By inclusionexclusion, it suffices to show that the right side of Eq. 14 is symmetric if we instead sum over all σ such that S ⊆ Des(σ, T). We denote this larger sum by A _{T}[Z; q, ≥ S]. Furthermore, it suffices to prove A _{T}[Z; q, ≥ S] is symmetric in any two consecutive variables z _{i}, z _{i+1}. Given (σ, T), let R _{i}(σ) be the set of those w ∈ T with w(σ) = i or w(σ) = i + 1. Note that if we permute the i and i + 1 entries among themselves we do not affect any inversion pairs or descents that involve a square outside R _{i}(σ). It follows that if we consider the contribution to A _{T}[Z; q, ≥ S] from all σ for which R _{i}(σ) equals a fixed set T _{0}, and the values of σ at the squares of T  T _{0} equal a fixed filling (β, T  T _{0}), we get the product of a constant monomial in {z _{1}..., z _{i1}, z _{i+2},..., z _{n}}, a constant power of q, and A _{T0}[z _{i}, z _{i+1}; q, ≥ S ∩ T _{0}]. Hence it suffices to show that for any S, T, A _{T}[z _{1}, z _{2}; q, ≥ S] = A _{T}[z _{2}, z _{1}; q, ≥ S].
Assume w ∈ Des(σ, T), so w(σ) = 2 and south(w)(σ) = 1. It is easy to check that if c is any square not equal to w or south(w), then the number of inversion pairs involving c and either w or south(w) is the same whether c(σ) = 1 or c(σ) = 2. Thus pairs of squares (w, south(w)), w ∈ S, contribute a constant power of q times a fixed power of z _{1} z _{2} to A _{T}[z _{1}, z _{2}; ≥ S]. Thus if E = T  S  {south(w), w ∈ S}, it now suffices to show A _{E}[z _{1}, z _{2}; q, ≥ ∅] = A _{E}[z _{2}, z _{1}; q, ≥ ∅].
Let n =E, and let m be the maximal row value of the squares of E. For 1 ≤ i ≤ n, if E(i) has coordinates (y, x) then set β_{i} = m  y + xε, where ε is a small positive number. It is easy to check that a pair (E(i), E(j)) of squares of E are in Inv(σ, E) if and only if (i, j) forms a βinversion in the sense of Definition 2, with f replaced by σ. The symmetry of A _{E}[z _{1}, z _{2}; q, ≥ ∅] now follows from Lemma 1.
Shuffles
We say a sequence σ_{1},..., σ_{n} is a shuffle of sequences a _{1},..., a _{k} if each a _{i} is a subsequence of σ, and σ is their disjoint union. Given a word σ of content α, note that the statistics maj(σ, T) and inv(σ, T) equal maj(σ′, T) and inv(σ′, T), respectively, where σ′ is the standardization of σ. Also, σ′ is a shuffle of increasing sequences of lengths α_{1}, α_{2},..., or equivalently (σ′)^{1} is a concatenation of increasing sequences of lengths α_{1}, α_{2},.... We call such a permutation an αshuffle, and if β is an αshuffle, we let word(β, α) denote the corresponding word of content α [so the standardization of word(β, α) equals β]. More generally, given a pair of partitions η, λ, withη +λ = n, we say σ ∈ S _{n} is a λ, ηshuffle if σ^{1} is the concatenation of alternating increasing and decreasing sequences of lengths λ_{1}, η_{1}, λ_{2}, η_{2},.... This definition also applies if η,λ are any compositions, where by a composition of n we mean a finite sequence of nonnegative integers whose sum is n.
Let 〈,〉 denote the Hall scalar product, with respect to which the Schur functions are orthonormal. It is well known that the coefficient of m _{λ} in a symmetric function f is given by 〈f, h _{λ}〉, where h _{k} = s _{k} = ∑_{λ⊢k} m _{λ} and h _{λ} = ∏_{i} h _{λi}. Results in ref. 6 involving the “superization” of symmetric functions connected to the space of diagonal harmonics transfer easily to the F _{T}[Z; q, S]. We list a few of the consequences below.
Theorem 2. For any S, T, μ ⊢ n, and compositions η, λ,
Corollary. If Conjecture 1 holds, then
For a subset D of {1, 2,..., n  1}, let
denote Gessel's quasisymmetric function.
Proposition 1. For any S, T,
Special Values
Proposition 2. Conjecture 1 is true if q = 1.
Proof: Clearly C̃ _{μ}[Z; 1, t] = ∏_{i} C̃ _{(μi})[Z; 1, t], and H̃ _{μ}[Z; 1, t] is also known to factor similarly. Thus it suffices to consider the case μ = (1^{n}), in which case it follows from the well known Cauchy identity and MacMahon's result on the equidistribution of t ^{maj(σ)} and t ^{inv(σ)} over words σ of fixed content.
One of the basic properties of the H̃ _{μ}[Z; q, t] is
where μ′ is the “conjugate” partition obtained by reflecting μ about the line y = x. Using this, the t = 1 case of Conjecture 1 follows from the following lemma, which was noticed by me and proven by N. Loehr and G. Warrington (personal communication).
Lemma 2. Let μ be a partition with two rows. Let β be a word of length μ_{1}, and α a composition of μ_{2}. Then
where the sum is over all words σ of content α, and σ + β is the word obtained by concatenating σ and β. Here is the qmultinomial coefficient ( 7 ).
A semistandard Young tableau of shape μ is a filling (σ, μ) where the entries are weakly increasing across rows and strictly decreasing down columns. The tableau is called standard if σ ∈ S _{n}. We let SSYT(μ, λ) denote the set of semistandard tableau of shape μ and content λ, and SYT(μ) denote the set of standard tableaux of shape μ. If τ is a standard tableau, we define the tableau descent set of τ, denoted descent(τ), to be the set of all i for which i + 1 is in a row of μ above the row containing i. Note that descent(τ) is different from the descent set Des when τ is viewed as a filling.
Theorem 3. Conjecture 1 is true if μ is a hook, i.e. μ = k1^{n} ^{k} for some 1 ≤ k ≤ n.
Proof: Converting (ref. 8, theorem 2.1) into a statement about the K̃ _{λ,μ}(q, t), we get
where
Using Eq. 19 we can rephrase Eq. 21 as
Applying the well known fact that
where K _{ν,λ} =SSYT(ν, λ), we now have
For any word σ of length n with 1 ≤ σ_{i} ≤ n, let rev(σ) = σ_{n}···σ_{2}σ_{1} and flip_{n}(σ) = n  σ_{1} + 1···n  σ_{n} + 1. Foata (9) (see also ref. 10) gave a bijective transformation φ on words that satisfies maj(σ) = inv(φ(σ)), and furthermore content (φ(σ)) = content (σ) and φ(σ)_{n} = σ_{n}. Let comaj(σ) = ∑_{i∈Des(σ)} n  i. For σ ∈ S _{n}, let π(σ) = (flip_{n} ○ rev ○ φ ○ rev ○ flip_{n})(σ), where ○ denotes composition. For σ a word of content λ, define π(σ) = word(π(σ′), λ). One checks that comaj(σ) = inv(π(σ)), π(σ)_{1} = σ_{1}, and π is an invertible map from the set of words of content λ to itself.
Given a λshuffle ζ ∈ S _{n}, let σ = word(ζ, λ), and let γ = σ_{1}···σ_{nk} + π^{1}(σ_{nk+1}···σ_{n}) be the word of content λ obtained by applying the map π^{1} to the last k letters of σ, and fixing the first n  k letters. The standardization γ′ is a λshuffle, and if we apply the RSK algorithm to γ′, we get a pair (P _{γ′}, Q _{γ′}) of SYT of the same shape, with Des(γ′) = descent(Q _{γ′}) and Des((γ′)^{1}) = descent(P _{γ′}) (see, for example, ref. 2, chapter 7). Furthermore, the values of maj(ζ, k1^{nk}) and inv(ζ, k1^{nk}) depend only on Q _{γ′}. Now descent (P _{γ′}) ⊆ {λ_{1}, λ_{1} + λ_{2},...}, hence in P _{γ′} the numbers 1 through λ_{1} form a horizontal strip, as do the numbers λ_{1} + 1 through λ_{1} + λ_{2}, etc. Thus we can associate a SSYT of content λ to P _{γ′}. It follows that as we vary ζ over all λshuffles in S _{n}, the number of different P _{γ′} that will occur with a given Q _{γ′} of shape ν equals K _{ν,λ}. Hence
by Eq. 26.
Remark 3: An interesting and perhaps important problem is to show
which by Eq. 19 must hold if Conjecture 1 is true. The arguments above show only that C̃ _{μ}[Z; 1, t] = C̃ _{μ′}[Z; t, 1]. We leave it as an exercise for the reader to verify Eq. 32 bijectively for hook shapes by using only the fact that C̃ _{μ}[Z; q, t] is a symmetric function, together with properties of the maps φ and π.
We can also prove the following special cases of our conjectures.
Proposition 3. Let d satisfy 0 ≤ d ≤ n. Then Eq. 16 holds when η = (n  d), λ = (d). Also,
where for any polynomial f(x), f_{xj} stands for the coefficient of x^{j} in f. In addition, Conjecture 2 holds when q = 1.
Remark 4: By taking the coefficient of z _{1} z _{2}···z _{n} in C̃ _{μ}[Z; q, t] we obtain a conjectured formula for the bigraded Hilbert series of the GarsiaHaiman modules V(μ). Garsia and Haiman (11) derive a statistical description for the Hilbert series when μ = k1^{nk}, which is easily shown to be equivalent to ours. They also obtain statistics for the case where μ has two rows, but I do not know how to show their formula is equivalent to that predicted by Conjecture 1 for this case.
A Recursive Formulation
Given λ ⊢ n and S, T with S ⊆ T, to calculate the coefficient of the monomial symmetric function m _{λ} in F _{T}[Z; q, S], by symmetry it suffices to calculate the coefficient of , so we can consider only fillings involving words of content rev(λ).
Recall the description of inv(σ, T) in Remark 2, involving triples of squares. The fact that all of the ns are larger than any other entry of σ will allow us to isolate the contribution to inv(σ, T) from triples involving an n. We will view the set of squares of (σ, T) containing ns as P ∪ Q, where P ⊆ T  S, Q ⊆ S.
Definition 3: Given P, Q, S, T as above, let ind(P, Q, S, T) denote the number of triples of squares u, v, w satisfying
where in these patterns a square occupied by
The following result is easily derived from the definition of F _{T}[Z; q, S] and ind(P, Q, S, T).
Theorem 4. For λ ⊢ n and S ⊆ T,
with the initial condition F _{∅}[Z; q, ∅] = 1.
Conjectures Involving Schur Coefficients
It would be very desirable to have a combinatorial description of the Schur coefficients of the F _{T}[Z; q, S]. Such formulas exist for the K̃ _{λ,μ} when λ or μ is a hook or when μ has two columns or two rows, and for some other shapes obtained by adding a square or two to one of the above shapes. All of the published formulas for the case when μ has two columns are fairly complicated, involving such things as rigged configurations and catabolism (1214).
We now advance a conjectured combinatorial description for 〈F _{μ}[Z; q, S], s _{λ}〉 whenever μ has at most three columns. Let F _{1} = (12···n, μ) be the filling of μ by the identity permutation and F _{2} = (n···21, μ) the filling by the reverse of the identity. For any pair of integers (a, b) with 1 ≤ a < b ≤ n, say a is in square A in F _{1} and b is in square B in F _{1}, i.e. A = μ(a), B = μ(b). Define the (multit variate) μweight of (a, b), denoted wt(μ, a, b), as
For example, for F _{1} as on the left in Fig. 3,
Given a SYT τ of partition shape withμ squares, our strategy will be to identify pairs (a, b) as “inversion pairs” of τ, then weight them as in Eq. 38. We begin by partially defining what constitutes an inversion by the following.

The pair (a, b) forms an inversion in τ if 1 ≤ a < b ≤μ and b is weakly northwest of a in τ, i.e. b is not in a column to the right of a.

If a < b and b is weakly southeast of a, i.e. is not in a row above a, then (a, b) do not form an inversion pair.

If a + 3 is neither weakly northwest or weakly southeast of a, then (a, a + 3) forms an inversion pair if τ contains the pattern on the left in Fig. 4 and does not if τ contains the pattern on the right.
Define
which is a “multit variate” version of C̃ _{μ}. By Eq. 12, if we replace t _{w} by t ^{leg(w)+1} for all w, this multit version will reduce to C̃ _{μ}[Z; q, t].
Let inversion(τ) denote the set of inversion pairs of τ.
Conjecture 3. If μ has at most three columns,
Example: If τ is the tableau on the right in Fig. 3, then
form inversions with nontrivial 3321weights, so the contribution of τ to is t _{(3,0)} ^{*} q ^{*} q ^{*} t _{(1,0)} q ^{2} ^{*} q ^{*} q ^{*} t _{(1,2)} ^{*} q ^{*} q = t _{(3,0)} t _{(1,0)} t _{(1,2)} q ^{4}.
Conjecture 3 has been checked in maple for all λ, μ withλ ≤ 12 andμ ≤ 12. The calculation made use of tables of the K _{λ,μ}(q, t) supplied by G. Tesler (Univeristy of California at San Diego, La Jolla), as well as J. Stembridge's maple package for symmetric functions sf (15), which was also used in testing our other conjectures. Note that if Eq. 40 holds, by taking the coefficient of ∏_{w∈S} t _{w} in the right side of Eq. 40 we obtain a formula for 〈F _{μ}[Z; q, S], s _{λ}〉.
Note. Conjecture 1 has been proven by M. Haiman (University of California, Berkeley), N. Loehr (University of Pennsylvania), and myself.
Acknowledgments
My research is partially supported by National Security Agency Grant MSPF02G193.
Footnotes

↵ † Email: jhaglund{at}math.upenn.edu.

This paper was submitted directly (Track II) to the PNAS office.
 Copyright © 2004, The National Academy of Sciences
References

↵
Macdonald, I. G. (1995) Symmetric Functions and Hall Polynomials (Oxford Univ. Press, New York), 2nd Ed.

↵
Stanley, R. P. (1999) Enumerative Combinatorics (Cambridge Univ. Press, Cambridge, U.K.), Vol. 2.

↵
Garsia, A. M. & Haiman, M. (1993) Proc. Natl. Acad. Sci. USA 90 , 36073610. pmid:11607377
 ↵

↵
Haiman, M. (1999) New Perspectives in Algebraic Combinatorics (Cambridge Univ. Press, Cambridge, U.K.), pp. 207254.

↵
Haglund, J., Haiman, M., Loehr, N., Remmel, J. & Ulyanov, A. (2004) Duke J. Math., in press.

↵
Andrews, G. E. (1998) The Theory of Partitions (Cambridge Univ. Press, Cambridge, U.K.).

↵
Stembridge, J. (1994) Proc. Am. Math. Soc. 121 , 469490.

↵
Foata, D. (1968) Proc. Am. Math. Soc. 19 , 236240.

↵
Foata, D. & Schützenberger, M.P. (1978) Math. Nachr. 83 , 143159.
 ↵

↵
Fishel, S. (1995) Proc. Am. Math. Soc. 123 , 29612969.

Lapointe, L. & Morse, J. (2003) Algebraic Combinatorics and Quantum Groups (World Scientific, River Edge, NJ), pp. 6184.

↵
Zabrocki, M. (1998) Electron. J. Combin. 5 , R45.
 ↵