# Chromatic symmetric functions
of Dyck paths and $q$-rook theory

Laura Colmenarejo  Department of Mathematics and Statistics, UMass Amherst,
U.S.A<EMAIL_ADDRESS>https://sites.google.com/view/l-colmenarejo/home ,  Alejandro H. Morales
Department of Mathematics and Statistics, UMass Amherst, U.S.A
<EMAIL_ADDRESS>https://people.math.umass.edu/ ahmorales/ and  Greta
Panova  Department of Mathematics, University of Southern California, U.S.A.
<EMAIL_ADDRESS>https://sites.google.com/usc.edu/gpanova/home

###### Abstract.

The chromatic symmetric function (CSF) of Dyck paths of Stanley and its
Shareshian–Wachs $q$-analogue have important connections to Hessenberg
varieties, diagonal harmonics and LLT polynomials. In the, so called, abelian
case they are also curiously related to placements of non-attacking rooks by
results of Stanley–Stembridge (1993) and Guay-Paquet (2013). For the
$q$-analogue, these results have been generalized by Abreu–Nigro (2020) and
Guay-Paquet (private communication), using $q$-hit numbers. Among our main
results is a new proof of Guay-Paquet’s elegant identity expressing the
$q$-CSFs in a CSF basis with $q$-hit coefficients. We further show its
equivalence to the Abreu–Nigro identity expanding the $q$-CSF in the
elementary symmetric functions. In the course of our work we establish that
the $q$-hit numbers in these expansions differ from the originally assumed
Garsia-Remmel $q$-hit numbers by certain powers of $q$. We prove new
identities for these $q$-hit numbers, and establish connections between the
three different variants.

L. Colmenarejo was partially supported by the AMS-Simons Travel Grant and by
MTM2016-75024-P, A. H. Morales was partially supported by the NSF grant
DMS-1855536, and G. Panova was partially supported by the NSF grant
DMS-1939717.

keywords: chromatic symmetric functions, abelian Hessenberg varieties, Dyck
paths, $q$-hit numbers, $q$-rook numbers.

##  1\. Introduction

Ever since their introduction in 1995 in [Sta95], the chromatic symmetric
functions have been this mysterious object combining the misleading simplicity
of graphs with the powerful tools of symmetric functions. Graph colorings
present some of the hardest problems in combinatorics111Informally, but also
formally as an NP-complete problem., and nice formulas there qualify as
miracles rather than general rules. It is thus even more appealing that the
chromatic symmetric functions, and their $q$-generalizations, are a source of
beautiful results and striking conjectures222Most notably the $e$-positivity
Conjecture 1.1 of Stembridge-Stanley [SS93], refined further by Shareshian-
Wachs [SW16].. The chromatic symmetric functions have found significant
connections beyond combinatorics – to _Hessenberg varieties_ [SW16], _diagonal
harmonics_ [CM18], and Macdonald polynomials [AP18, HW20].

In this paper we bring to light such an unusually nice combinatorial formula,
relating the _$q$ -rook theory_ which comes from generalizations of
permutations and their inversions, and chromatic symmetric functions for Dyck
paths of bounce two, aka abelian case. We give an elementary proof of the
strikingly elegant identity of Guay-Paquet (Theorem 1.3) which expresses the
chromatic symmetric function for an arbitrary path given by partition
$\lambda$ in terms of the chromatic symmetric functions for rectangles with
coefficients the very combinatorial $q$-hit numbers. Along the way we
establish numerous new identities for $q$-hit and $q$-rook numbers, give an
elementary proof of Theorem 1.2, and pose many conjectures stemming from our
findings. Our ultimate goal is to understand the chromatic symmetric functions
with more relations and connections, which could lead not only to a proof of
the $e$-positvity Conjecture 1.1, but also to a combinatorial interpretation
of these coefficients. The technique of symmetry-breaking used in our proof of
Theorem 1.3 could be extended beyond the abelian case as long as there is a
suitable conjectured expression for the coefficients in the $e$-basis.

###  1.1. Definitions and main results

Let $G$ be a graph with vertices $\\{v_{1},v_{2},\ldots,v_{n}\\}$ that are
totally ordered $v_{1}<v_{2}<\cdots<v_{n}$. In [Sta95], Stanley defined the
chromatic symmetric function (CSF) $X_{G}({\bf x})$ of $G$ as

$X_{G}({\bf x})=\sum_{\kappa:V\to\mathbb{P},\text{ proper}}{\bf
x}^{\kappa}=\sum_{\kappa:V\to\mathbb{P},\text{
proper}}x_{1}^{\\#\kappa^{-1}(1)}x_{2}^{\\#\kappa^{-1}(2)}\cdots,$

where $\mathbb{P}=\\{1,2,3,\ldots\\}$, ${\bf x}=(x_{1},x_{2},\ldots)$, and the
sum is over the proper colorings of the vertices of $G$.

Stanley and Stembridge [SS93] conjectured that the chromatic symmetric
functions expand with positive coefficients in the basis $\\{e_{\mu}\\}$ of
elementary symmetric functions for the graphs coming from Dyck paths in the
following way. Given a Dyck path $d$ from $(0,0)$ to $(n,n)$, let $G(d)$ be
the graph with vertices $\\{1\ldots n\\}$ and edges $(i,j)$, $i<j$ if and only
if the cell $(i,j)$ is below the path $d$ (see Figure 1). These are also the
incomparability graphs of unit interval orders or graphs obtained from
Hessenberg sequences.

Figure 1. The Dyck path
$d=\mathsf{n}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}}\mathsf{e}\mathsf{n}\mathsf{e}\mathsf{n}\mathsf{e}\mathsf{e}^{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}}$
associated to the partition $\lambda=(2,1)\subset 2\times 3$ and the
corresponding graph $G(\lambda)$. Each cell below the path $d$ corresponds to
an edge of the graph. An example of a proper coloring would be
$\kappa(1)=2,\kappa(2)=3,\kappa(3)=1,\kappa(4)=2,\kappa(5)=3$ which has
$\operatorname{asc}(\kappa)=4$.

Shareshian–Wachs [SW16] introduced a quasisymmetric version of $X_{G}({\bf
x})$ defined by

$\displaystyle X_{G}({\bf x},q)=\sum_{\kappa:V\to\mathbb{P},\text{
proper}}q^{\operatorname{asc}(\kappa)}{\bf x}^{\kappa},$

where $\operatorname{asc}(\kappa)$ is the number of edges $\\{v_{i},v_{j}\\}$
of $G$ with $i<j$ and $\kappa(v_{i})<\kappa(v_{j})$.

For the graphs $G(d)$ coming from Dyck paths, the quasisymmetric function
$X_{G(d)}({\bf x},q)$ is actually symmetric and Shareshian–Wachs gave a
refinement of the Stanley–Stembridge conjecture for this Catalan family of
graphs.

######  Conjecture 1.1 (Stanley–Stembridge, Shareshian–Wachs).

Let $d$ be a Dyck path. Then the coefficients of $X_{G(d)}({\bf x},q)$ in the
elementary basis are in $\mathbb{N}[q]$.

This conjecture has been verified independently and by different techniques by
Cho–Huh [CH19b], Harada–Precup [HP19], and Abreu–Nigro [AN21] for the case of
so-called abelian Dyck paths (corresponding to abelian Hessenberg varieties),
which are defined as Dyck paths $d$ of from $(0,0)$ to $(m+n,m+n)$ of the form
$\mathsf{n}^{m}w(\lambda)\mathsf{e}^{n}$ where $w(\lambda)$ is the encoding in
north ($\mathsf{n}$) and east ($\mathsf{e}$) steps of the partition
$\lambda\subset n\times m$ (see Figure 4A). We denote the associated graph by
$G(\lambda)$ and the chromatic symmetric function by $X_{\lambda}({\bf
x},q):=X_{G(\lambda)}({\bf x},q)$.

The symmetric functions $X_{\lambda}({\bf x},q)$ corresponding to abelian Dyck
paths are deeply related to the $q$-rook theory of Garsia–Remmel [GR86] as we
illustrate with the next two identities that use the following notation

$[n]_{k}=[n][n-1]\cdots[n-k+1],\quad[n]!=[n]_{n},\quad\begin{bmatrix}n\\\
k\end{bmatrix}=\frac{[n]_{k}}{[k]!},$

where $[x]=(1-q^{x})/(1-q)$.

We define $q$-hit numbers of rectangular boards of size $n\times m$ that we
denote as $H_{j}^{m,n}(\lambda)$ by a change of basis equation (2.1) involving
the _Garsia–Remmel $q$-rook numbers_. These $q$-hit numbers are polynomials in
$q$, satisfying $\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)=[m]_{n}$, and at $q=1$
give the number of placements of $n$ non-attacking rooks in an $n\times m$
board ($n\leq m$) with $j$ rooks in the board of $\lambda$. We show that these
$q$-hit numbers $H_{j}^{m,n}(\lambda)$ are symmetric polynomials in
$\mathbb{N}[q]$ and are realized by a statistic defined by Dworkin [Dwo98]
(see Theorem 2.9). In the case of a square board $m=n$, these $q$-hit numbers
$H_{j}^{n}(\lambda):=H_{j}^{n,n}(\lambda)$ are up to a power of $q$ equal to
the _Garsia–Remmel $q$-hit numbers_ (Proposition H.1) which are symmetric
unimodal polynomials in $\mathbb{N}[q]$ realized by different statistics by
Haglund and Dworkin (see [HR01]).

Abreu–Nigro gave an expansion of $X_{\lambda}({\bf x},q)$ in the elementary
basis in terms of $q$-hit numbers of square boards. This result is a
$q$-analogue of a special case of a result of Stanley–Stembridge [SS93, Thm.
4.3].

######  Theorem 1.2 (Abreu–Nigro [AN21]).

Let $\lambda$ be partition inside an $n\times m$ board with
$\ell(\lambda)=k\leq\lambda_{1}$. Then

$\displaystyle X_{\lambda}({\bf x},q)$
$\displaystyle=\left[k\right]!H_{k}^{m+n-k}(\lambda)\cdot
e_{m+n-k,k}+\sum_{j=0}^{k-1}q^{j}\left[j\right]!\left[m+n-2j\right]H_{j}^{m+n-j-1}(\lambda)\cdot
e_{m+n-j,j}.$

Our first main result is an elementary proof of an unpublished identity of
Guay-Paquet333Private communication [GPa].444This identity was independently
found by Lee and Soh [LS, Thm. 24] after this article was posted. in Section 4
that expands $X_{\lambda}({\bf x},q)$ in terms of chromatic symmetric
functions for rectangular shape with coefficients given by the $q$-hit numbers
of rectangular boards defined above.

This result appears as a $q$-analogue of a special case of [GPb, Prop. 4.1
(iv)].

######  Theorem 1.3 (Guay-Paquet [GPa]).

Let $\lambda$ be partition inside an $n\times m$ board ($n\leq m$). Then

$X_{\lambda}({\bf
x},q)=\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\cdot
X_{m^{j}}({\bf x},q).$

Our second result is a direct elementary proof of Theorem 1.2 following from
Theorem 1.3 and using our third result which is the definition and properties
of the $q$-hit numbers $H_{*}^{*,*}(\lambda)$, including a deletion
contraction relation, that we derive in Sections 3 and in the Appendix.

###  1.2. Old and new methods

The original proofs of the two statements above use a linear relation
satisfied by $X_{G(d)}({\bf x},q)$ called the modular relation [AN21, AS22,
GPb]. Our proof of Theorem 1.3 uses a simple inductive approach on both the
size $m+n$ of the graph and the number $M$ of variables (see Lemma 4.3). Our
approach ignores/breaks the symmetry of the chromatic symmetric function by
splitting the function as a polynomial in $x_{k}$, whose coefficients are
polynomials in $x_{1},\ldots,x_{k-1}$. The ultimate identities are derived
from identities of the coefficients; the $q$-hit numbers. Such an approach
could work in a more general setting if the coefficients in the expansion have
some recursive combinatorial structure. Moreover, following the recursion it
could be extended to a bijection, similar to RSK. The bottlenecks in this
approach are the necessary new $q$-hit identities, which we derive after
extensive use of generating functions555A fully combinatorial/bijective proof
would be highly desirable and could completely unravel the combinatorics for
CSFs in the abelian case. See Section 7.. The derivation of Theorem 1.2
follows from other $q$-hit identities, which can be proven also using
deletion-contraction on $q$-hit and $q$-rook numbers. Note that deletion-
contraction on the classical CSFs itself is not directly applicable due to the
inhomogeneity of the relation.

Along the way we prove new $q$-hit identities (Section 3 and Appendix) and
unravel a mystery on different combinatorial statistics leading to different
kinds of $q$-hit numbers (see Section 7.1 and the Appendix) that have been
mixed up in the literature. In particular, we establish new relations of
$q$-rook numbers and $q$-hit numbers (Lemmas 3.3, 3.4, 3.5, and 5.5) that
develop further the $q$-rook theory of rectangular boards [LM18].

As a Corollary to the fact that Theorems 1.2 and 1.3 are in essence linear
relation between chromatic symmetric functions, we establish that the same
linear relation holds of the unicellular LLT polynomials, see Section 6.1.

###  1.3. Organization

In Sections 2 and 3 we give the definitions of $q$-hit numbers and prove the
necessary identities used later on. Our elementary proof of Theorem 1.3 is in
Section 4, and the proof of Theorem 1.2 is in Section 5. In Section 6 we
discuss variations on these problems, expansions in other bases like CSFs for
staircase shapes, applications to LLT polynomials, and some conjectures.

In Appendices G, H, and K we present the Garsia–Remmel $q$-hit numbers and
their relation to the $q$-hit numbers appearing in Theorems 1.2,1.3, and the
deletion-contraction relations for each variant. Appendices I, J have the
proofs of Theorem 2.9 and the symmetry of the $q$-hit numbers, respectively.

## Acknowledgements

We thank Mathieu Guay-Paquet for generously sharing the notes [GPa] with
Theorem 1.3 as well as Alex Abreu, Per Alexandersson, Sergi Elizalde, Jim
Haglund, Philippe Nadeau, Antonio Nigro, Alexei Oblomkov, Franco Saliola,
Bruce Sagan, John Shareshian, and Michelle Wachs for insightful discussions.
We also thank the anonymous referees for the comments and suggestions. This
work was facilitated by computer experiments using Sage [The19] and its
algebraic combinatorics features developed by the Sage-Combinat community
[SCc08].

##  2\. Background on $q$-rook theory

For the rest of the paper, we assume $m$ and $n$ are non-negative integers
with $m\geq n$.

###  2.1. $q$-rook numbers

Rook placements are a generalizations of permutation diagrams, and their
$q$-analogues keep track of the number of inversions. We now summarize
important definitions and properties used later in relation to the chromatic
symmetric functions. In the Appendix we include the proofs and further
properties.

######  Definition 2.1 ($q$-rook numbers [GR86]).

Given a partition $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$
the _Garsia-Remmel $q$-rook numbers_ are defined as

$R_{k}(\lambda)=\sum_{p}q^{\operatorname{inv}(p)},$

where the sum is over all placements $p$ of $k$ non-attacking rooks on
$\lambda$ and $\operatorname{inv}(p)$ is the number of cells of $\lambda$ that
are not occupied by a rook or directly west or north of a rook (see Figure
3A).

######  Proposition 2.2 (Garsia-Remmel [GR86]).

Given a partition $\lambda=(\lambda_{1},\ldots,\lambda_{\ell})$ we have that

$F(x;\lambda):=\sum_{k=0}^{\ell}R_{k}(\lambda)[x]_{\ell-k}=\prod_{i=1}^{\ell}[x+\lambda_{\ell-i+1}-i+1],$

in particular $R_{\ell}(\lambda)=\prod_{i=1}^{\ell}[\lambda_{\ell-i+1}-i+1]$.

###  2.2. $q$-hit numbers

The $q$-hit numbers are defined in terms of the $q$-rook numbers by a change
of basis. Let $(a;q)_{k}=\prod_{i=0}^{k-1}(1-aq^{i})$ denote the
$q$-Pochhammer symbol.

######  Definition 2.3 ([LM18, Def. 3.1, Prop. 3.5]).

For $\lambda$ inside an $n\times m$ board, we define the _$q$ -hit polynomial_
of $\lambda$ by

(2.1)
$P(x;\lambda)=\sum_{i=0}^{n}H_{i}^{m,n}(\lambda)x^{i}:=\frac{q^{-|\lambda|}}{\left[m-n\right]!}\sum_{i=0}^{n}R_{i}(\lambda)\left[m-i\right]!(-1)^{i}q^{mi-\binom{i}{2}}(x;q)_{i},$

where the coefficients $H_{i}^{m,n}(\lambda)$ are the _$q$ -hit numbers_
associated to $\lambda$. Equivalently, we have that for every $k$

(2.2) $\displaystyle H_{k}^{m,n}(\lambda)$
$\displaystyle=\dfrac{q^{\binom{k}{2}-|\lambda|}}{\left[m-n\right]!}\sum_{i=k}^{n}R_{i}(\lambda)\left[m-i\right]!\begin{bmatrix}i\\\
k\end{bmatrix}(-1)^{i+k}q^{mi-\binom{i}{2}},$ and (2.3) $\displaystyle
R_{k}(\lambda)$
$\displaystyle=q^{|\lambda|-mk}\frac{[m-n]!}{[m-k]!}\sum_{i=k}^{n}H_{i}^{m,n}(\lambda)\begin{bmatrix}i\\\
k\end{bmatrix}_{q^{-1}}.$

######  Notation 2.4.

For square boards with $n=m$, we denote the $q$-hit number by
$H_{j}^{m}(\lambda)$.

######  Remark 2.5.

For the case $n=m$, Garsia–Remmel defined $q$-hit numbers
$\widetilde{H}_{k}^{n}(\lambda)$ by the relation

(2.4)
$\sum_{i=0}^{n}\widetilde{H}_{i}^{n}(\lambda)x^{i}=\sum_{i=0}^{n}R_{i}(\lambda)[n-i]!\prod_{k=n-i+1}^{n}(x-q^{k}).$

One can show that the Garsia–Remmel $q$-hit numbers and our $q$-hit numbers
differ by a power of $q$ (see Proposition H.1).

The $q$-hit numbers satisfy the following deletion-contraction relation that
is proved in Appendix K. Given a shape $\lambda$ and a corner cell $e$ in
$\lambda$, $\lambda\backslash e$ denotes the shape obtained after deleting the
cell $e$ in $\lambda$, and $\lambda/e$ denotes the shape obtained after
deleting in $\lambda$ the row and column containing $e$. See Figure 2 for an
example.

Figure 2. Example of the deletion and contraction of the board of a partition
$\lambda$.

######  Lemma 2.6.

We have the following deletion-contraction relation:

