# A generalization of (q,t)-Catalan and nabla operators

N. Bergeron<fnref n="1" />† and F. Descouens<fnref n="1" />,<fnref n="2" /> and M. Zabrocki<fnref n="1" />‡

**Abstract.** We introduce non-commutative analogs of k-Schur functions and prove that their images by the non-commutative nabla operator ▼ is ribbon Schur positive, up to a global sign. Inspired by these results, we define new filtrations of the usual (q, t)-Catalan polynomials by computing the image of certain commutative k-Schur functions by the commutative nabla operator ∇. In some particular cases, we give a combinatorial interpretation of these polynomials in terms of nested quantum Dick paths.

**Résumé.** Nous introduisons des analogues non commutatifs des $k$-fonctions de Schur et nous prouvons que leurs images par l'opérateur nabla non commutatif ▼ est Schur-rubans positif, à un signe global près. Guidés par ses résultats, nous définissons de nouvelles filtrations des (q, t)-nombres de Catalan usuels en calculant l'image de certaines $k$-fonctions de Schur par l'opérateur nabla commutatif ∇. Dans certains cas particuliers, nous donnons une interprétation combinatoire de ces polynômes en termes de chemins de Dyck imbriqués.

**Keywords:** $k$-Schur functions, nabla operator, (q, t)-Catalan numbers

## 1 Introduction

To study Macdonald polynomials and diagonal harmonics, F. Bergeron et. al [1] introduced an operator ∇ on symmetric functions with many interesting properties. One of the most striking examples of the simple beauty of this operator is that $∇(e_n)$ encodes the (q, t)-Frobenius image of the symmetric group module of diagonal harmonics. In particular, the coefficient $⟨∇(e_n), s_1^n⟩$ is the (q, t)-Catalan number $C_n(q, t)$. Much work has been done on these spaces to find a combinatorial realization of these symmetric functions and their coefficients, see [4, 8, 9, 10]. There are many more conjectures in [1] which state that ∇ applied to various symmetric functions is Schur positive (up to a global sign) with coefficient in $Z^+[q, t]$. This suggests that these images might be (q, t)-Frobenius images of some symmetric group modules.

In their approach to study Macdonald polynomials, L. Lapointe, A. Lascoux and J. Morse [15] have introduced $k$-Schur functions. As it turns out, these special functions have an importance of their own

<footnote n="1">¹Department of Mathematics and Statistics, York University, Toronto, Ontario M3J 1P3, CANADA</footnote>

<footnote n="2">²The Fields Institute, 222 College Street, Toronto, Ontario, M5T 3J1, CANADA</footnote>

<footnote>†partially supported by NSERC and CRC</footnote>

<footnote>‡Descouens and Zabrocki are partially supported by NSERC and NSF</footnote>
and are linked to other areas of research interest. For our purposes, they enrich the space of symmetric functions with much more to study.

In [2], we have started to develop a theory of Macdonald polynomials for non-commutative symmetric functions and defined a nabla operator ▽ on this space. We have shown that some of the conjectures for ∇ have analogous statement for ▽, and we have been able to provide a proof of them. In this paper, we continue our investigation of non-commutative symmetric functions. In Section 2, we show that the remaining conjectures of [1] on ∇ also have analogous statement for ▽ and are able to prove them. In Section 3, we then introduce a theory of non-commutative analogue of k-Schur functions. We show there that ▽ applied to these functions also give rise to positivity results. Guided by this, we conjecture in Section 4 that ∇ on k-Schur functions (with a slight twist on the parameter) is Schur positive up to a global sign in some special cases. This leads us to define (q, t)-Catalan at level k which give rise to an increasing filtration of the usual (q, t)-Catalan. We provide some conjectures of these k-level (q, t)-Catalan numbers and develop some results in Section 5.

## 2 Basic definitions

Let $X = \{x_1, x_2, \dots\}$ be a sequence of (commutative) variables. Let $h_n(X) = \sum_{i_1 \le i_2 \le \dots \le i_n} x_{i_1} x_{i_2} \cdots x_{i_n}$. This is the complete homogeneous symmetric function of degree $n$ in the variables $\bar{X}$. The space of symmetric functions $Sym$ over a field $F$ is the polynomial ring $F[h_1, h_2, \dots]$, where $h_n = h_n(X)$. This is a graded ring (in fact a Hopf algebra) where $\deg(h_n) = n$. It is convenient to index a basis of $Sym$ with sequences $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ where $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_k > 0$. Such a sequence $\lambda$ is a partition of $n$ if $n = \lambda_1 + \dots + \lambda_k$ and has length $\ell(\lambda) = k$. There are many interesting bases of this space. We are mostly concern with the homogeneous basis, $h_\lambda = h_{\lambda_1} h_{\lambda_2} \cdots h_{\lambda_k}$; the elementary basis $e_\lambda = e_{\lambda_1} e_{\lambda_2} \cdots e_{\lambda_k}$ where $e_n$ is defined by the recurrence $e_0 = 1$ and $\sum_{i+j=n} (-1)^i h_i e_j$; and the Schur basis given by $s_\lambda = \det[h_{\lambda_i+i-j}]$.

Let us now recall some basic definitions of Macdonald polynomials. The modified Macdonald polynomials $\tilde{H}_\lambda(X; q, t)$ is defined by

$$ \tilde{H}_{\lambda}(X; q, t) = t^{n(\lambda)} \sum_{\mu} K_{\mu\lambda}(q, 1/t) s_{\mu}(X), \quad (1) $$

where $K_{\mu\lambda}(q, t)$ Macdonald version of the Kosta coefficients defined in VI.8 of [18]. Let us denote by $Q'_\lambda(X; t)$ the twisted Hall-Littlewood polynomial indexed by $\lambda$. The linear operator $\nabla$ of [1] is defined by

