# An injection from standard fillings to parking functions

Elizabeth Niese

Department of Mathematics, Marshall University, Huntington, WV 25755

**Abstract.** The Hilbert series of the Garsia-Haiman module can be written as a generating function of standard fillings of Ferrers diagrams. It is conjectured by Haglund and Loehr that the Hilbert series of the diagonal harmonics can be written as a generating function of parking functions. In this paper we present a weight-preserving injection from standard fillings to parking functions for certain cases.

**Résumé.** La série Hilbert du module Garsia-Haiman peut être écrite comme fonction génératrice de tableaux des diagrammes Ferrers. Haglund et Loehr conjecturent que la série Hilbert de l'harmonic diagonale peut être écrite comme fonction génératrice des fonctions parking. Dans cet essai nous présentons une injection des tableaux vers les fonctions parking pour certains cas.

**Keywords:** Macdonald polynomials, parking functions, diagonal harmonics

## 1 Introduction

Over the past twenty years, Macdonald polynomials have become a central object of study in the theory of symmetric functions. The classical Macdonald polynomials, {$P_\mu$}, where $\mu$ ranges over all partitions of $n$, provide a basis for the vector space of symmetric functions, $\Lambda_n$ [Mac88, Mac95]. In addition, the $P_\mu$ specialize to many of the other common bases of $\Lambda_n$ such as the elementary, monomial, and Schur polynomials [Mac88, Mac95]. In [Mac88], Macdonald also introduces the dual basis, $Q_\mu$, and the integral basis, $J_\mu$, which can both be computed from $P_\mu$ by multiplication by a suitable rational expression that depends on $\mu$.

The modified Macdonald polynomials, $\tilde{H}_\mu(X; q, t)$, are obtained algebraically from the integral basis $J_\mu$ by a suitable plethystic transformation [Mac88, Mac95]. The $\tilde{H}_\mu(X; q, t)$ have connections to the representation theory of the symmetric group. In fact, Haiman showed [Hai01] that $\tilde{H}_\mu(X; q, t)$ is the Frobenius series of the Garsia-Haiman module [GH93], $M_\mu \subset \mathbb{C}[x_1, \dots, x_n, y_1, \dots, y_n]$. We show the construction of $M_\mu$ for $\mu = (2, 2, 1)$. First, we label each cell of the Ferrers diagram of $\mu$ with the Cartesian coordinates of that cell, as shown in Fig. 1. We then use the labels as exponents for $x_iy_i$ and
<figure><img src="image_1.png" /><figcaption>Fig. 1: Labeled Ferrers diagram for $\mu = (2, 2, 1)$</figcaption></figure>

construct the determinant $\Delta_{\mu}$ in (1).

$$ \Delta_{\mu} = \begin{vmatrix} x_1^0 y_1^0 & x_2^0 y_2^0 & x_3^0 y_3^0 & x_4^0 y_4^0 & x_5^0 y_5^0 \\ x_1^1 y_1^0 & x_2^1 y_2^0 & x_3^1 y_3^0 & x_4^1 y_4^0 & x_5^1 y_5^0 \\ x_1^0 y_1^1 & x_2^0 y_2^1 & x_3^0 y_3^1 & x_4^0 y_4^1 & x_5^0 y_5^1 \\ x_1^1 y_1^1 & x_2^1 y_2^1 & x_3^1 y_3^1 & x_4^1 y_4^1 & x_5^1 y_5^1 \\ x_1^0 y_1^2 & x_2^0 y_2^2 & x_3^0 y_3^2 & x_4^0 y_4^2 & x_5^0 y_5^2 \end{vmatrix} \quad (1) $$

After calculating the determinant, $M_{\mu}$ is obtained by taking linear combinations of all possible partial derivatives of $\Delta_{\mu}$. This module can be written as a doubly graded module based on the degree of the $x$ and $y$ coordinates [GH93]. Thus

$$ M_{\mu} = \bigoplus_{a,b \ge 0} M_{\mu}^{(a,b)} \quad (2) $$

where each $f \in M_{\mu}^{(a,b)}$ is homogeneous of degree $a$ in the $x_i$ and homogeneous of degree $b$ in the $y_j$. Then the Hilbert series of $M_{\mu}$ is

$$ \text{Hilb}(M_{\mu}) = \sum_{a,b \ge 0} \dim(M_{\mu}^{(a,b)}) q^a t^b. \quad (3) $$

Haglund conjectured [Hag04] and Haglund, Haiman, and Loehr proved [HHL05a] a combinatorial definition for the Hilbert series of $M_{\mu}$ as a generating function of certain fillings of the Ferrers diagram of $\mu$, which we describe in §2.