$H_{j}^{m,n}(\lambda)=H_{j}^{m,n}(\lambda\backslash
e)+q^{|\lambda/e|-|\lambda|+j+m-1}\left(H_{j-1}^{m-1,n-1}(\lambda/e)-qH_{j}^{m-1,n-1}(\lambda/e)\right).$

Guay-Paquet [GPa] defined the rectangular $q$-hit numbers using a statistic
similar to Dworkin’s statistic [Dwo98] for the Garsia–Remmel $q$-hit numbers
and we present this definition next, illustrated in Figure 3B.

######  Definition 2.7 (Statistic for the $q$-hit numbers).

Let $\lambda$ be a partition inside an $n\times m$ board. Given a placement
$p$ of $n$ non-attacking rooks on an $n\times m$ board, with exactly $j$ rooks
inside $\lambda$, let $\operatorname{stat}(p)$ be the number of cells $c$ in
the board such that:

  * (i)

there is no rook in $c$,

  * (ii)

there is no rook above $c$ on the same column, and either,

  * (iii)

if $c$ is in $\lambda$ then the rook on the same row of $c$ is in $\lambda$
and to the right of $c$ or

  * (iv)

if $c$ is not in $\lambda$ then the rook on same row of $c$ is either in
$\lambda$ or to the right of $c$.

######  Remark 2.8.

Intuitively, this statistic $\operatorname{stat}(p)$ counts the number of
remaining cells in the $n\times m$ board after: wrapping this board on a
vertical cylinder and each rook of $p$ cancels the cells south in its column
and the cells east in its row until the border of $\lambda$.

######  Theorem 2.9.

Let $\lambda$ be a partition inside an $n\times m$ board and $j=0,\ldots,n$
then

(2.5) $H_{j}^{m,n}(\lambda)=\sum_{p}q^{\operatorname{stat}(p)},$

where the sum is over all placements $p$ of $n$ non-attacking rooks on an
$n\times m$ board, with exactly $j$ rooks inside $\lambda$.

The proof for Theorem 2.9 is given in Appendix I.

######  Remark 2.10.

Note that the Garsia–Remmel $q$-hit numbers have a very similar description in
[HR01] (attributed to Dworkin) using a different attacking rule for the rooks.
Our proof of Theorem 2.9 in Appendix G follows by reducing to the case of the
Garsia–Remmel $q$-hit numbers. See also Section 7.1 for more details.

Moreover, for each partition $\lambda$, the statistic
$\operatorname{stat}(\cdot)$ is _Mahonian_.

######  Corollary 2.11.

Let $\lambda$ be a partition inside an $n\times m$ board, then

$\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)=[m]_{n}.$

###### Proof.

Set $k=0$ in (2.3) and since $R_{0}(\lambda)=q^{|\lambda|}$, we obtain

$\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)=q^{-|\lambda|}R_{0}(\lambda)[m]_{n}=[m]_{n}.\qed$

A

B

C

D

Figure 3. Example of the statistics of (A) a $q$-rook number and (B) a $q$-hit
number. (C)(D) Examples of the cases of $q$-hit numbers of a rectangle
$(m-1)^{k}\subset n\times m$ for Proposition 2.17.

######  Example 2.12.

Consider the partition $\lambda=(6,3,3,1)$ inside a $6\times 8$ board. In
Figures 3A and 3B, we present an example of a placement $p$ of two rooks on
$\lambda$ with $\operatorname{inv}(p)=7$ and an example of a placement
$p^{\prime}$ of six rooks on the $6\times 8$ board with two hits on $\lambda$
and $\operatorname{stat}(p^{\prime})=13$, respectively.

We finish this section with some results for $q$-hit numbers. The next two
results show the relation between the $q$-hit numbers when we change the
dimensions of the board.

######  Lemma 2.13.

Let $\lambda$ be a partition inside an $n\times m$ board. Then

$H_{j}^{m,n}(\lambda)=\frac{1}{[m-n]!}H_{j}^{m,m}(\lambda).$

###### Proof.

Since $R_{i}(\lambda)=0$ for $i=n+1,\ldots,m$ then (2.2) becomes,

$H_{j}^{m,n}(\lambda)=\dfrac{q^{\binom{j}{2}-|\lambda|}}{\left[m-n\right]!}\sum_{i=j}^{m}R_{i}(\lambda)\left[m-i\right]!\begin{bmatrix}i\\\
j\end{bmatrix}(-1)^{i+j}q^{mi-\binom{i}{2}}=\frac{1}{[m-n]!}H_{j}^{m,m}(\lambda).$

∎

######  Lemma 2.14.

Let $\lambda$ be a partition inside an $(n-1)\times m$ board. Then

$H_{j}^{m,n}(\lambda)=\left[m+1-n\right]H_{j}^{m,n-1}(\lambda).$

###### Proof.

We apply (2.2) to $H_{j}^{m,n}(\lambda)$

and use the fact $R_{n}(\lambda)=0$ since $\lambda\subset(n-1)\times m$ to
obtain

$\displaystyle H_{j}^{m,n}(\lambda)$
$\displaystyle=\left[m+1-n\right]\dfrac{q^{\binom{j}{2}-|\lambda|}}{\left[m-n+1\right]!}\sum_{i=j}^{n-1}R_{i}(\lambda)\left[m-i\right]!\begin{bmatrix}i\\\
j\end{bmatrix}(-1)^{i+j}q^{mi-\binom{i}{2}}$
$\displaystyle=\left[m+1-n\right]H_{j}^{m,n-1}(\lambda),$

where we used (2.1) again for $H_{j}^{m,n-1}(\lambda)$ to obtain the desired
formula. ∎

Finally, we give formulas for $q$-rook numbers and $q$-hit numbers of
rectangular shapes.

######  Proposition 2.15.

(2.6)
$R_{k}(a^{b})=q^{(a-k)(b-k)}\dfrac{\left[a\right]_{k}\left[b\right]_{k}}{\left[k\right]!}.$

###### Proof.

The result follows from the recurrence
$R_{k}(a^{b})=\left[b\right]R_{k-1}((a-1)^{b-1})+q^{b}R_{k}((a-1)^{b})$ or
from the fact that up to a power of $q$ and $(q-1)^{k}$, this is the number of
rank $k$ matrices of size $a\times b$ over a finite field with $q$ elements
[Hag98, Thm. 1], formulas for which can be found in [Mor06, Sec. 1.7]. ∎

######  Proposition 2.16.

(2.7) $\displaystyle
H_{k}^{N}(m^{j})=q^{(N-j-m+k)k}\left[m\right]_{k}\left[N-j\right]!\dfrac{\left[N-m\right]_{j-k}\left[j\right]_{j-k}}{\left[j-k\right]!}.$

###### Proof.

We compute the $q$-hit number directly using the statistic in (2.5). We claim
that

$\displaystyle H_{k}^{N}(m^{j})=R_{k}(m^{k})\cdot R_{j-k}((N-m)^{j})\cdot
R_{N-j}((N-j)^{N-j}).$

To show this, let us denote by $B$ the $N\times N$ board. Then there are $j-k$
rows occupied by rooks right of the shape $m^{j}$. These rooks cancel the
respective rows from the $m^{j}$ shape. The overall contribution to the
$q$-hit number from the $k$ rooks on the remaining shape $m^{k}$ is
$R_{k}(m^{k})=\left[m\right]_{k}$. The overall contribution to the $q$-hit
number from the $j-k$ rooks placed to the right of the shape $m^{j}$ is
$R_{j-k}((N-m)^{j})$. The $j$ rooks placed on the first $j$ rows of the board
$B$ cancel as many columns in the shape $N^{N-j}$ consisting of the last $N-j$
rows of the board $B$.

By Proposition 2.2, the overall contribution to the $q$-hit number from
placing the remaining $N-j$ rooks in the remaining shape $(N-j)^{N-j}$ is
$R_{N-j}((N-j)^{N-j})=[N-j]!$. This proves the claim and the result follows by
using the formula in (2.6) for $R_{k}(a^{b})$. ∎

######  Proposition 2.17.

$H_{r}^{m,n}((m-1)^{k})=\begin{cases}q^{k}[m-k][m-1]_{n-1}&r=k,\\\
[k][m-1]_{n-1}&r=k-1,\\\ 0&otherwise.\end{cases}$

###### Proof.

Since every row of the $n\times m$ board has a rook and the last column has at
most one rook then the rooks can only “hit” the shape $(m-1)^{k}$ $r=k$ or
$r=k-1$ times.

When $r=k$, the first $k$ cells of the last column are not cancelled in any
rook placement so they contribute to $\operatorname{stat}(\cdot)$. The
contribution to the $q$-hit number from the $k$ rooks placed on the shape
$(m-1)^{k}$ is $R_{k}((m-1)^{k})$. These rooks cancel $k$ columns in the shape
of the last $n-k$ rows. Then the contribution to the $q$-hit number of placing
$n-k$ rooks on the remaining shape $(m-k)^{n-k}$ is $R_{n-k}((m-k)^{n-k})$.
See Figure 3C. Thus,

$H_{k}^{m,n}((m-1)^{k})=q^{k}R_{k}((m-1)^{k})\cdot
R_{n-k}((m-k)^{n-k})=q^{k}[m-1]_{k}[m-k]_{n-k}=q^{k}[m-k][m-1]_{n-1}.$

When $r=k-1$, there is a rook on one of the first $k$ cells of the $m$th
column which cancels all the cells of its corresponding row $i=1,\ldots,k$ and
the cells below the rook in its column. This rook contributes $i-1$ to the
statistic (the cells above the rook in the $m$th column). There contribution
to the $q$-hit number from the $k-1$ rooks placed on the remaining shape
$(m-1)^{k-1}$ (without row $i$) is $R_{k-1}((m-1)^{k-1})$. The $k$ rooks on
the first $k$ rows cancel the cells of their columns in the shape of the last
$n-k$ rows. Then the contribution to the $q$-hit number of placing $n-k$ rooks
on the remaining shape $(m-k)^{n-k}$ is $R_{n-k}((m-k)^{n-k})$. See Figure 3D.
Summing over all $i=1,\ldots,k$ we obtain that

$H_{k-1}^{m,n}((m-1)^{k})=[k]R_{k-1}((m-1)^{k-1})\cdot
R_{n-k}((m-k)^{n-k})=[k][m-1]_{k-1}[m-k]_{n-k}=[k][m-1]_{n-1}.$

∎

##  3\. New $q$-rook and $q$-hit identities

The proofs of Theorems 1.2 and 1.3 rely on many new identities between $q$-hit
numbers, and their equivalent $q$-rook versions. While the $q$-hit and
$q$-rook identities are independent of the chromatic symmetric function
theory, we first prove them using elementary combinatorial methods and
univariate generating functions.

For brevity, we will denote by ${\lambda}/^{c}\,{j}$ the partition obtained
from $\lambda$ by removing its $j$th column, by ${\lambda}/^{r}\,{i}$ the
partition obtained by removing its $i$th row, and by $\lambda/(i,j)$ the
partition obtained from $\lambda$ by removing its $j$th column and its $i$th
row. Moreover, we denote $\ell=\ell(\lambda)$ and the conjugate partition of
$\lambda$ by $\lambda^{\prime}$.

###  3.1. Identities on $q$-rook numbers

The following $q$-rook identities can be proven directly using the generating
function identity in Proposition 2.2 of Garsia-Remmel. We start with a simple
algebraic identity.

######  Lemma 3.1.

Given a partition $\lambda=(\lambda_{1},\ldots,\lambda_{\ell})$,

$q^{\lambda_{1}}[x]\frac{F(x-1;\lambda)}{F(x;\lambda)}=[x-\ell+\lambda_{1}]-\sum_{j=1}^{\lambda_{1}}q^{\lambda_{1}-j}\prod_{t=1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}.$

###### Proof.

We use induction on $\ell(\lambda)$ and apply Proposition 2.2. For
$\ell(\lambda)=1$, we have

$[x]\frac{F(x-1;\lambda)}{F(x;\lambda)}=[x-1]+\sum_{j=1}^{\lambda_{1}}q^{-j}-q^{-j}\frac{[x+\lambda_{1}-1]}{[x+\lambda_{1}]}=q^{-\lambda_{1}}\frac{[x+\lambda_{1}-1]}{[x+\lambda_{1}]}([x+\lambda_{1}]-[\lambda_{1}]).$

Next, expanding the RHS of the above identity and doing standard manipulations
gives

$[x-\ell+\lambda_{1}]-\sum_{j=1}^{\lambda_{1}}q^{\lambda_{1}-j}\prod_{t=1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}=\\\
=q^{\lambda_{1}-\lambda_{2}}\frac{[x+\lambda_{1}-\ell]}{[x+\lambda_{1}-\ell+1]}\left([x+\lambda_{2}-(\ell-1)]-\sum_{j=1}^{\lambda_{2}}q^{\lambda_{2}-j}\prod_{t=2}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}\right).$

By induction hypothesis the parenthetical on the RHS above is
$q^{\lambda_{2}}[x]F(x-1;\tilde{\lambda})/F(x;\tilde{\lambda})$ where
$\tilde{\lambda}=(\lambda_{2},\ldots,\lambda_{\ell})$. Using
$\tilde{\lambda}_{t}=\lambda_{t+1}$ for the reindexing, we obtain the result.
∎

Next, we find the following $q$-analogue of the derivative of $F(x;\lambda)$.

######  Lemma 3.2.

We have the following formula for the $q$-analogue of the derivative of
$F(x;\lambda)$:

$DF(x;\lambda):=\sum_{k=0}^{\ell}[k]R_{k}(\lambda)[x]_{\ell-k}=q^{\ell-x}([x]F(x-1;\lambda)-[x-\ell]F(x;\lambda)).$

###### Proof.

Following the notation of Proposition 2.2,

$F(x;\lambda):=\sum_{k=0}^{\ell}R_{k}(\lambda)[x]_{\ell-k}=\prod_{i=1}^{\ell}[x+\lambda_{\ell-i+1}-i+1].$

Note that

$\displaystyle[x]_{\ell-k}-[x-1]_{\ell-k}$
$\displaystyle=[x-1]_{\ell-k-1}\left(\frac{1-q^{x}-1+q^{x-\ell+k}}{1-q}\right)=\frac{[x]_{\ell-k}}{[x]}\frac{q^{x-\ell}(q^{k}-q^{\ell})}{1-q}$
$\displaystyle=\frac{[x]_{\ell-k}}{[x]}q^{x-\ell}([\ell]-[k]).$

Apply this identity to each term in the following difference

$\displaystyle
F(x;\lambda)-F(x-1;\lambda)=\sum_{k=0}^{\ell}R_{k}(\lambda)\frac{[x]_{\ell-k}}{[x]}q^{x-\ell}([\ell]-[k]),$

so that

$\displaystyle[x](F(x;\lambda)-F(x-1;\lambda))=q^{x-\ell}[\ell]F(x;\lambda)-q^{x-\ell}DF(x;\lambda),$

where $DF(x;\lambda):=\sum_{k=0}^{\ell}[k]R_{k}(\lambda)[x]_{l-k}$. This gives
an equation for $DF(x;\lambda)$ which we solve as

$DF(x;\lambda)=-q^{\ell-x}([x]-q^{x-\ell}[\ell])F(x;\lambda)+q^{\ell-x}[x]F(x-1;\lambda)=q^{\ell-x}([x]F(x-1;\lambda)-[x-\ell]F(x;\lambda)),$

giving us the desired formula. ∎

The following result shows the relationship between $q$-rook numbers for
partitions obtained from deleting a column of $\lambda$.

######  Lemma 3.3.

For all $i$ fixed,

$\sum_{j}q^{m-j}R_{i}({\lambda}/^{c}\,{j})=R_{i}(\lambda)[m-i]-R_{i+1}(\lambda)(q^{m}-q^{m-i-1}).$

###### Proof.

Multiplying on both sides by $[x]_{\ell-i}$, the above claim is equivalent to
the generating function identity:

$\sum_{j}q^{m-j}F(x;{\lambda}/^{c}\,{j})=\sum_{i}(R_{i}(\lambda)[m-i]-R_{i+1}(\lambda)(q^{m}-q^{m-i-1}))[x]_{\ell-i}\\\
=\sum_{i}R_{i}(\lambda)\left([m-i][x]_{\ell-i}-(q^{m}-q^{m-i})[x]_{\ell-i+1}\right)=\sum_{i}R_{i}(\lambda)[x]_{\ell-i}[m+x-\ell]-q^{m}[x][x-1]_{\ell-i}\\\
=[m+x-\ell]F(x;\lambda)-q^{m}[x]F(x-1;\lambda),$

where we use the observation that

$[m-i][x]_{\ell-i}-(q^{m}-q^{m-i})[x]_{\ell-i+1}=[x]_{\ell-i}\frac{(1-q^{m-i})-(q^{m}-q^{m-i})(1-q^{x-\ell+i})}{1-q}\\\
=[x]_{\ell-i}\frac{1-q^{m-i}-q^{m}+q^{m-i}+q^{m+x-\ell+i}-q^{m+x-\ell}}{1-q}=[x]_{\ell-i}[x+m-\ell]-q^{m}[x]_{\ell-i+1}.$

We have that

$F(x;{\lambda}/^{c}\,{j})=\prod_{i=1}^{\lambda^{\prime}_{j}}[x+\lambda_{i}-1-\ell+i]\prod_{i=\lambda^{\prime}_{j}+1}^{\ell}[x+\lambda_{i}-\ell+i]=F(x;\lambda)\prod_{i=1}^{\lambda^{\prime}_{j}}\frac{[x-1+\lambda_{i}-\ell+i]}{[x+\lambda_{i}-\ell+i]}.$

Using Lemma 3.1 and that ${\lambda}/^{c}\,{j}=\lambda$ for $j>\lambda_{1}$,

$\sum_{j=1}^{m}q^{m-j}F(x;{\lambda}/^{c}\,{j})=F(x;\lambda)\left([m-\lambda_{1}]+q^{m-\lambda_{1}}\sum_{j}q^{\lambda_{1}-j}\prod_{i=1}^{\lambda^{\prime}_{j}}\frac{[x-1+\lambda_{i}-\ell+i]}{[x+\lambda_{i}-\ell+i]}\right)\\\
=F(x;\lambda)\left([m-\lambda_{1}]+q^{m-\lambda_{1}}[x-\ell+\lambda_{1}]-q^{m-\lambda_{1}}q^{\lambda_{1}}[x]\frac{F(x-1;\lambda)}{F(x;\lambda)}\right)\\\
=F(x;\lambda)[x-\ell+\lambda_{1}+m-\lambda_{1}]-q^{m}[x]F(x-1;\lambda),$

which is what we wanted to show and completes the proof. ∎

We also have the following relationship between $q$-rook numbers obtained from
removing a single row from $\lambda$.

######  Lemma 3.4.

For all fixed $k$,

$\displaystyle\sum_{i=1}^{n}q^{i-1+\lambda_{i}}R_{k}({\lambda}/^{r}\,{i})=[n]R_{k}(\lambda)-[k]R_{k}(\lambda).$