$$ \nabla(\tilde{H}_{\lambda}(X; q, t)) = t^{n(\lambda)} q^{n(\lambda')} \tilde{H}_{\lambda}(X; q, t). \quad (2) $$

There exist a long list of conjectures about the action of $\nabla$ on different bases of symmetric functions. For many of them there exist a combinatorial model (proved and conjectural) which explains the different properties.

The k-Schur functions $s_\lambda^{(k)}(X; t)$, with the first part of $\lambda$ smaller than or equal to $k$, forms a basis of the space $\mathcal{L}\{Q'_\lambda(X; t) : \lambda_1 \le k\}$ where $\mathcal{L}$ represents the vector space linear span of the elements. We are interested in this short note only in the explicit definition of the elements $s_{1n}^{(k)}(X; t)$. For these symmetric
functions, we simply define them to be

$$s_{1n}^{(k)}(X; t) = t^{k \binom{n \operatorname{div} k}{2} + (n \operatorname{mod} k)(n \operatorname{div} k)} \omega \left( Q'_{(k^n \operatorname{div} k), n \operatorname{mod} k} \left( X; \frac{1}{t} \right) \right). \quad (3)$$

For a definition of the other k-Schur functions with the parameter t, we refer the reader to the references [15, 16]. Note that these two references provide two different definitions which are conjectured to be equivalent. In the case of the indexing partition equal to 1^n we can show that they are both equal to (3).

## 3 Non-commutative symmetric functions

The number of elements on a sequence $\alpha$ is called the length and is denoted by $l(\alpha)$. A sequence of positive integers $\alpha = (\alpha_1, \dots, \alpha_{l(\alpha)})$ is a composition of size $n$, written $\alpha = n! / \alpha_1! \alpha_2! \dots \alpha_{l(\alpha)}!$. A composition $\alpha$ is usually represented by a rim-hook diagram whose rows have lengths $\alpha_1, \dots, \alpha_{l(\alpha)}$ (read from top to bottom).

In the theory of non-commutative symmetric functions, we are mainly interested in two kinds of concatenations. The first one is the usual concatenation defined, for $\alpha$ and $\beta$, by $\alpha \cdot \beta = (\alpha_1, \alpha_2, \dots, \alpha_{l(\alpha)}, \beta_1, \beta_2, \dots, \beta_{l(\beta)})$. The second operation is the attachment defined by $\alpha | \beta = (\alpha_1, \alpha_2, \dots, \alpha_{l(\alpha)-1}, \alpha_{l(\alpha)}+\beta_1, \beta_2, \dots, \beta_{l(\beta)})$. The descent set $D(\alpha)$ of a composition $\alpha$ is defined as the set $D(\alpha) = \{\alpha_1, \alpha_1 + \alpha_2, \dots, \alpha_1 + \dots + \alpha_{l(\alpha)-1}\}$. The descent set $D(\alpha)$ characterizes the composition $\alpha$ and is of size $l(\alpha) - 1$. It is easy to see that the compositions of $n$ are in one-to-one correspondence with the subsets of $\{1, 2, \dots, n-1\}$.

For any composition $\alpha$, the major index is defined by $n(\alpha) = \sum_{i \in D(\alpha)} i = \sum_{i=1}^{l(\alpha)} (i-1)\alpha_{l(\alpha)+1-i}$. For two compositions $\alpha$ and $\beta$, we can refine the previous statistic by defining $c(\alpha, \beta)$ as $c(\alpha, \beta) = \sum_{i \in D(\alpha) \cap D(\beta)} i$.

There is a natural partial order $\leq$ on the set of compositions of $n$, which is called the refinement order. We say that $\alpha$ is finer than $\beta$, written $\alpha \leq \beta$, if $D(\beta) \subseteq D(\alpha)$.

There exists three standard involutions on compositions. The first one is the reverse of composition defined by

$$\overleftarrow{\alpha} = (\alpha_{l(\alpha)}, \alpha_{l(\alpha)-1}, \dots, \alpha_1). \qquad (4)$$

If the descent set of $\alpha$ is $D(\alpha) = \{i_1, \dots, i_k\}$ then $D(\overleftarrow{\alpha}) = \{|\alpha| - i_1, |\alpha| - i_2, \dots, |\alpha| - i_k\}$. The second involution is the complement of a composition. For any composition $\alpha$ of $n$, the complement $\alpha^c$ of $\alpha$ is the composition with descent set the complement of $D(\alpha)$, i.e. $D(\alpha^c) = \{1, 2, \dots, n-1\} \setminus D(\alpha)$. The third one is the analog of the conjugate of a partition and corresponds to flipping the composition about the line $y = x$. It can be defined as $\alpha' = \overleftarrow{\alpha}^c = \overleftarrow{\alpha}^c$.

### 3.1 Non-commutative symmetric functions

For more detailed references about non-commutative symmetric functions see [7]. We will follow our usual convention for symmetric functions with fonts in bold to indicate non-commutative symmetric functions.

Let $A$ be a sequence of non commutative variables and $X$ the corresponding sequence where variables commute. For any composition $\alpha$, we define the non-commutative homogeneous functions by $h_{\alpha}(A) = h_{\alpha_1}(A) \dots h_{\alpha_{l(\alpha)}}(A)$, where $h_n(A)$ is a non-commutative element analogous to the usual commutative homogeneous function $h_n(X)$. The product of two non-commutative homogeneous symmetric functions is given by $h_{\alpha}(A)h_{\beta}(A) = h_{\alpha \cdot \beta}(A)$. The space of non-commutative symmetric functions
Sym over a field $F$ is defined by $\text{Sym} = F\langle h_1, h_2, \dots \rangle$. The elementary functions are defined for all compositions $\alpha$ by $e_\alpha(A) = e_{\alpha_1}(A)e_{\alpha_2}(A)\dots e_{\alpha_{l(\alpha)}}(A)$, where $e_n(A) = \sum_{\alpha \vdash n} (-1)^{n+l(\alpha)}h_\alpha(A)$
The analogs of Schur functions are the ribbon Schur functions defined for any composition $\alpha$ by $\mathbf{R}_\alpha(A) = \sum_{\alpha \le \beta} (-1)^{l(\alpha) - l(\beta)} \mathbf{h}_\beta(A)$. The multiplication rule of two ribbon Schur functions is given by $\mathbf{R}_\alpha(A)\mathbf{R}_\beta(A) = \mathbf{R}_{\alpha \cdot \beta}(A) + \mathbf{R}_{\alpha|\beta}(A)$. We define the commutative evaluation of a non-commutative symmetric function through the surjective map

$$ \chi: \begin{array}{ccc} \text{Sym} & \to & \text{Sym} \\ \mathbf{h}_{\alpha}(A) & \mapsto & h_{\alpha}(X) \end{array}. \qquad (5) $$

The image of the ribbon Schur function $\mathbf{R}_\alpha(A)$ by $\chi$ is the commutative skew Schur function indexed by the skew partition corresponding to the ribbon $\alpha$.

## 3.2 Deformations of non-commutative symmetric functions

As described in Section 2, the modified Hall-Littlewood functions $Q'_\lambda(X; t)$ and modified Macdonald polynomials $\tilde{H}_\lambda(X; q, t)$ are $t$-analogs and $(q, t)$-analogs of the complete functions $h_\lambda(X)$. In this section, we recall basic statements on the non-commutative analogs of these deformations defined in [2]. We can mention that different non-commutative analogs for Hall-Littlewood functions and Macdonald polynomials have been considered in [12, 13] with multivariate parameters and by L. Tevlin related to the reference [19].

In [2], the authors define non-commutative analogs of Hall-Littlewood functions by

$$ \mathbf{H}_{\alpha}(A; t) = \sum_{\beta \ge \alpha} t^{c(\alpha, \beta^c)} \mathbf{R}_{\beta}(A). \qquad (6) $$

The non-commutative Hall-Littlewood functions $\mathbf{H}_\alpha(A; t)$ satisfy the specializations

$$ \mathbf{H}_{\alpha}(A; 0) = \mathbf{R}_{\alpha}(A) \quad \text{and} \quad \mathbf{H}_{\alpha}(A; 1) = \mathbf{h}_{\alpha}(A). \qquad (7) $$

For a composition which is a hook $\alpha = (1^a, b)$, the commutative image of $\mathbf{H}_\alpha(A; t)$ coincide with the commutative modified Hall-Littlewood functions $Q'_{(b,1^a)}(X; t)$, i.e. $\chi(\mathbf{H}_{(1^a,b)}(A; t)) = Q'_{(b,1^a)}(X; t)$. In [2], we can find more detailed statements on these functions. For example, There is an explicit non-commutative formula for the product of two Hall-Littlewood functions in terms of Hall-Littlewood functions. The authors also give a Pieri formula, creation operators and a factorization formula at primitive roots of unity.

In [2], the authors also give a definition for non-commutative analogs of Macdonald polynomials in $\text{Sym}$. These functions are defined by

$$ \mathbf{H}_{\alpha}(A; q, t) = \sum_{\beta \vdash |\alpha|} t^{c(\alpha, \beta^c)} q^{c(\alpha', \beta')} \mathbf{R}_{\beta}(A). \qquad (8) $$

There is a modified version of these non-commutative Macdonald polynomials which have nicer properties and have an interpretation in the representation theory of the Hecke algebra at $q = 0$. They are defined for all compositions by

$$ \tilde{\mathbf{H}}_{\alpha}(A; q, t) = t^{n(\alpha)} \mathbf{H}_{\alpha} \left( A; q, \frac{1}{t} \right) = \sum_{\beta \vdash |\alpha|} t^{c(\alpha, \beta)} q^{c(\alpha', \beta')} \mathbf{R}_{\beta}(A). \qquad (9) $$
In the theory of commutative symmetric functions, the operator $∇$, defined in (2), has interesting properties. In [2], the authors give a non-commutative analog $\triangleleft$ of this operator in the space **Sym**.

**Definition 1** The non-commutative operator $\triangleleft$ is defined by $\triangleleft(\tilde{\mathbf{H}}_\alpha(A; q, t)) = t^{n(\alpha)}q^{n(\alpha')}\tilde{\mathbf{H}}_\alpha(A; q, t)$.

In the case of commutative symmetric functions, Lascoux gives the conjecture that the commutative symmetric functions $∇(Q'_\lambda(X; \frac{1}{t}))$ is Schur positive up to a global sign. We now prove a similar conjecture in the space of non-commutative symmetric functions **Sym**. Let $\tilde{\mathbf{H}}_\alpha(A; t) = \tilde{\mathbf{H}}_\alpha(A; 0, t)$ be the modified Hall-Littlewood functions and let $\tilde{\mathbf{H}}^0(A; t)$ be the vector $(\tilde{\mathbf{H}}_\alpha(A; t))_{\alpha \neq n}$.

**Theorem 2** The image of the non-commutative modified Hall-Littlewood functions by the operator $\triangleleft$ is ribbon Schur positive, up to a global sign.

# 4 Non-commutative analogue of k-Schur functions

We define an analogue of k-Schur functions in the space of non-commutative symmetric functions **Sym**. To find k-Schur functions, Lapointe, Lascoux and Morse originally observed that certain linear combinations of Hall-Littlewood functions were Schur positive and essentially give atoms that make up the Macdonald symmetric functions.

Let $\mathbf{Sym}^{(\gamma)}$ be the linear span of non-commutative Hall-Littlewood functions $\mathbf{H}_\alpha(A; t)$ such that $\alpha \le \gamma$. More precisely,

$$ \mathbf{Sym}^{(\gamma)} = \mathcal{L}\{\mathbf{H}_{\alpha}(A; t) \text{ such that } \alpha \models |\gamma| \text{ and } \alpha \le \gamma\}. \quad (10) $$

This space is a homogeneous component of a natural analog of the subspace of $\mathbf{Sym}^{(k)}$ generated by the modified Hall-Littlewood functions $Q'_\lambda(X; t)$ indexed by partitions with first part less than $k$.

For any vector $\mathbf{B}(A) = (\mathbf{B}_\alpha(A))_{\alpha \neq n}$ of basis elements $\mathbf{B}_\alpha(A)$ of **Sym**, we denote by $\mathbf{B}|_{\gamma}(A)$, the vector of elements of $\mathbf{B}_\alpha(A)$ which are living in the space $\mathbf{Sym}^{(\gamma)}$.

**Definition 3** Let $\gamma$ be a composition. The $\gamma$-ribbon Schur functions $\mathbf{R}_\alpha^{(\gamma)}(A; t)$ is defined by

$$ \mathbf{R}_{\alpha}^{(\gamma)}(A; t) = \sum_{D(\alpha) \setminus D(\beta) \subseteq D(\gamma)} t^{c(\alpha, \beta^c)} \mathbf{R}_{\beta}(A). \quad (11) $$

The compositions $\beta$ which appear in the sum are those which appear in the interval of the composition poset (for the refinement order) between $\alpha$ and the composition with descent set $D(\alpha) \setminus D(\gamma)$.

**Example 4** For $n = 5$, the expansion of the (131)-ribbon Schur function $\mathbf{R}_{1121}^{(131)}(A)$ is

$$ \mathbf{R}_{1121}^{(131)}(A; t) = \mathbf{R}_{1121}(A) + t \mathbf{R}_{221}(A) + t^4 \mathbf{R}_{113}(A) + t^5 \mathbf{R}_{23}(A). \quad (12) $$

Directly from Definition 3, the $\gamma$-ribbon Schur functions reduce to usual functions for special case of the level $\gamma$

$$ \mathbf{R}_{\alpha}^{(|\alpha|)}(A; t) = \mathbf{R}_{\alpha}(A) \quad \text{and} \quad \mathbf{R}_{\alpha}^{(\alpha)}(A; t) = \mathbf{H}_{\alpha}(A; t). \quad (13) $$

At this moment, it is not clear that the $\gamma$-ribbon Schur functions form a basis of the subspace $\mathbf{Sym}^{(\gamma)}$. The following theorem gives us an explicit expression for the $\gamma$-ribbon Schur functions in terms of Hall-Littlewood functions.
**Theorem 5** The set of elements $\{\mathbf{R}_{\alpha}^{(\gamma)}(A; t)\}_{\alpha \le \gamma}$ is a basis $\mathbf{Sym}^{\gamma}$. We have the following formulas for the change of bases between Hall-Littlewood functions and $(\gamma)$-ribbon Schur functions

$$ \mathbf{H}_{\alpha}(A; t) = \sum_{\alpha \le \beta \le \gamma} t^{c(\alpha, \beta^c)} \mathbf{R}_{\beta}^{(\gamma)}(A; t) \quad \text{and} \quad \mathbf{R}_{\alpha}^{(\gamma)}(A; t) = \sum_{\alpha \le \beta \le \gamma} (-1)^{l(\alpha) - l(\beta)} t^{c(\alpha, \beta^c)} \mathbf{H}_{\beta}(A; t). \qquad (14) $$

**Theorem 6** Let $\gamma$ be a composition and $\tilde{\gamma}$ the composition of weight $|\gamma|$ with descent set $D(\tilde{\gamma}) = D(\gamma)\setminus\{i\}$ for some integer $i$.

$$ \mathbf{R}_{\alpha}^{(\gamma)}(A; t) = \sum_{\substack{\alpha \le \beta \\ D(\alpha) \setminus D(\beta) \subseteq D(\gamma) \setminus D(\tilde{\gamma})}} t^{c(\alpha, \beta^c)} \mathbf{R}_{\beta}^{(\tilde{\gamma})}(A; t). \qquad (15) $$

This theorem is an analog of the branching rules from $k$-Schur functions to $(k+1)$-Schur functions in the commutative case which are still conjectural. The theorem means that there exists a family of branching rules for a given composition $\alpha$.

**Example 7** An example of branching rule from the level (1111) to the level (13)

$$ \mathbf{R}_{(1111)}^{(1111)}(A; t) = \mathbf{R}_{(1111)}^{(13)}(A; t) + t^2 \mathbf{R}_{(121)}^{(13)}(A; t) + t^3 \mathbf{R}_{(112)}^{(13)}(A; t) + t^5 \mathbf{R}_{(13)}^{(13)}(A; t). \qquad (16) $$

**Theorem 8** For any composition $\alpha \le \gamma$, the non-commutative Macdonald polynomials $\mathbf{H}_{\alpha}(A; q, t)$ and $\tilde{\mathbf{H}}_{\alpha}(A; q, t)$ are $\gamma$-Schur positive. More precisely,

$$ \mathbf{H}_{\alpha}(A; q, t) = \sum_{\beta \le \gamma} t^{c(\alpha, \beta^c)} q^{c(\alpha', \beta')} \mathbf{R}_{\beta}^{(\gamma)}(A) \quad \text{and} \quad \tilde{\mathbf{H}}_{\alpha}(A; q, t) = \sum_{\beta \le \gamma} t^{c(\alpha, \beta^c)} q^{c(\alpha', \beta')} \mathbf{R}_{\beta}^{(\gamma)}\left(A; \frac{1}{t}\right). \qquad (17) $$

**Theorem 9** The image of the modified $\gamma$-Schur functions in the parameter $1/t$ by the non-commutative operator $\bigtriangledown$ is ribbon Schur positive, up to a global sign.

**Remark:** There are many ways for defining non-commutative analogs of commutative symmetric functions. The fact that $\bigtriangledown$ of these analogs are ribbon-Schur positive, up to a global sign, is an interesting property which is shared with special cases of the commutative version as we will see in the next section.

Theorem 9 in the space of non-commutative symmetric functions $\mathbf{Sym}$ yields us to consider the same idea in the space of commutative symmetric functions $\mathbf{Sym}$. We obtain similar results but they are still conjectural. These computations allow us in the next section to define generalizations of $(q, t)$-Catalan numbers and to show some of their properties.

## 5 $(q, t)$-Catalan numbers of level $k$

We study a special case of Lascoux's conjecture for the action of $\nabla$ on a Hall-Littlewood symmetric function. This special case permits us to define new $(q, t)$-polynomials $C_n^{(k)}(q, t)$ with positive coefficients. These polynomials are a generalization of the usual $(q, t)$-Catalan numbers $C_n(q, t)$ defined in [6]. By specializing $q = 1$ and $t = 1$, we obtain different generalizations of Catalan numbers than those given in [11].
## 5.1 (q, t)-Catalan numbers

Let first recall the definition and a combinatorial interpretation of the (q, t)-Catalan numbers given in [4, 5, 6].

**Definition 10** ((q,t)-Catalan numbers) The (q, t)-Catalan numbers are the polynomials in q and t defined by

$$C_n(q, t) = \langle \nabla(e_n(X)), s_{1^n}(X) \rangle. \qquad (18)$$

**Example 11** The sixth (q, t)-Catalan number $C_6(q, t)$ is represented by the following matrix, where the entry $(i, j)$ is the coefficient of $q^i t^{\binom{n}{2}-j}$.

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

Garsia and Haglund prove that these polynomials are in $\mathbb{N}[q, t]$ by giving a combinatorial interpretation in terms of Dick paths. We briefly recall this interpretation which is generalized in [17] for interpreting $\langle s_{\lambda}(X), s_{1^n}(X) \rangle$.

A Dick path of length $n$ is a lattice path from $(0, 0)$ to $(n, n)$ consisting of $n$ north steps and $n$ east steps that never go below the line $y = x$. We denote by $DP_n$ the set of all the Dyck paths of length $n$. Dick paths of length $n$ are in bijection with sequences $(g_0, \dots, g_{n-1})$ of $n$ nonnegative integers satisfying the two following conditions

$$\left\{ \begin{array}{l} g_0 = 0, \\ g_{i+1} \le g_i + 1, \quad \forall i < n-1. \end{array} \right. \qquad (19)$$

The $i$-th entry $g_i$ of the sequence $g$ corresponds to the number of squares between the north step of the $i$-th row of the Dick path and the diagonal $y = x$. Such sequences are called Dyck sequences. We denote by $DS_n$ the set of all the Dick sequences of length $n$. On these sequences, there are two statistics, *area* and *dinv*, defined by Haglund, Haiman and al. in [8, 9]. The *area* associated to a Dick sequence $g$ is defined by $\text{area}(g) = \sum_{i=1}^{n-1} g_i$. On the corresponding Dick path, this statistic is the number of complete lattice squares between the diagonal $y = x$ and the lattice path. The statistic of diagonal inversions *dinv* is defined on a Dick sequence $g$ by $\text{dinv}(g) = \sum_{0 \le i < j < n} \chi(g_i - g_j \in \{0, 1\})$. We recall a graphical interpretation of this statistic on Dyck path. Let us call a *north point* a point where a north step arrive. Two north points give a contribution of 1 in *dinv*, if they are in the same diagonal or if the second point is in the diagonal just before the diagonal of the first one. These statistics permit to have the following
combinatorial interpretation for the $(q, t)$-Catalan numbers

$$C_n(q, t) = \sum_{g \in DS_n} t^{\text{area}(g)} q^{\text{dinv}(g)}. \qquad (20)$$

The original combinatorial interpretation of [5] uses the statistic *bounce* of a Dick path instead of the statistic *dinv*.

**Example 12** The $(q, t)$-Catalan number $C_3(q, t) = q^3 + q^2t + qt^2 + qt + t^3$ can be computing using the following 5 Dyck paths.

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

The black linked points correspond to pairs of points which give an contribution of 1 in dinv.

## 5.2 Definition of the filtration

By definition, the $k$-Schur functions indexed by column partitions $(1^n)$ are generalizations of the elementary functions $e_n(X)$ in the space of symmetric functions over $\mathbb{C}(t, q)$. Hence, we can replace elementary functions in Definition 10 by $k$-Schur functions $s_{1^n}^{(k)}(X; t)$ in order to obtain some generalizations of the $(q, t)$-Catalan numbers.

**Definition 13** Let $k$ be a positive integer and $n$ such that $k \le n$. A generalization $C_n^{(k)}(q, t)$ of $(q, t)$-Catalan numbers can be defined by

$$C_n^{(k)}(q, t) = \left\langle \nabla \left( s_{1^n}^{(k)} \left( X; \frac{1}{t} \right) \right), s_{1^n}(X) \right\rangle, \qquad (21)$$

where $\langle, \rangle$ is the usual scalar product on symmetric functions.

Now, assuming Conjecture 3 of [1] we have the following proposition.

**Proposition 14** The family of polynomials $(C_n^{(k)}(q, t))_{k \ge 1}$ is an increasing filtration of the usual $(q, t)$-Catalan numbers $C_n^{(k)}(q, t)$. More precisely, we have

$$\forall k \ge 1, C_n^{(k+1)}(q, t) - C_n^{(k)}(q, t) \in \mathbb{N}[t, q] \quad \text{and} \quad \forall k \ge n, C_n^{(k)}(q, t) = C_n(q, t). \qquad (22)$$

**Proof:** The first statement is a consequence of Conjecture 3 of [1]. The second statement of the proposition follows immediately from the following stability property of the $k$-Schur functions $\forall k \ge n$, $s_{1^n}^{(k)}(X; t) = e_n(X)$. □
**Example 15** Using the same conventions as in Example 11, the generalized (q, t)-Catalan numbers $C_6^{(k)}(q, t)$ are given by the following matrices

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

By specializing $q = 1$ and $t = 1$ in the generalized (q, t)-Catalan numbers $C_n^{(k)}(q, t)$, we obtain a filtration $C_n^{(k)}$ of the usual Catalan numbers $C_n$.

**Proposition 16** The polynomial $C^{(k)}(q, 1)$ (where $t = 1$) is a generating function for the number of Dyck paths which lie below the Dyck path with (k steps north and k steps east) repeated n div k times followed by n mod k steps north and n mod k steps east.

**Example 17** The triangle of the specialization of the generalized (q, t)-Catalan at $q = 1$ and $t = 1$ is

<table><thead><tr><th>n : k</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>1</td><td>2</td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>1</td><td>2</td><td>5</td><td></td><td></td><td></td></tr><tr><th>4</th><td>1</td><td>4</td><td>5</td><td>14</td><td></td><td></td></tr><tr><th>5</th><td>1</td><td>4</td><td>10</td><td>14</td><td>42</td><td></td></tr><tr><th>6</th><td>1</td><td>8</td><td>25</td><td>28</td><td>42</td><td>132</td></tr></tbody></table>

## 5.3 Combinatorial interpretation

We have some conjectural combinatorial models for special cases of these generalizations of (q, t)-Catalan numbers. We use the combinatorics of nested quantum Dick paths defined in [17] which explain combinatorially the expansion of $\nabla s_{\lambda}(X)$ on the Schur basis. More precisely, we have a combinatorial interpretation for the polynomials $C_n^{(k)}(q, t)$ for $k > n/2$.

### 5.3.1 Combinatorial interpretation of $\nabla(s_{\lambda}(X))$

In [17], the authors give a conjectural combinatorial interpretation for the (q, t)-polynomials obtained by the scalar product $\langle \nabla(s_{\lambda}(X)), s_{1^n}(X) \rangle$. We recall this interpretation which is the basis of our combinatorial interpretation for $C_n^{(k)}(q, t)$.
To a given partition $\lambda = (\lambda_1, \dots, \lambda_p)$, we can associate a sequence of $\lambda_1$ nonnegative integers $n = (n_0, \dots, n_{\lambda_1})$. We call this sequence the dissection sequence of $\lambda$. We say that a rim-hook is a border rim-hook of $\lambda$ if all its cells coincide with all the cells of the northeast frontier of $\lambda$. The entry $n_0$ is the number of cells of the border rim-hook $R_0$ of $\lambda'$ starting on the top row of $\lambda'$. The next entry $n_1$ is computed using the same procedure on the partition obtained by removing $R_0$ from $\lambda'$. If there is no border rim-hook starting at the $(\lambda_1 - 1)$-th row, we set $n_1 = 0$. The remaining entries of $n$ are obtained by iteration of this algorithm.

**Example 18** The sequence for the partition $\lambda = (53222)$ is $n = (9, 0, 0, 5, 0)$ as described by the picture

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

We define the spin of a partition $\lambda$ by $\text{sp}(\lambda) = \sum_R (h(R) - 1)$, where the sum is on all the border rim-hooks of $\lambda'$ and $h(R)$ the height of these ribbons. And the sign of a partition $\lambda$ is defined by $\text{sgn}(\lambda) = (-1)^{\text{sp}(\lambda)}$. The spin of $\lambda = (53222)$ is $\text{sp}(\lambda) = 4 + 1 = 5$ and consequently $\text{sgn}(\lambda) = -1$.

We also need to define the diagonal inversion adjustment by $\text{adj}(\lambda) = \sum_{i=0}^{\lambda_1 - 1} \lambda'_i \chi(n_i > 0)$. The adjustment is the sum of the row indices of $\lambda'$ (starting from the top of the diagram of the partition) where a border rim-hook starts. For the partition $\lambda = (53222)$, we have $\text{adj}(\lambda) = 1 + 4 = 5$. Let $\lambda = (\lambda_1, \dots, \lambda_p)$ be a partition of dissection sequence $n = (n_0, \dots, n_{\lambda_1 - 1})$. Let $\Pi = (\pi_0, \dots, \pi_{\lambda_1 - 1})$ be a sequence of Dyck paths $\pi_i$ of length $n_i$ from $(i, i)$ to $(i + n_i, i + n_i)$. If $n_i$ is equal to 0, $\pi_i$ is a degenerate Dyck path consisting in a single vertex at $(i, i)$. The sequence $\Pi$ is a nested Dyck path for the partition $\lambda$, if for all $i \neq j$, no edge or vertex of $\pi_i$ coincides with any edge or vertex of $\pi_j$. We denote by $NDP_\lambda$ the set of all the nested Dyck paths for the partition $\lambda$.

**Example 19** A nested Dyck path of $NDP_{(53222)}$ of dissection sequence $n = (9, 0, 0, 5, 0)$.

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

The encoding of Dyck paths using Dick sequences can be extended to nested Dyck paths. Let $\Pi = (\pi_0, \dots, \pi_{l-1})$ a nested Dyck path. The Dyck configuration corresponding to $\Pi$ is an $l$-tuple of words $G = (g^{(0)}, \dots, g^{(l-1)})$, where $g^{(i)}$ is the Dyck sequence encoding the Dyck path $\pi_i$. The indexing of the letters in these Dyck sequences are chosen to match the alignment of paths in the picture. In the following we identify nested Dyck paths and their corresponding Dyck configurations.

**Example 20** The nested Dyck path of Example 19 corresponds to the following Dyck configuration

$$ G = \left( \begin{array}{ccccccccc} g^{(0)}: & 0 & 1 & 2 & 2 & 2 & 3 & 4 & 3 & 3 \\ g^{(1)}: & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ g^{(2)}: & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ g^{(3)}: & \cdot & \cdot & \cdot & 0 & 1 & 1 & 0 & 1 & \cdot \\ g^{(4)}: & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \end{array} \right). $$
The statistic area and dinv can be extended to nested Dyck paths. The area of a nested Dyck path G is the sum of the areas of the Dyck paths of G, i.e. area(G) = $\sum_{i=0}^{l-1} \sum_{i \le j < i + n_i} g_j^{(i)}$. The diagonal inversion statistic for a nested Dyck path G is defined by

$$ \mathrm{dinv}(G) = \mathrm{adj}(\lambda) + \sum_{a,b,u,v} \chi(g_a^{(u)} - g_b^{(v)} = 1) \chi(a \le b) \\ + \sum_{a,b,u,v} \chi(g_a^{(u)} - g_b^{(v)} = 0) \chi((a < b) \text{ or } (a = b \text{ and } u < v)). \qquad (23) $$

The dinv of a nested Dyck path G = (g(0),...,g(l)) corresponds to the sum of the dinv of each Dyck path g(i) plus the number of pairs of points coming from different g(i)'s which form an inversion. A pair of points which form an inversion and which are in the same row are just counted one time.

**Example 21** area(G) and dinv(G) of G of Example 19 are area(G) = 24 and dinv(G) = 37.

The conjecture of [17] is the following expression for the coefficient of $\nabla(s_\lambda(X))$ on the Schur function $s_{1^n}(X)$

$$ \langle \nabla(s_{\lambda}(X)), s_{1^n}(X) \rangle = \operatorname{sgn}(\lambda) \sum_{G \in \mathcal{NDP}_{\lambda}} q^{\operatorname{area}(G)} t^{\operatorname{dinv}(G)}. \qquad (24) $$

**Example 22** For $\lambda = (221)$, we have $\langle \nabla(s_{221}(X)), s_{15}(X) \rangle = -q^6 t^3 - q^5 t^4 - q^4 t^5 - q^3 t^6$. The dissection vector of the partition $\lambda = (221)$ is $n = (4, 1)$ and $\mathrm{adj}(\lambda) = 1$. The combinatorial interpretation is given by the following four nested Dyck paths where we have linked the pairs of points which give a contribution of 1 in dinv.

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

### 5.3.2 Combinatorial interpretation for the filtration

We give an explicit combinatorial interpretation of the generalizations of (q,t)-Catalan numbers in the cases of $C_n^{(n-1)}(q,t)$ and $C_n^{(n-2)}(q,t)$ using the combinatorial materials given in the previous section. The ideas of these interpretations are based on bijections between different sets of nested Dyck paths which explain why the terms are canceling in the right, giving at the end a polynomial with only positive coefficients (up to a global sign).

**For level $n-1$**

For the level $n-1$, we have an explicit characterization of the Schur functions which appear in the $k$-Schur functions we are considering. Using equation (3) we have that

$$ s_{1^n}^{(n-1)}(X; t) = s_{1^n}(X) + t s_{21^{n-2}}(X). \qquad (25) $$

**Theorem 23 (Combinatorial interpretation of $C_n^{(n-1)}(q,t)$)** Let $DP_n^{(1,1)}$ denotes the set of Dyck paths which go through the lattice point $(1,1)$. The generalized $(q,t)$-Catalan numbers of level $(n-1)$ are given by

$$ C_n^{(n-1)}(q,t) = \sum_{g \in DP_n^{(1,1)}} q^{\mathrm{area}(g)} t^{\mathrm{dinv}(g)}. \qquad (26) $$
**Proof:** From Equation (25), we know that we have to use the combinatorial interpretation of $\langle \nabla s_{1^n}(X), s_{1^n}(X) \rangle$ and $\langle \nabla s_{21^{n-2}}(X), s_{1^n}(X) \rangle$. As $s_{1^n}(X) = e_n(X)$, we also know that $\langle \nabla s_{1^n}(X), s_{1^n}(X) \rangle = \sum_{g \in DP_n} q^{\text{area}(g)} t^{\text{dinv}(g)}$, where the sum is over all the Dyck paths of length $n$. Let now compute the combinatorial interpretation of $\langle \nabla s_{21^{n-2}}(X), s_{1^n}(X) \rangle$. The dissection vector of the partition $(21^{n-2})$ is $n = (n, 0)$ as described by the following picture

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

This implies that the nested Dyck paths corresponding to the partition $(21^{n-2})$ are the sequences of two non intersecting Dyck paths $G = (g^{(0)}, g^{(1)})$ such that: Dyck paths $g^{(0)}$ is a Dyck path of length $n$ avoiding the lattice point $(1, 1)$ and Dyck paths $g^{(1)}$ is reduced to the Dyck path of size 0 at the lattice point $(1, 1)$. Hence, we have

$$ \langle \nabla s_{21^{n-2}}(X), s_{1^n}(X) \rangle = - \sum_{G \in NDP_{21^{n-2}}} q^{\text{area}(G)} t^{\text{dinv}(G)}. \quad (27) $$

Let denote by $DP_n^{(1,1)^c}$ the set of all Dyck paths of size $n$ avoiding the lattice point $(1, 1)$. Let consider the following bijection $\Phi_n$ defined by

$$ \Phi_n : \begin{array}{ccc} NDP_{21^{n-2}} & \longrightarrow & DP_n^{(1,1)^c} \\ (g^{(0)}, g^{(1)}) & \longmapsto & g^{(0)}. \end{array} \quad (28) $$

The compatibility of $\Phi_n$ with the statistics area and dinv is given by

$$ \left\{ \begin{array}{l} \text{dinv}(\Phi_n(g^{(0)}, g^{(1)})) = \text{dinv}(g^{(0)}) + 1, \\ \text{area}(\Phi_n(g^{(0)}, g^{(1)})) = \text{area}(g^{(0)}). \end{array} \right. \quad (29) $$

To see this, let $G = (g^{(0)}, g^{(1)})$ be a nested Dyck path of $NDP_{21^{n-2}}$. By definition of $G$, the corresponding Dyck configuration is of the form

$$ \left( \begin{array}{ccccc} g^{(0)} & : & 0 & 1 & g^{(0)} \\ g^{(1)} & : & 0 & \cdot & \cdot \end{array} \right) . \quad (30) $$

Hence, the Dyck path $g^{(1)}$ always give a contribution of 1 in the $\text{dinv}(G)$. Using the property of $\Phi_n$ given in (29), Equation (27) can be rewritten as

$$ \langle s_{21^{n-2}}(X), s_{1^n}(X) \rangle = -t \sum_{g \in DP_n^{(1,1)^c}} q^{\text{area}(g)} t^{\text{dinv}(g)}. \quad (31) $$

Hence, we have for generalized $(q, t)$-Catalan of level $(n-1)$

$$ C_n^{(n-1)}(q,t) = \sum_{g \in DP_n} q^{\text{area}(g)} t^{\text{dinv}(g)} - \sum_{g \in DP_n^{(1,1)^c}} q^{\text{area}(g)} t^{\text{dinv}(g)} = \sum_{g \in DP_n^{(1,1)}} q^{\text{area}(g)} t^{\text{dinv}(g)}. \quad (32) $$

□
The concatenation of Dyck paths $g^{(1)} \cdot g^{(0)}$ corresponds to the following Dyck sequence

$$g^{(1)} \cdot g^{(0)} = (g_1^{(1)} = 0, 0, 1, 2, g_3^{(0)}, \dots, g_{n-2}^{(0)}). \qquad (39)$$

The first 0 gives now a contribution of 1 to $\mathrm{dinv}(g^{(1)} \cdot g^{(0)})$. Hence,

$$\mathrm{dinv}(\Psi_n(g^{(0)}, g^{(1)})) = \mathrm{dinv}(g^{(1)} \cdot g^{(0)}) = 1 + \mathrm{dinv}(g^{(0)}). \qquad (40)$$

Finally, by combining (38) and (40), we have $\mathrm{dinv}(\Psi_n(g^{(0)}, g^{(1)})) = \mathrm{dinv}(G) - 2$. Using (36), we have

$$\langle \nabla s_{221^{n-4}}(X), s_{1^n}(X) \rangle = -t^2 \sum_{g \in DP_n^{(1,1),(3,2)^c}} t^{\mathrm{dinv}(g)} q^{\mathrm{area}(g)}. \qquad (41)$$

Hence, using the expression (33) of $k$-Schur functions and combinatorial interpretation for level $n-1$, we obtain

$$\langle \nabla s_{1n}^{(n-2)} \left( X; \frac{1}{t} \right), s_{1n}(X) \rangle = \sum_{g \in DP_n^{(1,1)}} t^{\mathrm{dinv}(g)} q^{\mathrm{area}(g)} - \sum_{g \in DP_n^{(1,1),(3,2)^c}} t^{\mathrm{dinv}(g)} q^{\mathrm{area}(g)} = \sum_{g \in DP_n^{(1,1),(3,2)}} t^{\mathrm{dinv}(g)} q^{\mathrm{area}(g)}. \qquad \square$$

**Lemma 26** Generalized Catalan numbers of level $(n-2)$ are given by $C_n^{(n-2)}(1, 1) = 2C_{n-2}$.

**Proof:** There are two configurations for the first two steps of Dyck paths in $DP_n^{(1,1),(3,2)}$ given in the following picture

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

And it is well known that the number of lattice paths of length $n-3$ starting at the lattice point (3, 2) is $C_{n-2}$. Hence the cardinality of $DP_n^{(1,1),(3,2)}$ is $2C_{n-2}$. $\square$

**For other levels**

For the other levels, we can give an algorithm which describe how the cancellation are behaving correctly but it is not as nice as for the case of the diagonal $n-1$ and $n-2$.

**References**

[1] F. Bergeron, A. Garsia, M. Haiman and G. Tesler, *Identities and Positivity Conjectures for Some Remarkable Operators in the Theory of Symmetric Functions*, Methods and Applications of Analysis, **6**, 3, (1999), 363-420.

[2] N. Bergeron, M. Zabrocki, *q and q, t-analogs of non-commutative symmetric functions*, Discrete Maths, **298**, 1, (2005), 79-103.
[3] F. Descouens, *Making research on symmetric functions using MuPAD-Combinat*, *Lectures Notes in Computer Sciences*, Springer, **4151**, (2006).

[4] A. Garsia and J. Haglund, *A positivity result in the theory of Macdonald polynomials*, Proc. Natl. Acad. Sci, USA, **98**, 8, (2001), 4313-4316 (electronic).

[5] A. Garsia and J. Haglund, *A proof of the (q,t)-Catalan positivity conjecture*, Dis. Math. **256**, 3, (2002), 677-717.

[6] A. Garsia and M. Haiman, *A remarkable q, t-Catalan sequence and q-Lagrange inversion*, J. Algebraic Combinatorics **5**, (1996), 191-244.

[7] I.M. Gelfand, D. Krob, B. Leclerc, A. Lascoux, V.S. Retakh and J.-Y. Thibon, *Non commutative symmetric functions*, Adv. Math. **112**, (1995), 218-348.

[8] M. Haiman, J. Haglund, N. Loehr, J. Remmel and A. Ulyanov, *A combinatorial formula of the diagonal coinvariants*, Duke Math. J., **126** (2005), pp. 195-232.

[9] J. Haglund, *Conjectured statistics for the (q, t)-Catalan numbers*, Adv. Maths, **175**, 2, (2003), 319-334.

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

[11] P. Hilton and J. Pedersen, *Catalan numbers, their generalization, and their uses*, Math. Intell., **13**, (1991), 64-75.

[12] F. Hivert, *Hecke Algebra, Difference Operators, and Quasi-Symmetric Functions*, Adv. Math. **155** (2000), 181-238.

[13] F. Hivert, A. Lascoux and J.-Y. Thibon, *Non-commutative symmetric functions and quasi-symmetric functions with two and more parameters*, Preprint (2001) arXiv:math/0106191

[14] F. Hivert and N. Thiéry, *MuPAD-Combinat, an open source package for research in algebraic combinatorics*, Séminaire Lotharingien de Combinatoire, **51**, (2003), 70p electronic.

[15] L. Lapointe, A. Lascoux and J. Morse, *Tableaux atoms and a new Macdonald positivity conjecture*, Duke Math. J., **116**, 1, (2003), 103-146.

[16] L. Lapointe and J. Morse, *Schur functions analogs for a filtration of the symmetric functions space*, J. Combin. Theory Ser. A, **101**, 2, (2003), 191-224.

[17] N. Loehr and G. Warrington, *Nested quantum Dyck paths and $\nabla(s_\lambda)$*, Preprint (2007) arXiv:0705.4608.

[18] I.G. Macdonald, *Symmetric Functions and Hall-Polynomials*, Oxford Mathematical Monographs, Oxford Univ. Press, second edition, 1995.

[19] L. Tevlin, Noncommutative Analogs of Monomial Symmetric Functions, Cauchy Identity, and Hall Scalar Product, arXiv:0712.2201.