# The (m, n)-rational *q*, *t*-Catalan polynomials for *m* = 3 and their *q*, *t*-symmetry

Ryan Kaliszewski, Huilan Li

► To cite this version:

Ryan Kaliszewski, Huilan Li. The (m,n)-rational *q*, *t*-Catalan polynomials for *m* = 3 and their *q*, *t*-symmetry. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.769-780, 10.46298/dmtcs.2500. hal-01337775

HAL Id: hal-01337775

https://hal.science/hal-01337775

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# The (m, n)-rational q, t-Catalan polynomials for m = 3 and their q, t-symmetry

Ryan Kaliszewski† and Huilan Li‡

Department of Mathematics, Drexel University, 3141 Chestnut Street, Philadelphia, PA 19104, USA

**Abstract.** We introduce a new statistic, skip, on rational (3, n)-Dyck paths and define a marked rank word for each path when n is not a multiple of 3. If a triple of valid statistics (area, skip, dinv) are given, we have an algorithm to construct the marked rank word corresponding to the triple. By considering all valid triples we give an explicit formula for the (m, n)-rational q, t-Catalan polynomials when m = 3. Then there is a natural bijection on the triples of statistics (area, skip, dinv) which exchanges the statistics area and dinv while fixing the skip. Thus we prove the q, t-symmetry of (m, n)-rational q, t-Catalan polynomials for m = 3.

**Résumé.** Nous introduisons une nouvelle statistique, le skip, sur les chemins de (3, n)-Dyck rationnels et définissons le mot de rang marqué pour chaque chemin quand n n'est pas un multiple de 3. Si un triplet valide de statistiques (aire, skip, dinv) est donné, nous avons un algorithme pour construire le mot de rang marqué correspondant au triplet. En considérant tous les triplets valides, nous donnons une formule explicite pour les polynômes de q, t-Catalan (m, n)-rationnels quand m = 3. Enfin, il existe une bijection naturelle sur les triplets de statistiques (aire, skip, dinv)) qui échange les statistiques aires et dinv en conservant le skip. Ainsi, nous prouvons la q, t-symétrie des polynômes de q, t-Catalan (m, n)-rationnels pour m = 3.

**Keywords:** Dyck path, Catalan number, rank word

## 1 Introduction

In the early 1990's Garsia and Haiman introduced an important sum of rational functions in q, t, the classic q, t-Catalan polynomial $C_n(q, t)$, which has since been shown to have interpretations in terms of algebraic geometry and representation theory. Now it is well-known that the classic q, t-Catalan polynomial is

$$C_n(q, t) = \sum_{\pi} q^{\mathrm{dinv}(\pi)} t^{\mathrm{area}(\pi)} \quad (1)$$

$$= \sum_{\pi} q^{\mathrm{area}(\pi)} t^{\mathrm{bounce}(\pi)}, \quad (2)$$

<footnote>†Email: rlk72@drexel.edu</footnote>

<footnote>‡Email: huilan@math.drexel.edu</footnote>
where the sums are over all Dyck paths $\pi$ from $(0, 0)$ to $(n, n)$ and (2) is due to Haglund (2003). Though the symmetry problem of the classic $q, t$-Catalan polynomials has been solved through the use of Macdonald polynomials, no bijective proof has been found, where the bijection means an involution on the set of Dyck paths that exchanges (dinv, area) or (area, bounce). For an overview of the classical $q, t$-Catalan polynomials and Dyck paths, see, Garsia and Haiman (1996), Garsia and Haglund (2002), Haglund et al. (2005), and Haglund (2008).

Let $m$ and $n$ be coprime. An $(m, n)$-Dyck path is a path in $m \times n$ lattice which proceeds by north and east steps from $(0, 0)$ to $(m, n)$ and which always remains weakly above the main diagonal $y = \frac{m}{n}x$. The number of full cells between an $(m, n)$-Dyck path $\Pi$ and the main diagonal is denoted area($\Pi$). The collection of cells above a Dyck path $\Pi$ forms an English Ferrers diagram $\lambda(\Pi)$. For any cell $x \in \lambda(\Pi)$, let $\text{leg}(x)$ and $\text{arm}(x)$ denote number of cells in $\lambda(\Pi)$ which are strictly south or strictly east of $x$, respectively. Then define $\text{dinv}(\Pi)$ is the number of cells above the path $\Pi$ satisfying

$$ \frac{\text{arm}(x)}{\text{leg}(x) + 1} < \frac{m}{n} < \frac{\text{arm}(x) + 1}{\text{leg}(x)}. \qquad (3) $$