###### Proof.

First of all, notice that we can replace $n$ with $\ell$ since for $i>\ell$,
${\lambda}/^{r}\,{i}=\lambda$, $\lambda_{i}=0$ and
$[n]-\sum_{i=\ell+1}^{n}q^{i-1}=[\ell]$. Multiplying by
$[y]_{\ell-k}=[y][y-1]_{(\ell-1)-k}$ on both sides and summing over all $k$,
the identity is equivalent to

$\displaystyle[y]\sum_{i=1}^{\ell}q^{i-1+\lambda_{i}}\sum_{k}R_{k}({\lambda}/^{r}\,{i})[y-1]_{(\ell-1)-k}=[n]\sum_{k}R_{k}(\lambda)[y]_{\ell-k}-\sum_{k}[k]R_{k}(\lambda)[y]_{\ell-k}.$

Thus, the identity is then equivalent to the generating function identity

$[y]\sum_{i=1}^{\ell}q^{i-1+\lambda_{i}}F(y-1,{\lambda}/^{r}\,{i})\\\
=[\ell]F(y;\lambda)-DF(y;\lambda)=[\ell]F(y,\lambda)+q^{-y+\ell}[y-\ell]F(y,\lambda)-q^{\ell-y}[y]F(y-1,\lambda).$

We have that for $i\leq\ell$

$F(y-1,{\lambda}/^{r}\,{i})=\prod_{j=1}^{\ell-1}[y-1+({\lambda}/^{r}\,{i})_{j}-(\ell-1)+i]=\prod_{j=1}^{i-1}[y-1+\lambda_{j}-\ell+1+j]\prod_{j=i+1}^{\ell}[y-1+\lambda_{j}-(\ell-1)+j-1]\\\
=\frac{1}{[y-1+\lambda_{i}-\ell+i]}\prod_{j=1}^{i-1}\frac{[y+\lambda_{j}-\ell]}{[y-1+\lambda_{j}-\ell]}F(y-1,\lambda),$

and so we reach the following equivalent identity

$[y]\sum_{i=1}^{\ell}\frac{q^{y-\ell+i-1+\lambda_{i}}}{[y-1+\lambda_{i}-\ell+i]}\prod_{j=1}^{i-1}\frac{[y+\lambda_{j}-\ell]}{[y-1+\lambda_{j}-\ell]}F(y-1,\lambda)\\\
=q^{y-\ell}[\ell]F(y,\lambda)+[y-\ell]F(y,\lambda)-[y]F(y-1,\lambda).$

We can rewrite it as

$[y]\sum_{i=1}^{\ell}\frac{[y-\ell+i+\lambda_{i}]-[y-1-\ell+i+\lambda_{i}]}{[y-1+\lambda_{i}-\ell+i]}\prod_{j=1}^{i-1}\frac{[y+\lambda_{j}-\ell+j]}{[y-1+\lambda_{j}-\ell+j]}F(y-1,\lambda)\\\
=q^{y-\ell}[\ell]F(y,\lambda)+[y-\ell]F(y,\lambda)-[y]F(y-1,\lambda),$

which reduces again to

$\displaystyle[y]F(y-1,\lambda)\sum_{i=1}^{\ell}\left(\prod_{j=1}^{i}\frac{[y+\lambda_{j}-\ell+j]}{[y-1+\lambda_{j}-\ell+j]}-\prod_{j=1}^{i-1}\frac{[y+\lambda_{j}-\ell+j]}{[y-1+\lambda_{j}-\ell+j]}\right)=[y]F(y,\lambda)-[y]F(y-1,\lambda).$

After canceling the terms in the telescoping sum on the LHS, the identity
reduces to

$[y]F(y-1,\lambda)\left(\prod_{j=1}^{\ell}\frac{[y+\lambda_{j}-\ell+j]}{[y-1+\lambda_{j}-\ell+j]}-1\right)-[y]F(y,\lambda)+[y]F(y-1,\lambda)\\\
=[y](F(y,\lambda)-F(y-1,\lambda))-[y]F(y,\lambda)+[y]F(y-1,\lambda)=0,$

which completes the proof. ∎

######  Lemma 3.5.

We have the following identity for $q$-rook numbers:

$\sum_{(i,j)\in\lambda}q^{i-j+\lambda_{i}}R_{k}(\lambda/(i,j))=q[k+1]R_{k+1}(\lambda).$

###### Proof.

Translating this identity into generating functions, we have that it is
equivalent to

$\displaystyle\sum_{k=0}^{\ell-1}\sum_{(i,j)\in\lambda}q^{i-j+\lambda_{i}}R_{k}(\lambda/(i,j))[x]_{\ell-1-k}=\sum_{k=0}^{\ell-1}q[k+1]R_{k+1}(\lambda)[x]_{\ell-k-1}=\sum_{t=0}^{\ell}q[t]R_{t}(\lambda)[x]_{\ell-t},$

which can be rewritten, with the help of Lemma 3.2, in terms of the $F$
function as

(3.1)
$\displaystyle\sum_{(i,j)\in\lambda}q^{i-j+\lambda_{i}}F(x;\lambda/(i,j))=qDF(x;\lambda)=-q^{\ell-x+1}[x-\ell]F(x;\lambda)+q^{1+\ell-x}[x]F(x-1;\lambda).$

Now, we notice that if $\mu=\lambda/(i,j)$

$\displaystyle F(x;\lambda/(i,j))$
$\displaystyle=\prod_{t=1}^{\ell-1}[x+\mu_{t}-\ell+1+t]$
$\displaystyle=\prod_{t=1}^{i-1}[x+\lambda_{t}-1-\ell+1+t]\prod_{t=i}^{\lambda_{j}^{\prime}-1}[x+\lambda_{t+1}-1-\ell+1+t]\prod_{t=\lambda_{j}^{\prime}}^{\ell-1}[x+\lambda_{t+1}-\ell+1+t]$
$\displaystyle=F(x;\lambda)\frac{\prod_{t=i+1}^{\lambda_{j}^{\prime}}[x+\lambda_{t}-1-\ell+t]}{\prod_{t=i}^{\lambda_{j}^{\prime}}[x+\lambda_{t}-\ell+t]}.$

Note that
$q^{x-1-\ell+i+\lambda_{i}}=[x+\lambda_{i}-\ell+i]-[x+\lambda_{i}-\ell+i-1]$,
so we can rewrite this as

$q^{i-j+\lambda_{i}}F(x;\lambda/(i,j))\\\
=q^{-x+1+\ell-j}F(x;\lambda)([x+\lambda_{i}-\ell+i]-[x+\lambda_{i}-\ell+i-1])\frac{\prod_{t=i+1}^{\lambda_{j}^{\prime}}[x+\lambda_{t}-1-\ell+t]}{\prod_{t=i}^{\lambda_{j}^{\prime}}[x+\lambda_{t}-\ell+t]}\\\
=q^{-x+1+\ell-j}F(x;\lambda)\left(\prod_{t=i+1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}-\prod_{t=i}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}\right).$

Fixing $j$ and summing over all possible $i=1\ldots\lambda_{j}^{\prime}$ we
get telescoping cancellations and so

$\displaystyle\sum_{(i,j)\in\lambda}q^{i-j+\lambda_{i}}F(x;\lambda/(i,j))=\sum_{j}q^{-x+1+\ell-j}F(x;\lambda)\left(1-\prod_{t=1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}\right).$

Substituting this into the LHS of (3.1), the needed identity transforms to the
equivalent

$\displaystyle\sum_{j}q^{1-j+\ell-x}F(x;\lambda)\left(1-\prod_{t=1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}\right)$
$\displaystyle=qDF(x;\lambda)$
$\displaystyle=q^{\ell-x+1}\left([x]F(x-1;\lambda)-[x-\ell]F(x;\lambda)\right),$

which is equivalent to

$[x]\frac{F(x-1;\lambda)}{F(x;\lambda)}=[x-\ell]+\sum_{j=1}^{\lambda_{1}}q^{-j}-q^{-j}\prod_{t=1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]}.$

This last identity simplifies as

$q^{\lambda_{1}}[x]\frac{F(x-1;\lambda)}{F(x;\lambda)}=[x-\ell+\lambda_{1}]-\sum_{j=1}^{\lambda_{1}}q^{\lambda_{1}-j}\prod_{t=1}^{\lambda_{j}^{\prime}}\frac{[x+\lambda_{t}-1-\ell+t]}{[x+\lambda_{t}-\ell+t]},$

and is equivalent to the formula in Lemma 3.1, which completes the proof. ∎

###  3.2. $q$-hit identities

We now translate the above rook identities into $q$-hit identities using the
relationship from Definition 2.3. Let

$G^{m,n}(x;\lambda)=\sum_{k=0}^{n}H_{k}^{m,n}(\lambda)(q^{x})^{k}.$

Then we have the following equivalences in terms of the generating functions

(3.2) $\displaystyle G^{m,n}(x;\lambda)$
$\displaystyle:=\sum_{i=0}^{n}\sum_{k=0}^{i}\dfrac{q^{\binom{k}{2}-|\lambda|}}{\left[m-n\right]!}R_{i}(\lambda)\left[m-i\right]!\begin{bmatrix}i\\\
k\end{bmatrix}(-1)^{i+k}q^{mi-\binom{i}{2}}q^{xk}$
$\displaystyle=\frac{q^{-|\lambda|}}{\left[m-n\right]!}\sum_{i=0}^{n}R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i}{2}}(-1)^{i}\sum_{k=0}^{i}q^{\binom{k}{2}}\begin{bmatrix}i\\\
k\end{bmatrix}(-q^{x})^{k}$
$\displaystyle=\frac{q^{-|\lambda|}}{\left[m-n\right]!}\sum_{i=0}^{n}R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i}{2}}(-1)^{i}\prod_{k=0}^{i-1}(1-q^{x+k}).$

######  Lemma 3.6.

For every $\lambda$ inside an $n\times m$ board and for every $k$

$\sum_{j=1}^{m}q^{m+n-j-\lambda_{j}^{\prime}}H_{k}^{m-1,n}({\lambda}/^{c}\,{j})=[m-n]H_{k}^{m,n}(\lambda)q^{n-k}.$

###### Proof.

The collection of identities for $k=0,\ldots,n$ is equivalent to the following
generating function identities

$\sum_{k=0}^{n}\sum_{j=1}^{m}q^{m+n-j-\lambda_{j}^{\prime}}H_{k}^{m-1,n}({\lambda}/^{c}\,{j})q^{xk}\\\
=[m-n]\sum_{k=0}^{n}H_{k}^{m,n}(\lambda)q^{n-k}q^{xk}\sum_{j=1}^{m}q^{m+n-j-\lambda_{j}^{\prime}}G^{m-1,n}(x;{\lambda}/^{c}\,{j})=q^{n}[m-n]G^{m,n}(x-1;\lambda).$

Using (3.2) and expanding in the $q^{x}$-polynomial basis
$(q^{x};q)_{k}=\prod_{k=0}^{i-1}(1-q^{x+k})$ for $i=0,\ldots,n$, the
$G$-identity is equivalent to the following rook identity for every $i$:

$\sum_{j=1}^{m}q^{m+n-j-\lambda_{j}^{\prime}}\frac{q^{-|\lambda|+\lambda_{j}^{\prime}}}{\left[m-1-n\right]!}\sum_{i=0}^{n}R_{i}({\lambda}/^{c}\,{j})\left[m-1-i\right]!q^{mi-i-\binom{i}{2}}(-1)^{i}\prod_{k=0}^{i-1}(1-q^{x+k})\\\
=q^{n}[m-n]\frac{q^{-|\lambda|}}{\left[m-n\right]!}\sum_{i=0}^{n}R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i}{2}}(-1)^{i}\prod_{k=0}^{i-1}(1-q^{x-1+k}),$

which simplifies as

$\sum_{j=1}^{m}q^{m-j}\sum_{i=0}^{n}R_{i}({\lambda}/^{c}\,{j})\left[m-1-i\right]!q^{mi-i-\binom{i}{2}}(-1)^{i}\prod_{k=0}^{i-1}(1-q^{x+k})\\\
=\sum_{i=0}^{n}R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i}{2}-i}(-1)^{i}q^{i}\prod_{k=0}^{i-1}(1-q^{x-1+k}).$

Notice that

$q^{i}(q^{x-1};q)_{i}=(q^{i}-q^{x+i-1})(q^{x};q)_{i-1}=(q^{i}-1)(q^{x};q)_{i-1}+(q^{x};q)_{i},$

and so the RHS above expands in the $(q^{x};q)_{i}$ basis as:

$\sum_{i=0}^{n}R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i+1}{2}}(-1)^{i}((q^{i}-1)(q^{x};q)_{i-1}+(q^{x};q)_{i})\\\
=\sum_{i=0}^{n}(-1)^{i}(q^{x};q)_{i}\left(R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i+1}{2}}-R_{i+1}(\lambda)\left[m-i-1\right]!q^{mi+m-\binom{i+2}{2}}(q^{i+1}-1)\right).$

Therefore, this is equivalent to the following $q$-rook identity for every
$i$:

$\sum_{j=1}^{m}q^{m-j}R_{i}({\lambda}/^{c}\,{j})\left[m-1-i\right]!q^{mi-\binom{i+1}{2}}\\\
=\left(R_{i}(\lambda)\left[m-i\right]!q^{mi-\binom{i+1}{2}}-R_{i+1}(\lambda)\left[m-i-1\right]!q^{mi+m-\binom{i+2}{2}}(q^{i+1}-1)\right).$

Simplifying last expression, we obtain

$\displaystyle\sum_{j=1}^{m}q^{m-j}R_{i}({\lambda}/^{c}\,{j})=R_{i}(\lambda)[m-i]-R_{i+1}(\lambda)(q^{m}-q^{m-i-1}),$

which is exactly Lemma 3.3. ∎

######  Lemma 3.7.

Let $k\leq n\leq m$ be fixed, and $\lambda\subset n\times m$. We have the
following $q$-hit identity:

$[m-n+1]\sum_{i=1}^{n}q^{i-1}H_{k}^{m,n-1}({\lambda}/^{r}\,{i})=H_{k}^{m,n}(\lambda)q^{k}[n-k]+H_{k+1}^{m,n}(\lambda)[k+1].$

###### Proof.

Multiplying both sides by $(q^{x})^{k}$ and summing over all $k$, the identity
becomes equivalent to the following generating function identity:

$\displaystyle[m-n+1]\sum_{i=1}^{n}q^{i-1}G^{m,n-1}(x;{\lambda}/^{r}\,{i})=\sum_{k=0}^{n-1}H_{k}^{m,n}(\lambda)(q^{x+1})^{k}[n-k]+\sum_{k=0}^{n-1}H_{k+1}^{m,n}(\lambda)[k+1]q^{xk}.$

To prove the above identity, we will use the following difference operator and
its properties:

$\Delta
F(x):=\frac{F(x+1)-F(x)}{q^{x}(q-1)},\quad\Delta(q^{x})^{p}=[p](q^{x})^{p-1},\quad\Delta(q^{x},q)_{p}=-[p](q^{x+1},q)_{p-1}=-\frac{[p](q^{x};q)_{p}}{1-x}.$

Notice also that $q^{k}[n-k]=[n]-[k]$ and $[k+1]q^{xk}=\Delta q^{x(k+1)}$.
Therefore, we have

$\displaystyle\sum_{k=0}^{n-1}H_{k}^{m,n}(\lambda)\left(q^{x+1}\right)^{k}[n-k]$
$\displaystyle=\sum_{k=0}^{n-1}H_{k}^{m,n}(\lambda)q^{xk}[n]-\sum_{k=0}^{n-1}H_{k}^{m,n}(\lambda)[k]q^{xk}$
$\displaystyle=[n]G^{m,n}(x;\lambda)-q^{x}\Delta G^{m,n}(x;\lambda)$ and
$\displaystyle\sum_{k=0}^{n-1}H_{k+1}^{m,n}(\lambda)[k+1]q^{xk}$
$\displaystyle=\Delta G^{m,n}(x;\lambda).$

Thus, the generating function identity is equivalent to

$\displaystyle[m-n+1]\sum_{i=1}^{n}q^{i-1}G^{m,n-1}(x;{\lambda}/^{r}\,{i})=[n]G^{m,n}(x;\lambda)-q^{x}\Delta
G^{m,n}(x;\lambda)+\Delta G^{m,n}(x;\lambda).$

Using the formula

$(1-q^{x})\Delta
G^{m,n}(x;\lambda)=\frac{q^{-|\lambda|}}{[m-n]!}\sum_{k=0}^{n}[k]R_{k}(\lambda)[m-k]!q^{mk-\binom{k}{2}}(-1)^{k-1}\underbrace{(1-q^{x})(q^{x+1},q)_{k-1}}_{(q^{x};q)_{k}},$

we can express the generating function identity in terms of $q$-rook numbers
generating function as:

$[m-n+1]\sum_{i=1}^{n}q^{i-1}\frac{q^{-|\lambda|+\lambda_{i}}}{[m-n+1]!}\sum_{k=0}^{n}R_{k}({\lambda}/^{r}\,{i})[m-k]!q^{mk-\binom{k}{2}}(-1)^{k}(q^{x},q)_{k}\\\
=[n]\frac{q^{-|\lambda|}}{[m-n]!}\sum_{k}R_{k}(\lambda)[m-k]!q^{mk-\binom{k}{2}}(-1)^{k}(q^{x},q)_{k}\\\
+\frac{q^{-|\lambda|}}{[m-n]!}\sum_{k=0}^{n}[k]R_{k}(\lambda)[m-k]!q^{mk-\binom{k}{2}}(-1)^{k-1}(q^{x};q)_{k}.$

For each $k$, the coefficients at $(q^{x};q)_{k}$ coincide, after canceling
common factors, and reducing then to the $q$-rook identities from Lemma 3.4

$\displaystyle\sum_{i=1}^{n}q^{i-1+\lambda_{i}}R_{k}({\lambda}/^{r}\,{i})=[n]R_{k}(\lambda)-[k]R_{k}(\lambda).$

∎

######  Lemma 3.8.

We have the following identity

$q^{k}\sum_{(i,j)\in\lambda}q^{i+(m-j-\lambda^{\prime}_{j})}H_{k}^{m-1,n-1}(\lambda/(i,j))=[k+1]H_{k+1}^{m,n}(\lambda).$

###### Proof.

We show that this result follows from Lemma 3.5. By (2.2),

$\displaystyle[k+1]H_{k+1}^{m,n}(\lambda)$
$\displaystyle=[k+1]\frac{q^{\binom{k+1}{2}-|\lambda|}}{[m-n]!}\sum_{t=k+1}^{n}R_{t}(\lambda)[m-t]!\begin{bmatrix}t\\\
k+1\end{bmatrix}(-1)^{t+k+1}q^{mt-\binom{t}{2}}$
$\displaystyle=\frac{q^{\binom{k+1}{2}-|\lambda|}}{[m-n]!}\sum_{t^{\prime}=k}^{n-1}[t^{\prime}+1]R_{t^{\prime}+1}(\lambda)[m-t^{\prime}-1]!\begin{bmatrix}t^{\prime}\\\
k\end{bmatrix}(-1)^{t^{\prime}+k}q^{mt^{\prime}+m-\binom{t^{\prime}+1}{2}},$