For $\mu$ a partition of $n$, the Garsia-Haiman module, $M_{\mu}$, is a submodule of the module of diagonal harmonics, $DH_n$ [Hag08, Hai94]. The diagonal harmonics of order $n$ are defined as

$$ DH_n = \left\{ f \in \mathbb{C}[x_1, \dots, x_n, y_1, \dots, y_n] : \sum_{i=1}^{n} \frac{\partial^h}{\partial x_1^h} \frac{\partial^k}{\partial y_i^k} f = 0 \text{ for } 1 \le h + k \le n \right\}. \quad (4) $$

We can also write $DH_n$ as a doubly graded module by setting $DH_n^{(a,b)}$ to be the set of $f \in DH_n$ that are homogeneous of degree $a$ in the $x_i$ and homogeneous of degree $b$ in the $y_j$. Then

$$ DH_n = \bigoplus_{a,b \ge 0} DH_n^{(a,b)}. \quad (5) $$

The Hilbert series of $DH_n$ is

$$ \text{Hilb}(DH_n) = \sum_{a,b \ge 0} \dim(DH_n^{(a,b)}) q^a t^b. \quad (6) $$
Haglund and Loehr have conjectured [HL05] a combinatorial formula for (6) as a weighted sum over parking functions on $n$ cars, which is described in §3. Assuming Haglund and Loehr's conjecture holds, then, since $M_\mu$ is a submodule of $DH_n$, there exists a weight-preserving injection from standard fillings to parking functions. We want to find an explicit combinatorial definition of the injection to provide more evidence for the conjecture in [HL05]. Such a definition would also help us to better understand the relation between the algebraic structures and the combinatorial structures. In this paper we first review the necessary combinatorial definitions (§2,3) and then establish such an injection for certain cases (§4).

## 2 Haglund's combinatorial definition of Hilb($M_\mu$)

In this section we define the Hilbert series of the Garsia-Haiman module, $M_\mu$, using Haglund's combinatorial definition [Hag04, HHL05a]. Recall that a *partition* $\mu$ of the positive integer $n$ is a sequence $\mu = (\mu_1 \ge \mu_2 \ge \cdots \ge \mu_k)$ with $\mu_1 + \mu_2 + \cdots + \mu_k = n$. The *diagram* of $\mu$ is

$$ \mathrm{dg}(\mu) = \{(i, j) \in \mathbb{N}^{+} \times \mathbb{N}^{+} : 1 \le i \le k, 1 \le j \le \mu_i\}. $$

We visualize $\mathrm{dg}(\mu)$ by using a *Ferrers diagram*, a collection of left justified boxes (following the French convention) such that the bottom row has $\mu_1$ boxes, the next has $\mu_2$, etc. A *standard filling* of $\mu$ is a bijection $T : \mathrm{dg}(\mu) \to \{1, \dots, n\}$ which we visualize by placing $T(c)$ in cell $c$ of the Ferrers diagram of $\mu$ as in Fig. 2. Let $\mathcal{F}_\mu = \{\text{standard fillings of shape } \mu\}$. Given $T \in \mathcal{F}_\mu$, construct $\mu_1$ column words

$$ T = \begin{array}{c|ccc} 3 & 4 & 1 \\ 8 & 2 & 7 \\ 5 & 9 & 6 \end{array} $$

<caption>Fig. 2: $T$ is a standard filling of $\mu = (3, 3, 2, 1)$</caption>

by reading down each column individually. Thus, for $T$ in Fig. 2, the column words are 3485, 129, and 76. In a word $w = w_1w_2\cdots w_k$, a *descent* occurs when $w_i > w_{i+1}$. The *descent set* of $w$ is defined $\mathrm{Des}(w) = \{i : w_i > w_{i+1}\}$. The *major index* of $w$ is $\mathrm{maj}(w) = \sum_{i \in \mathrm{Des}(w)} i$. We now can define the $\mu$-major index of $T$ as

$$ \mathrm{maj}_{\mu}(T) = \sum_{w \text{ a column word of } T} \mathrm{maj}(w). $$

Thus, for the filling in Fig. 2,

$$ \begin{align*} \mathrm{maj}_{\mu}(T) &= \sum_{w \text{ a column word of } T} \mathrm{maj}(w) \\ &= \mathrm{maj}(3485) + \mathrm{maj}(129) + \mathrm{maj}(76) \\ &= 3 + 0 + 1 \\ &= 4. \end{align*} $$

A cell $(i, j)$ in the diagram of $\mu$ attacks cells in the set $\{(a, b) : a = i \text{ and } b > j\} \cup \{(a, b) : a = i - 1 \text{ and } b < j\}$. That is, $(i, j)$ attacks cells in the same row and to the right, or in the row below and to
<figure><img src="image_2.png" /><figcaption>Fig. 3: Cells attacked by c</figcaption></figure>