The $(m, n)$-rational $q, t$-Catalan polynomial is

$$ C_{m,n}(q,t) = \sum_{\Pi} q^{\text{dinv}(\Pi)} t^{\text{area}(\Pi)}, $$

where the sum is over all $(m, n)$-Dyck paths. Note that for every $(m, n)$-Dyck path there is a complementary $(n, m)$-Dyck path with identical statistics. For example,

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

Thus the $(m, n)$-rational $q, t$-Catalan polynomial is symmetric in the parameters $m$ and $n$.

The classic $q, t$-Catalan polynomials correspond to the cases $m = n+1$. It is an open conjecture that the $(m, n)$-rational $q, t$-Catalan polynomials are symmetric in $q$ and $t$. Gorsky and Mazin (2014) have proven the $q, t$-symmetry for the case when $m \le 3$ without giving an explicit formula for the polynomials. Also, independently, Lee et al. (2014) have proven the $q, t$-symmetry when $m \le 4$.

Using the definition of Hikita (2012), parking functions and their statistics can be extended to the $(m, n)$-rational case. Hikita (2012) defined polynomials

$$ H_{m,n}(X;q,t) = \sum_{\text{PF}} t^{\text{area(PF)}} q^{\text{dinv(PF)}} F_{\text{ides(PF)}}(X), \qquad (4) $$

where the sum is over all parking functions PF over all $(m, n)$-Dyck paths and the $F$ are the (Gessel) fundamental quasisymmetric functions indexed by the inverse descent composition of the reading word
of the parking functions PF. When $m = 2$ or $n = 2$, the structure of Hikita's polynomials have been completely described by Leven (2014). Since, for each $(m, n)$-rational Dyck path there is a parking function on that path with the same statistics as the underlying Dyck path, the $(m, n)$-rational $q, t$-Catalan polynomial appears as the coefficient of $F_{(1^n)}$ in the expansion of the Hikita's polynomial $H_{m,n}$. Thus, describing the structure of the $(m, n)$-rational $q, t$-Catalan polynomials is the first step to uncovering the structure of the Hikita's polynomials.

In this paper, we prove that

$$C_{3,n}(q,t) = \sum_{s=0}^{\lfloor n/3 \rfloor} \sum_{\substack{a,d \ge s \\ a+s+d+1=n}} q^{d} t^{a} \qquad (5)$$

$$= \sum_{s=0}^{\lfloor n/3 \rfloor} \sum_{a=s}^{n-2s-1} q^{n-a-s-1} t^a \qquad (6)$$

and the $q, t$-symmetry, i.e.

$$C_{3,n}(q,t) = C_{3,n}(t,q). \qquad (7)$$

For each $(3, n)$-Dyck path, we define a marked rank word corresponding to the path and a new statistic skip on the path or the marked rank word. If a triple of valid statistics area, skip and dinv are given, we have an algorithm to construct a marked rank word corresponding to the triple. Then there is a natural bijection on the triples of statistics (area, skip, dinv) which switched the statistics area and dinv. Thus the symmetry in $q, t$ is proved. Gorsky and Mazin (2014) use a construction similar to our rank words, but the skip statistic in this paper only arises from the markings we place upon the words.

In Section 2, we introduce the notations, background and define the new statistic skip on $(3, n)$-Dyck paths. In Section 3, we show that every $(3, n)$-Dyck path is uniquely determined by the triple of statistics area, skip and dinv. We use this triple to construct an explicit formula for $C_{3,n}(q, t)$. The formula and the uniqueness of the triple allows us to find a unique bijection on $(3, n)$-Dyck paths which switches the area and dinv statistics while fixing skip. Therefore, the $q, t$-symmetry of $(m, n)$-rational $q, t$-Catalan polynomials for $m = 3$ is proved.

## 2 Notation and Background

Suppose $n$ is a non-negative integer that is not divisible by 3. Let $L_{3,n}$ be the finite $\mathbb{Z}$-sublattice in the first quadrant with $n$ rows and 3 columns. We use coordinates to describe the location of each cell in $L_{3,n}$ by first listing the column and then the row. Rows are labeled from bottom to top and columns are labeled from left to right. So the lower-left corner of cell (1,1) rests on the origin. We fill each $(a, b)$ cell in the diagram by its rank: $R(a, b) = -an + 3(b - 1)$. If we denote a cell by a variable, $x$, then we will denote the rank of $x$ by $rk(x)$.