where we reindexed the sum with $t^{\prime}=t-1$. Next, we apply Lemma 3.5 and
exchange sums to obtain

$[k+1]H_{k+1}^{m,n}(\lambda)=\frac{q^{\binom{k+1}{2}-|\lambda|}}{[m-n]!}\sum_{(i,j)\in\lambda}q^{m-j+\lambda_{i}}\sum_{t^{\prime}=k}^{n-1}R_{t^{\prime}}(\lambda/(i,j))[m-t^{\prime}-1]!\begin{bmatrix}t^{\prime}\\\
k\end{bmatrix}(-1)^{t^{\prime}+k}q^{mt^{\prime}+m-\binom{t^{\prime}+1}{2}}\\\
=q^{k}\sum_{(i,j)\in\lambda}q^{i+m-j-\lambda^{\prime}_{j}}\frac{q^{\binom{k}{2}}-|\lambda/(i,j)|}{[m-n]!}\sum_{t^{\prime}=k}^{n-1}R_{t^{\prime}}(\lambda/(i,j))[m-t^{\prime}-1]!\begin{bmatrix}t^{\prime}\\\
k\end{bmatrix}(-1)^{t^{\prime}+k}q^{(m-1)t^{\prime}-\binom{t^{\prime}}{2}}\\\
=q^{k}\sum_{(i,j)\in\lambda}q^{i+m-j-\lambda^{\prime}_{j}}H_{k}^{m-1,n-1}(\lambda/(i,j)),$

where we also used that
$|\lambda/(i,j)|=|\lambda|-\lambda_{i}-\lambda^{\prime}_{j}+1$ and (2.2) for
$H_{k}^{m-1,n-1}(\lambda/(i,j))$. ∎

##  4\. The Guay-Paquet $q$-hit identity

In this section we give our main result, a proof of Theorem 1.3 using the
$q$-rook theory identities from Section 3. We start by giving an example of
this elegant identity.

######  Example 4.1.

For $\lambda=(2,1)$ inside a $2\times 3$ board, looking at Figure 4B, we see
that $H_{0}^{3,2}(\lambda)=q^{0}=1$, $H_{1}^{3,2}(\lambda)=2q+2q^{2}$,
$H_{2}^{3,2}(\lambda)=q^{3}$. One can verify that

$X_{21}({\bf x},q)=\dfrac{1}{[3][2]}\left(X_{3^{0}}({\bf
x},q)+(2q^{2}+2q)X_{3^{1}}({\bf x},q)+q^{3}X_{3^{2}}({\bf x},q)\right).$

######  Remark 4.2.

By Lemma 2.13, the identity in Theorem 1.3 can be rewritten as

(4.1) $X_{\lambda}({\bf
x},q)\,=\,\dfrac{1}{\left[m\right]!}\sum_{j=0}^{n}H_{j}^{m}(\lambda)\cdot
X_{m^{j}}({\bf x},q).$

A

B

Figure 4. (A) an abelian Dyck path $\lambda$ inside an $n\times m$ board. (B)
Top: the paths for $\lambda=(2,1)$, and for the rectangles $3^{0},3^{1},3^{2}$
inside a $2\times 3$ board. (B) Bottom: the six placements of $2$ rooks in
$2\times 3$ divided by how many rooks “hit” $(2,1)$ (in gray) and the
associated statistic to each rook placement.

Our main self-contained proof is an inductive argument, where the induction is
applied both on the size $m+n$ of the graph, and also on the number of
variables in the symmetric polynomials. Namely, we consider the chromatic
symmetric functions in variables $x_{1},\ldots,x_{M}$ and each monomial
appearing as a particular assignment of the variables (i.e. colors) to the
vertices. That is, the vertices $1,\ldots,N=m+n$ are colored
$\\{1,\ldots,M\\}$. For simplicity, we denote by $X_{\lambda}^{N}(M)$ the
chromatic symmetric polynomial $X_{G(\lambda)}(x_{1},\ldots,x_{M};q)$ where
the graph $G(\lambda)$ has $N$ vertices. We will use induction on both $M$ and
$n,\ m$ when necessary, driven by the following recursion.

Recall that $\lambda/(i,j)$ is the partition obtained by removing the $i$th
row and the $j$th column from $\lambda$. Moreover, we denote by $\lambda/i$
the partitions obtained by removing from $\lambda$ the $i$th column, for
$i=1,\ldots,m$, or the $(m+n-i+1)$th row, for $i=m+1,\ldots,m+n$.

######  Lemma 4.3.

For $\lambda\subset n\times m$ we have the following recursion

$\displaystyle X_{\lambda}^{m+n}(M)=$ $\displaystyle
X_{\lambda}^{m+n}(M-1)+x_{M}\sum_{i=1}^{m+n}q^{m+n-i-\lambda_{i}^{\prime}}X^{m+n-1}_{\lambda/i}(M-1)$
$\displaystyle+x_{M}^{2}\sum_{(i,j)\in\lambda}q^{i-1+(m+n-j-\lambda_{j}^{\prime})}X^{m+n-2}_{\lambda/(i,j)}(M-1).$

###### Proof.

In the abelian case, i.e. when $\lambda\subset n\times m$, the graph
$G(\lambda)$ consists of a clique with vertices $\\{1,\ldots,m\\}$, a clique
with vertices $\\{m+1,\ldots,m+n\\}$ and a bipartite graph in between with
edges $(i,m+j)$ for each $(i,j)$ in
$\\{1,\ldots,n\\}\times\\{1,\ldots,m\\}\setminus\lambda$ (the complement of
$\lambda$ in $n\times m$). Therefore, a coloring of this graph has at most two
vertices of the same color. If the colors used are in $\\{1,\ldots,M\\}$,
there are three cases for the appearances of color $M$:

  * 1.

No vertex is colored $M$, this term contributes $X_{\lambda}^{m+n-1}(M-1)$ to
$X_{\lambda}^{m+n}(M)$.

  * 2.

Only one vertex is colored $M$. Suppose this vertex is in column $j$ (from
left) and row $i=N-j$ (from top to bottom). It creates ascents with all
vertices above it but not in $\lambda$, giving $N-j-\lambda_{j}^{\prime}$
ascents. Deleting this vertex corresponds to deleting its row and column (only
one would be a row/column of $\lambda$) and we get a graph on $N-1$ vertices
with shape $\lambda/j$ (deleting either row $N-j$ from $\lambda$, or column
$j$ from $\lambda$). The remaining vertices and their ascents are not affected
by this, so all their possible colorings contribute

$x_{M}\sum_{j=1}^{N}q^{N-j-\lambda^{\prime}_{j}}X_{\lambda/j}^{m+n-1}(M-1).$

  * 3.

Two vertices are colored $M$. Suppose that the lower one is in column $j$ and
the higher one is in row $i$ (counting from the top), necessarily with
$(i,j)\in\lambda$. The lower vertex contributes $N-j-\lambda_{j}^{\prime}$
ascents with the “visible” vertices above it. The higher vertex contributes
$i-1$ ascents, the number of vertices above it, giving a total of
$N-j-\lambda_{j}^{\prime}+i-1$ ascents. We can remove these two vertices, by
removing row $i$ and column $j$ from $\lambda$ and decreasing $N$ by 2. Again,
the remaining vertices and their ascents are not affected, so these terms
contribute

$x_{M}^{2}\sum_{(i,j)}q^{N-j-\lambda^{\prime}_{j}+i-1}X^{m+n-2}_{\lambda/(i,j)}(M-1).$

∎

For rectangular shapes $\lambda=(m^{k})$, Lemma 4.3 simplifies to give the
following recursive expansion.

######  Lemma 4.4.

$\displaystyle X^{m+n}_{m^{k}}(M)$
$\displaystyle=X^{m+n}_{m^{k}}(M-1)+x_{M}\left(q^{n-k}[m]X^{m+n-1}_{(m-1)^{k}}(M-1)+[k]X^{m+n-1}_{m^{k-1}}(M-1)\right.$
$\displaystyle\left.+q^{k}[n-k]X^{m+n-1}_{m^{k}}(M-1)\right)+x_{M}^{2}q^{n-k}[k][m]X^{m+n-2}_{(m-1)^{k-1}}(M-1).$

###### Proof.

This follows by carefully applying Lemma 4.3 to the shape $\lambda=m^{k}$. If
$i\in[1,m]$ then $\lambda/i=(m-1)^{k}$ and $N-i-\lambda_{i}^{\prime}=m+n-i-k$.
If $i\in[m+1,m+n-k]$, then it is not a row or column of $\lambda$ and we have
$\lambda/i=m^{k}$ with $m+n-i-0$ ascents. If $i\in[m+n-k+1,m+n]$ then
$\lambda/i=m^{k-1}$ and there are $m+n-i$ ascents. For $(i,j)\in\lambda$ we
always have $\lambda/(i,j)=(m-1)^{k-1}$ and the ascents are $m+n-j-k+i-1$.
Summing over the row/column indices in the given intervals we get the desired
ascent statistics as the given $q$-integers. ∎

###### Proof of Theorem 1.3.

Translating Theorem 1.3 into chromatic symmetric polynomials, we want to prove
that for every $M$ we have

(4.2) $\displaystyle
X_{\lambda}^{m+n}(M)=\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\cdot
X_{m^{j}}^{m+n}(M).$

If $M<m$ then both $X_{\lambda}^{m+n}(M)=0$ and $X_{m^{j}}^{m+n}(M)=0$ since
there is no proper coloring of the lower complete graph on $m$ vertices.
Otherwise, if $M=1$ then $m=1$ and so $n=1$ and if $\lambda=\emptyset$ then
$X_{\lambda}^{2}(M)\neq 0$ with $X_{m^{0}}(1)=0$ and
$H_{1}^{1,1}(\emptyset)=0$, and the identity is satisfied. If $\lambda=(1)$
then $X^{2}_{(1)}(1)=x_{1}^{2}$, $[m]_{n}=[1]_{1}=1$, $H_{0}^{1,1}((1))=0$ and
$H_{1}^{1,1}((1))=1$ with $m^{1}=(1)$, and the identity is again trivially
satisfied. This completes the initial conditions for the recursion in Lemma
4.3.

We will prove identity (4.2) by induction on $M$. As the argument above shows,
the identity is trivially satisfied for $M=1$. Suppose that (4.2) is true for
$M-1$, every $m\geq n$, and every shape $\lambda\subset m^{n}$. Naturally, if
$M<m$ then both sides become trivially 0.

The rest of the proof is as follows. We apply Lemma 4.4 to each term
$X_{m^{j}}(M)$ appearing in the RHS of (4.2). We also apply Lemma 4.3 to the
LHS of (4.2), and the inductive hypothesis to $X_{\mu}^{\star}(M-1)$ for all
appearing terms, where $\star$ means any value $\leq m+n$.

Applying Lemma 4.4 to each term $X_{m^{j}}(M)$ appearing in the RHS in (4.2),
we obtain

$\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\cdot
X_{m^{j}}^{m+n}(M)=\frac{1}{[m]_{n}}\sum_{k}H_{k}^{m,n}(\lambda)\left(X^{m+n}_{m^{k}}(M-1)+x_{M}\left(q^{n-k}[m]X^{m+n-1}_{(m-1)^{k}}(M-1)\right.\right.\\\
\left.\left.+[k]X^{m+n-1}_{m^{k-1}}(M-1)+q^{k}[n-k]X^{m+n-1}_{m^{k}}(M-1)\right)+x_{M}^{2}q^{n-k}[k][m]X^{m+n-2}_{(m-1)^{k-1}}(M-1)\right).$

We now apply Lemma 4.3 to the LHS in (4.2). We split the sum in the linear
$x_{M}$ term into $j\in[1,m]$, when
$\lambda/j={\lambda}/^{c}\,{j}\subset(m-1)\times n$ (removing column $j$), and
then $i=m+n+1-j\in[1,n]$, where $\lambda_{j}^{\prime}=0$ and
$m+n-j-\lambda_{j}^{\prime}=i-1$ and $\lambda/i\subset(n-1)\times m$. We then
apply the inductive hypothesis to each $X_{\mu}^{\star}(M-1)$ appearing with
the corresponding rectangular frame, obtaining

$X_{\lambda}^{m+n}(M)=X_{\lambda}^{m+n}(M-1)\\\
+x_{M}\sum_{j=1}^{m+n}q^{m+n-j-\lambda_{j}^{\prime}}X^{m+n-1}_{\lambda/j}(M-1)+x_{M}^{2}\sum_{(i,j)\in\lambda}q^{i-1+(m+n-j-\lambda_{j}^{\prime})}X^{m+n-2}_{\lambda/(i,j)}(M-1)\\\
$
$=\frac{1}{[m]_{n}}\sum_{k}H_{k}^{m,n}(\lambda)X^{m+n}_{m^{k}}(M-1)+x_{M}\sum_{k}\frac{\sum_{j=1}^{m}q^{m+n-j-\lambda_{j}^{\prime}}H_{k}^{m-1,n}({\lambda}/^{c}\,{j})}{[m-1]_{n}}X^{m+n-1}_{(m-1)^{k}}(M-1)\\\
+x_{M}\sum_{k}\frac{\sum_{i=1}^{n}q^{i-1}H_{k}^{m,n-1}(\lambda/i)}{[m]_{n-1}}X^{m+n-1}_{m^{k}}(M-1)\\\
+x_{M}^{2}\sum_{k}\frac{\sum_{(i,j)\in\lambda}q^{i-1+(m+n-j-\lambda_{j}^{\prime})}H_{k}^{m-1,n-1}(\lambda/(i,j))}{[m-1]_{n-1}}X^{m+n-2}_{(m-1)^{k}}(M-1).$

Applying Lemmas 3.6, 3.7 and 3.8 to the sums of $q$-hit numbers above, we get
that

$\displaystyle X_{\lambda}^{m+n}(M)$
$\displaystyle=\frac{1}{[m]_{n}}\sum_{k}H_{k}^{m,n}(\lambda)X^{m+n}_{m^{k}}(M-1)+x_{M}\sum_{k}\frac{q^{n-k}[m-n]H_{k}^{m,n}(\lambda)}{[m-1]_{n}}X^{m+n-1}_{(m-1)^{k}}(M-1)$
$\displaystyle+x_{M}\sum_{k}\frac{q^{k}[n-k]H_{k}^{m,n}(\lambda)+[k+1]H_{k+1}^{m,n}(\lambda)}{[m-n+1][m]_{n-1}}X^{m+n-1}_{m^{k}}(M-1)$
$\displaystyle+x_{M}^{2}\sum_{k}\frac{q^{n-1-k}[k+1]H_{k+1}^{m,n}(\lambda)}{[m-1]_{n-1}}X^{m+n-2}_{(m-1)^{k}}(M-1).$

Simplifying the factors $\frac{[m-1]_{n}}{[m-n]}=\frac{[m]_{n}}{[m]}$ ,
$[m-n+1][m]_{n-1}=[m]_{n}$ and $[m-1]_{n-1}=\frac{[m]_{n}}{[m]}$, and grouping
the terms with $H_{k}^{m,n}(\lambda)$, we can rewrite the above identity as

$X_{\lambda}^{m+n}(M)=\frac{1}{[m]_{n}}\sum_{k}H_{k}^{m,n}(\lambda)\times\left(X^{m+n}_{m^{k}}(M-1)+x_{M}q^{n-k}[m]X^{m+n-1}_{(m-1)^{k}}(M-1)\right.\\\
\left.+x_{M}(q^{k}[n-k]X^{m+n-1}_{m^{k}}(M-1)+[k]X^{m+n-1}_{m^{k-1}}(M-1))+x_{M}^{2}q^{n-k}[k][m]X^{m+n-2}_{(m-1)^{k-1}}(M-1)\right)\\\
=\frac{1}{[m]_{n}}\sum_{k}H_{k}^{m,n}(\lambda)X_{m^{k}}^{m+n}(M),$

where we recognized the sum in the parentheses as the RHS of the recursion for
rectangular CSF, namely Lemma 4.4. This completes the induction.

∎

##  5\. The Abreu–Nigro expansion in the elementary basis

In this section we show that Guay-Paquet’s identity (Theorem 1.3) is
equivalent to Abreu–Nigro’s identity (Theorem 1.2). We start by giving a proof
of Abreu–Nigro’s identity for rectangular shapes.

######  Lemma 5.1 (Abreu–Nigro’s formula for rectangles).

$\displaystyle X_{m^{k}}({\bf x},q)$
$\displaystyle=\left[k\right]!H_{k}^{m+n-k}(m^{k})\cdot
e_{m+n-k,k}+\sum_{r=0}^{k-1}q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{k})\cdot
e_{m+n-r,r}.$

In order to prove this case of the Abreu–Nigro identity we need the following
result.

######  Lemma 5.2 (Guay-Paquet formula for rectangles).

For the shape $(m-1)^{k}\subset n\times m$ we have that,

$[m]X_{(m-1)^{k}}=q^{k}[m-k]X_{m^{k}}+[k]X_{m^{k-1}}.$

######  Corollary 5.3.

$\begin{bmatrix}m-1\\\
k\end{bmatrix}X_{m^{k}}=\sum_{j=0}^{k}\begin{bmatrix}m\\\
j\end{bmatrix}(-1)^{k-j}q^{-(k+j)(k-j+1)/2}X_{(m-1)^{j}}.$

###### Proof of Lemma 5.2.

By Theorem 1.3 for the shape $\lambda=(m-1)^{k}\subset n\times m$ and the
formula for the $q$-hit numbers $H_{r}^{m,n}((m-1)^{k})$ from Proposition 2.17
we obtain

$\displaystyle X_{(m-1)^{k}}$
$\displaystyle=\frac{1}{[m]_{n}}q^{k}[m-1]_{k}[m-k]_{n-k}X_{m^{k}}+\frac{1}{[m]_{n}}[k][m-1]_{k-1}[m-k]_{n-k}X_{m^{k-1}},$
which simplifies to $\displaystyle[m]X_{(m-1)^{k}}$
$\displaystyle=q^{k}[m-k]X_{m^{k}}+[k]X_{m^{k-1}}.$

∎

###### Proof of Lemma 5.1.

We use induction on $m$ and $k$. For the base case, note that
$X_{m^{0}}=[m+n]!e_{m+n}=H_{0}^{m+n}(m^{0})e_{m+n}$. Now, by Lemma 5.2 we have
that

$q^{k}[m-k]X_{m^{k}}=\left([m]X_{(m-1)^{k}}-[k]X_{m^{k-1}}\right).$