the left, as seen in Fig. 3. An attack inversion of $T$ occurs when cell $c$ attacks cell $d$ and $T(c) > T(d)$. We define

$$ \mathrm{Inv}(T) = \{(T(c), T(d)) : c \text{ attacks } d \text{ and } T(c) > T(d)\}. $$

Given a cell $c$, the arm of $c$, ARM($c$) is the set of cells in the diagram of $\mu$ in the same row and to the right of $c$. We define the $\mu$-inversions of $T$ to be

$$ \mathrm{inv}_{\mu}(T) = |\mathrm{Inv}(T)| - \sum_{c \in \mathrm{Des}(T)} |\mathrm{ARM}(c)|. $$

For $T$ in Fig. 2, $\mathrm{Inv}(T) = \{(9, 6), (8, 2), (8, 7), (7, 5), (4, 1)\}$ and $\sum_{c \in \mathrm{Des}(T)} |\mathrm{ARM}(c)| = 2$. Thus $\mathrm{inv}_{\mu}(T) = |\mathrm{Inv}(T)| - |\mathrm{ARM}(\mathrm{Des}(T))| = 5 - 2 = 3$.

**Definition 1 ([HHL05a, HHL05b])** The Hilbert series for the Garsia-Haiman module, $M_{\mu}$, is

$$ \mathrm{Hilb}(M_{\mu}) = \tilde{F}_{\mu}(q, t) = \sum_{T \in \mathcal{F}_{\mu}} q^{\mathrm{inv}_{\mu}(T)} t^{\mathrm{maj}_{\mu}(T)}. $$

## 3 Parking functions and $\mathrm{Hilb}(DH_n)$

A combinatorial formula for $\mathrm{Hilb}(DH_n)$, as a weighted sum of *parking functions*, is conjectured in [HL05]. A function $f: \{1, \dots, n\} \to \{1, \dots, n\}$ is a *parking function* of order $n$ if and only if

$$ |\{x : f(x) \le i\}| \ge i \text{ for } 1 \le i \le n. $$

Let $\mathcal{P}_n$ denote the set of all parking functions of order $n$. It is known that $|\mathcal{P}_n| = (n+1)^{n-1}$ [Sta99].

A Dyck path of order $n$ is a path from $(0, 0)$ to $(n, n)$ consisting of $n$ north and $n$ east steps such that no step goes strictly below the diagonal $x = y$. A labeled Dyck path is a Dyck path with vertical steps labeled $1, \dots, n$ such that labels of consecutive vertical steps increase from bottom to top, as seen in Fig. 4. There is a bijection between parking functions and labeled Dyck paths [Loe05, Loe11]. Let $f$ be a parking function of order $n$. Place all $x$ such that $f(x) = y$ in column $y$. Thus the parking function defined by $f(1) = 2, f(2) = 1, f(3) = 4, f(4) = 1, f(5) = 4, f(6) = 4$ maps to the labeled Dyck path in Fig. 4. Similarly, when given a labeled Dyck path $P$, for all entries $x$ in row $y$, set $f(x) = y$. The resulting function is a parking function.

The *area* of a labeled Dyck path $P$ is the number of complete lattice squares between the path and the line $x = y$. We can construct the *area vector*, $g(P)$, by setting $g_i$ to be the number of complete squares between the path and $x = y$ in row $i$, where row 1 is the bottom row of the path. Thus, for the path in Fig. 4, $g(P) = (0, 1, 1, 0, 1, 2)$. Then

$$ \mathrm{area}(P) = \sum_{i=1}^{n} g_i \qquad (7) $$
<figure><img src="image_3.png" /><figcaption>Fig. 4: A labeled Dyck path</figcaption></figure>

and $area(P) = 0 + 1 + 1 + 0 + 1 + 2 = 5$ for the path in Fig. 4.

We can also construct a *content vector*, $p(P)$, by setting $p_i$ to be the entry in row $i$ of $P$. For the path in Fig. 4, $p(P) = (2, 4, 1, 3, 5, 6)$. A Dyck path can be constructed from a pair of vectors $(g, p)$ if and only if [Loe05]

1. $g$ and $p$ have length $n$.

2. $g_1 = 0$.

3. $g_i \ge 0$ for $1 \le i \le n$.

4. $g_{i+1} \le g_i + 1$ for $1 \le i \le n - 1$.

5. $p$ is a permutation of $\{1, \dots, n\}$.

6. $g_{i+1} = g_i + 1$ implies $p_i < p_{i+1}$.