The *rank word* of $L_{3,n}$ is a list of the positive ranks of $L_{3,n}$ in increasing order with those ranks in the first column colored with subscript 1's and those in the second column colored with subscript 2's. The rank word of the sublattice $L_{3,n}$ will be denoted by $rk(L_{3,n})$.

**Example 2.1** The rank word $rk(L_{3,5})$ is $[1_1, 2_2, 4_1, 7_1]$.
One can think of the rank word as being composed of two interleaved sublists, one colored with 1's and the other with 2's. Sublist 1 contains all of the positive integers that are less than $2n$ and equivalent to $2n$ modulo 3, and sublist 2 contains all of the positive integers that are less than $n$ and equivalent to $n$ modulo 3. Thus there are $\lfloor n/3 \rfloor$ entries with subscript 2 and $\lfloor 2n/3 \rfloor$ entries with subscript 1. This means that there are $n-1$ entries in $rk(L_{3,n})$.

The *rank word of a (3, n)-Dyck path* is the rank word of the underlying diagram, $L_{3,n}$, with those entries above the Dyck path are marked. In this paper we will mark entries by putting a box around them.

**Example 2.2 If**

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

then

$$rk(\Pi) = [1_1, [2_2], 4_1, [7_1]].$$

If $\Pi$ is a (3, n)-Dyck path, define its *skip* as a collection of adjacent unboxed entries in the rank word with one or more boxed entries to the right and left. In the above example, the 4 is a *skip* because the 2 and 7 are both in boxes. The 1 is not a *skip* because there are no boxed entries to the left. Define the *skip statistic* of $\Pi$ to be the total number of skips, denoted by $skip(\Pi)$.

**Example 2.3 Let**

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

$$rk(\Pi_1) = [ 1_1, \boxed{2_2}, 4_1, \boxed{5_2}, 7_1, \boxed{10_1}, \boxed{13_1} ]$$

$$rk(\Pi_2) = [ 1_1, 2_2, 4_1, \boxed{5_2}, 7_1, 10_1, \boxed{13_1} ].$$

Therefore skip($\Pi_1$) is 2 because the entries 4 and 7 are each skips. However, skip($\Pi_2$) is only 1 because the 7 and 10 entries comprise a single skip. It is useful to confirm that for the Dyck paths above, $\text{area}(\Pi_1) = 3$, $\text{area}(\Pi_2) = 5$, $\text{dinv}(\Pi_1) = 2$, and $\text{dinv}(\Pi_2) = 1$.

We will turn our discussion to the $\text{dinv}$ statistic for the rest of this section. Note that the ranks in $rk(L_{3,n})$ only lie in the first and second columns of $L_{3,n}$.

**Proposition 2.4** Any cell in the second column that is above a $(3, n)$-Dyck path satisfies the inequality (3), and thus contributes to the $\text{dinv}$.

**Proof:** As stated earlier, there are at most $\lfloor n/3 \rfloor$ cells above the path that lie in the second column. Let $x$ be one such cell. This means that $\text{arm}(x) = 0$ and $\text{leg}(x) < n/3$. Since $\text{arm}(x) = 0$ the left inequality in (3) certainly holds, so we just need to show that $3 \cdot \text{leg}(x) < n$. But this is exactly what we just claimed. $\square$

**Proposition 2.5** Let $\Pi$ be a $(3, n)$-Dyck path. Any cell $x$ in the first column and above $\Pi$ that does not satisfy the inequality (3) must satisfy one of the following:

$$\text{arm}(x) = 1 \text{ and } \text{leg}(x) < \frac{n}{3} - 1, \qquad (8)$$

$$\text{arm}(x) = 0 \text{ and } \text{leg}(x) > \frac{n}{3}. \qquad (9)$$

**Proof:** Let $x$ be a cell in the first column above the path $\Pi$ that does not satisfy the inequality (3). Then $\text{arm}(x) = 1$ or $\text{arm}(x) = 0$.

Suppose $\text{arm}(x) = 1$. Then the inequality (3) becomes

$$\frac{1}{\text{leg}(x) + 1} < \frac{3}{n} < \frac{2}{\text{leg}(x)}.$$

From the right inequality, then we have $\text{leg}(x) < \frac{2n}{3}$. As we previously discussed, there are never more than $\lfloor 2n/3 \rfloor$ positive entries above the path in the first column. So the right inequality is always satisfied. Therefore, the left inequality does not hold, which is equivalent to $\text{leg}(x) < \frac{n}{3} - 1$, which is line (8).

Suppose $\text{arm}(x) = 0$. Then the inequality (3) becomes