Next, we use the induction hypothesis on $X_{(m-1)^{k}}$ and $X_{m^{k-1}}$ and
we simplify our expression, so we want to prove that

(5.1) $q^{k}[m-k]\Big{(}\left[k\right]!H_{k}^{m+n-k}(m^{k})\cdot
e_{m+n-k,k}+\sum_{r=0}^{k-1}q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{k})\cdot
e_{m+n-r,r}\Big{)}\\\
=\left[m\right]\Big{(}\left[k\right]!H_{k}^{m+n-k}((m-1)^{k})\cdot
e_{m+n-k,k}+\sum_{r=0}^{k-1}q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}((m-1)^{k})\cdot
e_{m+n-r,r}\Big{)}\\\
-\left[k\right]\Big{(}\left[k-1\right]!H_{k-1}^{m+n-k+1}(m^{k-1})\cdot
e_{m+n-k+1,k-1}-\sum_{r=0}^{k-2}q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{k-1})\cdot
e_{m+n-r,r}\Big{)}.$

We do so by looking at the coefficient of $e_{m-n-r,r}$ for $0\leq r\leq k$.
For $r=k$, we have that

$q^{k}[m-k]\left[k\right]!H_{k}^{m+n-k}(m^{k})=\left[m\right]\left[k\right]!H_{k}^{m+n-k}((m-1)^{k}),$

which follows from (2.7) using routine simplifications.

For $r=k-1$, we have that

(5.2)
$q^{k}[m-k]q^{k-1}\left[k-1\right]!\left[m+n-2k+2\right]H_{k-1}^{m+n-k}(m^{k})\\\
=\left[m\right]q^{k-1}\left[k-1\right]!\left[m+n-2k+2\right]H_{k-1}^{m+n-k}((m-1)^{k})-\left[k\right]\left[k-1\right]!H_{k-1}^{m+n-k+1}(m^{k-1}).$

Using (2.7), we obtain that (5.2) is equivalent to

(5.3) $\displaystyle
q\left[m-k\right]\left[n-k\right]=\left[m-k+1\right]\left[n-k+1\right]-\left[m+n-2k+1\right].$

For $0\leq r\leq k-2$, we have that

(5.4)
$q^{k}\left[m-k\right]q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{k})\\\
=\left[m\right]q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}((m-1)^{k})-\left[k\right]q^{r}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{k-1}).$

Using (2.7), we obtain that (5.4) is equivalent to

(5.5) $\displaystyle
q^{k-r}\left[m-k\right]\left[n-k\right]=\left[m-r\right]\left[n-r\right]-\left[m+n-r-k\right]\left[k-r\right],$

which is straightforward to verify by expanding both sides. Note that (5.3) is
a particular case of (5.5) by taking $r=k-1$. ∎

We are now ready to prove that the Guay-Paquet’s identity and Abreu–Nigro’s
follow from each other. As a corollary, we obtain a new proof of the latter.
The following example illustrates Abreu–Nigro’s result.

######  Example 5.4.

For $\lambda=(2,1)$ inside a $2\times 3$ board, we have that for $k=2$,
$H_{2}^{3}(\lambda)=q^{3}$, $H_{1}^{3}(\lambda)=2q^{2}+2q$ (see Figure 5), and
$H_{0}^{4}(\lambda)=q^{3}+3q^{2}+3q+1$. Therefore,

$X_{2,1}({\bf x},q)=q^{3}(1+q)e_{{3,2}}({\bf
x})+q(1+q+q^{2})(2q^{2}+2q)e_{{4,1}}({\bf
x})+(1+q+q^{2}+q^{3})(q^{3}+3q^{2}+3q+1)e_{{5}}({\bf x}).$

Figure 5. Placements of $3$ rooks in $3\times 3$ that “hit” $(2,1)$ (in gray)
once and twice and the associated statistic to each rook placement.

###### Proof of Theorem 1.2.

Applying Lemma 5.1 to the RHS of the formula in Theorem 1.3, we obtain that

$\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\cdot
X_{m^{j}}({\bf
x},q)=\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\Big{(}\left[j\right]!H_{j}^{m+n-j}(m^{j})\cdot
e_{m+n-j,j}\Big{)}\\\\[5.05942pt]
+\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\Big{(}q^{r}\sum_{r=0}^{j-1}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{j})\cdot
e_{m+n-r,r}\Big{)}.$

Now, switching the summation order, we have that

$\dfrac{1}{\left[m\right]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\cdot
X_{m^{j}}({\bf
x},q)=\sum_{r=0}^{n}e_{m+n-r,r}\dfrac{1}{\left[m\right]_{n}}\left[r\right]!H_{r}^{m+n-r}(m^{r})H_{r}^{m,n}(\lambda)\\\
+\sum_{r=0}^{n-1}e_{m+n-r,r}\dfrac{1}{\left[m\right]_{n}}\Big{(}q^{r}\sum_{j=r+1}^{n}\left[r\right]!\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{j})H_{j}^{m,n}(\lambda)\Big{)}.$

Thus, we need to show that for $r=k=\ell(\lambda)$,

$\displaystyle\left[m\right]_{n}H_{k}^{m+n-k}(\lambda)$
$\displaystyle=H_{k}^{m+n-k}(m^{k})H_{k}^{m,n}(\lambda)+q^{k}\sum_{j=k+1}^{n}\left[m+n-2k\right]H_{k}^{m+n-k-1}(m^{j})H_{j}^{m,n}(\lambda)$
$\displaystyle=H_{k}^{m+n-k}(m^{k})H_{k}^{m,n}(\lambda),$

since $H_{j}^{m,n}(\lambda)=0$ for $j=k+1,\ldots,n$. We also need to show that
for $r<k=\ell(\lambda)$,

$\displaystyle\left[m\right]_{n}q^{r}\left[m+n-2r\right]H_{r}^{m+n-r-1}(\lambda)$
$\displaystyle=H_{r}^{m+n-r}(m^{r})H_{r}^{m,n}(\lambda)$
$\displaystyle+q^{r}\sum_{j=r+1}^{n}\left[m+n-2r\right]H_{r}^{m+n-r-1}(m^{j})H_{j}^{m,n}(\lambda).$

After using (2.7), these two relations are equivalent to the following
identities relating $q$-hit numbers of $\lambda$ in square boards and
rectangular boards. Thus, the Abreu-Nigro expansion for $X_{\lambda}({\bf
x},q)$ follows now from Lemma 5.5 below, which completes the proof. ∎

######  Lemma 5.5.

Let $\lambda$ be a partition inside an $n\times m$ board and
$k=\ell(\lambda)$, then

(5.6) $\displaystyle\begin{bmatrix}m-k\\\
n-k\end{bmatrix}H_{k}^{m+n-k}(\lambda)$
$\displaystyle=q^{k(n-k)}\left[m+n-2k\right]_{m-k}H_{k}^{m,n}(\lambda),$ and
for $0\leq r<k$, we have $\displaystyle\begin{bmatrix}m-r\\\
n-r\end{bmatrix}H_{r}^{m+n-r-1}(\lambda)$
$\displaystyle=q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}H_{r}^{m,n}(\lambda)$
(5.7) $\displaystyle+\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}H_{j}^{m,n}(\lambda).$

###### Proof.

The first relation follows from a simple combinatorial observation together
with Lemma 2.13. For $k=\ell(\lambda)$, we see that the $k$ rooks on the first
$k$ rows on the board have to be all inside $\lambda$, and all the cells
outside $\lambda$ in these first rows will be empty. Thus

$H_{k}^{N}(\lambda)=H_{k}^{k,\lambda_{1}}(\lambda)q^{k(N-\lambda_{1})}[N-k]!.$

Similarly, by the proof of Lemma I.1 we have

$H_{k}^{m,n}(\lambda)=H_{k}^{k,\lambda_{1}}(\lambda)q^{k(m-\lambda_{1})}\begin{bmatrix}m+n-2k\\\
n-k\end{bmatrix}.$

Substituting these formulas in each side of (5.6) we get the desired identity.

For the second relation, we switch gears and use a deletion-contraction
relation of $q$-hit numbers (Lemma 2.6). The idea is to use induction of the
size of $\lambda$, the deletion-contraction relation for $q$-hit numbers, and
deduce the identity by matching coefficients at each $q$-hit number.

######  Remark 5.6.

An alternative proof appears in Section L, where the $q$-hits are expressed in
terms of $q$-rooks and matching coefficients at each $q$-rook reduces to
$q$-binomial identities.

Let us start with the RHS of (5.5). Denote by

$\displaystyle B_{r}^{m,n}(\lambda)$
$\displaystyle:=q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}H_{r}^{m,n}(\lambda)$
$\displaystyle+\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}H_{j}^{m,n}(\lambda).$

If we apply the deletion-contraction relation in Lemma 2.6 to the $q$-hit
numbers, we have that

$\displaystyle B_{r}^{m,n}(\lambda)$
$\displaystyle=q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}H_{r}^{m,n}(\lambda\backslash
e)$
$\displaystyle+q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}q^{|\lambda/e|-|\lambda|+r+m-1}H_{r-1}^{m-1,n-1}(\lambda/e)$
$\displaystyle-q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}q^{|\lambda/e|-|\lambda|+r+m}H_{r}^{m-1,n-1}(\lambda/e)$
$\displaystyle+\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}H_{j}^{m,n}(\lambda\backslash
e)$ $\displaystyle+\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}q^{|\lambda/e|-|\lambda|+j+m-1}H_{j-1}^{m-1,n-1}(\lambda/e)$
(5.8) $\displaystyle-\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}q^{|\lambda/e|-|\lambda|+j+m}H_{j}^{m-1,n-1}(\lambda/e).$

For the LHS of (5.5), we denote $C_{r}^{m,n}(\lambda):=\begin{bmatrix}m-r\\\
n-r\end{bmatrix}H_{r}^{m+n-r-1}(\lambda)$. Then by Corollary K.2,

$\displaystyle C_{r}^{m,n}(\lambda)$ $\displaystyle=\begin{bmatrix}m-r\\\
n-r\end{bmatrix}H_{r}^{m+n-r-1}(\lambda\backslash e)$
$\displaystyle+\begin{bmatrix}m-r\\\
n-r\end{bmatrix}q^{|\lambda/e|-|\lambda|+r+m+n-r-2}\left(H_{r-1}^{m+n-r-2}(\lambda/e)-qH_{r}^{m+n-r-2}(\lambda/e)\right).$

That is, we have the following deletion-contraction relation for the $C$’s:

(5.9) $\displaystyle C_{r}^{m,n}(\lambda)=C_{r}^{m,n}(\lambda\backslash
e)+q^{|\lambda/e|-|\lambda|+m+n-2}\left(C_{r-1}^{m-1,n-1}(\lambda/e)-q\dfrac{\left[m-r\right]}{\left[m-n\right]}C_{r}^{m-1,n}(\lambda/e)\right).$

Now, we want to compare the two expressions in (5) and (5.9). By _inductive
hypothesis_ ,

$\displaystyle C_{r}^{m,n}(\lambda\backslash e)$
$\displaystyle=q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}H_{r}^{m,n}(\lambda\backslash
e)$ $\displaystyle+\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}H_{j}^{m,n}(\lambda\backslash
e)=B_{r}^{m,n}(\lambda\backslash e).$

These terms appear both in (5) and in (5.9), and so they cancel. We have left
to show that

$q^{|\lambda/e|-|\lambda|+m+n-2}\left(C_{r-1}^{m-1,n-1}(\lambda/e)-q\dfrac{\left[m-r\right]}{\left[m-n\right]}C_{r}^{m-1,n}(\lambda/e)\right)\\\
=q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}q^{|\lambda/e|-|\lambda|+r+m-1}H_{r-1}^{m-1,n-1}(\lambda/e)\\\
-q^{r(n-r-1)}\left[m+n-2r-1\right]_{m-r-1}q^{|\lambda/e|-|\lambda|+r+m}H_{r}^{m-1,n-1}(\lambda/e)\\\
+\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}q^{|\lambda/e|-|\lambda|+j+m-1}H_{j-1}^{m-1,n-1}(\lambda/e)\\\
-\sum_{j=r+1}^{n}q^{r(n-1-j)}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}q^{|\lambda/e|-|\lambda|+j+m}H_{j}^{m-1,n-1}(\lambda/e).$

This last equation simplify to the following identity:

(5.10)
$q^{n-2}\left(C_{r-1}^{m-1,n-1}(\lambda/e)-q\dfrac{\left[m-r\right]}{\left[m-n\right]}C_{r}^{m-1,n}(\lambda/e)\right)\\\
=q^{r(n-r)-1}\left[m+n-2r-1\right]_{m-r-1}\left(H_{r-1}^{m-1,n-1}(\lambda/e)-qH_{r}^{m-1,n-1}(\lambda/e)\right)\\\
+\sum_{j=r+1}^{n}q^{r(n-1-j)+j-1}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]}\left(H_{j-1}^{m-1,n-1}(\lambda/e)-qH_{j}^{m-1,n-1}(\lambda/e)\right),$

In order to show (5.10), we apply first the _inductive hypothesis_ in the
$C$’s together with the relation in Corollary 2.14 to obtain their expansion
in terms of $q$-hit numbers of the form $H_{j}^{m-1,n-1}(\lambda/e)$:

$\displaystyle q^{n-2}C_{r-1}^{m-1,n-1}(\lambda/e)$
$\displaystyle=q^{(r-1)(n-r-1)+n-2}\left[m+n-2r-1\right]_{m-r-1}H_{r-1}^{m-1,n-1}(\lambda/e)$
$\displaystyle+\sum_{j=r}^{n-1}q^{(r-1)(n-2-j)+n-2}\begin{bmatrix}j\\\
r-1\end{bmatrix}\dfrac{\left[m+n-r-j-2\right]_{m-r}}{\left[n-r\right]}H_{j}^{m-1,n-1}(\lambda/e),$
$\displaystyle
q^{n-1}\dfrac{\left[m-r\right]}{\left[m-n\right]}C_{r}^{m-1,n}(\lambda/e)$
$\displaystyle=q^{r(n-r-1)+n-1}\dfrac{\left[m-r\right]}{\left[m-n\right]}\left[m+n-2r-2\right]_{m-r-2}H_{r}^{m-1,n}(\lambda/e)$
$\displaystyle+\sum_{j=r+1}^{n}q^{r(n-1-j)+n-1}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m-r\right]}{\left[m-n\right]}\dfrac{\left[m+n-r-j-2\right]_{m-r-1}}{\left[n-r\right]}H_{j}^{m-1,n}(\lambda/e).$

Finally, we compare the coefficients in (5.10). For
$H_{r-1}^{m-1,n-1}(\lambda/e)$, we have

$\displaystyle LHS$
$\displaystyle=q^{(r-1)(n-r-1)+n-2}\left[m+n-2r-1\right]_{m-r-1}=RHS.$

For $H_{r}^{m-1,n-1}(\lambda/e)$, we have

$\displaystyle LHS$ $\displaystyle=q^{(r-1)(n-2-r)+n-2}\begin{bmatrix}r\\\
r-1\end{bmatrix}\dfrac{\left[m+n-r-r-2\right]_{m-r}}{\left[n-r\right]}-q^{r(n-r-1)+n-1}\left[m-r\right]\left[m+n-2r-2\right]_{m-r-2},$
$\displaystyle RHS$
$\displaystyle=-q^{r(n-r)}\left[m+n-2r-1\right]_{m-r-1}+q^{r(n-2-r)+r}\begin{bmatrix}r+1\\\
r\end{bmatrix}\dfrac{\left[m+n-2r-2\right]_{m-r}}{\left[n-r\right]},$

which simplifies to the relation
$\left[m+n-2r-1\right]=q^{n-r-1}\left[m-r\right]+\left[n-r-1\right]$. This
last relation is a straightforward verification by expanding both sides.

For $H_{j}^{m-1,n-1}(\lambda/e)$, with $r+1\leq j\leq n-1$,

$\displaystyle LHS$ $\displaystyle=q^{(r-1)(n-2-j)+n-2}\begin{bmatrix}j\\\
r-1\end{bmatrix}\dfrac{\left[m+n-r-j-2\right]_{m-r}}{\left[n-r\right]}$
$\displaystyle-q^{r(n-1-j)+n-1}\begin{bmatrix}j\\\
r\end{bmatrix}\left[m-r\right]\dfrac{\left[m+n-r-j-2\right]_{m-r-1}}{\left[n-r\right]},$
$\displaystyle RHS$ $\displaystyle=q^{r(n-2-j)+j}\begin{bmatrix}j+1\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-2\right]_{m-r}}{\left[n-r\right]}-q^{r(n-1-j)+j}\begin{bmatrix}j\\\
r\end{bmatrix}\dfrac{\left[m+n-r-j-1\right]_{m-r}}{\left[n-r\right]},$

which simplifies to the relation
$\left[m+n-r-j-1\right]=q^{n-j-1}\left[m-r\right]+\left[n-j-1\right]$. This
last relation is a straightforward verification by expanding both sides.

∎

##  6\. Variations and applications

###  6.1. Theorems 1.2 and 1.3 in terms of unicellular LLT polynomials

Chromatic symmetric functions of Dyck paths are related to unicellular LLT
polynomials [LLT97] that can be defined as follows. For a Dyck path $d$, let
$G(d)$ be the associated graph and denote

$\displaystyle\operatorname{LLT}_{G(d)}({\bf
x},q):=\sum_{\kappa:V(G(d))\to\mathbb{P}}q^{\operatorname{asc}(\kappa)}{\bf
x}^{\kappa},$

where the sum is over all vertex colorings $\kappa$ of $G(d)$ and
$\operatorname{asc}(\kappa)$ is the same as in the definition of $X_{G}({\bf
x},q)$.

The function $\operatorname{LLT}_{G(d)}({\bf x},q)$ is actually symmetric (see
[AP18, Sec. 3.1]) and the symmetric functions $X_{G(d)}({\bf x},q)$ and
$\operatorname{LLT}_{d}({\bf x},q)$ are related via a plethystic substitution
discovered independently by Carlsson–Mellit [CM18, Prop. 3.4] and Guay-Paquet
[GPc, Lemma 172]:

$\operatorname{LLT}_{G(d)}({\bf x},q)=(q-1)^{n}X_{G(d)}[{\bf x}/(q-1),q],$

where $n$ is the size of the Dyck path. As a consequence of this connection,
any linear relation in one family implies the same relation in the other one.
Since Theorems 1.2 and 1.3 yield a linear relation among certain chromatic
symmetric functions, we immediately obtain the same relations for the
corresponding unicellular LLT polynomials.

######  Corollary 6.1.

Let $\lambda$ be partition inside an $n\times m$ board with
$\ell(\lambda)=k\leq\lambda_{1}$. Then