For a parking function $f \in \mathcal{P}_n$ corresponding to the labeled Dyck path $P$, set $area(f) = area(P)$, $g(f) = g(P)$, and $p(f) = p(P)$. We define a second weight on $f$ by

$$ \mathrm{dinv}(f) = \sum_{i<j} [\chi(g_i(f) = g_j(f) \text{ and } p_i(f) < p_j(f)) \\ + \chi(g_i(f) = g_j(f) + 1 \text{ and } p_i(f) > p_j(f))] \quad (8) $$

where, for a logical statement $A$, $\chi(A) = 1$ if $A$ is true and $\chi(A) = 0$ if $A$ is false.

**Conjecture 2 ([HL05]** The Hilbert series of $DH_n$ is given by the polynomial

$$ CH_n(q, t) = \sum_{f \in \mathcal{P}_n} q^{\mathrm{dinv}(f)} t^{\mathrm{area}(f)}. \quad (9) $$

# 4 Weight-preserving injection

For two classes of fillings, namely those with a $\mu$-major index of zero and those with shape $\mu = (1^{n-k}k)$, we will define an injection from standard fillings to parking functions. Given a filling $T \in \mathcal{F}_\mu$, the reading word of $T$, denoted $RW(T)$, is obtained by reading the entries of $T$ from left to right, top to bottom. To find the reading word of a labeled Dyck path, denoted $RW(P)$, read down the diagonals from right to left,
top to bottom. The reverse of a word $w = w_1 \dots w_k$ is $w^R = w_k w_{k-1} \dots w_1$. The inverse descent set of a filling (resp. labeled Dyck path), denoted $\mathrm{IDes}(T)$ (resp. $\mathrm{IDes}(P)$), is the descent set of the inverse of $\mathrm{RW}(T)$ (resp. $\mathrm{RW}(P)$) as a permutation. Thus $\mathrm{IDes}(T) = \{i : i + 1$ appears earlier than $i$ in $\mathrm{RW}(T)\}$. Ultimately, we want to define an injection $f : \mathcal{F}_\mu \to \mathcal{P}_n$ with the following properties:

1. $\mathrm{inv}_\mu(T) = \mathrm{dinv}(f(T)),$

2. $\mathrm{maj}_\mu(T) = \mathrm{area}(f(T))$, and

3. $\mathrm{IDes}(T) = \mathrm{IDes}(f(T)).$

## 4.1 $\mu$-major index of zero

We consider fillings $T$ of shape $\mu$ with $\mathrm{maj}_\mu(T) = 0$. Note that if $\mathrm{maj}_\mu(T) = 0$ then each column must increase from top to bottom and $\mathrm{Des}(T) = \emptyset$. Then $\mathrm{inv}_\mu(T) = |\mathrm{Inv}(T)|$, the number of attack inversions in $T$, since $\sum_{c \in \mathrm{Des}(T)} |\mathrm{ARM}(c)| = 0$. These fillings must be sent to a parking function $P = (g, p)$ with $\mathrm{area}(P) = 0$. Setting $p = \mathrm{RW}(T)^R$ can introduce many new inversions that will be counted by $\mathrm{dinv}(P)$ as seen in Fig. 5, so the injection must rearrange $\mathrm{RW}(T)$ to compensate for these new inversions.

<figure><img src="image_4.png" /><figcaption>**Fig. 5:** A map taking $T$ to $P$ that does not preserve inversions</figcaption></figure>

In order to address the additional inversions present in the reading word of $T$ we define a new type of inversion that may be present in $T$ but is not counted by $\mathrm{inv}_\mu(T)$. We say that a cell $(i, j)$ *defends* cells in the set $\{(a, b) : a = i - 1 \text{ and } b > j\} \cup \{(a, b) : a = i - 2 \text{ and } b < j\}$ as seen in Fig. 6. A *defense* inversion occurs when cell $c$ *defends* cell $d$ and $T(c) > T(d)$. We define $\mathrm{DefInv}(T) = \{(T(c), T(d)) : c \text{ defends } d \text{ and } T(c) > T(d)\}$. We are now ready to define a map $f : \mathcal{F}_\mu|_{\mathrm{maj}_\mu=0} \to \mathcal{P}_n|_{\mathrm{area}=0}$ with the form $f(T) = (g(T), p(T)).$

<figure><img src="image_5.png" /><figcaption>**Fig. 6:** Cells defended by $c$</figcaption></figure>
<table><caption>**Tab. 1:** Calculating $w^{(i)}$</caption><thead><tr><th>i</th><th>w<sup>(i)</sup></th><th></th></tr></thead><tbody><tr><td>1</td><td>15362874</td><td>1 is not defended by any w<sub>j</sub></td></tr><tr><td>2</td><td>15362874</td><td>5 is not defended by any w<sub>j</sub></td></tr><tr><td>3</td><td>15362874</td><td>3 is not defended by any w<sub>j</sub></td></tr><tr><td>4</td><td>15362874</td><td>6 is defended by 1, but 1 &lt; 6</td></tr><tr><td>5</td><td>15326874</td><td>2 is defended by 5 and 5 &gt; 2</td></tr><tr><td>6</td><td>15326874</td><td>8 is defended by 5, but 5 &lt; 8</td></tr><tr><td>7</td><td>15326874</td><td>7 is defended by 1 and 3, but 1 &lt; 7 and 3 &lt; 7</td></tr><tr><td>8</td><td>15326487</td><td>4 is defended by 5 and 6 and 6 &gt; 4, 5 &gt; 4</td></tr></tbody></table>

**Definition 3** Let $T \in \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0}$ and set $w = \mathrm{RW}(T)$. For each $i$, $1 < i \le n$, let $c_i$ be the number of $j$, $1 \le j < i$ such that $w_j$ and $w_i$ form a defense inversion. Define $w^{(i)}$ to be $w^{(i-1)}$ with $w_i$ shifted left $c_i$ places. Define $f: \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0} \to \mathcal{P}_n|_{\mathrm{area}=0}$ by $f(T) = (g(T), p(T))$ where $g(T) = (0, 0, \dots, 0)$ and $p(T) = (w^{(n)})^R$.