$$\frac{0}{\text{leg}(x) + 1} < \frac{3}{n} < \frac{1}{\text{leg}(x)}.$$

so the left inequality is immediately satisfied. Therefore, the right inequality does not hold, which is equivalent to $\text{leg}(x) > \frac{n}{3}$, which is line (9). $\square$
This proposition tells us that the only cells above the Dyck path that do not contribute to the dinv are those without a cell immediately to the right (above the path) with many cells below or those with a cell immediately to the right (above the path) with few cells below. Thus we can have one case or the other, but not both.

Now consider:

**Proposition 2.6** If $\Pi$ is a (3, n)-Dyck path then

$$ \mathrm{area}(\Pi) + \mathrm{skip}(\Pi) + \mathrm{dinv}(\Pi) = |\mathrm{rk}(L_{3,n})| = n - 1. $$

**Proof:** It is sufficient to show that for every cell above the path that does not contribute to the dinv of $\Pi$ there is a unique corresponding skip in the rank word of $\Pi$. Let $x$ be a such cell that does not satisfy the inequality (3). Then by Proposition 2.5, $x$ satisfies one of two cases:

*Case 1:* $\mathrm{arm}(x) = 1$ and $\mathrm{leg}(x) < \frac{n}{3} - 1$. In this case it is certainly true that $\mathrm{leg}(x) < \lfloor n/3 \rfloor$. Let $\underline{x}$ be the cell that is directly $\lfloor n/3 \rfloor$ cells below $x$. We know that $\underline{x}$ must lie below the path. We will show that for each $x_i$ that does not contribute to the dinv, the rank of $\underline{x}_i$ will lie in a distinct skip.

Suppose $x$ is a cell with $\mathrm{arm}(x) = 1$ that does not contribute to the dinv. From $\mathrm{arm}(x) = 1, \mathrm{rk}(x) > n$. So $\mathrm{rk}(\underline{x}) = \mathrm{rk}(x) - 3 \cdot \lfloor n/3 \rfloor > 0$. Let $\hat{x}$ be the cell immediately to the right of $x$. So $\mathrm{rk}(\hat{x}) = \mathrm{rk}(x) - n$. From $n > 3 \cdot \lfloor n/3 \rfloor$,

$$ \mathrm{rk}(\hat{x}) < \mathrm{rk}(\underline{x}) < \mathrm{rk}(x). $$

Since $x$ and $\hat{x}$ are both above the path, $\mathrm{rk}(\underline{x})$ must be in a skip.

Suppose that $x$ and $y$ are two cells with $\mathrm{arm}(x) = \mathrm{arm}(y) = 1$ that do not contribute to the dinv. Assume that $\mathrm{rk}(x) > \mathrm{rk}(y)$. So $\mathrm{rk}(x) - 3 \geq \mathrm{rk}(y)$ and $\mathrm{rk}(y) > \mathrm{rk}(\underline{x})$. From $3 \cdot \lfloor n/3 \rfloor + 3 > n$,

$$ \mathrm{rk}(\underline{y}) = \mathrm{rk}(y) - 3 \cdot \lfloor n/3 \rfloor \leq \mathrm{rk}(x) - 3 \cdot \lfloor n/3 \rfloor - 3 < \mathrm{rk}(x) - n = \mathrm{rk}(\hat{x}). $$

So

$$ \mathrm{rk}(\hat{y}) < \mathrm{rk}(\underline{y}) < \mathrm{rk}(\hat{x}) < \mathrm{rk}(\underline{x}) < \mathrm{rk}(x), $$

i.e., $\mathrm{rk}(\underline{x})$ and $\mathrm{rk}(\hat{y})$ must be in distinct skips.

*Case 2:* $\mathrm{arm}(x) = 0$ and $\mathrm{leg}(x) > \frac{n}{3}$. From $\mathrm{arm}(x) = 0$, $\hat{x}$ must lie below the path. We will show that for each $x_i$ that does not contribute to the dinv, the rank of $\hat{x}_i$ will lie in a distinct skip.

Let $\bar{x}$ be the cell $\lfloor n/3 \rfloor$ below cell $x$. Since $\mathrm{leg}(x) > \frac{n}{3}$ then cell $\bar{x}$ is above the path. From $3 \cdot \lfloor n/3 \rfloor > n$, $\mathrm{rk}(\bar{x}) = \mathrm{rk}(x) - 3 \cdot \lfloor n/3 \rfloor < \mathrm{rk}(x) - n = \mathrm{rk}(\hat{x})$. So we have

