# Combinatorial Formula for the Hilbert Series of bigraded $S_n$-modules

Meesue Yoo<fnref n="1" />

**Abstract.** We introduce a combinatorial way of calculating the Hilbert series of bigraded $S_n$-modules as a weighted sum over standard Young tableaux in the hook shape case. This method is based on Macdonald formula for Hall-Littlewood polynomial and extends the result of A. Garsia and C. Procesi for the Hilbert series when $q = 0$. Moreover, we give the way of associating the fillings giving the monomial terms of Macdonald polynomials to the standard Young tableaux.

**Résumé.** Nous introduisons une méthode combinatoire pour calculer la série de Hilbert de modules bigradués de $S_n$ comme une somme pondérée sur les tableaux de Young standards à la forme crochet. Cette méthode se fonde sur la formule Macdonald pour les polynômes Hall-Littlewood et généralise un résultat de A. Garsia et C. Procesi pour la série de Hilbert dans le cas $q = 0$. De plus, nous proposons une méthode pour associer aux tableaux de Young standards les remplissages des monomes des polynômes de Macdonald.

**Keywords:** combinatorial formula, Hilbert series, Garsia-Haiman modules

<footnote n="1">¹Dept. Math, University of Pennsylvania, Philadelphia, PA, USA</footnote>
# 1 Introduction

In 1988 (Mac), Macdonald introduced a family of symmetric functions with two variables that are known as the Macdonald polynomials which becomes a basis for the space of symmetric functions. Upon introducing these polynomials, Macdonald conjectured that the coefficients of the Schur expansion of Macdonald polynomials are polynomials in the parameters $q$ and $t$ with nonnegative integer coefficients. To prove the positivity conjecture of Macdonald polynomials, Garsia and Haiman introduced certain bigraded $S_n$ modules $M_\mu$ (GH93) and Haiman proved that the bigraded Frobenius characteristic $\mathcal{F}(M_\mu)$, which by definition is simply the image of the bigraded character of $M_\mu$ under the Frobenius map, is the transformed Macdonald polynomials, i.e.,

$$ \mathcal{F}_{M_{\mu}}(x; q, t) = \tilde{H}_{\mu}(x; q, t), $$

where $\tilde{H}_{\mu}(x; q, t)$ is the modified Macdonald polynomials (HHL05). For the Garsia-Haiman module $M_\mu$, if we define $\mathcal{H}_{h,k}(M_\mu)$ to be the subspace of $M_\mu$ spanned by its bihomogeneous elements of degree $h$ in $x$ and degree $k$ in $y$, we can write a bivariate Hilbert series such as