For $T$ in Fig. 5 we compute $f(T)$ using Def. 3. We start by calculating $w^{(n)}$ in Table 1. Then $p(T) = (7, 8, 4, 6, 2, 3, 5, 1)$ and thus $f(T) = ((0, 0, 0, 0, 0, 0, 0), (7, 8, 4, 6, 2, 3, 5, 1))$. By construction, $\mathrm{area}(f(T)) = 0$. One can compute $\mathrm{dinv}(f(T)) = 6 = \mathrm{inv}_{\mu}(T)$ and $\mathrm{IDes}(T) = \{2, 4, 7\} = \mathrm{IDes}(f(T))$.

The construction of $w^{(n)}$ from the reading word of $T$ is designed to undo the additional inversions $\mathrm{RW}(T)$ has due to defense inversions in $T$.

**Lemma 4** Given $T \in \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0}$,

$$ \mathrm{inv}(w^{(n)}) = \mathrm{inv}(\mathrm{RW}(T)) - \sum_{i=1}^{n} c_i. \qquad (10) $$

**Proof:** We will show that two consecutive entries in $\mathrm{RW}(T)$ with $w_i < w_j$ where $i < j$ cannot appear as $\dots w_j \dots w_i \dots$ in $w^{(n)}$. For each $i$, let

$$ U_i = \{w_k \in \mathrm{RW}(T) : w_k \text{ defends } w_i \text{ and } w_k > w_i\}. $$

Then $c_i = |U_i|$ and it is sufficient to show that $c_i + j - i > c_j$, that is, that $w_i$ will move farther to the left than $w_j$.

Suppose $w_i$ and $w_j$ are in the same row. The possible entries in $U_i$ and $U_j$ are shaded in Fig. 7. If a cell in a dark gray region forms a defense inversion with $w_j$, then it also forms a defense inversion with $w_i$. Cells in the light gray shaded region can only be in $U_i$. Cells in the black region can only be in $U_j$. Note that there are $j - i - 1$ cells in the black region. Thus $|U_i| \ge |U_j| - (j - i - 1)$.

Now suppose $w_i$ is in a row higher than $w_j$. In Fig. 8 the possible elements of $U_i$ and $U_j$ are shaded using the same scheme as before. If a cell in a dark gray region forms a defense inversion with $w_j$, then it must also form a defense inversion with $w_i$ since $w_j > w_i$. The cells in the light gray region can only be in $U_i$, while cells shaded black can only be in $U_j$. There are at most $j - i - 1$ cells in the black region. Thus $|U_i| \ge |U_j| - (j - i - 1)$.
<figure><img src="image_6.png" /><figcaption>Fig. 7: $w_i$ and $w_j$ in same row</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 8: A possible configuration of $w_i$, $w_j$</figcaption></figure>

Therefore $|U_i| \ge |U_j| - (j - i - 1)$, so $c_i + j - i > c_j$. Since $w_i$ cannot be moved past a smaller entry of $w^{(i-1)}$, $w_i$ must move past $c_i$ entries of $w^{(i-1)}$ that are greater than $w_i$ and hence

$$ \mathrm{inv}(w^{(i)}) = \mathrm{inv}(w^{(i-1)}) - c_i. $$