$$ \mathrm{rk}(\bar{x}) < \mathrm{rk}(\hat{x}) < \mathrm{rk}(x). $$

Since $x$ and $\bar{x}$ are both above the path, $\mathrm{rk}(\hat{x})$ must be in a skip.

Suppose that $x$ and $y$ are two cells with $\mathrm{arm}(x) = \mathrm{arm}(y) = 0$ that do not contribute to the dinv. Assume that $\mathrm{rk}(x) > \mathrm{rk}(y)$. So $\mathrm{rk}(x) - 3 \geq \mathrm{rk}(y)$ and $\mathrm{rk}(y) > \mathrm{rk}(\bar{x})$. From $3 \cdot \lfloor n/3 \rfloor > n + 3$,

$$ \mathrm{rk}(\hat{y}) = \mathrm{rk}(y) - n \leq \mathrm{rk}(x) - n - 3 < \mathrm{rk}(x) - 3 \cdot \lfloor n/3 \rfloor = \mathrm{rk}(\bar{x}). $$

So

$$ \mathrm{rk}(\bar{y}) < \mathrm{rk}(\hat{y}) < \mathrm{rk}(\bar{x}) < \mathrm{rk}(\hat{x}) < \mathrm{rk}(x), $$

i.e., $\mathrm{rk}(\hat{x})$ and $\mathrm{rk}(\hat{y})$ must be in distinct skips. $\square$
## 3 Uniqueness of rank words

In this section we will show that every (3, n)-Dyck path is uniquely determined by the dinv, area, and skip statistics. That is if $\Pi_1$ and $\Pi_2$ are Dyck paths such that

$$ \text{area}(\Pi_1) = \text{area}(\Pi_2), $$

$$ \text{skip}(\Pi_1) = \text{skip}(\Pi_2), $$

$$ \text{dinv}(\Pi_1) = \text{dinv}(\Pi_2), $$

then $\Pi_1 = \Pi_2$. We know that $\text{area}(\Pi_1) + \text{skip}(\Pi_1) + \text{dinv}(\Pi_1) = |\text{rk}(L_{3,n})| = n - 1$. Therefore it is immediate that both paths must be inscribed in the same lattice. So let us consider an algorithm that generates a rank word, given a Dyck path (later we will prove that it is the rank word associated to the Dyck path):

### Path rank word construction algorithm

**Data:** Three non-negative integers, $a, s$, and $d$ such that $a = \text{area}(\Pi)$, $s = \text{skip}(\Pi)$, and $d = \text{dinv}(\Pi)$ for some (3, n)-Dyck path.

**Result:** The rank word of $\Pi$, $\text{rk}(\Pi)$.

Let $n = a + s + d + 1$ and set $r = \text{rk}(L_{3,n})$, the rank word of the diagram.

Put boxes around the rightmost $d$ entries of $r$.

**For** $i = 1$ to $s$

Moving left, skip all successive entries of the same color.

Box the rightmost entry that hasn't been skipped or boxed.

**end**

**Example 3.1** Consider the (3, 8)-Dyck paths:

<figure><img src="image_5.png" /></figure>
We can compute that $\text{dinv}(\Pi_1) = 2$ and $\text{skip}(\Pi_1) = 2$. If we follow the algorithm we have:

Initial: $[ 1_1, 2_2, 4_1, 5_2, 7_1, \boxed{10_1}, \boxed{13_1} ]$ because $d = 2$.

$i = 1$: $[ 1_1, 2_2, 4_1, \boxed{5_2}, 7_1, \boxed{10_1}, \boxed{13_1} ]$ because we skipped the 7 which has color 1 and boxed the rightmost entry that hasn't been skipped or boxed, the 5.

$i = 2$: $[ 1_1, \boxed{2_2}, 4_1, \boxed{5_2}, 7_1, \boxed{10_1}, \boxed{13_1} ]$ because we skip the 4, and boxed the rightmost entry that hasn't been skipped or boxed, the 2.

Since $s = 2$ we only perform two iterations of the loop, so we are done.

Similarly for $\Pi_2$ we have:

Initial: $[ 1_1, 2_2, 4_1, 5_2, 7_1, 10_1, \boxed{13_1} ]$ because $d = 1$.

$i = 1$: $[ 1_1, 2_2, 4_1, \boxed{5_2}, 7_1, 10_1, \boxed{13_1} ]$ we skip the 10 and the 7 because they are adjacent and have the same color. Then we box the rightmost entry which hasn't been boxed or skipped, which is the 5.