$\displaystyle\operatorname{LLT}_{G(\lambda)}({\bf x},q)$
$\displaystyle=\frac{1}{[m+n-k]!}H_{k}^{m+n-k}(\lambda)\cdot\operatorname{LLT}_{K(m+n-k,k)}({\bf
x},q)$
$\displaystyle+\sum_{j=0}^{k-1}q^{j}\frac{\left[m+n-2j\right]}{[m+n-j]!}H_{j}^{m+n-j-1}(\lambda)\cdot\operatorname{LLT}_{K(m+n-j,j)}({\bf
x},q),$

where $K(a,b)$ is the disjoint union of complete graphs on vertices
$\\{1,\ldots,a\\}$ and $\\{a+1,\ldots,a+b\\}$.

###### Proof.

Since $X_{K(a,b)}({\bf x},q)=[a]![b]!e_{a,b}$, then Theorem 1.2 yields a
linear relation among $X_{G(\lambda)}({\bf x},q)$, $X_{K(m+n,0)}({\bf
x},q),\ldots,X_{K(m+n-k,k)}({\bf x},q)$. The result then follows from the fact
that every linear relation among a set of chromatic symmetric functions of
Dyck paths has a corresponding relation among unicellular LLT polynomials
[AP18, Prop. 55]. ∎

######  Corollary 6.2.

Let $\lambda$ be a partition inside an $n\times m$ ($n\leq m$) board. Then

$\operatorname{LLT}_{G(\lambda)}({\bf
x},q)=\frac{1}{[m]_{n}}\sum_{j=0}^{n}H_{j}^{m,n}(\lambda)\cdot\operatorname{LLT}_{G(m^{j})}({\bf
x},q).$

###### Proof.

Theorem 1.3 yields a linear relation among $X_{\lambda}({\bf x},q)$,
$X_{m^{0}}({\bf x},q),\ldots,X_{m^{n}}({\bf x},q)$. The result then follows by
the same fact as in the proof above. ∎

###  6.2. The staircase basis

Let $V^{m,n}:=\text{span}_{\mathbb{Q}(q)}\\{X_{\lambda}\mid\lambda\text{
inside an }n\times m\text{ board}\\}$. Consider the set of chromatic symmetric
functions given by rectangular shapes
$\mathcal{R}^{m,n}:=\left\\{X_{m^{j}}({\bf x},q)\right\\}_{j=0}^{n}$. This set
is actually a basis for $V^{m,n}$.

######  Corollary 6.3.

The set $\mathcal{R}^{m,n}$ forms a basis for the $\mathbb{Q}(q)$-vector space
$V^{m,n}$.

To prove this result we need the following result.

######  Proposition 6.4.

Let $\lambda$ be a partition inside the $n\times m$ board and let
$k=\ell(\lambda)\leq\lambda_{1}$

(6.1) $X_{\lambda}({\bf
x},q)=[k]!H_{k}^{m+n-k}(\lambda)s_{2^{k}1^{m+n-2k}}({\bf x})\\\
+\sum_{i=0}^{k-1}s_{2^{i}1^{m+n-2i}}({\bf
x})\Big{(}[k]!H_{k}^{m+n-k}(\lambda)+\sum_{j\geq
i}^{k-1}q^{j}[j]![m+n-2j]H_{j}^{m+n-j-1}(\lambda)\Big{)}.$

###### Proof.

This expansion follows by combining expressing the elementary symmetric
functions in the Schur basis $e_{n-j,j}=\sum_{i=0}^{j}s_{2^{i}1^{n-2i}}$ in
Theorem 1.2. ∎

###### Proof of Corollary 6.3.

By Theorem 1.3 we have that $\mathcal{R}^{m,n}$ span $V^{m,n}$.

By Theorem 1.2 the leading term $X_{m^{j}}({\bf x},q)$ in the $e$-basis is
$H_{j}^{m+n-j}(m^{j})e_{m+n-j,j}$. Since $j\leq m$ we can certainly place $j$
rooks on $m^{j}$ and see that $H_{j}^{m+n-j}(m^{j})\neq 0$. Note that the full
formula is given in Proposition 2.16. Thus the transition matrix between
$\mathcal{R}^{m,n}$ and the $e_{m+n-j,j}$’s is upper triangular with nonzero
diagonal entries, so they are linearly independent and form a basis. ∎

Guay-Paquet considered another basis for the space $V^{m,n}$. This basis is
called the _staircase basis_ since it is indexed by the staircase partitions,
which are partitions inside an $n\times m$ board of the form
$\delta_{j}=(j,j-1,\ldots,1)$, for $j=0,\ldots,n$. Let
$\mathcal{S}^{m,n}:=\left\\{X_{\delta_{j}}({\bf x},q)\right\\}_{j=0}^{n}$.

######  Proposition 6.5 ([GPa]).

The set $\mathcal{S}^{m,n}$ forms a basis for the $\mathbb{Q}(q)$-vector space
$V^{m,n}$.

###### Proof.

We look at the expansion in Proposition 1.2 for $\delta_{j}$. In this case,
$H_{j}^{m+n-j}(\delta_{j})\neq 0$ because we can place $j$ rooks on the main
diagonal of $\delta_{j}$ and place $m+n-2j$ remaining rooks outside
$\delta_{j}$ (for instance, in the main diagonal of the square board).
Therefore, the leading term of $X_{\delta_{j}}({\bf x},q)$ is
$H_{j}^{m+n-j}(\delta_{j})e_{m+n-j,j}\neq 0$. That is, $\mathcal{S}^{m,n}$’s
transfer matrix with the $V^{m,n}$ basis given by $\\{e_{m+n-j,j}\\}$ is upper
triangular with nonzero diagonal and hence is also a basis. ∎

Since the coefficients of $X_{\lambda}({\bf x},q)$ in the $\mathcal{R}^{m,n}$
basis involve $q$-hit numbers, we also want to study the coefficients
appearing in the decomposition of $X_{\lambda}({\bf x},q)$ in this new basis
$\mathcal{S}^{m,n}$. That is, we want to understand the coefficients
$a_{j}^{m,n}(\lambda,q)$ in the expression

(6.2) $X_{\lambda}({\bf x},q)=\sum_{j=0}^{n}a_{j}^{m,n}(\lambda,q)\cdot
X_{\delta_{j}}({\bf x},q).$

Calculations suggest that up to a sign and a power of $q$, these coefficients
are in $\mathbb{N}[q]$.

######  Conjecture 6.6.

Let $\lambda$ be a partition inside an $n\times m$ board ($n\leq m$) and $j$
be fixed, then $a_{j}^{m,n}(\lambda,q)$ is a Laurent polynomial in $q$ whose
coefficients are integers of the same sign.666This conjecture was proved by
Nadeau–Tewari [NT, Thm. 3.5].

######  Example 6.7.

For $\lambda=3$ inside a $2\times 3$ board, we have

$q^{2}X_{3}({\bf x},q)=-(q+1)X_{\varnothing}({\bf x},q)+(q^{2}+q+1)X_{1}({\bf
x},q)+0\cdot X_{21}({\bf x},q).$

Figure 6. Left: the path for $\lambda=3$ inside a $2\times 3$ board. Right:
the three staircase paths $\delta_{0},\delta_{1},\delta_{2}$ for $m=3$ and
$n=2$.

A possible approach to Conjecture 6.6 is looking at the change of bases
between the rectangular basis $\mathcal{R}^{m,n}$ and the staircase basis
$\mathcal{S}^{m,n}$. Let us start showing that the coefficients of the change
of bases determine $a_{j}^{m,n}(\lambda,q)$.

######  Proposition 6.8.

$\displaystyle{a_{j}^{m,n}(\lambda,q)=\frac{1}{[m]_{n}}\sum_{i=0}^{n}H_{i}^{m,n}(\lambda)a_{j}^{m,n}(m^{i},q)}$.

###### Proof.

This follows from basic linear algebra. By Theorem 1.3 and (6.2), we have that

$\displaystyle X_{\lambda}({\bf x},q)$
$\displaystyle=\frac{1}{[m]_{n}}\sum_{k=0}^{n}H_{k}^{m,n}(\lambda)\cdot
X_{m^{k}}({\bf x},q)$
$\displaystyle=\frac{1}{[m]_{n}}\sum_{k=0}^{n}H_{k}^{m,n}(\lambda)\sum_{j=0}^{n}a_{j}^{m,n}(m^{k},q)X_{\delta_{j}}({\bf
x},q).$ Next, we exchange the order of summation to obtain $\displaystyle
X_{\lambda}({\bf x},q)$ $\displaystyle=\sum_{j=0}^{n}X_{\delta_{j}}({\bf
x},q)\frac{1}{[m]_{n}}\sum_{k=0}^{n}H_{k}^{m,n}(\lambda)a_{j}^{m,n}(m^{k},q).$

The result then follows by extracting the coefficient of $X_{\delta_{j}}({\bf
x},q)$ on both sides above. ∎

This means that in order to prove Conjecture 6.6 it suffices to verify it for
$a_{j}^{m,n}(m^{k},q)$.

######  Remark 6.9.

We have the following $(n+1)\times(n+1)$ matrix and its inverse

$\mathcal{A}:=\left(a_{j}^{m,n}(m^{k},q)\right)_{0\leq j,k\leq
n},\quad\mathcal{H}:=\mathcal{A}^{-1}=\dfrac{1}{[m]_{n}}\left(H_{j}^{m,n}(\delta_{k})\right)_{0\leq
j,k\leq n}.$

Moreover $H_{j}^{n,n}(\delta_{n})=A_{n,j+1}(q)$ equals the
$(\operatorname{maj},\operatorname{des})$ $q$-Eulerian polynomials (see
[SW07]) defined by

$\displaystyle{A_{n,j+1}(q):=\sum_{\begin{subarray}{c}w\in\mathfrak{S_{n}}\\\
\operatorname{des}(w)=j\end{subarray}}q^{\operatorname{maj}(w)}},$

where $\operatorname{des}(w)$ and $\operatorname{maj}(w)$ are the number of
descents and the major index of $w$ (see [GR86, Eq. I.1,I.2] and Appendix H).
Also, one can check that the specialization

$\left.H_{j}^{n,n}(\delta_{n-r})\right|_{q=1}=A_{n,j}^{(r)},$

where the $A^{(r)}_{n,j}$ are the $r$-excedence numbers that count the number
of permutations in $\mathfrak{S}_{n}$ with $j$ $r$-excendences $\\{i\mid
w(i)\geq i+r\\}$ (see [FS06, Eli21]).

Note that the coefficients $a_{j}^{m,n}(\lambda,q)$ add up to one.

######  Proposition 6.10.

Let $\lambda$ be a partition inside an $n\times m$ ($n\leq m$) board. Then
$\displaystyle{\sum_{j=0}^{n}a_{j}^{m,n}(\lambda,q)=1}$.

###### Proof.

By Proposition 6.8 and Corollary 2.11 it is enough to show the result for the
$a_{j}^{m,n}(m^{k},q)$. That is, to show that the columns of the matrix
$\mathcal{A}$ from Remark 6.9 add up to one. This follows from basic linear
algebra since the columns of the inverse matrix $\mathcal{A}^{-1}=\mathcal{H}$
also add up to one by Corollary 2.11. ∎

###  6.3. Theorem 1.3 in terms of $q$-rook numbers

Theorem 1.3 expresses $X_{\lambda}({\bf x},q)$ as a linear combination of the
functions $X_{m^{j}}({\bf x},q)$ where the coefficients are normalized $q$-hit
numbers. Since the latter are defined in (2.2) in terms of $q$-rook numbers it
is natural to give an expression for $X_{\lambda}({\bf x},q)$ involving
$q$-rook numbers $R_{i}(\lambda)$.

######  Definition 6.11.

For non-negative integers $m$, $n$, and $i$, with $m\geq n$ and $0\leq i\leq
n$, define

$Y^{m,n}_{i}({\bf x},q):=\sum_{k=0}^{i}(-1)^{i-k}\begin{bmatrix}i\\\
k\end{bmatrix}q^{\binom{k}{2}}X_{m^{k}}({\bf x},q).$

######  Corollary 6.12.

Let $\lambda$ be a partition inside an $n\times m$ board ($n\leq m$). Then

$X_{\lambda}({\bf
x},q)=\dfrac{1}{\left[m\right]!}\sum_{i=0}^{n}\left[m-i\right]!q^{mi-\binom{i}{2}-|\lambda|}R_{i}(\lambda)\cdot
Y^{m,n}_{i}({\bf x},q).$

###### Proof.

We use (2.2) in Theorem 1.3 and change the order to summation to obtain:

$\displaystyle X_{\lambda}({\bf x},q)$
$\displaystyle=\frac{1}{\left[m\right]_{n}}\sum_{k=0}^{n}\dfrac{q^{\binom{k}{2}-|\lambda|}}{\left[m-n\right]!}\sum_{i=k}^{n}\left[m-i\right]!\begin{bmatrix}i\\\
k\end{bmatrix}(-1)^{i+k}q^{mi-\binom{i}{2}}R_{i}(\lambda)X_{m^{k}}({\bf x},q)$
$\displaystyle=\dfrac{1}{\left[m\right]!}\sum_{i=0}^{n}\left[m-i\right]!q^{mi-\binom{i}{2}-|\lambda|}R_{i}(\lambda)\cdot\left(\sum_{k=0}^{i}(-1)^{i-k}\begin{bmatrix}i\\\
k\end{bmatrix}q^{\binom{k}{2}}X_{m^{k}}({\bf x},q)\right).$

The result follows by noting that the sum in parenthesis on the RHS is exactly
${Y_{i}({\bf x},q)}$. ∎

The following example shows that the $Y^{m,n}_{i}({\bf x},q)$ are not
$m$-positive.

######  Example 6.13.

For $m=3$, $n=2$ and $i=1$, we have that

$Y_{1}^{3,2}({\bf x},q)=X_{3^{1}}({\bf x},q)-X_{3^{0}}({\bf x},q).$

Expanding in the $m$-basis, we have that

$\displaystyle Y_{1}^{3,2}({\bf x},q)$
$\displaystyle=\left(-q^{10}-4q^{9}-9q^{8}-14q^{7}-12q^{6}-2q^{5}+11q^{4}+16q^{3}+11q^{2}+4q\right)m_{1,1,1,1,1}$
$\displaystyle+\left(q^{6}+3q^{5}+5q^{4}+5q^{3}+3q^{2}+q\right)m_{2,1,1,1}.$
However, in the $e$-basis we have that
$\displaystyle=\left(q^{6}+3q^{5}+5q^{4}+5q^{3}+3q^{2}+q\right)e_{4,1}$
$\displaystyle-\left(q^{10}+4q^{9}+9q^{8}+14q^{7}+17q^{6}+17q^{5}+14q^{4}+9q^{3}+4q^{2}+q\right)e_{5}$

As noted by John Shareshian (private communication), the expansion of the
$Y_{i}^{m,n}$ in the elementary basis in the previous example is a product of
$q$-numbers. This is always the case as the next result shows.

######  Proposition 6.14.

Consider the functions $Y_{i}({\bf x},q)$, then

$Y_{i}({\bf
x},q)=q^{in}[m]![i]![m+n-2i-1]_{n-i-1}\sum_{r=0}^{i}(-1)^{i+r}q^{\frac{(r-2i)(r+1)}{2}}[m+n-2r]\begin{bmatrix}m+n-r-i-1\\\
i-r\end{bmatrix}e_{m+n-r,r}.$

###### Proof.

By [NT, §4.4.2], the Abreu–Nigro expansion of $X_{m^{k}}({\bf x},q)$ in Lemma
5.1 can be written compactly as

$X_{m^{k}}({\bf
x},q)=\sum_{j=0}^{k}q^{j}[j]![m+n-2j]H_{j}^{m+n-j-1}(m^{k})\cdot e_{m+n-j,j}.$

Thus the coefficient $c_{r}(q)$ of the elementary basis $e_{m+n-r,r}$ in
$Y_{i}({\bf x},q)$ equals

$c_{r}(q)=\sum_{k=r}^{i}(-1)^{i-k}\begin{bmatrix}i\\\
k\end{bmatrix}q^{\binom{k}{2}+r}[r]![m+n-2r]H_{r}^{m+n-r-1}(m^{k}).$

Next, we use the explicit expression for the $q$-hit numbers of rectangles in
Proposition 2.16 and standard manipulations to obtain

$c_{r}(q)=(-1)^{i+r}[i]![m+n-r-i-1]![m+n-2r][m]_{r}q^{nr-\binom{r+1}{2}}\times\\\
\times\sum_{k=r}^{i}(-1)^{k-r}q^{\binom{k-r}{2}}\begin{bmatrix}n-r-1\\\
k-r\end{bmatrix}\begin{bmatrix}m+n-r-1-k\\\ i-k\end{bmatrix}.$

Lastly, we simplify the sum on the RHS above using the following identity of
$q$-binomials

$\sum_{a+b=c}(-1)^{a}q^{\binom{a}{2}}\begin{bmatrix}A\\\
a\end{bmatrix}\begin{bmatrix}B+b\\\
b\end{bmatrix}=q^{Ac}\begin{bmatrix}B-A+c\\\ c\end{bmatrix}$

for $A=n-r-1$, $B=m+n-r-1-i$, and $c=i-r$, and do standard manipulations, to
obtain the desired result. ∎

##  7\. Final Remarks

###  7.1. A tale of two variants of $q$-hit numbers

To our surprise, the $q$-hit numbers appearing in Theorems 1.2 and Theorem 1.3
are not exactly the Garsia–Remmel $q$-hit numbers denoted by
$\widetilde{H}_{j}^{n}(\lambda)$ but instead, they are off by a power of $q$
(see Proposition H.1). Thus, these two variants of $q$-hit numbers satisfy
different versions of deletion-contraction (see Appendix K).

While working on this project, we have encountered two different variants of
Dworkin’s statistic for the Garsia–Remmel $q$-hit numbers
$\widetilde{H}_{n}^{j}(\lambda)$ for $\lambda\subset n\times n$. In [Dwo98,
Sec. 7, Fig. 3] Dworkin gives a statistic with a rule that is the transpose of
the statistic in Definition 2.7. However, this statistic actually yields our
$q$-hit numbers $H_{j}^{n}(\lambda)$ (this can be seen from the change of
basis to $q$-rook numbers and because the latter stay invariant under
conjugation) and not the Garsia–Remmel $q$-hit numbers
$\widetilde{H}_{j}^{n}(\lambda)$ as claimed in [Dwo98]. In [HR01, Fig. 5],
Haglund and Remmel give a statistic similar to Dworkin that they attribute to
him (see Definition G.2) that does yield the Garsia–Remmel $q$-hit numbers.
The authors in [HR01] give a weight-preserving bijection between their version
of Dworkin’s statistic and Haglund’s statistic for
$\widetilde{H}_{j}^{n}(\lambda)$ from [Hag98] thus proving the validity of
their version of Dworkin’s statistic.

See Appendices G and H for more details on the Garsia–Remmel $q$-hit numbers
and their relation to our $q$-hit numbers. And see Appendix I for a proof of
Theorem 2.9 which shows the statistic in Definition 2.7 that yields the
$q$-hit numbers $H_{m,n}^{j}(\lambda)$.