Note that $\mathrm{inv}(w^{(1)}) = \mathrm{inv}(\mathrm{RW}(T))$ and thus, by induction,

$$ \mathrm{inv}(w^{(n)}) = \mathrm{inv}(\mathrm{RW}(T)) - \sum_{i=1}^{n} c_i. $$

□

We now show that $f$ preserves weights and inverse descent sets between standard fillings and parking functions.

**Theorem 5** The map $f : \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0} \to \mathcal{P}_n|_{\mathrm{area}=0}$ has the following properties:

(a) $\mathrm{maj}_{\mu}(T) = \mathrm{area}(f(T))$,

(b) $\mathrm{inv}_{\mu}(T) = \mathrm{dinv}(f(T))$, and

(c) $\mathrm{IDes}(\mathrm{RW}(T)) = \mathrm{IDes}(\mathrm{RW}(f(T)))$.

**Proof:** Let $T \in \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0}$. By definition of $f$, $\mathrm{maj}_{\mu}(T) = \mathrm{area}(f(T))$. To show that $\mathrm{inv}_{\mu}(T) = \mathrm{dinv}(f(T))$ we first note that $\mathrm{inv}(\mathrm{RW}(T)) = \mathrm{inv}_{\mu}(T) + |\mathrm{DefInv}(T)|$. Since $\mathrm{area}(f(T)) = 0$, $\mathrm{dinv}(f(T)) = \mathrm{inv}(p(T)^R) = \mathrm{inv}(w^{(n)})$. Thus, it is sufficient to show that $\mathrm{inv}_{\mu}(T) = \mathrm{inv}(w^{(n)})$ since $w^{(n)} = p(T)^R$.
By Lemma 4,

$$ \begin{aligned} \mathrm{inv}(w^{(n)}) &= \mathrm{inv}(\mathrm{RW}(T)) - \sum c_i \\ &= \mathrm{inv}(\mathrm{RW}(T)) - |\mathrm{DefInv}(T)| \\ &= \mathrm{inv}_{\mu}(T). \end{aligned} $$

Finally, to show that $\mathrm{IDes}(\mathrm{RW}(T)) = \mathrm{IDes}(\mathrm{RW}(f(T)))$ suffices to show that $i$ and $i+1$ can never switch places during the construction of $p(T)$ since when $\mathrm{area}(f(T)) = 0$, $\mathrm{RW}(f(T)) = p(T)^R$. From the proof of Lemma 4 we know that if $i$ and $i+1$ are in positions $w_k$ and $w_{k+j}$ respectively, they will not exchange positions since $i < i+1$.

Suppose $i+1 = w_k$ and $i = w_{k+j}$ for some $k, j > 0$. Suppose $c_k = m$. Then $c_{k+j} \le m + j$ since any entry that forms a defense inversion with $w_k$ must also form a defense inversion with $w_{k+j}$ and there are at most $j$ additional entries of $T$ that could form a defense inversion with $w_{k+j}$. $\square$

It remains to show that $f$ is indeed an injection.

**Theorem 6** *The function $f: \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0} \to \mathcal{P}_n|_{\mathrm{area}=0}$ is an injection.*

**Proof:**

Suppose, to the contrary, that there exist $T_1, T_2 \in \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0}$ such that $T_1 \neq T_2$ but $f(T_1) = f(T_2)$. Set $w = \mathrm{RW}(T_1)$ and $v = \mathrm{RW}(T_2)$. Since $f(T_1) = f(T_2)$, $w^{(n)} = v^{(n)} = u$. Let $i$ be the smallest index such that $w_i \neq v_i$. We will assume that $w_i < v_i$. As in the definition of $f$, let $c_k = |\mathrm{DefInv}(w_k)|$ for all $k$. Since $w$ and $v$ are both permutations of $\{1, \dots, n\}$, there exists some $j > i$ such that $v_j = w_i$. We will show that $v_j$ cannot end up in the same location as $w_i$ in $u$. In order for $v_j$ to be in the same location in $u$ as $w_i$, we need $|\mathrm{DefInv}(v_j)| = c_i + j - i$.

First note that if $v_j$ is in a lower row and to the right of $v_i$ or more than one row below $v_i$ and $v_j$ has some entry $v_k < v_j$ directly above it, then by the proof of Lemma 4, $v_j$ cannot be moved past $v_k$ and hence cannot ever achieve the same position as $w_i$ in $u$. This leaves three potential configurations for $v_i$ and $v_j$ in $T_2$.