We have finished the algorithm at this point because $s = 1$, so we only performed one iteration of the loop.

This leads us to the following proposition:

**Proposition 3.2** If $\Pi$ is a (3, n)-Dyck path and we use the path rank word construction algorithm to generate a word $\omega(\Pi)$, then $\omega(\Pi) = \text{rk}(\Pi)$.

**Proof:** To construct a (3, n)-Dyck path it is equivalent to choose a number of cells in the first column as well as a number of cells in the second column (subject to constraints) to be above the path. This is essentially choosing a number of entries colored 1 as well as a number of entries colored 2 in the $\text{rk}(L_{3,n})$ to box. Moreover, all of the boxed entries of a specific color must be the rightmost entries. For instance, in the previous example, when we constructed the rank word of $\Pi_1$ we boxed the two rightmost entries colored with 1 and the two rightmost entries colored with 2. Suppose that there are $k$ cells above the path in the first column and $\ell$ cells above the path in the second column.

**Case 1:** Suppose that $k < n/3$. We will show that $k = \text{dinv}(\Pi)$ and $\ell = \text{skip}(\Pi)$. From Proposition 2.5, each cell in column one that has arm equal to zero will contribute to the dinv of $\Pi$ because the leg is certainly less than $n/3$. Every cell in column one that has arm equal to one does not contribute to the dinv.

Suppose $\ell > 0$. Consider the upper left cell, call it $x$. We have $\text{arm}(x) = 1$ and $\text{leg}(x) = k-1 < \frac{n}{3}-1$, i.e., $x$ does not contribute to dinv. The other cells in column one with arm one have shorter legs. They will not contribute to dinv either.

In $\text{rk}(L_{3,n})$ the rightmost $\text{dinv}(\Pi) = k$ entries will be boxed, and they are all color 1. Then the remaining rightmost 1-colored entries will be skipped (due to skipping) and the rightmost $\text{skip}(\Pi) = \ell$ 2-colored entries will be boxed. This concludes the proof of this case.

**Case 2:** Suppose that $k > n/3$ and $k - \ell > \frac{n}{3} + 1$. From Proposition 2.5, $\text{skip}(\Pi)$ is equal to the number of cells with arm zero and whose leg is greater than $n/3$. There are $k - \ell - \lfloor n/3 \rfloor$ such cells so $\text{skip}(\Pi) = k - \ell - \lfloor n/3 \rfloor$ and $\text{dinv}(\Pi) = 2\ell + \lfloor n/3 \rfloor$.

In $\text{rk}(L_{3,n})$ there are $\lfloor n/3 \rfloor$ entries with color 1 on the right and then the entries alternate in color, beginning with 2. Thus we will box $\lfloor n/3 \rfloor$ color 1 entries, then $\ell$ entries with color 2 and $\ell$ entries with
color 1. Since the last entry we boxed was 1, we will begin skipping color 2 entries and box $k - \ell - \lfloor n/3 \rfloor$
color 1 entries. Therefore the rightmost $\ell$ color 2 entries are boxed and the rightmost $\lfloor n/3 \rfloor + \ell +$
$(k - \ell - \lfloor n/3 \rfloor) = k$ color 1 entries are boxed. This completes the proof for this case.

Case 3: Suppose that $k > n/3$ and $k - \ell < \frac{n}{3} + 1$. From Proposition 2.5, skip($\Pi$) is equal to the number of cells with arm equal to one and whose leg is less than $\frac{n}{3} - 1$. There are $\ell - k + \lfloor n/3 \rfloor$ of these. Thus skip($\Pi$) = $\ell - k + \lfloor n/3 \rfloor$ and dinv($\Pi$) = $2k - \lfloor n/3 \rfloor$.

In rk($L_{3,n}$) there are $\lceil n/3 \rceil$ color 1 entries on the right and then the entries alternate in color, beginning
with 2. Thus we will box $\lceil n/3 \rceil$ color 1 entries. Then we will box $2k - \lfloor n/3 \rfloor - \lceil n/3 \rceil = 2k - 2 \cdot \lfloor n/3 \rfloor - 1$
entries: $k - \lfloor n/3 \rfloor$ color 2 entries and $k - \lfloor n/3 \rfloor - 1$ color 1 ones. Then we will box $\ell - k + \lfloor n/3 \rfloor$ color 2
entries at the same time skip $\ell - k + \lfloor n/3 \rfloor$ color 1 entries. So we have boxed $\lceil n/3 \rceil + k - \lfloor n/3 \rfloor - 1 = k$
entries with color 1 and $k - \lfloor n/3 \rfloor + \ell - k + \lfloor n/3 \rfloor = \ell$ entries with color 2. This completes the proof. $\square$