For a recent $q$-analogue of hit numbers for general boards, not just Ferrers
boards, see [LM18].

###  7.2. A conjectured deletion-contraction relation for $q$-hit numbers

We use the deletion-contraction of $q$-hit numbers (Lemma 2.6) in our proof of
Theorem 1.2. It appears that the $q$-hit numbers satisfy a similar deletion-
contraction relation with simpler powers of $q$. For more details in another
deletion-contraction relation of $q$-hit numbers see Appendix K.

######  Conjecture 7.1.

Let $\lambda$ be a partition inside an $n\times m$ board and $e$ be an outer
corner of $\lambda$. Then we have the following recursion:
$H_{j}^{m,n}(\varnothing)=\left[m\right]_{n}\delta_{j,0}$ and

$qH_{j}^{m,n}(\lambda)=H_{j}^{m,n}(\lambda\backslash
e)+q^{m}H_{j-1}^{m-1,n-1}(\lambda/e)-H_{j}^{m-1,n-1}(\lambda/e).$

###  7.3. Combinatorial proof of Theorem 1.3

Guay-Paquet’s proof of Theorem 1.3 sketched in [GPa] is based on the idea of
dual basis from linear algebra. He shows that the vector space $V^{m,n}$,
together with the basis $\mathcal{R}^{m,n}$, has a dual vector space
$V^{*}_{m,n}:=\text{span}_{\mathbb{Q}(q)}\big{(}P(x;\lambda)/[m]_{n}\mid\lambda\subset
n\times m\big{)}$ with dual basis $\\{x^{i}\mid i=0,\ldots n\\}$. Now, the
dual basis coefficients are given by the normalized $q$-hit numbers
$H_{i}^{m,n}(\lambda)/[m]_{n}$ as shown (up to normalization) in (2.1).

In contrast, our proof of Theorem 1.3 uses $q$-rook theory, it would be
interesting to find a bijective proof of this result relating colorings with
rook placements.

Specifically, we can rewrite the identity as

$[m]_{n}X_{\lambda}({\bf
x},q)=\sum_{k=0}^{n}H_{k}^{m,n}(\lambda)X_{m^{k}}({\bf x},q).$

Matching monomials in ${\bf x}$, powers of $q$, and interpreting
$[m]_{n}=H_{0}^{m,n}(\emptyset)$ we are looking for a bijection
$\varphi_{\nu}$ for every $\nu=(2,\ldots,2,1,\ldots)$ as follows.

_From:_

Pairs of a rook placement $P_{0}^{m,n}(\emptyset)$ of $n$ rooks on $n\times m$
board with $\operatorname{inv}(P)$ inversions and a proper coloring
$\kappa(\lambda,\nu)$ of $G_{\lambda}$ of type $\nu$ and
$\operatorname{asc}(\kappa)$ total ascents.

_Into:_

Triples $k,P_{k}^{m,n}(\lambda),\kappa(m^{k},\nu)$ consisting of an integer
$k\in[0,n]$, a rook placement on $n\times m$ with exactly $k$ rooks inside
$\lambda$, and a proper coloring of $G_{m^{k}}$ of type $\nu$,

_such that_

$\operatorname{asc}(\kappa(m^{k},\nu))+\operatorname{inv}(P_{k}^{m,n})=\operatorname{asc}(\kappa)+\operatorname{inv}(P).$

###  7.4. Combinatorial proof of Theorem 1.2

There are other rules for the elementary basis expansion of $X_{\lambda}({\bf
x},q)$. In particular, Cho–Huh [CH19b] give an expansion in terms of
$P$-tableaux of shape $2^{j}1^{m+n-2j}$ such that there is no $s\geq j+2$ such
that $(a_{i,1},a_{s,1})\in\lambda$ for all $i\in\\{\ell+1,\ldots,s-1\\}$ (see
[SW16, Sec. 6] for details on $P$-tableaux). We denote such set of
$P$-tableaux by $\mathcal{T}^{\prime}((m+n-j,j))$. Let

$c_{j}^{m,n}(q):=\sum_{T\in\mathcal{T}^{\prime}(m+n-j,j)}q^{\operatorname{inv}_{G(\lambda)}(T)}.$

For the definitions of $P$-tableau and $\operatorname{inv}_{G}(T)$ see [SW16,
Sec. 6].

It would be interesting to find a weight-preserving bijection that shows that

$c_{j}^{m,n}(q)=\begin{cases}[j]!H_{j}^{m+n-j}(\lambda)&\text{ if
}j=\ell(\lambda),\\\ q^{j}[j]![m+n-2j]H_{j}^{m+n-j-1}(\lambda)&\text{ if
}j<\ell(\lambda).\end{cases}$

For instance, for the case $j=\ell(\lambda)$, we need to establish a weight-
preserving bijection between the rook placements with $j$ rooks inside
$\lambda$, together with some labeling of the ones inside $\lambda$ to account
for $\left[j\right]!$, and $\mathcal{T}^{\prime}((m+n-j,j))$.

###  7.5. Extending Theorems 1.2 and 1.3 to bicolored graphs

Both Theorem 1.2 and Theorem 1.3 are $q$-analogues of a special cases of
respective results by Stanley–Stembridge [SS93, Thm. 4.3] and by Guay-Paquet
[GPb, Prop. 4.1 (iv)] for bicolored graphs. It would be interesting to find a
$q$-analogue of these more general results for bicolored graphs $G$. However,
for such graphs $G$ the function $X_{G}({\bf x},q)$ may not be symmetric.

###  7.6. Beyond the abelian case

We have studied the chromatic symmetric function $X_{G(d)}({\bf x},q)$ for
Dyck paths $d$ of bounce two, aka the abelian case [HP19]. Recently Cho–Hong
[CH19a] verified Conjecture 1.1 when $q=1$ for Dyck paths of bounce three.
Their expansion is in terms of certain $P$-tableaux. For these Dyck paths, it
would be interesting to find an $e$-expansion involving $q$-rook theory or
extending Theorem 1.3.

## References

  * [AN21] A. Abreu and A. Nigro.  Chromatic symmetric functions from the modular law.  J. Comb. Theory, Ser. A, 180:105407, 2021.
  * [AP18] P. Alexandersson and G. Panova.  LLT polynomials, chromatic quasisymmetric functions and graphs with cycles.  Discrete Math., 341(12):3453–3482, 2018.
  * [AS22] P. Alexandersson and R. Sulzgruber.  A combinatorial expansion of vertical-strip llt polynomials in the basis of elementary symmetric functions.  Advances in Mathematics, 400:108256, 2022.
  * [CH19a] S. Cho and J. Hong.  Positivity of chromatic symmetric functions associated with Hessenberg functions of bounce number 3.  In: ArXiv:https://arxiv.org/abs/1910.07308, 2019\.
  * [CH19b] S. Cho and J. Huh.  On $e$-positivity and $e$-unimodality of chromatic quasisymmetric functions.  SIAM Journal on Discrete Mathematics, 33(4):2286–2315, 2019.
  * [CM18] E. Carlsson and A. Mellit.  A proof of the shuffle conjecture.  J. Amer. Math. Soc., 31(3):661–697, 2018.
  * [Dwo98] M. Dworkin.  An interpretation for garsia and remmel’s $q$-hit numbers.  J. Combin. Theory Ser. A, 81(2):149–175, 1998.
  * [Eli21] S. Elizalde.  Descents on quasi-Stirling permutations.  J. Combin. Theory Ser. A, 180:Paper No. 105429, 35, 2021.
  * [FS06] D. Foata and M.-P. Schützenberger.  Théorie géométrique des polynômes eulériens, volume 138.  Springer, 2006.
  * [GPa] M. Guay-Paquet.  Linear relations between $q$-chromatic symmetric functions.  Non-published, shared by private communication.
  * [GPb] M. Guay-Paquet.  A modular relation for the chromatic symmetric functions of (3+1)-free posets.  In: ArXiv:1306.2400 (2013).
  * [GPc] M. Guay-Paquet.  A second proof of the shareshian–wachs conjecture, by way of a new hopf algebra.  In: ArXiv:1601.05498 (2016).
  * [GR86] A. M. Garsia and J.B. Remmel.  $q$-counting rook configurations and a formula of Frobenius.  J. Combin. Theory Ser. A, 41:246–275, 1986.
  * [Hag98] J. Haglund.  $q$-rook polynomials and matrices over finite fields.  Adv. in Appl. Math., 20(4):450–487, 1998.
  * [HP19] M. Harada and M. E. Precup.  The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture.  Algebr. Comb., 2(6):1059–1108, 2019.
  * [HR01] J. Haglund and J. B. Remmel.  Rook theory for perfect matchings.  Adv. in Appl. Math., 27(2-3):438–481, 2001.  Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000).
  * [HW20] J. Haglund and A.T. Wilson.  Macdonald polynomials and chromatic quasisymmetric functions.  Electron. J. Comb., 27(3):P3.37, 2020.
  * [LLT97] A. Lascoux, B. Leclerc, and J.-Y. Thibon.  Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras, and unipotent varieties.  J. Math. Phys., 38(2):1041–1068, 1997.
  * [LM18] J. B. Lewis and A. H. Morales.  Rook theory of the finite general linear group.  Exp. Math., pages 1–19, 2018.
  * [LS] S. J. Lee and S. K. Y. Soh.  Explicit formulas for e-positivity of chromatic quasisymmetric functions.  In: ArXiv:2201.13080 (2022).
  * [Mor06] K. E. Morrison.  Integer sequences and matrices over finite fields.  J. Integer Seq., 9(2):Article 06.2.1, 28, 2006.
  * [NT] P. Nadeau and V. Tewari.  Down-up algebras and chromatic symmetric functions.  In: ArXiv:2208.04175 (2022).
  * [SCc08] The Sage-Combinat community.  Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008.  http://combinat.sagemath.org.
  * [SS93] R. P. Stanley and J. R. Stembridge.  On immanants of Jacobi-Trudi matrices and permutations with restricted position.  J. Combin. Theory Ser. A, 62(2):261–279, 1993.
  * [Sta95] R. P. Stanley.  A symmetric function generalization of the chromatic polynomial of a graph.  Adv. Math., 111:166–194, 1995.
  * [SW07] J. Shareshian and M. Wachs.  $q$-Eulerian polynomials: excedance number and major index.  Electronic Research Announcements of the American Mathematical Society, 13(4):33–45, 2007.
  * [SW16] J. Shareshian and M. L. Wachs.  Chromatic quasisymmetric functions.  Adv. Math., 295:497–551, 2016.
  * [The19] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 8.9), 2019.  https://www.sagemath.org.

## Appendix

In this appendix we give more details on the two variants of the statistic on
the Garsia–Remmel $q$-hit numbers, their relation, and their deletion-
contraction relations.

###  G. Garsia-Remmel $q$-hit numbers and Dworkin’s statistic

We start by defining the original version of the $q$-hit numbers given by
Garsia–Remmel that is different than our $q$-hit numbers. Recall that $m\geq
n$.

######  Definition G.1 ([GR86]).

For $\lambda$ inside an $n\times n$ board, we define the Garsia-Remmel _$q$
-hit polynomial_ of $\lambda$ by

(G.1)
$\sum_{i=0}^{n}\widetilde{H}_{i}^{n,n}(\lambda)x^{i}:=\sum_{i=0}^{n}R_{i}(\lambda)\left[n-i\right]!\prod_{k=n-i+1}^{n}(x-q^{k}).$

Garsia and Remmel [GR86, Theorem 2.1] showed that
$\widetilde{H}_{i}^{n}(\lambda):=\widetilde{H}_{i}^{n,n}(\lambda)$ is a
polynomial with nonnegative coefficients and Dworkin [Dwo98] and Haglund
[Hag98] gave different statistics realizing these $q$-hit numbers. We focus on
Dworkin’s statistic (as presented in [HR01], see Section 7.1) since it is very
similar to the statistic in Definition 2.7.

######  Definition G.2 (Dworkin’s statistic for the $q$-hit numbers [HR01]).

Let $\lambda$ be a partition inside an $n\times m$ board. Given a placement
$p$ of $n$ non-attacking rooks on an $n\times n$ board, with exactly $j$
inside $\lambda$, let $\operatorname{stat_{D}}(p)$ be the number of cells $c$
in the $n\times m$ board such that

  * (i)

there is no rook in $c$,

  * (ii)

there is no rook below $c$ on the same column, and either,

  * (iii)

if $c$ is in $\lambda$ then the rook on the same row of $c$ is either outside
$\lambda$ or else to the left of $c$; or

  * (iv)

if $c$ is not in $\lambda$ then the rook on same row of $c$ is not in
$\lambda$ and to the left of $c$.

######  Example G.3.

Consider the partition $\lambda=(4,3,2,2)$ inside a $6\times 6$ board. In
Figure 7A, we present a rook placement $p$ of six rooks on the $6\times 6$
board with three hits on $\lambda$ where $\operatorname{stat_{D}}(p)=4$.

A

B

C

Figure 7. (A) For the same rook placement $p$, examples of (A) the statistic
$\operatorname{stat_{D}}(p)$ for the Garsia–Remmel $q$-hit numbers, and (B) of
the statistic $\operatorname{stat}(p)$ for our $q$-hit numbers. Note how the
empty cells in the calculation of one statistic correspond to the double
crossings in the other. Moreover in each placement
$\operatorname{stat}(p)-\operatorname{cross}(p)=j\cdot m-|\lambda|$. (C)
Illustration of bijection between rook placement counted in
$H_{j}^{m,m}(\lambda)$ and rook placements counted in $H_{j}^{m,n}(\lambda)$
and $R_{m-n}((m-n)^{m-n})$, respectively.

######  Theorem G.4 (Dworkin [Dwo98, HR01]).

Let $\lambda$ be a partition inside an $n\times n$ board and $j=0,\ldots,n$
then

$\widetilde{H}_{j}^{n}(\lambda)=\sum_{p}q^{\operatorname{stat_{D}}(p)},$

where the sum is over all placements $p$ of $n$ non-attacking rooks on an
$n\times n$ board with exactly $j$ rooks inside $\lambda$.

###  H. Relation between $q$-hit numbers $H_{j}^{n}(\lambda)$ and
$\widetilde{H}_{j}^{n}(\lambda)$

The next result shows that our $q$-hit numbers and the Garsia–Remmel $q$-hit
numbers are off by a power of $q$. We show this from the respective
definitions of each $q$-hit numbers from the generating polynomials of
$q$-rook numbers. We will ultimately show Theorem 2.9 by showing that for a
rook placement $p$, the statistics $\operatorname{stat}(p)$ and
$\operatorname{stat_{D}}(p)$ are off by the same power (see Lemma I.2).

######  Proposition H.1.

(H.1)
$\displaystyle\widetilde{H}_{j}^{m}(\lambda):=q^{|\lambda|-jm}H_{j}^{m}(\lambda).$

###### Proof.

We compare (G.1) and (2.1). Substituting $xq^{-m}$ and multiplying by
$q^{|\lambda|}$ in (2.1), rewriting the factor
$q^{mi-\binom{i}{2}}=q^{\sum_{k=0}^{i-1}m-k}$ and rewriting the $q$-Pochhammer
symbol we have

$\displaystyle\sum_{j=0}^{m}H_{j}^{m}(\lambda)q^{|\lambda|}(xq^{-m})^{j}$
$\displaystyle=\sum_{i=0}^{m}R_{i}(\lambda)[m-i]!(-1)^{i}\prod_{k=0}^{i-1}q^{m-k}(1-xq^{-m}q^{k})$
$\displaystyle=\sum_{i=0}^{m}R_{i}(\lambda)[m-i]!\prod_{k=0}^{i-1}(x-q^{m-k}),$

which is the RHS of (G.1) for $m=n$. Comparing coefficients at $x^{j}$ we
obtain the desired identity. ∎

As a consequence of the symmetry and reciprocity of the Garsia–Remmel $q$-hit
numbers we obtain the following result. Given $\lambda$ inside $m\times m$
board, let $\overline{\lambda}$ be the complementary partition of $\lambda$,
viewed as a Ferrers board.

######  Corollary H.2.

(H.2) $H_{j}^{m}(\lambda)=\widetilde{H}_{m-j}^{m}(\overline{\lambda}).$

###### Proof.

The result follows by combining Proposition H.1 with both the reciprocity
[Dwo98, Lemma 8.19] and the symmetry [Dwo98, Thm. 9.22] of the Garsia–Remmel
$q$-hit numbers:

$\displaystyle\widetilde{H}_{j}^{m}(\lambda,q)$
$\displaystyle=q^{\binom{m}{2}}\widetilde{H}_{m-j}^{m}(\overline{\lambda},q^{-1}),$
$\displaystyle
q^{\binom{m}{2}+|\lambda|-jm}\widetilde{H}_{j}^{m}(\lambda,q^{-1})$
$\displaystyle=\widetilde{H}_{j}^{m}(\lambda,q).$

∎

###  I. Proof of Theorem 2.9

Let $\widehat{H}^{m,n}_{j}(\lambda)$ be the sum in the RHS of (2.5). The next
result is an analogue of Lemma 2.13 for $\widehat{H}^{m,n}_{j}(\lambda)$.

######  Lemma I.1.

Let $\lambda$ be a partition inside an $n\times m$ board. Then

$\widehat{H}^{m,n}_{j}(\lambda)=\frac{1}{[m-n]!}\widehat{H}^{m,m}_{j}(\lambda).$

###### Proof.

We claim that

(I.1) $\widehat{H}^{m,n}_{j}(\lambda)=\widehat{H}_{j}^{m,n}(\lambda)\cdot
R_{m-n}((m-n)^{m-n}).$

The result then follows since by Proposition 2.2,
$R_{m-n}((m-n)^{m-n})=[m-n]!$. This $q$-factorial corresponds to the
$q^{\operatorname{stat}}$-weighted enumeration of rook placements in a
$(m-n)\times(m-n)$ board. Let $p$ be a rook placement on an $m\times m$ board
with $j$ rooks inside $\lambda\subset m\times n$ and $p^{\prime}$ be the
placement obtained by restricting $p$ to the top $m$ rows. Then the bottom
$m-n$ rows contain $m-n$ rooks outside $\lambda$ and after removing the $n$
columns occupied by rooks from the top $n$ column we obtain a placement
$p^{\prime\prime}$ of $m-n$ rooks on an $(m-n)\times(m-n)$ board. This gives a
bijection $p\mapsto(p^{\prime},p^{\prime\prime})$ between the rook placements
on the LHS and pairs of rook placements from the RHS of (I.1). See Figure 7C
Moreover, the bijection is weight-preserving. That is

$\displaystyle\operatorname{stat}(p)=\operatorname{stat}(p^{\prime})+\operatorname{stat}(p^{\prime\prime})=\operatorname{stat}(p^{\prime})+\operatorname{inv}(p^{\prime\prime}),$