1. We look first at what happens if $v_j$ is just one row below $v_i$ and to the left of $v_i$. This can be seen in Fig. 9. The dark gray in the picture indicates the entries that could be in $\mathrm{DefInv}(v_i)$, while the dark and light gray indicate the entries that could be in $\mathrm{DefInv}(v_j)$. Note that $\mathrm{DefInv}(v_i) \subseteq \mathrm{DefInv}(v_j)$ since $v_j < v_i$. The farthest left that $v_j$ can be moved during the construction of $v^{(n)}$ is $|\mathrm{DefInv}(v_j)| \le |\mathrm{DefInv}(w_i)| + j - i - 1$, but this is not far enough to move $v_j$ to the same location as $w_i$ in $u$.

2. If $v_i$ and $v_j$ are in the same row (with $v_j$ to the right of $v_i$), there are at most $j - i - 1$ possible entries of $T_2$ in $\mathrm{DefInv}(v_j)$ that are not also in $\mathrm{DefInv}(w_i)$. Thus, there is no way for $v_j$ to move far enough left in $v^{(n)}$ to end in the same position as $w_i$ in $u$.

3. Similarly, if $v_j$ is in a lower row and to the right of $v_i$, with no entries in the column above $v_j$, there are still at most $j - i - 1$ possible entries of $T_2$ in $\mathrm{DefInv}(v_j)$ that are not also in $\mathrm{DefInv}(w_i)$.

Therefore, $f: \mathcal{F}_{\mu}|_{\mathrm{maj}_{\mu}=0} \to \mathcal{P}_n|_{\mathrm{area}=0}$ is an injection. $\square$
<figure><img src="image_8.png" /><figcaption>Fig. 9: One possible configuration of $v_i$ and $v_j$</figcaption></figure>

## 4.2 Injection when $\mu$ is a hook shape

In this section we describe an injection from $\mathcal{F}_\mu$ to $\mathcal{P}_n$ when $\mu = (1^{n-k}k)$, that is, the diagram of $\mu$ has a hook shape. Let $T \in \mathcal{F}_{(1^{n-k}k)}$. Create a new filling $T_g$ of shape $(1^{n-k}k)$ by filling all cells $(i, 1)$ in the bottom row with 0. Compute $T_g$ recursively by letting $T_g(i, j) = T_g(i - 1, j)$ if $T(i, j) < T(i - 1, j)$ or $T_g(i, j) = T_g(i - 1, j) + 1$ if $T(i, j) > T(i - 1, j)$. Note that $T_g$ can be calculated in this manner for $T$ of any partition shape and is not restricted to hook shapes.

<figure><img src="image_9.png" /><figcaption>Fig. 10: Calculating $T_g$ from a given $T$</figcaption></figure>

**Lemma 7** Given $T \in \mathcal{F}_\mu$,

$$ \mathrm{maj}_{\mu}(T) = \sum_{c \in T_g} c. \qquad (11) $$

We are now ready to define the function $f : \mathcal{F}_{(1^{n-k}k)} \to \mathcal{P}_n$.

**Definition 8** Define $f : \mathcal{F}_{(1^{n-k}k)} \to \mathcal{P}_n$ by $f(T) = (g(T), p(T))$. To find $g(T)$, compute $T_g$ (see Fig. 10) and then set $g(T) = \mathrm{RW}^R(T_g)$. To find $p(T)$, first note that $\mathrm{RW}(T) = \mathrm{wv}$ where $w = w_1 \dots w_m$ is the subword containing those entries of $T$ whose corresponding entries in $T_g$ are nonzero and $v = v_1 \dots v_{n-m}$ is the subword containing those entries of $T$ whose corresponding entries in $T_g$ are zero. For $1 < i \le n-m$ let $c_i$ be the number of $v_j$ forming defense inversions with $v_i$ where $i > j$. Let $v^{(i)}$ be defined recursively as $v^{(i-1)}$ with $v_i$ shifted left $c_i$ places. Then $p(T) = (v^{(n-m)})^R w^R$.

Note that the construction of $f(T)$ means that the only possible contributors to $\mathrm{dinv}(f(T))$ are those that are on the same diagonal.

For $\mu = (1^54)$ and $T$ as in Fig. 10, we find that $g(T) = (0,0,0,0,0,1,1,2,2)$ and $\mathrm{RW}(T) = 781546293$. Then $w = 7815$ and $v = 46293$. See Table 2 to see how $v^{(5)} = 42639$ is calculated. Then $p(T) = (9,3,6,2,4,5,1,8,7)$. See Fig. 11 for the associated labeled Dyck path. Note that $\mathrm{maj}_\mu(T) = 6 = \mathrm{area}(f(T))$, $\mathrm{inv}_\mu(T) = 3 = \mathrm{dinv}(f(T))$, and $\mathrm{IDes}(T) = \{4,6,3\} = \mathrm{IDes}(f(T))$.
<table><caption>Tab. 2: Computing $v^{(i)}$</caption><thead><tr><th>$i$</th><th>$v^{(i)}$</th><th></th></tr></thead><tbody><tr><td>1</td><td>46293</td><td>4 is not defended by any $v_j$</td></tr><tr><td>2</td><td>46293</td><td>6 is not defended by any $v_j$</td></tr><tr><td>3</td><td>42693</td><td>2 is defended by 4 and $4 > 2$</td></tr><tr><td>4</td><td>42693</td><td>9 is defended by 4, but $9 > 4$</td></tr><tr><td>5</td><td>42639</td><td>3 is defended by 4 and $4 > 3$</td></tr></tbody></table>

