{'fraction_non_alphanumeric': 0.08034894398530762, 'fraction_numerical': 0.017026323844505663, 'mean_word_length': 3.4295398695025847, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 41, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Combinatorial Formula for Macdonald Polynomials

We prove a combinatorial formula for the Macdonald polynomial H_mu(x;q,t) which had been conjectured by the first author. Corollaries to our main theorem include the expansion of H_mu(x;q,t) in terms of LLT polynomials, a new proof of the charge formula of Lascoux and Schutzenberger for Hall-Littlewood polynomials, a new proof of Knop and Sahi's combinatorial formula for Jack polynomials as well as a lifting of their formula to integral form Macdonald polynomials, and a new combinatorial rule for the Kostka-Macdonald coefficients K_{lambda,mu}(q,t) in the case that mu is a partition with parts less than or equal to 2.


Introduction
The Macdonald polynomialsH µ (x; q, t) have been the subject of much attention in combinatorics since Macdonald [25] defined them and conjectured that their expansion in terms of Schur polynomials should have positive coefficients. Macdonald's conjecture was proven in [11] by geometric and representation-theoretic means, but these results do not provide any purely combinatorial interpretation forH µ (x; q, t). Such an interpretation, which had been sought for many years, was recently conjectured by one of us (Haglund [8]). The goal of this paper is to prove the validity of Haglund's conjectured formula.
A number of consequences flow from the new formula and its proof. We shall summarize a few of them here. Some follow instantly, and the rest will be discussed in more detail in later sections of the paper.
(i) The Macdonald polynomialsH µ (x; q, t) are characterized by certain axioms (see below). Their existence is not obvious from the axioms. To prove our combinatorial formula, we will show directly that it satisfies the axioms. Therefore we get a new proof of the existence theorem.
(ii) By definition, the coefficients of the Macdonald polynomialsH µ (x; q, t) belong to the field of rational functions Q(q, t). In fact, the coefficients belong to Z[q, t]. This integrality property was not proven until six or seven years after Macdonald formulated his conjecture, although many different proofs have since been found [5,6,7,15,16,19,28]. As our combinatorial formula is manifestly a polynomial, we get a new proof of integrality. (iii) The celebrated formula of Lascoux and Schützenberger [22] for the expansion of Hall-Littlewood polynomials in terms of Schur functions is a corollary to our formula. In our setting, the charge, an intricate combinatorial statistic appearing in the Lascoux-Schützenberger formula, emerges naturally from simpler concepts.
(iv) The combinatorial formula of Knop and Sahi [17] for the Jack polynomials is a corollary to our formula. In fact, our formula yields a lift of the Knop-Sahi formula from Jack polynomials J (α) µ (x) to integral form Macdonald polynomials J µ (x; q, t). (The Jack polynomial is the specialization J (α) µ (x) = lim t→1 J µ (x; t α , t)/(1 − t) |µ| .) (v) Our formula can be interpreted as expressingH µ (x; q, t) in terms of LLT polynomials, the symmetric functions involving one parameter q introduced by Lascoux, Leclerc and Thibon [20]. The contact between Macdonald and LLT polynomials first seen in our earlier work with Remmel and Ulyanov [9] is thereby made stronger. We remark that the conjecture formulated in [9] led the first author to the formula established in this paper.
(vi) When the diagram of the partition µ has two columns, we obtain a new combinatorial formula for the coefficientsK λµ (q, t) in the expansion ofH µ (x; q, t) in terms of Schur polynomials s λ (x). It appears to be different from other combinatorial formulas that are known in the two-column case [4,18,32].
(vii) We hope that our formula may eventually lead to a combinatorial formula forK λµ (q, t) for general µ, and so to a combinatorial proof of the positivity theorem from [11] that K λµ (q, t) is a polynomial in q and t with non-negative coefficients. As things stand, our formula does not yet solve this problem, because it expressesH µ (x; q, t) in terms of monomials, rather than Schur polynomials. Our formula does, however, reduce the problem to a special case of the conjecture in [20] that LLT polynomials have positive expansions in terms of Schur polynomials. That conjecture is known to hold for LLT polynomials indexed by tuples of partition diagrams [9,24]. The case required for Macdonald positivity is that of a tuple of ribbon skew diagrams (see §3).
If A is a polynomial or formal series, p k [A] denotes the result of substituting a k for each indeterminate a appearing in A (including q and t). For arbitrary f ∈ Λ, the plethystic substitution f [A] is the result of expressing f as a polynomial in the power-sums p k and substituting p k [A] for p k in f . By convention, we set X = x 1 + x 2 + · · · , Y = y 1 + y 2 + · · · .
is the image of f under the algebra homomorphism mapping p k (x) to (1 − q k )p k (x). See, e.g., [10, §2] for a fuller account.
The Macdonald polynomialsH µ [Z; q, t] are the basis of Λ defined and characterized by the following triangularity and normalization axioms (see [10,Prop. 2.6] or [12, §6.1] for their equivalence with Macdonald's triangularity and orthogonality axioms).
for suitable coefficients a λµ , b λµ ∈ Q(q, t). It is easy to see, as in [10,12], that symmetric functions satisfying these axioms are unique if they exist. Their existence is equivalent to Macdonald's existence theorem in [25] and, as noted above, is also a corollary to the proof of our main theorem. The main result of this paper (Theorem 2.2) is an identityH µ (x; q, t) = C µ (x; q, t), where the right-hand side is a purely combinatorial expression (Definition 2.1) given as the sum, over all Z + -valued functions σ on the diagram of µ, of a monomial x σ = u x σ(u) multiplied by a suitable weight q inv(σ) t maj(σ) . The combinatorial statistics inv(σ) and maj(σ) are defined in §2.
Theorem 2.2 is proven in §5. The proof is a direct verification that the combinatorial expression C µ (x; q, t) satisfies the defining axioms (4) forH µ (x; q, t). The normalization axiom (N) turns out to be trivial. Each of the two triangularity axioms (T1-2) is proven with the aid of a suitable sign-reversing involution.
In order to interpret (T1-2) for C µ (x; q, t) combinatorially, we must first show that C µ (x; q, t) is a symmetric function. This crucial result was announced by Haglund in [8]. We give its proof in §3, using the theory of LLT polynomials. In the process, we obtain the LLT expansion of C µ (x; q, t), and hence ofH µ (x; q, t), mentioned above under (v). This given, we can apply a standard technique of superization using quasisymmetric function expansions; this is explained in §4.
Finally, in view of the important consequences of our main theorem on the one hand, and the essential simplicity of its proof on the other, it was our desire to keep the reasoning in this paper self-contained, elementary and combinatorial. In fact, the only exception to these desiderata occurs in our reliance on the theory of LLT polynomials to establish the symmetry of C µ (x; q, t). Even this exception is removable, however, as we show in an appendix ( §10) where we provide a new, elementary proof of the symmetry theorem for LLT polynomials.

The formula
Let µ = (µ 1 ≥ µ 2 ≥ · · · ≥ µ l ) be a partition of n = µ 1 + · · · + µ l , and let be its Young (or Ferrers) diagram, whose elements are called cells. We draw diagrams in the first quadrant, French style, as For simplicity, we henceforth write µ instead of dg(µ) when it will not cause confusion. A filling is a function σ : µ → Z + , which we picture as assigning integer entries to the cells of µ. We define a monomial of degree n in the variables x = x 1 , x 2 , . . .. Haglund's formula gives the Macdonald polynomial as the sum of q inv(σ) t maj(σ) x σ over all fillings σ : µ → Z + , where inv(σ) and maj(σ) are simple combinatorial statistics, which we define next. A descent of σ is a pair of entries σ(u) > σ(v), where the cell u is immediately above v, that is, v = (i, j), u = (i + 1, j). Define The example below has two descents, as shown. Two cells u, v ∈ µ are said to attack each other if either (i) they are in the same row: u = (i, j), v = (i, k); or (ii) they are in consecutive rows, with the cell in the upper row strictly to the right of the one in the lower row: u = (i + 1, k), v = (i, j), where j < k.
The figure below shows the two types of pairs of attacking cells.
The reading order is the total ordering on the cells of µ given by reading them row by row, top to bottom, and left to right within each row. More formally, (i, j) < (i ′ , j ′ ) in the reading order if (−i, j) is lexicographically less than (−i ′ , j ′ ). An inversion of σ is a pair of entries σ(u) > σ(v), where u and v attack each other, and u precedes v in the reading order. Our example (9) has 7 inversions: four in the bottom row and one in the top row, and two formed by the entry 8 in the second row attacking the two 4's in the bottom row. Define (11) Inv Finally, the arm of a cell u ∈ µ is the number of cells strictly to the right of u in the same row; its leg is the number of cells strictly above u in the same column, as illustrated below.
Haglund's formula is as follows.
In [8] it was observed that the statistic inv(σ) defined in (13) is always non-negative. We recall the explanation, which we will need later. Three cells u, v, w ∈ µ are said to form a triple if they are situated as shown below, namely, v is directly below u, and w is in the same row as u, to its right. Define for x, y ∈ Z + (16) Let σ be a filling and let x, y, z be the entries of σ in the cells of a triple (u, v, w): Then I(x, y) = 1 if and only if u ∈ Des(σ), and I(x, z)+I(z, y) is the contribution to | Inv(σ)| from the two attacking pairs {u, w}, {v, w}. Note that every attacking pair either belongs to a unique triple or consists of two cells in the bottom row. The number of triples involving u as their upper left cell is arm(u). Therefore where J is the number of inversions in the bottom row, the sum is over triples (u, v, w) in µ, and we denote x = σ(u), y = σ(v), z = σ(w). The transitive law for < implies that I(x, z) + I(z, y) − I(x, y) ∈ {0, 1}. Hence inv(σ) is non-negative, equal to J plus the number of inversion triples in σ, defined as triples for which I(x, z) + I(z, y) − I(x, y) = 1.

LLT expansion and symmetry
Theorem 3.1. The polynomial C µ (x; q, t) is symmetric in the variables x.
We will prove Theorem 3.1 by expanding C µ (x; q, t) in terms of the remarkable symmetric functions defined by Lascoux, Leclerc and Thibon [20] and commonly known as LLT polynomials. We use here a variant definition of LLT polynomials introduced in [9].
A skew diagram is a subset of Z + × Z + of the form λ \ µ, where λ and µ are partition diagrams such that µ ⊆ λ. The content of a cell u = (i, j) in a skew diagram ν is the integer c(u) = i − j. So that c(u) has a definite meaning, we do not follow the common practice of identifying skew diagrams that are translates of each other. As usual, a semistandard Young tableau of shape ν is a function T : ν → Z + which is weakly increasing on each row of ν and strictly increasing on each column. We denote the set of them by SSYT(ν). Given T ∈ SSYT(ν), define its monomial (19) x T = u∈ν x T (u) .
To relate formula (14) to the polynomials G ν (x; q), we focus on the terms in (14) corresponding to fillings with a given descent set. For each subset D ⊆ {(i, j) ∈ µ : i > 1}, define Then, clearly, where a(D) = u∈D arm(u) and maj(D) = u∈D (leg(u) + 1). A ribbon is a connected skew shape containing no 2 × 2 block of cells, as shown: (24) .
We only consider ribbons in fixed position such that the lower-right cell has content 1. Then the contents of all the cells are consecutive integers 1, 2, . . . , m. Define the descent set of a ribbon ν be the set of contents c(u) of those cells u = (i, j) ∈ ν such that the cell v = (i−1, j) directly below u also belongs to ν. In our example, , Des(ν) = {3, 6, 7}.
Clearly, we have a one-to-one correspondence between ribbons of size m and descent sets D ⊆ {2, . . . , m}.
To a partition µ and a subset D ⊆ {(i, j) ∈ µ : i > 1}, we associate a tuple of ribbons (26) ν(µ, D) = (ν (1) , . . . , ν (k) ), where k = µ 1 is the number of columns of µ, and ν (j) has size µ ′ j , cell contents {1, 2, . . . , µ ′ j }, and descent set Des(ν (j) ) = {i : (i, j) ∈ D}. Proposition 3.4. We have Proof. Let ν be the disjoint union of the ribbons ν (j) . Then we can identify semistandard tableaux of shape ν with suitable functions T : ν → Z + . Let θ : ν → µ be the bijection mapping the cell u ∈ ν (j) with content c(u) = i to the cell (i, j) ∈ µ. Then θ maps ν (j) onto the j-th column of µ, and for any filling σ : µ → Z + , we see that T = σ • θ is a semistandard tableau if and only if Des(σ) = D. Comparing the definition of inversions for a filling σ of µ with the definition of inversions for a semistandard tableau T ∈ SSYT(ν), we also see that | Inv(σ)| = inv(T ). This implies (27). Theorem 3.1 follows immediately from Theorem 3.3 and Proposition 3.4. The symmetry theorem for LLT polynomials, Theorem 3.3, is a crucial ingredient in the proof of our main result. Its original proof in [20,24] relies on a construction of Kashiwara, Miwa and Stern [14] in the representation theory of affine Hecke algebras. Apart from Theorem 3.3, all the results in this paper are deduced by elementary combinatorial means. To remove this one exception, we present in §10 a new, elementary proof of Theorem 3.3.

Quasisymmetric function expansion and superization
Given a non-negative integer n and a subset D ⊆ {1, . . . , n − 1}, Gessel's quasisymmetric function Q n,D (x) of degree n in variables x = x 1 , x 2 , . . . is defined by the formula where the indices a i belong to Z + . More generally, consider a "super" alphabet of positive letters i and negative letters i. We will use two different orderings of A: Fix now either of these, or any total ordering of A. The "super" quasisymmetric functioñ Q n,D (x, y) in variables x = x 1 , x 2 , . . . and y = y 1 , y 2 , . . . is defined by where the indices a i belong to A, and we set z i = x i for i positive, z i = y i for i negative.
considered as a symmetric function of the y variables only).

Proposition 4.2 ([9]
). Let f (x) be a symmetric function homogeneous of degree n, written in terms of quasisymmetric functions as Then its superization is given by We remark that the Proposition is well-known and that the proof outlined in [9] works equally well for any chosen ordering of the alphabet A.
Next we give the quasisymmetric function expansion of the polynomial C µ (x; q, t) and its superizationC µ (x, y; q, t). Given a super alphabet A, a super filling of µ is a function σ : µ → A. We adapt the definitions of Inv(σ) and Des(σ) to super fillings as follows. Extend the notation I(x, y) in (16) to x, y ∈ A by setting For cells u directly above v in µ, we say that σ(u) and σ(v) form a descent if I(σ(u), σ(v)) = 1, and as before, we take Des(σ) to be the set of cells u occurring as the upper cell in a descent. An inversion is a pair of entries σ(u), σ(v) such that I(σ(u), σ(v)) = 1, the cells u and v attack each other, and u precedes v in the reading order. As before, Inv(σ) is the set of positions forming inversions in σ. The statistics inv(σ) and maj(σ) are defined in terms of Inv(σ) and Des(σ) by (13), as for ordinary fillings. The definition of inversion triples and the demonstration that inv(σ) is non-negative go through verbatim with the extended definition of I(x, y). Note that an ordinary filling is the special case of a super filling with only positive entries. Define a filling σ to be standard if it is a bijection σ : µ ∼ = {1, . . . , n}. Given a super filling σ, its standardization is the unique standard filling ξ such that σ • ξ −1 is weakly increasing, and for each x ∈ A, the restriction of ξ to σ −1 ({x}) is increasing with respect to the reading order if x is positive, decreasing if x is negative. An example, using the ordering It is immediate from the definitions that Inv(σ) = Inv(ξ), Des(σ) = Des(ξ), inv(σ) = inv(ξ), and maj(σ) = maj(ξ). Define the reading word of a filling to be the sequence of its entries listed in the reading order. Then the reading word of a standard filling ξ is a permutation of {1, . . . , n}, where n = |µ|. Let D(ξ) ⊆ {1, . . . , n − 1} be the descent set of the inverse permutation, that is, i ∈ D(ξ) if ξ −1 (i + 1) precedes ξ −1 (i) in the reading order. For the example in (35), we have D(ξ) = {1, 2, 4, 6, 7}. If ξ is the standardization of σ, the weakly increasing function a = σ • ξ −1 : {1, . . . , n} → A also satisfies the conditions: a(i) = a(i + 1) ∈ Z + implies i ∈ D(ξ), and a(i) = a(i + 1) ∈ Z − implies i ∈ D(ξ). Conversely, given ξ and a satisfying these conditions, σ = a • ξ is a super filling whose standardization is ξ. These observations together with Theorem 3.1 and Proposition 4.2 yield the following formulas. Proposition 4.3. With n = |µ|, the polynomial C µ (x; q, t) has the quasisymmetric function expansion given by the sum over standard fillings .
This last is equal to the generating function for super fillings

Proof of the formula
This section is devoted to the proof of Theorem 2.2. We will prove that the combinatorial expression C µ (x; q, t) in Definition 2.1 satisfies the defining conditions (T1-2) and (N) for H µ (x; q, t) displayed in (4). We will do this by introducing a sign-reversing involution on super fillings to prove each of (T1-2).
Before proceeding further, we rewrite the conditions (T1-2) in a more convenient form. Recall that for any plethystic alphabet Y , and any symmetric function f homogeneous of . Also recall that ωs λ (x) = s λ ′ (x), and that transpose reverses the partial ordering on partitions: λ ≤ ρ ⇔ ρ ′ ≤ λ ′ . Finally, recall that the Schur and monomial bases are mutually lower triangular with respect to this ordering, i.e. s λ ∈ Z{m ρ : ρ ≤ λ} and m ρ ∈ Z{s λ : λ ≤ ρ}. Using these facts, we see that (T1-2) are equivalent to for suitable coefficients c ρµ , d ρµ . Now consider condition (N). Since {h µ } and {m µ } are dual bases relative to the Hall scalar product, and since s (n) = h n , (N) is equivalent to the requirement that the coefficient of x n 1 inH µ (x; q, t) is equal to 1. It is immediate from the definition that C µ (x; q, t) satisfies this condition, since the filling σ(u) = 1 for all u has maj(σ) = inv(σ) = 0.

5.1.
Proof that C µ (x; q, t) satisfies (A1). We use the ordering < 1 on A. We shall construct a sign-reversing, weight-preserving involution Ψ on super fillings σ : µ → A, which cancels out all terms in (40) If there is no pair of attacking cells u, v such that |σ(u)| = |σ(v)|, define Ψσ = σ. Otherwise, let a be the smallest integer that occurs as |σ(u)| = |σ(v)| for some attacking pair. Fix v to be the last cell in the reading order that is part of an attacking pair with |σ(u)| = |σ(v)| = a, and fix u to be the last cell in the reading order that attacks v and has |σ(u)| = a. Now define Ψσ(w) = σw for all w = u, and Ψσ(u) = σ(u), i.e., applying Ψ flips the sign of the entry in cell u. Clearly, ΨΨσ = σ, since a, u and v only depend on |σ|.
Note that the indicator I(x, y) in (34), when defined with the respect to the ordering < 1 , has the property that Lemma 5.1. We have To prove (43), we need to show that Ψ preserves the weight q p(σ)+inv(σ) t maj(σ) . Take a, u, v as in the definition of Ψ. Interchanging σ and Ψσ if necessary, we can assume that σ(u) is positive, i.e., that σ(u) = a, Ψσ(u) = a. We first show that Des(Ψσ) = Des(σ), which implies maj(Ψσ) = maj(σ). For this, consider the entries (if any) directly above and below cell u in σ and in Ψσ: Either x or y may be missing, if u is at the top or bottom of a column. The cell w below u, if present, follows v in the reading order and attacks v. By definition, v is the last cell in the reading order that has |σ(v)| = a and attacks another cell with the same property.
Hence |y| = a. In the ordering < 1 , this implies I(a, y) = I(a, y), so u ∈ Des(Ψσ) if and only if u ∈ Des(σ). If the cell t directly above u is present, then (42) shows that t ∈ Des(Ψσ) if and only if t ∈ Des(σ). Hence Des(Ψσ) = Des(σ), as claimed.
By assumption, p(Ψσ) = p(σ) − 1, so it remains to prove that inv(Ψσ) = inv(σ) + 1. We already have Des(Ψσ) = Des(σ), so we are to prove that | Inv(Ψσ)| = | Inv(σ)| + 1. Now, {u, v} belongs to Inv(Ψσ) but not to Inv(σ), since |σ(v)| = a, and for |y| = a, we have I(a, y) = 1, I(a, y) = 0. We claim that Inv(Ψσ) and Inv(σ) are otherwise identical. Clearly, the only other inversions that might differ are of the form {u, w}, where u attacks w. By (42), we can assume further that w follows u in the reading order. Moreover, we must have |w| = a. But then w precedes v in the reading order, by the definition of v. This contradicts the definition of u. The lemma is proved.
The fixed points of Ψ are non-attacking fillings σ : µ → A, characterized by the property that if u, v ∈ µ attack each other, then |σ(u)| = |σ(v)|. In particular, this implies that for all x ∈ Z + , there is at most one entry of σ with absolute value x in each row of µ. Suppose ρ is a partition and x |σ| = x ρ = x ρ 1 1 x ρ 2 2 · · · x ρ l l for some non-attacking filling σ. Then ρ 1 + · · · + ρ j is the total number of entries in σ with absolute value at most j. By the preceding observation, this cannot exceed i min(µ i , j) = µ ′ 1 + · · · + µ ′ j . Hence ρ ≤ µ ′ , proving that C µ (x; q, t) satisfies (A1).
If |σ(u)| ≥ i for all cells u = (i, j) ∈ µ, define Φσ = σ. Otherwise, let a be the smallest integer which occurs as |σ(u)| < i for some u = (i, j). Let u be the first cell in the reading order with |σ(u)| = a; note that the row coordinate i is maximal for this cell, so a < i. Define Φσ(w) = σ(w) for all w = u, and Φσ(u) = σ(u), so applying Φ flips the sign of the entry in cell u. Clearly, ΦΦσ = σ, since a and u depend only on |σ|.
Proof. As in the proof of Lemma 5.1, Φ is sign-reversing and preserves x |σ| . Take a, u as in the definition of Φ. We may assume that σ(u) = a, Φσ(u) = a. Then we are to prove that inv(Φσ) = inv(σ) and maj(Φσ) = maj(σ) + 1. Note that by construction, u is in row i with i > a, so u is not in the bottom row of µ.
For maj(Φσ), consider the entries directly above and below cell u: Here x may be missing, but y is always present. Moreover, |y| ≥ a, since |y| < a would imply |y| < i − 1, and as y is in row i − 1, this would contradict the choice of a. In the ordering < 2 , for |y| ≥ a, we have I(a, y) = 0, I(a, y) = 1. Hence u ∈ Des(Φσ), u ∈ Des(σ).
Recall from the discussion at the end of §2 that inv(σ) is the number of inversions in row 1 plus the number of inversion triples in σ. Since σ and Φσ are identical in row 1, they have the same inversions there. To complete the proof, we verify that σ and Φσ have the same inversion triples. A triple that might differ must include the cell u. There are three cases.
Case I: u is the bottom cell in the triple, so we have Then |x|, |y| = a, by the choice of u, and |x|, |y| < a, by the choice of a. Hence |x|, |y| > a and a < 2 x, y < 2 a. In σ we have I(x, a) = I(y, a) = 1, while in Φσ we have I(x, a) = I(y, a) = 0. In both σ and Φσ, this triple is an inversion triple if and only if I(x, y) = 1. Case II: u is the upper right cell in the triple, so we have The choice of a and u implies |x| > a and |y| ≥ a, so a < 2 x < 2 a and a ≤ 2 y ≤ 2 a. In σ, we have I( We deduce that |x|, |y| ≥ a, so a ≤ 2 x, y ≤ 2 a. In σ, we have I(a, x) = I(a, y) = 0, while in Φσ, we have I(a, x) = I(a, y) = 1. In both σ and Φσ, this is an inversion triple if and only if I(x, y) = 1.

Macdonald specialization
In this and the next two sections we discuss some previously known results from the theory of Macdonald and Jack polynomials that can be deduced directly from Theorem 2.2. Our first example is the following proposition, equivalent to an identity of Macdonald [26,Ch. VI (8.8)].
Proof. From formula (38) we see that the coefficient in question is the sum of q inv(σ) t maj(σ) over super fillings σ with n−d entries equal to 1 and d entries equal to 1. Use an ordering in which 1 < 1. Then u ∈ Des(σ) if and only if σ(u) = 1 and u is not in row 1. Furthermore, each such u forms an inversion with every cell to its right in the same row, and with every cell to its left in the row below. Subtracting arm(u), the contribution to inv(σ) from u = (i, j) ∈ Des(σ) is j − 1. The contribution to maj(σ) from u is leg(u) + 1.
For u in row 1 with σ(u) = 1 we get an inversion between u and every cell to its right. These observations show that if for u = (i, j), we define then q inv(σ) t maj(σ) = σ(u)=1 L(u). Summing over fillings with n − d 1's and d 1's, the result follows, once we verify that Consider the figure below, in which the entries q j−1 t i−1 in the first diagram sum to B µ , and the entries in the second diagram are L(u). In this example and in general, row 1 in the second diagram is the reverse of row 1 in the first diagram, and except for row 1, each column in the second diagram is the reverse of the corresponding column in the first diagram. This proves (52).

Cocharge specialization
Next we show that the celebrated charge formula of Lascoux and Schützenberger [22], which expresses the Hall-Littlewood polynomials in terms of Schur functions, arises naturally as a corollary to Theorem 2.2.
where cc(T ) is the cocharge of T . The sum is over semistandard tableaux T of shape λ and content µ, i.e., such that the multiset of entries in T is {1 µ 1 , 2 µ 2 , . . . , l µ l }.
Before proving the proposition, let us recall the definition of cocharge. Let µ be a partition of n, and let w = w 1 · · · w n be a word whose multiset of letters is {1 µ 1 , 2 µ 2 , . . . , l µ l }. Such a word w is said to have partition content. One defines cocharge in terms of words, then extends the definition to tableaux T with partition content by setting cc(T ) = cc(w), where w is the reading word of T (the sequence of its entries listed in the reading order).
In the general case, we first extract a subword y of w as follows. Let k 1 = max{k : w k = 1} be the position of the rightmost 1 in w, and define k 2 , . . . , k l inductively by k i = max{k < k i−1 : w k = i} if this set is non-empty, or k i = max{k : w k = i}, otherwise. In less formal terms, one can think of scanning the word from right to left, returning to the right when necessary, seeking entries w k 1 = 1, w k 2 = 2, . . . , w k l = l in succession. Let S = {k 1 , . . . , k l }, let y be the subword of w indexed by S, and let z be the subword of w indexed by the complement of S. Then y is a permutation of {1, . . . , l}, z again has partition content, and the cocharge is defined inductively as cc(w) = cc(y) + cc(z).
Proof of Proposition 7.1. Since C µ (x; 0, t) enumerates fillings with inv(σ) = 0, we begin by describing their structure. Let l be the length of µ and for each i = 1, . . . , l, fix a multiset M i of µ i positive integers. Consider those fillings σ in which M i is the multiset of entries in row i. By a lemma in [8], there is a unique such σ with inv(σ) = 0. We can also see directly how to uniquely construct the required σ, by observing that inv(σ) = 0 if and only if (i) σ is non-decreasing in row 1; and (ii) for every cell u not in row 1, if v is the cell directly below u, and S is the set consisting of u and the cells to its right in the same row, then σ(u) ≤ σ(v) implies that x ≤ σ(v) for all x ∈ σ(S), and σ(u) = min σ(S), while σ(u) > σ(v) implies that σ(u) = min{x ∈ σ(S) : x > σ(v)}. Hence the entries of σ in row 1 must be the elements of M 1 in non-decreasing order. Once rows 1 through i − 1 have been constructed, the entries σ(u) in row i are determined one by one, from left to right, as follows. Let v be the cell directly below u. If M i contains an unused element x > σ(v), then σ(u) is the smallest such x; otherwise σ(u) is the smallest .
We claim that if inv(σ) = 0, then maj(σ) = cc(cw(σ)). To see this, consider the symbols i k 1 = 1, . . . , i k l = l in cw(σ) corresponding to the cells u k 1 = (1, 1), . . . , u k l = (l, 1) in the first column of µ. The fact that σ ((1, 1)) is the smallest entry in row 1 implies that i k 1 is the rightmost 1 in cw(σ). For i > 1, σ((i, 1)) is the smallest entry greater than σ((i − 1, 1)) in row i, if one exists; otherwise σ((i, 1)) is the smallest entry in row i entirely. This implies that i k i is the rightmost i to the left of i k i−1 in cw(σ), if one exists; otherwise i k i is the rightmost i entirely. It follows that the subword y in the definition of cc(cw(σ)) consists of i k 1 through i k l . Moreover, it is clear that the descents in the first column of σ match the descent set of the permutation y −1 , and therefore (57) cc(y) = u=(i,1)∈Des(σ) (leg(u) + 1).
The complementary subword z of cw(σ) is just cw(σ 1 ), where σ 1 is the restriction of σ to the diagram obtained by deleting the first column of u. We again have inv(σ 1 ) = 0, so the claim follows by induction. It is known (and easy to prove using the Knuth relations, see [23], [27, Ex. 1.7.6]) that cc(w) is an invariant of the plactic monoid, i.e., if P (w) denotes the RSK insertion tableau of w, then cc(w) = cc(P (w)) for every word w with partition content. Let M(σ) be the multiset of pairs (σ(u), i), where u = (i, j) ∈ µ. To give M(σ) it is equivalent to give the multisets M i of entries in each row. For µ fixed, σ → M(σ) is therefore a bijection from fillings with inv(σ) = 0 to multisubsets of Z + × Z + such that the projection of M(σ) on the second index is {1 µ 1 , . . . , l µ l }. Applying RSK to M(σ), using the reverse ordering of Z + on the first index, yields a pair (P (σ), Q(σ)) of semistandard tableau of the same shape, say λ. The use of the reverse ordering on the first index means that when M(σ) is written in lexicographically non-decreasing order, the second indices form the cocharge word cw(σ). Hence P (σ) = P (cw(σ)). By construction, x σ = x Q(σ) . Since σ → (P (σ), Q(σ)) is a bijection from fillings σ of µ satisfying inv(σ) = 0 to pairs (P, Q) of semistandard tableaux of the same shape, such that P has content µ, we deduce that which is the same as (54).
Remark. Besides being somewhat easier than the original proof outlined in [22,23] and completed in [1] (see also [2]), our proof of Proposition 7.1 has the virtue that the rather intricate definition of cocharge emerges naturally from simpler concepts. Namely, cc(w) is just a way of expressing maj(σ) for fillings σ such that inv(σ) = 0 and cw(σ) = w.

Jack specialization
In this section we use Theorem 2.2 and Lemma 5.1 to obtain a new formula for the monomial expansion of Macdonald's integral form symmetric functions J µ (x; q, t), defined in [26,Ch. VI.8]. As a corollary we recover the monomial expansion of Knop and Sahi for Jack symmetric functions.
Recall from the end of §5.1 that the fixed fillings Ψσ = σ in (43) are the non-attacking super fillings, in which |σ(u)| = |σ(v)| for cells u, v that attack each other. As in (43), p(σ) and m(σ) denote the number of positive and negative entries σ. We use the ordering < 1 on the super alphabet A.
Fix n = |µ|, and define (using conflicting but standard notation) The relationship between J µ (x; q, t) andH µ (x; q, t) is given by using the identityH µ (x; q, t) =H µ ′ (x; t, q), which is equivalent to [26,Ch. VI,(8.6)]. Originally, (60) was the definition ofH µ (x; q, t). From our present point of view, (60) follows by reversing the derivation of the axiomatic characterization (4) from the original definition. Theorem 2.2 and Lemma 5.1 yield where the sum is over non-attacking super fillings of µ ′ . For any cell u = (i, j) not in the first row of µ, denote the cell v = (i−1, j) directly below u by d(u). Define the absolute inversion number ainv(σ) to be the number of inversion triples (u, v, w) in which the numbers |σ(u)|, |σ(v)|, |σ(w)| are all distinct, plus the number of inversions in row 1 (necessarily with |σ(u)| = |σ(v)|, by the non-attacking property). With the ordering < 1 , we see that ainv(σ) = ainv(|σ|). Similarly, define the absolute major index to be the contribution to maj(σ) involving descents between entries which differ in absolute value. In a positive filling, these are all the descents, so amaj(σ) = amaj(|σ|) = maj(|σ|). Now define the signed inversion number and signed major index to make up the difference: Given a non-attacking positive filling τ of µ ′ , we now derive a formula for the part of the sum in (63) corresponding to those σ with |σ| = τ . Note that every such σ is automatically non-attacking. We have (66) t n(µ)+n Consider a triple (u, v, w) in µ ′ , with v = d(u). For this triple to contribute to sinv(σ), we must have at least two of the numbers τ (u), τ (v), τ (w) equal to each other. Since τ is non-attacking, this forces τ (u) = τ (v) = τ (w), and one checks that this is an inversion triple if and only if σ(u) ∈ Z + . Also, a cell u not in row 1 belongs to Des(σ) but not to Des(τ ), and so contributes to smaj(σ), if and only if τ (u) = τ (d(u)) and σ(u) ∈ Z − . It follows that for each cell u ∈ µ ′ with τ (u) = τ (d(u)), to calculate its contribution to the sum on the right-hand side of (66), we can weight a negative entry in u by −q leg(u)+1 and a positive entry by t − arm(u)−1 . For each cell u such that τ (u) = τ (d(u)), including u in the bottom row, we weight a negative entry by −1 and a positive entry by t −1 . Thus (66) is equal to Using (67) and the fact that for positive, non-attacking τ , we obtain the following.
Proposition 8.1. For any partition µ, where the cells u in the bottom row of µ ′ are included in the last factor.
By setting q = t α in Proposition 8.1 and letting t → 1, we recover the following formula of Knop and Sahi [17].

Two-column case
In the case where µ has only two columns, we can derive from Theorem 2.2 a new combinatorial rule for the coefficientsK λµ (q, t) in the expansion ofH µ (x; q, t) in terms of Schur functions s λ (x). Definition 9.1. A word w ∈ Z n + is Yamanouchi if each of its final segments w k w k+1 · · · w n has partition content (as defined in §7 after Proposition 7.1). Denote by Yam(λ) the set of Yamanouchi words with content {1 λ 1 , . . . , l λ l }.
Readers accustomed to English partition notation may be more familiar with the term lattice permutation. A lattice permutation is the reverse of a Yamanouchi word. Proposition 9.2. When µ 1 ≤ 2, the coefficients in the Schur function expansioñ H µ (x; q, t) = λK λµ (q, t)s λ (x) are given by where w(σ) is the reading word of σ.
Using van Leeuwen's reformulation [31, Prop. 3.1.4] of Carré and Leclerc's Yamanouchi property for domino tableaux, it is possible to show that it corresponds via the equivalences in [9] to the property that a tableau T ∈ SSYT(ν) has Yamanouchi content reading word. Then one can deduce Proposition 9.2 from [31, Prop. 4.2.1 & Thm. 4.2.2]. However, it is complicated to trace this through in detail, besides which, the proofs of the results in [31] are also complicated. It is more convenient to prove Proposition 9.2 directly by using the relationship between crystals of type A and the RSK algorithm. We should remark that this is also van Leeuwen's approach (he calls the crystal operators "coplactic operations"), but it is simpler when we avoid using domino tableaux as an intermediate step.
We take as known the theory of the RSK algorithm and jeu-de-taquin, as presented for instance in [30, Ch. 7 & Appendix A1]. A homomorphism between crystals is a map φ : The set B = Z n + of words w = w 1 . . . w n comes with a standard crystal structure. The weight function is wt(w) = x w = i x w i . For each i, let y be the subword of w consisting of letters w k ∈ {i, i + 1}. For simplicity, take i = 1. In y, regard 2's as left parentheses and 1's as right parentheses. Let z be the subword of y that remains after repeatedly deleting all closed pairs of parentheses 21. Then z has the form 11 · · · 122 · · · 2. If z is all 1's, then E 1 w = 0. If z is all 2's, then F 1 w = 0. Otherwise, E 1 w is the result of changing the first 2 in z to a 1, and F 1 w is the result of changing the last 1 in z to a 2. The operators E i and F i are defined similarly. For example, 342233132124 → E 2 342223132124, the subword y being 32233322, and the first unmatched 3 being the second 3 in y.
The maximal elements in the crystal Z n + are precisely the Yamanouchi words. Note that the operator E i decreases the sum of the letters in w by 1. Hence every word can be reduced to a Yamanouchi word by applying a finite sequence of operators E i .
More general crystals associated with root systems have been defined by Kashiwara [13] in connection with crystal bases, but the combinatorial crystal structure for type A was known much earlier to Lascoux and Schützenberger [21]. The following lemmas are essentially due to them. Lemma 9.4. Let R(w) (the rectification of w) be the reading word of the RSK insertion tableau P (w). Then R : Z n + → Z n + is a crystal homomorphism. Moreover, the crystal operators E i , F i on Z n + preserve the RSK recording tableau Q(w). Proof. One checks easily that for any skew shape ν, the set of reading words w(T ) for T ∈ SSYT(ν) is closed under the crystal operators, and that these operators commute with jeu-de-taquin. Jeu-de-taquin transforms the totally disconnected tableau with reading word w to the RSK insertion tableau P (w) with reading word R(w). This implies that R is a crystal homomorphism. Moreover, when the jeu-de-taquin steps are performed in an order which simulates the RSK insertion algorithm as in [29], the sequence of intermediate shapes produced determines the recording tableau Q(w). Hence the crystal operators do not change Q(w).
Lemma 9.5. Among words with a given RSK recording tableau Q there is a unique Yamanouchi word w. The content of w is equal to the shape λ of Q.
Proof. Jeu-de-taquin preserves the Yamanouchi property, so this reduces to the facts that for each λ there is a unique tableau T ∈ SSYT(λ) whose reading word w(T ) is Yamanouchi, and that this w(T ) has content λ. Corollary 9.6. For each standard tableau Q of size n, the set of words w with RSK recording tableau equal to Q is a connected component of the crystal Z n + . Proof. Lemma 9.4 implies that the recording tableau Q is constant on connected components. Given two words w, w ′ with the same recording tableau Q, we can apply some sequence of operators E i to reduce them to Yamanouchi words v, v ′ . Then Lemma 9.5 shows that v = v ′ . Proposition 9.7. Let φ : B → A be a homomorphism of crystals, and assume A is connected. Then every preimage φ −1 ({a}) has the same cardinality, for all a ∈ A.
Proof. If b = E i a in A, the definitions imply that E i and F i are mutually inverse bijections between φ −1 ({a}) and φ −1 ({b}).
Corollary 9.8. Let B be a crystal, and let α : B → Q(q, t) be a function that is constant on connected components of B. Let φ : B → Z n + be a crystal homomorphism. Assume that B has finitely many elements of each weight, and set ch B = b∈B α(b) wt(b). Then ch B is a symmetric function, and the coefficient c λ (q, t) in the Schur function expansion ch B = λ c λ (q, t)s λ (x) is equal to Proof. We temporarily define c λ (q, t) by formula (73), and prove that ch B = λ c λ (q, t)s λ (x), with c λ (q, t) so defined. Let B (λ) be the set of elements b ∈ B such that R(φ(B)) has shape λ. Let V λ be the crystal consisting of reading words w(T ) for T ∈ SSYT(λ); it is a connected component of the crystal Z n + . Let T 0 ∈ SSYT(λ) be the unique tableau such that We have defined c λ (q, t) to be the sum of α(b) over all b in this set. Since α is constant on components of B (λ) , Proposition 9.7 implies that for every w ∈ V λ , the sum of α(b) over all b ∈ (R•φ) −1 ({w}) is equal to c λ (q, t). Now, s λ (x) = w∈V λ x w = w∈V λ wt(w), and therefore ch B (λ) = c λ (q, t)s λ (x). But B is the disjoint union of its subsets B (λ) , and summing over them all yields ch B = λ c λ (q, t)s λ (x).
Proof of Proposition 9.2. We will construct a crystal structure on the set Σ µ of all fillings σ : µ → Z + , with the following properties. First, the weight function is the obvious one, wt(σ) = x σ . Second, the map φ : Σ µ → Z n + defined by φ(σ) = R(w(σ)) is a crystal homomorphism, where w(σ) denotes the reading word of σ. Third, q inv(σ) t maj(σ) is constant on each component of Σ µ . Then Proposition 9.2 is a special case of Corollary 9.8.
For simplicity, we define the crystal operators E 1 , F 1 . The definition of E i , F i is the same with 1, 2 replaced by i, i + 1 in what follows. Fix the list u 1 , . . . , u n of all the cells of µ in reading order. Since µ has two columns, there is an index k 0 such that u k attacks u k+1 for all k 0 ≤ k < n, and these are the only attacking pairs. Call u k 0 , . . . , u n the attack zone.
If F 1 w(σ) = 0 (in Z n + ) we define F 1 σ = 0. Otherwise, let u k be the cell such that σ(u k ) is the 1 in w(σ) that would be changed to a 2 by applying the standard crystal operator F 1 . If k ≥ 2, and u k−2 , u k−1 , u k are in the attack zone, and σ(u k−2 )σ(u k−1 )σ(u k ) = 211, then w(σ) has the form y 211 z, and we define F 1 σ by w(F 1 σ) = y 221 z. Otherwise, let l ≥ k be the largest index such that l − k is even, u k , u k+1 , . . . , u l is contained in the attack zone if k = l, and σ(u k )σ(u k+1 ) · · · σ(u l ) = 1212 · · · 1. Then w(σ) has the form y 1212 · · · 1 z and we define F 1 σ by w(F 1 σ) = y 2121 · · · 2 z.
Obviously, E i , F i behave correctly with respect to weights. We must verify that E i σ = τ if and only if F i τ = σ. It suffices to consider i = 1. Suppose that E 1 σ = τ . We are in one of two cases. In the first case, the reading words are The first unmatched 2 in w(σ) is at the beginning of the indicated subsequence 221. It follows that the last unmatched 1 in w(τ ) is at the end of the indicated subsequence 211.
We are in the first case of the rule for F 1 τ , so F 1 τ = σ. In the second case of the rule for E 1 σ, the reading words are The first unmatched 2 in w(σ) is at the end of the indicated subsequence 2121 · · · 2. Therefore the last unmatched 1 in w(τ ) is at the beginning of indicated subsequence 1212 · · · 1. Moreover, y does not end with 21 in the attack zone, since the index j was minimal. Also, it cannot happen that the subsequence 1212 · · · 1 is in the attack zone and z begins with 21, also in the attack zone, since that would put us in the first case of the rule for E 1 σ. Hence we are in the second case of the rule for F 1 τ , and F 1 τ = σ.
The proof that F 1 τ = σ implies E 1 σ = τ is entirely similar and will be omitted. Next we show that the operators E i , F i preserve inv(σ) and maj(σ). In fact, we'll show that they preserve | Inv(σ)| and Des(σ). The only inversions and descents that might be affected involve entries in {i − 1, i, i + 1, i + 2}, so it suffices to consider i = 2. By the crystal axioms, it suffices to consider the operator E 2 . In the first case of the rule for E 2 σ, the relevant subsequence 332 of w(σ) occupies cells in µ forming one of the configurations (76) where x or y may be missing. If they are present, x = 3 and y = 2, because the first 3 in the subsequence 332 is the first unmatched 3 in w. Hence changing the middle 3 in 332 to a 2 does not change Des(σ), and it clearly does not change | Inv(σ)|.
In the second case of the rule, we have a subsequence 3232 · · · 3 of the type x y 3 2 3 2 3 z w or x y 3 2 3 2 3 z w .
For simplicity, we have illustrated the situation with a subsequence of length 5, although the actual picture might have more or fewer rows 3 2 or 2 3 . Again, some of x, y, z, w might be missing. If they are present, then x, y = 3 and z, w = 2. To see this, note that y = 3 or x = 3, y = 2 would contradict the fact that the bottom 3 is the first unmatched 3 in w(σ), while x = 3, y = 2 would contradict the minimality of the index j. Similarly, z = 2 or w = 2, z = 3 contradicts unmatchedness, while w = 2, z = 3 would put us in the first case of the rule for E 2 σ. Given that x, y = 3 and z, w = 2, it is easy to see that exchanging 2's with 3's in the subsequence 3232 · · · 3 leaves Des(σ) and | Inv(σ)| unchanged.
The last thing we need to prove is that φ(σ) = R(w(σ)) defines a crystal homomorphism. Since R is a crystal homomorphism, this follows if we show that R(w(E i σ)) = R(E i w(σ)) and R(w(F i σ)) = R(F i w(σ)). In other words, we must show that after applying our crystal operators to σ, we get a reading word which is jeu-de-taquin equivalent to the one we would have gotten by applying the standard crystal operators to w(σ). Consider the operator E 1 .
In the first case of the rule, our operator gives y 211 z, while the standard E 1 would give y 121 z. But 211 ≈ 121 is a Knuth relation, so this case is fine. In the second case of the rule, our operator gives y 1212 · · · 121 z, while the standard E 1 would give y 2121 · · · 211. In this case, the result follows from the fact that 1212 · · · 121 and 2121 · · · 211 have the same RSK insertion tableau, namely, the tableau with all 1's in row 1 and all 2's in row 2. The same argument applies to E i by taking i, i + 1 in place of 1, 2. The argument for F i is entirely similar.
Remark. Since the crystal operators preserve Des(σ), the proof shows that the analog of Proposition 9.2 holds for each of the functions F µ,D (x; q) in (22)-(23).

Appendix: a new proof of LLT symmetry
In this appendix we give a purely combinatorial proof of Theorem 3.3. Recall the notations from §3. We need to extend them to "super" analogs of the LLT polynomial G ν (x; q). Let A be a super alphabet, as in (29), and define a super tableau T on a skew shape ν to be a function T : ν → A, weakly increasing on each row and column, with the property that if i is positive then T −1 ({i}) is a horizontal strip (i.e., has no two cells in the same column) and if i is negative, then T −1 ({i}) is a vertical strip (no two cells in the same row). A super tableau with positive entries is just an ordinary semistandard tableau. Let SSYT ± (ν) denote the set of super tableaux, and for a tuple ν = (ν (1) , . . . , ν (k) ), define SSYT ± (ν) = SSYT ± (ν (1) ) × · · · × SSYT ± (ν (k) ).
For u ∈ ν (j) , define The fractional part of β determines j, hence β(u) = β(v) if and only if u and v lie on a common diagonal c(u) = c(v) in the same shape ν (j) . The content reading order is the unique total ordering on the cells of ν such that β is weakly increasing, and cells with β(u) = β(v) increase upward and to the right along diagonals. (Under the identification in the proof of Proposition 3.4 between fillings of µ and semistandard tableaux on tuples of ribbons, the content reading order corresponds to the reading order defined previously for fillings.) Given u preceding v in the content reading order, define entries T (u) and T (v) in a super tableau T ∈ SSYT ± (ν) to form an inversion if Let inv(T ) be the number of inversions in T and define where z i = x i for i positive, z i = y i for i negative, as in (31). For semistandard tableaux with positive letters, (78) is equivalent to our original definition of inversions in T , hencẽ G ν (x, 0; q) = G ν (x; q).
A semistandard tableau S is standard if it is a bijection S : ν → {1, . . . , n}, where n = |ν| = j |ν (j) |. Denote the set of standard tableau by SYT(ν). Note that every ν (j) is a horizontal strip if and only if the labelling of the cells of ν from 1 to n in increasing content reading order is a standard tableau. Similarly, every ν (j) is a vertical strip if and only the labelling of ν in decreasing content reading order is standard. It follows that every super tableau T ∈ SSYT ± (ν) has a unique standardization S ∈ SYT(ν) such that T • S −1 is weakly increasing, and for x ∈ A, the entries of S on T If S is the standardization of T , then a = T • S −1 : {1, . . . , n} → A is weakly increasing, and satisfies the additional conditions that a(i) = a(i + 1) ∈ Z + implies i ∈ D(S), and a(i) = a(i + 1) ∈ Z − implies i ∈ D(S). Conversely, if a : {1, . . . , n} → A satisfies these conditions, then T = a • S is a super tableau, and its standardization is S. Comparing the definitions (31) and (79), we see that Setting y = 0, we deduce as a special case that q inv(S) Q n,D(S) (x).
Lemma 10.1. Let ν ′ be obtained from ν by transposing each ν (j) and reversing the tuple.
We now prove Theorem 3.3 by means of a series of reductions. It suffices to prove that the LLT polynomial G ν (x; q) is symmetric in x i and x i+1 , for each i. Given a tableau T ∈ SSYT(ν), let ρ = (ρ (i) , . . . , ρ (k) ) = T −1 ({i, i + 1}) and S = T | ρ , so S is the part of T formed by entries i and i + 1. Let U = T | ν\ρ be the rest of T . Note that ρ is a tuple of skew shapes, and for ρ and U fixed, every semistandard tableau S ∈ SSYT(ρ) occurs for a unique T . Moreover, where i(ρ, U) is a constant independent of S. This holds because for entries x = U(u) ∈ {i, i + 1} and y = S(v) ∈ {i, i + 1}, the condition x > y is independent of y. Partitioning the defining sum in (21) into smaller sums for each (ρ, U), we reduce the symmetry problem to the case of shapes ρ and tableaux S ∈ SSYT(ρ) with entries in a two-element set {i, i + 1}.
We can now assume that each ν (j) has at most two cells in each column, and we can evaluate G ν (x; q) in just two variables x = x 1 , x 2 . Consider a column with two cells {u, v} in ν (j) , say with v above u; in every tableau T ∈ SSYT(ν), we must have T (u) = 1, T (v) = 2.
If T (w) = 1, then T (v) > T (w) is an inversion, but T (w) = T (u) is not. Alternatively, if T (w) = 2, then T (w) > T (u) is an inversion, but T (v) = T (w) is not. Hence the cells u, v, w make a net contribution of 1 to inv(T ). One checks similarly that if w does not satisfy (85), then the contribution to inv(T ) from u, v, w is zero, independent of T (w). Let now ρ be the shape that remains upon deleting all two-cell columns from ν, and let S = T | ρ . Note that each ρ (j) is a skew shape, and we get every S ∈ SSYT(ρ) as the restriction of a unique T . The preceding observations show that where h(ν) is a constant independent of S, and m is the number of two-cell columns in ν. This reduces the problem to the case where each ν (j) is a horizontal strip. Applying Lemma 10.1, we need only consider the case where each ν (j) is a vertical strip. Applying once more the same reductions that we used above for general ν, we reach the case that each ν (j) is a disconnected union of single cells. Then the numbers β(u) in (77) are distinct for all cells u ∈ ν, and every function T : ν → {1, 2} is a semistandard tableau. Thus we come down to the following lemma. Lemma 10.2. Let β 1 < β 2 < · · · < β n be arbitrary real numbers. For every word w = w 1 w 2 . . . w n with w i ∈ {1, 2}, define inv β (w) = |{(i < j) : w j > w i and β j − β i < 1}|. Then the polynomial x w i is symmetric in x 1 and x 2 .
We now compare inv α (w) and inv β (w) for an arbitrary word w. In positions i < j < n, w i and w j form an inversion with respect to α if and only if they form an inversion with respect to β. This also holds for j = n and i = n − r, since β n − β i < 1 if and only if i ≥ n − r, and α n − α i < 1 if and only if i ≥ n − r + 1. Hence (87) inv β (w) = inv α (w) + 1 if w n−r = 2, w n = 1 0 otherwise. Now, if w n−r = 2 and w n = 1, then w n−r and w n together form exactly one inversion with each w i for n − r < i < n, and no inversions with w i for i < n − r. This holds for inversions with respect to either α or β. Hence the contribution to G β (x; q) from terms indexed by such words w is q r x 1 x 2 G γ (x; q), where γ = (β 1 , . . . , , β n−r−1 , β n−r+1 , . . . , β n−1 ), while the contribution to G α (x; q) from the same words w is q r−1 x 1 x 2 G γ (x; q). The contributions to G α (x; q) and G β (x; q) from all other words are equal. Hence (88) G β (x; q) − G α (x; q) = (q r − q r−1 )x 1 x 2 G γ (x; q).
Since G γ (x; q) is symmetric by induction on n, and G α (x; q) is symmetric by induction on r, the lemma is proved, and the proof of Theorem 3.3 is complete.