$$ \mathcal{H}_{M_{\mu}}(q, t) = \sum_{h=0}^{n(\mu)} \sum_{k=0}^{n(\mu')} t^h q^k \dim(\mathcal{H}_{h,k}(M_{\mu})). $$

Noting that the degree of the $S_n$ character $\chi_\lambda$ is given by $<p_1^n, s_\lambda>$, where $<$, $>$ is the usual inner product on symmetric functions and $p_k$ is the $k^{th}$ power sum, we may write

$$ \mathcal{H}_{M_{\mu}}(q, t) = \langle p_1^n, \mathcal{F}_{M_{\mu}} \rangle. $$

Therefore, the coefficient of $x_1x_2\cdots x_n$ of $\tilde{H}_{\mu}(x; q, t)$ gives the Hilbert series of Garsia-Haiman module $M_\mu$.

On the other hand, Haglund, Haiman and Loehr found the combinatorial formula for the monomial expansion of $\tilde{H}_{\mu}[X; q, t]$ given by (HHL05)

$$ \tilde{H}_{\mu}(x; q, t) = \sum_{\sigma: \mu \to \mathbb{Z}_+} q^{\mathrm{inv}(\mu, \sigma)} t^{\mathrm{maj}(\mu, \sigma)} x^{\sigma} \quad (1) $$

where the definitions of $\mathrm{inv}(\mu, \sigma)$ and $\mathrm{maj}(\mu, \sigma)$ are given in Section 2. This combinatorial formula gives a way of calculating the Hilbert series $\mathcal{H}_{M_\mu}(q, t)$ as a sum of $n!$ monomials. In this paper, we introduce a combinatorial formula for this Hilbert series which can be calculated over only the standard Young tableaux of shape $\mu$ when $\mu$ has a hook shape. This combinatorial formula is motivated by the formula for the 2 column shape case which is conjectured by Haglund and proved by Garsia and Haglund.

# 2 The Formula

We begin by recalling definitions of $q$-analogs :

$$ [n]_q = 1 + q + \cdots + q^{n-1}, $$

$$ [n]_q! = [1]_q \cdots [n]_q. $$
Given a sequence $(\mu_1, \mu_2, \dots)$ of nonincreasing, nonnegative integers with $\sum_i \mu_i = n$, we say $\mu$ is a partition of $n$, denoted by either $|\mu| = n$ or $\mu \vdash n$. And let

$$dg(\mu) = \{(i, j) \in \mathbb{Z}_+ \times \mathbb{Z}_+ : j \le \mu_i\}$$

be its Young (or Ferrers) diagram, whose elements are called cells. For simplicity, we henceforth write $\mu$ instead of $dg(\mu)$ when it will not cause confusion. A filling is a function $\sigma : \mu \to \mathbb{Z}_+$ assigning integer entries to the cells of $\mu$. A semi-standard Young tableau is a filling which is weakly increasing along each row of $\mu$ and strictly increasing along each column. A semi-standard Young tableau is standard if it is a bijection from $\mu$ to $[n] = \{1, 2, \dots, n\}$. We define

$$\text{SYT}(\mu) = \{ \text{standard Young tableaux } T : \mu \to [n], T \text{ bijection} \}.$$

A descent of $\sigma$ is a pair of entries $\sigma(u) > \sigma(v)$, where the cell $u$ is immediately above $v$. Define

$$\text{Des}(\sigma, \mu) = \{u \in \mu : \sigma(u) > \sigma(v) \text{ a descent}\}.$$

The arm of a cell $u \in \mu$ is the number of cells strictly to the right of $u$ in the same row, and its leg is the number of cells strictly above $u$ in the same column. Then define

$$\text{maj}(\sigma, \mu) = \sum_{u \in \text{Des}(\sigma, \mu)} (\text{leg}(u) + 1).$$

Three cells $u, v, w \in \mu$ are said to form a triple if they are situated as shown below,

$\boxed{\substack{\text{u} \\ \text{v}}}$

$\boxed{\text{w}}$

namely, $v$ is directly below $u$, and $w$ is in the same row as $u$, to its right. Let $\sigma$ be a filling and let $x, y, z$ be the entries of $\sigma$ in the cells of a triple $(u, v, w)$:

$\boxed{\substack{\text{y} \\ \text{x}}}$

$\boxed{\text{z}}$

If a path starting from the smallest entry to the largest entry rotates in counter clockwise way, then the triple is called an inversion triple. Otherwise, it is called a coinversion triple. Define

$$\text{inv}(\sigma, \mu) = \text{number of inversion triples in } \mu \text{ with } \sigma \text{ filling,} \\ \text{coinv}(\sigma, \mu) = \text{number of coinversion triples in } \mu \text{ with } \sigma \text{ filling.}$$

For a hook $\mu' = (n - s, 1^s)$, we define

$$\tilde{G}_{\mu'}(q, t) = \sum_{T \in \text{SYT}(\mu')} \prod_{i=1}^{n} [a_i(T)]_t \cdot [s]_q! \left( 1 + \sum_{j=1}^{s} q^j t^{\alpha_j(T)} \right)$$

where $a_i(T)$ and $\alpha_i(T)$ are calculated in the following way : to construct $T \in \text{SYT}(\mu')$, staring with the cell containing 1, add cells containing 2, 3, ..., $i$, one at a time. After adding the cell containing $i$, $a_i(T)$ counts the number of columns which have the same height with the column containing the
square just added with $i$. And $\alpha_j(T)$ is the number of cells in the first row with column height 1 (i.e., strictly to the right of the first column) having bigger element than the element in $(s-j+1, 1)$ cell. Then, for $\tilde{F}_{(n-s,1^s)'}(q,t) = \sum_{\sigma \in S_n} q^{\mathrm{maj}(\sigma, \mu')} t^{\mathrm{coinv}(\sigma, \mu')}$, where $\tilde{F}_{\mu'}(q,t) = t^{n(\mu)} F_{\mu}(\frac{1}{t}, q)^{(i)}$, $n(\mu) = \sum_{i \ge q} (i-1)\mu_i$, we have the following theorem :

**Theorem 2.1**

$$ \tilde{F}_{(n-s,1^s)'}(q,t) = \tilde{G}_{(n-s,1^s)'}(q,t). $$

**Example 2.2 (μ = (2, 1) case)** We calculate $\tilde{F}_{(2,1)}(q,t) = \sum_{\sigma \in S_3} q^{\mathrm{maj}(\sigma, \mu')} t^{\mathrm{coinv}(\sigma, \mu')} \text{ first.}$

<figure><img src="image_1.png" /></figure>

From the above tableaux, reading from the left, we get

$$ \tilde{F}_{(2,1)}(q,t) = t + 1 + qt + 1 + qt + q = 2 + q + t + 2qt. \qquad (2) $$

Now we consider $\tilde{G}_{(2,1)}(q,t)$ over the two standard tableaux.

$$ T_1 = \begin{bmatrix} 2 \\ 1 \\ 3 \end{bmatrix}, \quad T_2 = \begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix} $$

For the SYT $T_1$, if we add 1, there is only one column with height 1, so we multiply 1. And if we add 2, since it is going on the top of the square with 1, it makes a column with height 2 and so there is only one column with height 2 which gives us factor 1 again. Adding the square with 3, since there is one column with height 1 and the column containing the square with 3 is height 1, it again gives the factor 1. Hence for this tableau, the first factor is 1. For $\alpha_j(T_1)$, we compare the element in the first row to the right of the square with 2, and that is 3 which is bigger than 2, so it gives $\alpha_1(T_1) = 0$ which contributes the factor $(1+qt)$. Hence, $T_1$ gives the $1 \cdot (1+qt)$. Now we consider $T_2$. If we add the second square with 2, then it makes two columns with height 1, so we get $\alpha_2(T_2) = [2]_t = (1+t)$. Adding the last square gives the factor 1, so the first factor is $(1+t)$. If we consider the second factor, since 3 is the biggest element in this case, the power of $t$ becomes 0 and that makes $\alpha_1(T_2) = 0$. Hence from $T_2$, we get $(1+t)(1+q)$. If we add two polynomials from two standard young tableaux of shape $\mu = (2,1)$, we get

$$ \tilde{G}_{(2,1)}(q,t) = 1 \cdot (1+qt) + (1+t)(1+q) = 1 + qt + 1 + t + q + qt = 2 + q + t + 2qt $$

which is equal to (2), i.e., $\tilde{F}_{(2,1)}(q,t) = \tilde{G}_{(2,1)}(q,t)$.

**Proof:** We first note the Garsia-Haiman recursion for the Hilbert series of the hooks (GH96) : for $\mu = (s+1, 1^{n-s-1})$,

$$ F_{\mu}(q,t) = [n-s-1]_t F_{(s+1,1^{n-s-2})} + \binom{n-1}{s} t^{n-s-1} [n-s-1]_t! [s]_q! + q[s]_q F_{(s,1^{n-s-1})}. \quad (3) $$

<footnote>(i) Note that $F_{\mu}(q,t)$ denotes the Hilbert series of Garsia-Haiman module $M_{\mu}$.</footnote>
We derive the recursion formula for $\tilde{G}_{\mu'}(q, t)$ over standard tableaux by fixing the position of the cell with the largest number $n$:

<figure><img src="image_2.png" /></figure>

Let's first start from a SYT of shape $(n-s, 1^{s-1})$ and say

$$ \tilde{G}_{(n-s, 1^{s-1})}(q, t) = \sum_{T \in \text{SYT}((n-s, 1^{s-1}))} \prod_{i=1}^{n-1} [a_i(T)]_t \cdot [s]_q! \left( 1 + \sum_{j=1}^{s-1} q^j t^{\alpha_j(T)} \right) $$

and put the cell with $n$ on the top of the first column. Then, since there is no other column with height $s+1$, adding the cell with $n$ on the top of the first column gives $a_n = [1]_t$ which doesn't change the first part of the above formula. Now as for the $q$ part, we will have an additional factor of $[s]_q$, and all the $q$ powers in the last parenthesis will be increased by 1 and it will have additional $q$ from the top cell of the first column. The exponent of $t$ with that $q$ is 0 since $n$ is the largest possible number. Hence, for the first case tableaux, the formula we get becomes

$$ \sum_{T \in \text{SYT}((n-s, 1^{s-1}))} \prod_{i=1}^{n-1} [a_i(T)]_t \cdot [s]_q! \left[ 1 + q \left( 1 + \sum_{j=1}^{s-1} q^j t^{\alpha_j(T)} \right) \right] = \left( \sum_{T \in \text{SYT}((n-s, 1^{s-1}))} \prod_{i=1}^{n-1} [a_i(T)]_t \cdot [s]_q! \right) + q[s]_q \tilde{G}_{(n-s, 1^{s-1})}(q, t) $$

and in terms of $\tilde{G}_{(n-s, 1^{s-1})}(q, t)$, this is equal to

$$ [s]_q! \tilde{G}_{(n-s, 1^{s-1})}(0, t) + q[s]_q \tilde{G}_{(n-s, 1^{s-1})}(q, t). $$

In the second case, we start from a SYT of shape $(n-s-1, 1^s)$ and add the cell with $n$ in the end of the first row. This increases the number of columns with height 1 from $n-s-2$ to $n-s-1$, so contributes the $t$ factor $a_n = [n-s-1]_t$. Since it doesn't affect the first column, we don't get any extra $q$ factor, but having the largest number $n$ in the first row increases all the $\alpha_j$'s by 1. In other words, if we let the formula for the SYT of shape $(n-s-1, 1^s)$ as

$$ \tilde{G}_{(n-s-1, 1^s)}(q, t) = \sum_{T \in \text{SYT}((n-s-1, 1^s))} \prod_{i=1}^{n-1} [a_i(T)]_t \cdot [s]_q! \left( 1 + \sum_{j=1}^{s} q^j t^{\alpha_j(T)} \right) $$

then by adding the cell with $n$ in the end of the first row, it changes to

$$ \sum_{T \in \text{SYT}(n-s-1, 1^s)} [n-s-1]_t \cdot \prod_{i=1}^{n-1} [a_i(T)]_t \cdot [s]_q! \left( 1 + \sum_{j=1}^{s-1} q^j t^{\alpha_j(T)+1} \right) $$
$$= \sum_{T \in \text{SYT}(n-s-1, 1^s)} [n-s-1]_t \cdot \prod_{i=1}^{n-1} [a_i(T)]_t \cdot [s]_q! \left[ t \left( 1 + \sum_{j=1}^{s} q^j t^{\alpha_j(T)} \right) + (1-t) \right].$$

Thus, in terms of $\tilde{G}_{(n-s-1,1^s)}$, this can be expressed as

$$t[n-s-1]_t \tilde{G}_{(n-s-1,1^s)}(q,t) + (1-t)[n-s-1]_t [s]_q! \tilde{G}_{(n-s-1,1^s)}(0,t).$$

In conclusion, the recursive formula is the following :

$$\tilde{G}_{(n-s,1^s)}(q,t) = q[s]_q \tilde{G}_{(n-s,1^{s-1})}(q,t) + t[n-s-1]_t \tilde{G}_{(n-s-1,1^s)}(q,t) \\ +[s]_q!(\tilde{G}_{(n-s,1^{s-1})}(0,t) + (1-t^{n-s-1})\tilde{G}_{(n-s-1,1^s)}(0,t)).$$

To compare it to the Hilbert series $F_\mu(q, t)$, we do the transformations $\tilde{G}_{\mu'}(q, t) = G_\mu(\frac{1}{t}, q) t^{n(\mu)}$, and we get the recursion formula for $G_\mu(q, t)$

$$G_{(s+1,1^{n-s-1})}(q,t) = q[s]_q G_{(s,1^{n-s-1})}(q,t) + [n-s-1]_t G_{(s+1,1^{n-s-2})}(q,t) \\ +[s]_q!(G_{(s,1^{n-s-1})}(0,t) + (t^{n-s-1}-1)G_{(s+1,1^{n-s-2})}(0,t)).$$

By calculation, we get

$$G_{(s,1^{n-s-1})}(0,t) + G_{(s+1,1^{n-s-2})}(0,t) = [n-s-1]_t![s]_q! \binom{n-1}{s} t^{n-s-1}.$$

Thus the recursion formula for $G_\mu(q, t)$ simplifies to

$$G_{(s+1,1^{n-s-1})}(q,t) = q[s]_q G_{(s,1^{n-s-1})}(q,t) + [n-s-1]_t G_{(s+1,1^{n-s-2})}(q,t) \quad (4) \\ +[n-s-1]_t![s]_q! \binom{n-1}{s} t^{n-s-1}.$$

We compare two recursions (3) and (4) and we can confirm that $F_\mu(q, t)$ and $G_\mu(q, t)$ both satisfy the same recursion. Based on the fact that $F_{(2,1)}(q,t) = G_{(2,1)}(q,t)$ (note that we confirmed it in the previous example), we conclude that $F_\mu(q, t) = G_\mu(q, t)$ which implies $\tilde{F}_{\mu'}(q,t) = \tilde{G}_{\mu'}(q,t)$. $\square$

**Remark 2.3** We can construct a combinatorial way of calculating $F_\mu(q, t)$ directly over the standard Young tableaux :

$$F_{\mu}(q,t) = \sum_{T \in \text{SYT}(\mu)} \prod_{i=1}^{n} [a_i(T)]_t [\mu_1 - 1]_q! \left( \sum_{j=1}^{\mu_1 - 1} q^{j-1} t^{b_j(T)} + q^{\mu_1 - 1} \right)$$

where $a_i(T)$ counts the number of rows having the same width with the row containing $i$ as adding the cell $i$, from 1 to $n$, and $b_j(T)$ counts the number of cells in the first column in rows strictly higher than row 1 containing bigger numbers than the element in the cell $(1, j + 1)$.
### 3 Association with the Fillings

For the association with fillings, we are going to introduce a grouping table. For the general hook of shape $\mu = (s, 1^{n-s})$, the way that we make the grouping table is the following: first we choose $s$ many numbers including 1 and $n$, in all possible ways. Note that for this we have $\binom{n-2}{s-2}$ many choices. The unchosen $n-s$ many numbers will be placed in the first column above the (1, 1) cell, in all possible ways, and the chosen $s$ many numbers will come in the first row, in all possible ways. Then, this set of fillings will correspond to one standard Young tableau. We read out the polynomial corresponding the standard tableau in the following way: keeping in mind that we are calculating $q^{\text{inv}}t^{\text{maj}}$, since the permutations in the first column without including the (1, 1) cell give $[n-s]_t!$ factor and the permutations in the first row without the (1, 1) cell give $[s-1]_q!$ factor, we just consider $s$ many different cases as we change the element coming in the (1, 1) cell by the chosen ones and each will give $q^a t^b [n-s]_t! [s-1]_q!$ where $a$ is the number of elements in the first row to the right of (1, 1) cell which are smaller than the element in the (1, 1) cell, and $b$ is the number of elements in the first column above (1, 1) cell which are bigger than the one in the (1, 1) cell. We repeat choosing $s$ many numbers within 1 to $n-k$ including 1 and $n-k$, where $k$ changes from 1 to $n-s+1$. Then the rest of the procedure will be the same. We consider an example for $\mu = (3, 1, 1)$. The corresponding grouping table is the following:

<figure><img src="image_3.png" /></figure>

The rows between dividing lines will be grouped in the same set and the entries marked by $\times$ will come on the row and permute in all possible ways, and the entries marked by $\circ$ will come on the column not including the (1, 1) cell, and permute all possible ways. All the fillings obtained by these permutations of row and column will correspond to one standard tableau. For instance, from the first grouping $\times \times \circ \circ \times$, we get 12 different fillings.

<figure><img src="image_4.png" /></figure>

If we calculate $t^{\text{maj}}q^{\text{inv}}$ from the left of the top line, we get

$$t^3 + qt^3 + t^2 + qt^2 + qt^3 + q^2t^3 + qt^2 + q^2t^2 + q^2t + q^3t + q^2 + q^3 = (1+t)(1+q)(t^2+qt^2+q^2)$$
which will correspond to the standard tableau

<figure><img src="image_5.png" /></figure>

Noting that the permutations of either column or row not including the (1, 1) cell will give (1 + t) from the permutations of the column, and (1 + q) from the permutations of the row, the monomial coefficient factors $q^a t^b$ multiplied by $(1+t)(1+q)$ will be calculated by the following way : say $k$ is placed in the (1, 1) cell, then $a$ is the number of chosen elements (i.e., × marked in the table) strictly smaller than $k$ (or number of ×'s strictly to the left of $k$), and $b$ is the number of unchosen elements (i.e., ◦ marked in the table) strictly bigger than $k$ (or number of ◦'s strictly to the right of $k$). Following this method, we read out the following polynomials from the grouping table, from the second line

$$ (1+t)(1+q)(t^2+qt+q^2), \\ (1+t)(1+q)(t^2+q+q^2), \\ (1+t)^2(1+q)(t+qt+q^2), \\ (1+t)^2(1+q)(t+q+q^2), \\ (1+t)(1+t+t^2)(1+q)(1+q+q^2). $$

And the corresponding standard tableaux are from the top

<figure><img src="image_6.png" /></figure>

We use the modified Garsia-Procesi tree (GP92) to find the corresponding standard Young tableau given the polynomial from the group of fillings. For the running example for $\mu = (3, 1, 1)$, the modified Garsia-Procesi tree is given in the Figure 1. The way of finding the standard tableau from the modified Garsia-Procesi tree is the following : given the polynomial from the fillings, either of the form $(1+t)(1+q)(t^a+qt^b+q^2)$ or $(1+t)^2(1+q)(t^a+qt^b+q^2)$, compare $(a, b)$ with the numbers on the right-top of bottom leaves in the tree. Finding the same numbers in the tree, trace back the tree from the bottom to top filling the cells from 1 to $n$ (here $n = 5$) as the tree adds the cells. Then on the top of the tree, we get the corresponding standard tableau giving exactly the same polynomial as we calculated before.

**Proposition 3.1** *The grouping table gives the complete Hilbert series.*

**Proof:** By the way of constructing the grouping table that we don't count the same filling multiple times, we only need to check that the number of fillings that are counted in the grouping table is $n!$. From the permutations on the first column and the first row not including (1, 1) we count $(s-1)!(n-s)!$. In the grouping table, the set with $k$ lines will be $\binom{n-(k-1)}{s-2}$ many and each line represents $s$ different fillings. Adding up them all, the number of fillings that the grouping table counts is

$$ s!(n-s)! \left( \binom{n-2}{s-1} + 2\binom{n-3}{s-2} + \cdots + (n-s)\binom{s-1}{s-2} + (n-s+1)\binom{s-2}{s-2} \right). $$
<figure><img src="image_7.png" /><figcaption>Fig. 1: The modified Garsia-Procesi tree for $\mu = (3, 1, 1)$.</figcaption></figure>

Therefore, we want to show the following identity

$$ \binom{n}{s} = \binom{n-2}{s-1} + 2\binom{n-3}{s-2} + \dots + (n-s)\binom{s-1}{s-2} + (n-s+1)\binom{s-2}{s-2}. \quad (5) $$

Note the identity

$$ \sum_{j=k}^{n-1} \binom{j}{k} = \binom{n}{k}. \quad (6) $$

Then, by applying (6) twice, the right hand side of (5) becomes

$$ \begin{aligned} & \binom{n-2}{s-1} + 2\binom{n-3}{s-2} + \dots + (n-s)\binom{s-1}{s-2} + (n-s+1)\binom{s-2}{s-2} \\ = & \left( \binom{n-2}{s-1} + \binom{n-3}{s-2} + \dots + \binom{s-1}{s-2} + \binom{s-2}{s-2} \right) \\ & + \left( \binom{n-3}{s-2} + \dots + \binom{s-1}{s-2} + \binom{s-2}{s-2} \right) + \dots + \binom{s-2}{s-2} \end{aligned} $$
$$ 
\begin{aligned}
&= \binom{n-1}{s-1} + \binom{n-2}{s-1} + \dots + \binom{s}{s-1} + \binom{s-1}{s-1} \\
&= \binom{n}{s},
\end{aligned}
$$

which is the left hand side of (5). This shows that we considered all $n!$ possible fillings, hence the grouping table gives the complete Hilbert series. $\square$

**Proposition 3.2** *The grouping table gives the association with the fillings corresponding to the standard tableaux.*

**Proof:** Remind that for the hook of shape $\mu = (s, 1^{n-s})$, the Hilbert series will be expressed as the following.

$$ F_{\mu}(q, t) = [n-s]_t! [s-1]_q! \sum_{j_1=2}^{n-s+1} \dots \sum_{j_{s-1}=j_{s-2}+1}^{n} [j_1-1]_t (t^{b_1} + qt^{b_2} + \dots + q^{s-2}t^{b_{s-1}} + q^{s-1}) \quad (7) $$

where $b_i$ is the number of elements in the first column above the (1, 1) cell which are bigger than $j_i$. We start from the case where we have 1-lined set in the grouping table. Note that by knowing the tail part of the standard tableaux in the Garsia-Procesi tree, we know that in this case, the standard tableaux look like Figure 2. Then there are $\binom{n-2}{s-2}$ possibilities for the choice of the rest of the $(s-2)$ elements in the

<figure><img src="image_8.png" /><figcaption>**Fig. 2:** SYT corresponding to 1-lined set in grouping table</figcaption></figure>

first row. Let's say $1, a_1, \dots, a_{s-2}, n, a_i < a_j$ for $i < j$, are chosen in the grouping table. If 1 comes in the (1, 1) cell, then all the elements in the first row to the right and all the elements in the first column above 1 are bigger than 1, so the monomial factor will be $t^{n-s}$. And if $a_1$ comes in the (1, 1) cell, then we gain one power of $q$ since 1 will be to the right of 2 in the first row, and the power of $t$ will depend on $a_i$. Similarly, as $a_i$ comes in the (1, 1) cell, as $i$ gets larger by 1, the power of $q$ will be increased by 1, and finally when $n$ comes in the (1, 1) cell, since there are no bigger elements than $n$, it doesn't have any $t$ powers and the power of $q$ will be $s-1$, since all the rest of the chosen numbers are smaller than $n$. So this case gives the following form of polynomial

$$ [n-s]_t! [s-1]_q! (t^{n-s} + qt^{b_1} + \dots + q^{s-2}t^{b_{s-2}} + q^{s-1}) $$

where $b_i$ is the number of elements in the unchosen ones which are bigger than $a_i$. Note that the fact that we don't have any repeated lines in the grouping table guarantees that we don't get the same polynomials multiple times, since the power of $t$, $b_i$, is the number of unchosen ones to the right of $a_i$ in the grouping table. Secondly, consider the two-lined sets in the grouping table. Again, by the tail looking of the
<figure><img src="image_9.png" /><figcaption>Fig. 3: SYT corresponding to 2-lined set in grouping table</figcaption></figure>

standard tableaux in the tree, we know that this case takes care of the standard tableaux of the kind in Figure 3. Then there are $\binom{n-3}{s-2}$ many choices for the $s-2$ elements in the rest of the first row. Let's say we have chosen $1, a_1, \dots, a_{s-2}, n-1$ in the first line. Then, by the construction, $2, a_1+1, \dots, a_{s-2}+1, n$ will be chosen as well in the second line. Notice that in the grouping table, the lost of one $\circ$ under $n$ in the

<table><caption>Tab. 1: 2-lined set of the grouping table.</caption><thead><tr><th>1</th><th>2</th><th>a<sub>1</sub></th><th>...</th><th>a<sub>s-2</sub></th><th>n-1</th><th>n</th></tr></thead><tbody><tr><td>×</td><td>[ ]</td><td></td><td></td><td></td><td>×</td><td>○</td></tr><tr><td>○</td><td>×</td><td>[ ]</td><td></td><td></td><td></td><td>×</td></tr></tbody></table>

second line means that all the monomial factors from the first line have 1 more power of $t$ than the ones from the second line, hence we get $(1+t)$ factor after we sum them up all. So the polynomial that we get from this case is the following

$$[n-s]_t![s-1]_q!(1+t)(t^{n-s-1} + qt^{b_1} + \dots + q^{s-2}t^{b_{s-s}} + q^{s-1})$$

where $b_i$ is the number of circles in the grouping table to the right of $a_i + 1$. Now, we consider a general case when we have $k$-lined set in the grouping table. This case takes care of the form of standard tableaux in Figure 4. Again, there are $\binom{n-(k+1)}{s-2}$ different possibilities for the different choice of numbers

<figure><img src="image_10.png" /><figcaption>Fig. 4: SYT corresponding to $k$-lined set in grouping table</figcaption></figure>

coming in the rest of the first column. Let's say we choose $1, a_1, \dots, a_{s-2}, n-k+1$ in the first line, then $2, a_1+1, \dots, a_{s-2}+1, n-k+2$ will be chosen in the second line, and finally in the $k^{th}$ line, $k, a'_1, \dots, a'_{s-2}, n$ will be chosen where $a'_i = a_i + k - 1$. Keeping in mind that the right most consecutive circles in the same line will give the common $t$ powers and having the same number of circles and the same pattern means that the $k$ lines have the common factor which comes from the $k^{th}$ line, this case gives the polynomials as follows

$$[n-s]_t![s-1]_q![k]_t(t^{n-s-(k-1)} + qt^{b_1} + \dots + q^{s-2}t^{b_{s-s}} + q^{s-1})$$
where $b_i$ is the number of circles to the right of $a'_i$. In the last set of the grouping table, we choose 1, 2, ..., $s$ in the first line and $n-s+1, ..., n$ in the last (which is $(n-s+1)^{th}$) line. This whole set of fillings will correspond to the standard tableaux of the kind in Figure 5. The fact that there is no $\circ$ between

<figure><img src="image_11.png" /><figcaption>Fig. 5: SYT corresponding to the last line in grouping table</figcaption></figure>

times marks means there is no $t$ powers combined with $q$ and the consecutive circles to the right of the chosen elements will give the common $t$ factors. Adding up them all will give

$$[n-s]_t![s-1]_q![n-s+1]_t(1+q+q^2+\cdots+q^{s-1}).$$

By comparing the polynomials coming from the grouping table and the polynomials added in the Hilbert series, we can confirm that the sets in the grouping table give the polynomials corresponding standard Young tableaux. Since we know that the grouping table gives the complete Hilbert series by Proposition 3.1, we conclude that the grouping table gives the association with fillings to the standard tableaux. $\square$

**Remark 3.3** We note that the grouping table doesn't give the information about what the right corresponding standard tableau is. But since we can know which polynomial the standard tableau gives, once the modified Garsia-Procesi tree is given, by using the powers of $t$ combined with $q$'s, we can trace back the tree to construct the corresponding the standard tableau, as we did in the example for $\mu = (3, 1, 1)$.

## References

[GH93] Adriano M. Garsia and Mark Haiman, *A graded representation model for Macdonald's polynomials*, Proc. Nat. Acad. Sci. U.S.A. **90** (1993), no. 8, 3607-3610. MR MR1214091 (94b:05206)

[GH96] A. M. Garsia and M. Haiman, *Some natural bigraded $S_n$-modules and $q, t$-Kostka coefficients*, Electron. J. Combin. **3** (1996), no. 2, Research Paper 24, approx. 60 pp. (electronic), The Foata Festschrift. MR MR1392509 (97k:05205)

[GP92] A. M. Garsia and C. Procesi, *On certain graded $S_n$-modules and the $q$-Kostka polynomials*, Adv. Math. **94** (1992), no. 1, 82-138. MR MR1168926 (93j:20030)

[HHL05] J. Haglund, M. Haiman, and N. Loehr, *A combinatorial formula for Macdonald polynomials*, J. Amer. Math. Soc. **18** (2005), no. 3, 735-761 (electronic). MR MR2138143 (2006g:05223a)

[Mac] I. G. Macdonald, *A new class of symmetric functions*, Actes du 20e Seminaire Lotharingien 372, 131-171.