<figure><img src="image_10.png" /><figcaption>Fig. 11: Labeled Dyck path with $g = (0, 0, 0, 0, 0, 1, 1, 2, 2)$ and $p = (9, 3, 6, 2, 4, 5, 1, 8, 7)$</figcaption></figure>

**Proposition 9** Let $\mu = (1^{n-k}k)$. Then $f : \mathcal{F}_{(1^{n-k}k)} \to \mathcal{P}_n$ is an injection and

(a) $\mathrm{maj}_{\mu}(T) = \mathrm{area}(f(T))$,

(b) $\mathrm{inv}_{\mu}(T) = \mathrm{dinv}(f(T))$, and

(c) $\mathrm{IDes}(T) = \mathrm{IDes}(f(T))$.

**Proof:** Let $T \in \mathcal{F}_{\mu}$ for $\mu = (1^{n-k}k)$. From Lemma 7 and (7) we know that $\mathrm{maj}_{\mu}(T) = \mathrm{area}(f(T))$. Properties (b), (c), and injectivity follow quickly from the proof of Theorem 5 and the fact that the order of the entries in $T$ that correspond to nonzero entries in $T_g$ do not get reordered and do not contribute either to $\mathrm{inv}_{\mu}(T)$ or $\mathrm{dinv}(f(T))$. $\square$

## 5 Conclusion

In this paper we have shown a new injection from the standard fillings of Ferrers diagrams that generate the Hilbert series of the Garsia-Haiman module to parking functions, which are conjectured to generate the Hilbert series of the module of diagonal harmonics, for two special cases. It is desirable to have an injection that works for any partition $\mu$. Maps similar to those in this paper appear to give the desired result in fillings with $\sum_{c \in \mathrm{Des}(T)} |\mathrm{ARM}(c)| = 0$, but difficulties arise when $\sum_{c \in \mathrm{Des}(T)} |\mathrm{ARM}(c)| \neq 0$.

## References

[GH93] A. Garsia and M. Haiman. A graded representation model for Macdonald's polynomials. *Proc. Natl. Acad. Sci. USA*, 90:3607–3610, 1993.
[Hag04] J. Haglund. A combinatorial model for the Macdonald polynomials. Proc. Natl. Acad. Sci. USA, 101:16127-16131, 2004.

[Hag08] J. Haglund. *The q, t-Catalan numbers and the space of diagonal harmonics, with an appendix on the combinatorics of Macdonald polynomials.* AMS University Lecture Series, 2008.

[Hai94] M. Haiman. Conjectures on the quotient ring by diagonal invariants. J. Algebraic Combin., 3:17-76, 1994.

[Hai01] M. Haiman. Hilbert schemes, polygraphs, and the Macdonald positivity conjecture. J. Amer. Math. Soc., 14:941-1006, 2001.

[HHL05a] J. Haglund, M. Haiman, and N. Loehr. A combinatorial formula for Macdonald polynomials. J. Amer. Math. Soc., 18:735-761, 2005.

[HHL05b] J. Haglund, M. Haiman, and N. Loehr. Combinatorial theory of Macdonald polynomials I: Proof of Haglund's formula. Proc. Natl. Acad. Sci. USA, 102:2690-2696, 2005.

[HL05] J. Haglund and N. Loehr. A conjectured combinatorial formula for the Hilbert series for diagonal harmonics. Discrete Math., 298:189-204, 2005.

[Loe05] N. Loehr. Combinatorics of q, t-parking functions. Adv. in Appl. Math., 34:408-425, 2005.

[Loe11] N. Loehr. *Bijective Combinatorics*. Taylor and Francis/CRC Press, 2011.

[Mac88] I. Macdonald. A new class of symmetric functions. Actes du 20e Séminaire Lotharingien, 372/S-20:131-171, 1988.

[Mac95] I. Macdonald. *Symmetric functions and Hall polynomials*. Oxford University Press, second edition, 1995.

[Sta99] R. P. Stanley. *Enumerative Combinatorics*, volume 2. Cambridge University Press, 1999.