where $\operatorname{inv}(p^{\prime\prime})$ is the statistic of the $q$-rook
numbers. This weight-preserving bijection gives the desired result. ∎

The next lemma shows that for a fixed rook placement the statistics
$\operatorname{stat}(\cdot)$ and $\operatorname{stat_{D}}(\cdot)$ are related.

######  Lemma I.2.

Let $\lambda$ be a partition inside an $m\times m$ board. Given a placement
$p$ of $m$ non-attacking rooks on an $m\times m$ board with $j$ rooks inside
$\lambda$ then

$\operatorname{stat}(p)-\operatorname{stat_{D}}(p)=j\cdot m-|\lambda|.$

######  Example I.3.

Consider the partition $\lambda=(4,3,2,2)$ inside a $6\times 6$ board. Figure
7B illustrates an example of a placement $p$ of six rooks on the $6\times 6$
board with $j=3$ hits on $\lambda$ with $\operatorname{stat}(p)=11$. Figure 7A
illustrates for the same rook placement $p$ that
$\operatorname{stat_{D}}(p)=4$. Note that

$\operatorname{stat}(p)-\operatorname{stat_{D}}(p)=7=3\cdot 6-|\lambda|.$

The proof of Lemma I.2 is postponed to the end of the section. We now use this
lemma to complete the proof of our main result of this appendix.

###### Proof of Theorem 2.9.

By Lemma I.2 we have that

$\widetilde{H}_{j}^{m,m}(\lambda)=q^{|\lambda|-jm}\widehat{H}^{m,m}_{j}(\lambda).$

Next, by comparing this identity with Proposition H.1 we conclude that
$H_{j}^{m,m}(\lambda)=\widehat{H}^{m,m}_{j}(\lambda)$. Finally, combining this
with both Lemma 2.13 and Lemma I.1 we conclude that
$H_{j}^{m,n}(\lambda)=\widehat{H}^{m,n}_{j}(\lambda)$ as desired. ∎

The rest of the section is devoted to the proof of Lemma I.2. We need the
following definition.

######  Definition I.4 (crossing statistic for the $q$-hit numbers).

Let $\lambda$ be a partition inside an $m\times m$ board. Given a placements
$p$ of $m$ non-attacking rooks on an $n\times m$ board, with exactly $j$ rooks
inside $\lambda$, let $\operatorname{cross}(p)$ be the number of cells $c$ in
the $m\times m$ board such that

  * (i)

there is no rook in $c$,

  * (ii)

there is a rook on the same column and below $c$,

  * (ii)

if $c$ is in $\lambda$ then there is a rook on the same row in $\lambda$ to
the right of $c$,

  * (iii)

if $c$ is not in $\lambda$ then either there is a rook on the same row in
$\lambda$ or a rook on the same row to the right of $c$.

In other words, $\operatorname{cross}(p)$ is the number of cells that have
double crossings after the rook cancellations used to obtain
$\operatorname{stat}(p)$. See Remark 2.8 and Figure 7B.

######  Example I.5.

For the rook placement $p$ in Example I.3 and Figure 7B we have that
$\operatorname{stat}(p)=11$ and $\operatorname{cross}(p)=4$.

First observe that for a rook placement $p$ on the $m\times m$ board we have
that $\operatorname{stat_{D}}(p)=\operatorname{cross}(p)$, since the rays in
$\operatorname{stat}$ and $\operatorname{stat_{D}}$ are complementary to each
other and the crossings in one directly correspond to the empty boxes in the
other. Therefore Lemma I.2 follows from the next lemma.

######  Lemma I.6.

Let $\lambda$ be a partition inside an $m\times m$ Given a placement $p$ of
$m$ non-attacking rooks on an $m\times m$ board with $j$ rooks inside
$\lambda$ then

(I.2) $\operatorname{stat}(p)-\operatorname{cross}(p)=j\cdot m-|\lambda|.$

###### Proof.

We proceed by induction on $|\lambda|$ for $\lambda\subset m\times m$. When
$\lambda=\emptyset$ we only have rook placements for $j=0$, and then it is
clear that,

$\operatorname{stat}(p)=\operatorname{stat_{D}}(p)=\operatorname{cross}(p)=\operatorname{inv}(w),$

the number of inversions of the permutation $w$ corresponding to the rook
diagram. Thus the identity (I.2) is verified.

Suppose the identity (I.2) holds for all $|\lambda|\leq N$ and then for any
$j=0,\ldots,m$. Let $\nu$ be a partition of $N+1$ and $\nu=\lambda+e$, where
$e$ is a corner cell. Let $p$ be a rook configuration with $j$ rooks in $\nu$,
and let $p^{\prime}$ be the same rook configuration on $\lambda$ (so there are
$j$ or $j-1$ rooks in $\lambda$). Note that cell $e$ cannot be empty since
there is a rook in its row, which is either in $\nu$, and hence the rook’s
“arm” crosses $e$ or is outside in which case the wrap-around also crosses
$e$. We now consider several cases:

  * Case 1.

Cell $e$ has a rook and hence the horizontal arm stops at $e$ as the border of
$\nu$. Thus there are no crossings in the row of $e$. Suppose there are $k$
empty boxes in the row of $e$, then there are also $m-k-1$ vertical crossings
in this row. Now consider $p^{\prime}$ as a configuration with $j-1$ rooks in
$\lambda$. The rook in $e$ is outside $\lambda$ and this time the entire row
is crossed, so all empty cells have now a horizontal line and all vertically
crossed cells have now a double crossing. Thus

$\qquad\qquad\operatorname{stat}(p^{\prime})-\operatorname{cross}(p^{\prime})=\operatorname{stat}(p)-k-(\operatorname{cross}(p)+m-k-1)=\operatorname{stat}(p)-\operatorname{cross}(p)-m+1.$

By induction we have

$\operatorname{stat}(p^{\prime})-\operatorname{cross}(p^{\prime})=m(j-1)-|\lambda|=j\dot{m}-|\nu|-m+1,$

and matching sides we obtain the desired identity in this case.

  * Case 2.

The rook in the row of $e$ is to the left of $e$. Then either $e$ is a double
crossing or is only a horizontal crossing. Then in the rook placement
$p^{\prime}$ there is no horizontal line crossing $e$. If $e$ was a double
crossing in $p$, then it is neither a double crossing nor empty cell in
$p^{\prime}$, and if $e$ was not a double crossing in $p$ then it became an
empty cell in $p^{\prime}$. In both cases we have

$\operatorname{stat}(p^{\prime})-\operatorname{cross}(p^{\prime})=\operatorname{stat}(p)-\operatorname{cross}(p)+1.$

Since the number of rooks inside $\lambda$ is still $j$ then we have

$\operatorname{stat}(p)-\operatorname{cross}(p)=\operatorname{stat}(p^{\prime})-\operatorname{cross}(p^{\prime})-1=j\cdot
m-|\lambda|-1=j\cdot m-|\nu|.$

This gives the desired identity in this case.

  * Case 3.

The rook in the row of $e$ is to right of $e$, so outside $\nu$. Then again
there is a horizontal line crossing $e$, so $e$ is either a double crossing in
$p$ or neither a double crossing nor an empty cell in $p$. In both cases when
we remove $e$ from $\nu$ we either turn the double crossing on $e$ in $p$ to a
not a double crossing in $p^{\prime}$ or from not a double crossing in $e$ to
an empty cell in $p^{\prime}$. Thus, again

$\operatorname{stat}(p^{\prime})-\operatorname{cross}(p^{\prime})=\operatorname{stat}(p)-\operatorname{cross}(p)+1.$

Since the number of rooks inside $\lambda$ is still $j$ then we have

$\operatorname{stat}(p)-\operatorname{cross}(p)=\operatorname{stat}(p^{\prime})-\operatorname{cross}(p^{\prime})-1=j\cdot
m-|\lambda|-1=j\cdot m-|\nu|.$

This gives the desired identity in this case.

This completes the proof. ∎

###  J. Symmetry of $q$-hit numbers of rectangular boards

Since the Garsia–Remmel $q$-hit numbers are symmetric polynomials in
$\mathbb{N}[q]$ [GR86, Dwo98, Hag98], then so are $H_{j}^{m,n}(\lambda)$.

######  Corollary J.1.

The $q$-hit numbers $H_{j}^{m,n}(\lambda)$ are symmetric polynomials in
$\mathbb{N}[q]$.

###### Proof.

By Theorem 2.9 we have that $H_{j}^{m,n}(\lambda)$ are in $\mathbb{N}[q]$. By
Lemma 2.13 and Proposition H.1 we have that

$H_{j}^{m,n}(\lambda)=\frac{1}{[m-n]!}q^{|jm-\lambda|}\widetilde{H}_{j}^{m}(\lambda).$

Now $[m-n]!$ is a symmetric polynomial in $\mathbb{N}[q]$ and so are the
Garsia–Remmel $q$-hit numbers $\widetilde{H}_{j}^{m}(\lambda)$ [Hag98, Sec.
5]. Therefore, the result follows. ∎

###  K. Deletion-contraction for $q$-hit numbers

In this section we give a proof of the deletion-contraction relations for the
$q$-hit numbers $H_{j}^{m,n}(\lambda)$ and $\widetilde{H}_{j}^{m,n}(\lambda)$.

######  Lemma K.1 ([Dwo98, Thm. 6.11]).

Let $\lambda$ be a partition inside an $n\times m$ board and $e$ be an outer
corner of $\lambda$. Then we have the following recursion:

$\widetilde{H}_{j}^{m,n}(\lambda)=q\widetilde{H}_{j}^{m,n}(\lambda\backslash
e)+\widetilde{H}_{j-1}^{m-1,n-1}(\lambda/e)-q^{m}\widetilde{H}_{j}^{m-1,n-1}(\lambda/e),\qquad\widetilde{H}_{j}^{m,n}(\varnothing)=\left[m\right]_{n}\delta_{j,0}.$

###### Proof.

This follows from the deletion-contraction relation for $q$-rook numbers
[Dwo98, Thm. 6.10]

$R_{i}(\lambda)\,=\,q\cdot R_{i}(\lambda\backslash
e)+R_{i-1}(\lambda/e),\qquad R_{i}(\varnothing)=\delta_{i,0},$

which follows directly from considering if a placement $p$ of $i$ rooks in
$\lambda$ has or not a rook in cell $e$. Substituting this rook recursion in
(2.2), we obtain

$H_{k}^{m,n}(\lambda)=\dfrac{q^{\binom{k}{2}-|\lambda|}}{\left[m-n\right]!}\sum_{i=k}^{n}(q\cdot
R_{i}(\lambda\backslash
e)+R_{i-1}(\lambda/e))\left[m-i\right]!\begin{bmatrix}i\\\
k\end{bmatrix}(-1)^{i+k}q^{mi-\binom{i}{2}}\\\
=\dfrac{q^{\binom{k}{2}-|\lambda\backslash
e|}}{\left[m-n\right]!}\sum_{i=k}^{n}R_{i}(\lambda\backslash
e)\left[m-i\right]!\begin{bmatrix}i\\\
k\end{bmatrix}(-1)^{i+k}q^{mi-\binom{i}{2}}+\dfrac{q^{\binom{k}{2}-|\lambda|}}{\left[m-n\right]!}\sum_{i=k}^{n}R_{i-1}(\lambda/e)\left[m-i\right]!\begin{bmatrix}i\\\
k\end{bmatrix}(-1)^{i+k}q^{mi-\binom{i}{2}}.$

Manipulating the last expression from $q$-rook numbers into $q$-hit numbers,
we obtain the following recurrence

$H_{k}^{m,n}(\lambda)=H_{k}^{m,n}(\lambda\backslash
e)+q^{m+k-1-|\lambda|+|\lambda/e|}H_{k-1}^{m-1,n-1}(\lambda/e)-q^{k+m-|\lambda|+|\lambda/e|}H_{k}^{m-1,n-1}(\lambda/e)$

Now, we use (H.1) to translate this recursion into the recursion for the
$\widetilde{H}$’s:

$\displaystyle q^{km-|\lambda|}\widetilde{H}_{k}^{m,n}(\lambda)$
$\displaystyle=q^{km-|\lambda\backslash
e|}\widetilde{H}_{k}^{m,n}(\lambda\backslash
e)+q^{(k-1)(m-1)-|\lambda/e|}q^{m+k-1-|\lambda|+|\lambda/e|}\widetilde{H}_{k-1}^{m-1,n-1}(\lambda/e)$
$\displaystyle-q^{k(m-1)-|\lambda/e|}q^{k+m-|\lambda|+|\lambda/e|}H_{k}^{m-1,n-1}(\lambda/e),$

which simplifies to the desired recursion.

∎

###### Proof of Lemma 2.6.

Combining together (H.1) and Lemma K.1, we obtain

$\displaystyle q^{|\lambda|-jm}H_{j}^{m,n}(\nu)$
$\displaystyle=q^{|\lambda\backslash e|-jm+1}H_{j}^{m,n}(\lambda\backslash e)$
$\displaystyle+q^{|\lambda/e|-(j-1)(m-1)}H_{j-1}^{m-1,n-1}(\lambda/e)-q^{|\lambda/e|-j(m-1)+m}\widetilde{H}_{j}^{m-1,n-1}(\lambda/e).$

Noticing that $|\lambda\backslash e|+1=|\lambda|$ and simplifying the
expression we obtain that

$\displaystyle H_{j}^{m,n}(\nu)$ $\displaystyle=H_{j}^{m,n}(\lambda\backslash
e)+q^{|\lambda/e|-|\lambda|+j+m-1}H_{j-1}^{m-1,n-1}(\lambda/e)-q^{|\lambda/e|-|\lambda|+j+m}H_{j}^{m-1,n-1}(\lambda/e)$
$\displaystyle=H_{j}^{m,n}(\lambda\backslash
e)+q^{|\lambda/e|-|\lambda|+j+m-1}\left(H_{j-1}^{m-1,n-1}(\lambda/e)-qH_{j}^{m-1,n-1}(\lambda/e)\right).$

∎

The previous deletion-contraction relation specializes to square boards as
follows.

######  Corollary K.2.

$H_{j}^{N}(\lambda)=H_{j}^{N}(\lambda\backslash
e)+q^{|\lambda/e|-|\lambda|+j+N-1}\left[H_{j-1}^{N-1}(\lambda/e)-qH_{j}^{N-1}(\lambda/e)\right]$.

######  Conjecture K.3.

Let $\lambda$ be a partition inside an $n\times m$ board and $e$ be an outer
corner of $\lambda$, then we have: $P(x;\varnothing)=[m]_{n}$, and

$P(x;\lambda)=qP(x;\lambda\backslash e)+(xq^{m}-1)P(x;\lambda/e).$

###  L. Another proof of Lemma 5.5

In this section we include the proof of (5.5) using $q$-binomials.

###### Proof of (5.5) in Lemma 5.5.

We use Proposition 2.2 to rewrite both the LHS and RHS in terms of $q$-rook
numbers $R_{i}(\lambda)$. By $q$-manipulations, we have that (5.5) is
equivalent to

(L.1) $\displaystyle\begin{bmatrix}m+n-r-i-1\\\
n-r-1\end{bmatrix}=q^{(n-r-1)(r-i)}\cdot\left(\sum_{j=r}^{i}\begin{bmatrix}m+n-r-j-1\\\
n-j-1\end{bmatrix}\begin{bmatrix}i-r\\\
j-r\end{bmatrix}(-1)^{j-r}q^{\binom{j-r}{2}}\right).$

Now, to prove this $q$-binomial identity, we consider the following
$q$-binomial identities:

$\displaystyle\prod_{k=0}^{i-r-1}(1-q^{k}t)$
$\displaystyle=\sum_{k=0}^{i-r}q^{\binom{k}{2}}\begin{bmatrix}i-r\\\
k\end{bmatrix}(-1)^{k}t^{k},$
$\displaystyle\prod_{k=0}^{m-r-1}\dfrac{1}{(1-q^{k}t)}$
$\displaystyle=\sum_{k=0}^{\infty}\begin{bmatrix}m-r+k-1\\\
k\end{bmatrix}t^{k}.$

We have that

$\prod_{k=0}^{i-r-1}(1-q^{k}(q^{a}t))\prod_{k=0}^{m-r-1}\dfrac{1}{(1-q^{k}(q^{b}t))}\,=\,\\\
\left(\sum_{j-r=0}^{i-r}q^{\binom{j-r}{2}}\begin{bmatrix}i-r\\\
j-r\end{bmatrix}(-1)^{j-r}q^{a(j-r)}t^{j-r}\right)\cdot\left(\sum_{k=0}^{\infty}\begin{bmatrix}m-r+k-1\\\
k\end{bmatrix}q^{bk}t^{k}\right).$

Taking the coefficient at $t^{n-r-1}$ at the RHS we get

$\displaystyle\sum_{j-r=0}^{i-r}q^{\binom{j-r}{2}}\begin{bmatrix}i-r\\\
j-r\end{bmatrix}\begin{bmatrix}m-r+n-j-1\\\
n-j-1\end{bmatrix}q^{b(n-j-1)}t^{n-j-1}(-1)^{j-r}q^{a(j-r)}t^{j-r},$
$\displaystyle=\sum_{j=r}^{i}(-1)^{j-r}\begin{bmatrix}i-r\\\
j-r\end{bmatrix}\begin{bmatrix}m-r+n-j-1\\\
n-j\end{bmatrix}q^{\binom{j-r}{2}+b(n-j-1)+a(j-r)}.$

Setting $a=b=r-i$ and denoting by $[t^{\ell}]@P$ the coefficient of $t^{\ell}$
at $P$, we have that

$\displaystyle\begin{bmatrix}m-i+n-r-1\\\
n-r-1\end{bmatrix}=[t^{n-r-1}]@\prod_{k=0}^{m-i-1}\dfrac{1}{(1-q^{k}t)}$
$\displaystyle=[t^{n-r-1}]@\prod_{k=0}^{i-r-1}(1-q^{k}(q^{r-i}t))\prod_{k=0}^{m-r-1}\dfrac{1}{(1-q^{k}(q^{r-i}t))}$
$\displaystyle=[t^{n-r-1}]\sum_{j-r=0}^{i-r}q^{\binom{j}{2}}\begin{bmatrix}i-r\\\
j-r\end{bmatrix}\begin{bmatrix}m-r+n-j-1\\\
n-j-1\end{bmatrix}q^{(r-i)(n-j-1)}t^{n-j-1}(-1)^{j-r}q^{(r-i)(j-r)}t^{j-r}$
$\displaystyle=\sum_{j=r}^{i}(-1)^{j-r}\begin{bmatrix}i-r\\\
j-r\end{bmatrix}\begin{bmatrix}m-r+n-j-1\\\
n-j-1\end{bmatrix}q^{\binom{j-r}{2}+(r-i)(j-r)+(r-i)(n-j-1)},$

as desired. ∎