**Remark 1** Any rank word with the rightmost *k* color 1 entries boxed, the rightmost *l* color 2 entries boxed, and *k* ≥ *l* corresponds uniquely to a (3, *n*)-Dyck path.

In order to satisfy these conditions, the following inequalities must hold for any (3, n)-Dyck path Π:

1. $0 \le \text{skip}(\Pi) < n/3,$

$$
2. \text{skip}(\Pi) \le \text{dinv}(\Pi) \le n - 1 - 2 \cdot \text{skip}(\Pi),
$$

3. $\text{skip}(\Pi) \le \text{area}(\Pi) \le n - 1 - 2 \cdot \text{skip}(\Pi).$

The first inequality is clear because either the rank word skips only color 2 entries (of which there are $\lfloor n/3 \rfloor$) or skips only color 1 entries. There are $\lfloor 2n/3 \rfloor$ color 1 entries, but the first $\lfloor n/3 \rfloor$ entries only contribute at most one skip. We know $\lfloor 2n/3 \rfloor - \lfloor n/3 \rfloor \le \lfloor n/3 \rfloor$. When $\lfloor 2n/3 \rfloor - \lfloor n/3 \rfloor < \lfloor n/3 \rfloor$, the first entry of the rank work has color 2. So, totally, there are at most $\lfloor n/3 \rfloor$ entries with color 1 that contribute skips. When $\lfloor 2n/3 \rfloor - \lfloor n/3 \rfloor = \lfloor n/3 \rfloor$, the first entry of the rank work is color 1, which can not be a skip. Again, totally, there are at most $\lfloor n/3 \rfloor$ entries with color 1 that contribute skips.

For the second inequality, if $\text{dinv}(\Pi) \ge \lfloor n/3 \rfloor$, from $\text{skip}(\Pi) < n/3$ we have $\text{skip}(\Pi) \le \text{dinv}(\Pi)$. If $\text{dinv}(\Pi) < \lfloor n/3 \rfloor$, then only color 1 entries are skipped. The number of boxed color 1 entries is $\text{dinv}(\Pi)$ and the number of boxed color 2 entries is $\text{skip}(\Pi)$. Recall that there must be at least as many color 1 ranks boxed as color 2 ranks boxed in the rank word of a path. So $\text{skip}(\Pi) \le \text{dinv}(\Pi)$.

The right part of the second inequality equivalent to skip(Π) ≤ area(Π) (recall that area(Π) + skip(Π) + dinv(Π) = n − 1). It follows from the fact that the area of a path is the number of un-boxed entries in the rank word and a skip must always skip at least one entry. From this argument one can also see that the second and third inequalities are actually equivalent.

The definition of $\omega$, above, does not actually require a path. If we have three non-negative integers that satisfy the above inequalities we can generate a rank word, call it $\omega(\text{area}, \text{skip}, \text{dinv})$.

**Corollary 3.3** Given three non-negative integers *a*, *s*, *d* that satisfy

1. $s \le a,$

2. $s \le d,$

3. $a + s + d + 1$ is not divisible by 3,
then there is a unique $(3, a + s + d + 1)$-Dyck path $\Pi$ with $a = \text{area}(\Pi)$, $s = \text{skip}(\Pi)$, and $d = \text{dinv}(\Pi)$.

**Proof:** Set $n = a + s + d + 1$. We only need to check that $\omega(a, s, d)$ has enough entries to ensure that $s$ skips can be performed. If $d \ge \lfloor n/3 \rfloor$ then each skip corresponds to two entries, one skipped and one not skipped. So we need $2s + d \le s + a + d$, which is true. If $d < \lfloor n/3 \rfloor$ then the first skip and the rightmost $d$ entries together encompass $\lfloor n/3 \rfloor + 1$ of the total entries. The remaining skips then correspond to two entries. Again, we need $2(s - 1) + \lfloor n/3 \rfloor + 1 \le s + a + d$, which is equivalent to

$$s - 1 + \lfloor n/3 \rfloor \le a + d. \qquad (10)$$

Recall that area is the unboxed entries. Since there were $\lfloor n/3 \rfloor - d$ skipped entries at the first skip and $s - 1$ skipped entries in the middle, $a \ge \lfloor n/3 \rfloor - d + s - 1$, which is exactly inequality (10). $\square$

**Remark 2** Note that if $s \le a, d$ and $n = a + s + d + 1$ then immediately $s < n/3$.

This leads us to the following theorem:

**Theorem 3.4**

$$C_{3,n}(q,t) = \sum_{s=0}^{\lfloor n/3 \rfloor} \sum_{\substack{a,d \ge s \\ a+s+d+1=n}} q^d t^a \qquad (11)$$

$$= \sum_{s=0}^{\lfloor n/3 \rfloor} \sum_{a=s}^{n-2s-1} q^{n-a-s-1} t^a \qquad (12)$$

**Theorem 3.5** There is a unique bijection on the set of $(3, n)$-Dyck paths that exchanges area and dinv while fixing skip.

**Proof:** This follows from the fact that the area, skip, and dinv statistics uniquely define a path and for every $(a, s, d)$ triple corresponding to a path, $(d, s, a)$ also corresponds to a path. $\square$

**Corollary 3.6** The $(3, n)$-rational $q, t$-Catalan polynomials are symmetric in $q$ and $t$, i.e.,

$$C_{3,n}(q,t) = C_{3,n}(t,q). \qquad (13)$$

This theorem leads us in two natural directions for further research. First, generalize the skip statistic to arbitrary $(m, n)$-Dyck paths, which would give insight into finding an involution that exchanges area and dinv. Second, completely describe Hikita's polynomial $H_{3,n}$ (4) since we know the coefficient of $F_{(1^n)}$.

Acknowledgements

We would like to thank Adriano Garsia and Jim Haglund for the motivation to work on this problem. We wish to thank Emily Leven for inspiring conversations on this topic. We are also grateful to the anonymous reviewers for providing useful comments and papers to compare to our work.
References

A. M. Garsia and J. Haglund. A proof of the *q*, *t*-Catalan positivity conjecture. *Discrete Math.*, 256 (3):677–717, 2002. ISSN 0012-365X. doi: 10.1016/S0012-365X(02)00343-6. URL http://dx.doi.org/10.1016/S0012-365X(02)00343-6. LaCIM 2000 Conference on Combinatorics, Computer Science and Applications (Montreal, QC).

A. M. Garsia and M. Haiman. Some natural bigraded $S_n$-modules and $q, t$-Kostka coefficients. *Electron. J. Combin.*, 3(2):Research Paper 24, approx. 60 pp. 1996. ISSN 1077-8926. URL http://www.combinatorics.org/Volume_3/Abstracts/v3i2r24.html. The Foata Festschrift.

E. Gorsky and M. Mazin. Compactified Jacobians and *q*, *t*-Catalan numbers, II. *J. Algebraic Combin.*, 39(1):153–186, 2014. ISSN 0925-9899. doi: 10.1007/s10801-013-0443-z. URL http://dx.doi.org/10.1007/s10801-013-0443-z.

J. Haglund. Conjectured statistics for the *q*, *t*-Catalan numbers. *Adv. Math.*, 175(2):319–334, 2003. ISSN 0001-8708. doi: 10.1016/S0001-8708(02)00061-0. URL http://dx.doi.org/10.1016/S0001-8708(02)00061-0.

J. Haglund. *The q,t-Catalan numbers and the space of diagonal harmonics*, volume 41 of *University Lecture Series*. American Mathematical Society, Providence, RI, 2008. ISBN 978-0-8218-4411-3; 0-8218-4411-3. With an appendix on the combinatorics of Macdonald polynomials.

J. Haglund, M. Haiman, N. Loehr, J. B. Remmel, and A. Ulyanov. A combinatorial formula for the character of the diagonal coinvariants. *Duke Math. J.*, 126(2):195–232, 2005. ISSN 0012-7094. doi: 10.1215/S0012-7094-04-12621-1. URL http://dx.doi.org/10.1215/S0012-7094-04-12621-1.

T. Hikita. Affine Springer fibers of type A and combinatorics of diagonal coinvariants. *ArXiv e-prints*, Mar. 2012.

K. Lee, L. Li, and N. A. Loehr. Combinatorics of certain higher *q*, *t*-Catalan polynomials: chains, joint symmetry, and the Garsia-Haiman formula. *J. Algebraic Combin.*, 39(4):749–781, 2014. ISSN 0925-9899. doi: 10.1007/s10801-013-0466-5. URL http://dx.doi.org/10.1007/s10801-013-0466-5.

E. Leven. Two special cases of the Rational Shuffle Conjecture. *DMTCS FPSAC Proceedings*, pages 789–800, 2014.