# The sandpile model on a bipartite graph, parallelogram polyominoes, and a q,t-Narayana polynomial

Mark Dukes, Yvan Le Borgne

► To cite this version:

Mark Dukes, Yvan Le Borgne. The sandpile model on a bipartite graph, parallelogram polyominoes, and a q,t-Narayana polynomial. 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), Jul 2012, Nagoya, Japan. pp.337-348. hal-00996796

HAL Id: hal-00996796

https://hal.science/hal-00996796

Submitted on 27 May 2014

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# The sandpile model on a bipartite graph, parallelogram polyominoes, and a $q, t$-Narayana polynomial

Mark Dukes¹†and Yvan Le Borgne²‡

¹Department of Computer and Information Sciences, University of Strathclyde, Glasgow G1 1XH, United Kingdom

²CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence cedex, France

**Abstract.** We give a polyomino characterisation of recurrent configurations of the sandpile model on the complete bipartite graph $K_{m,n}$ in which one designated vertex is the sink. We present a bijection from these recurrent configurations to decorated parallelogram polyominoes whose bounding box is a $m \times n$ rectangle. Other combinatorial structures appear in special cases of this correspondence: for example bicomposition matrices (a matrix analogue of set partitions), and (2+2)-free posets.

A canonical toppling process for recurrent configurations gives rise to a path within the associated parallelogram polyominoes. We define a collection of polynomials that we call $q, t$-Narayana polynomials, the generating functions of the bistatistic (area, parabounce) on the set of parallelogram polyominoes, akin to Haglund's (area, hagbounce) bistatistic on Dyck paths. In doing so, we have extended a bistatistic of Egge et al. to the set of parallelogram polyominoes. This is one answer to their question concerning extensions to other combinatorial objects.

We conjecture the $q, t$-Narayana polynomials to be symmetric and discuss the proofs for numerous special cases. We also show a relationship between the $q, t$-Catalan polynomials and our bistatistic (area, parabounce) on a subset of parallelogram polyominoes.

**Résumé.** Pour le modèle du tas de sable sur un graphe $K_{m,n}$ biparti complet, on donne une description des configurations récurrentes à l'aide d'une bijection avec des polyominos parallélogrammes décorés de rectangle englobant $m \times n$. D'autres classes combinatoires apparaissent comme des cas particuliers de cette construction: par exemple les matrices de bicomposition et les ordres partiels évitant le motif (2+2).

Un processus d'éboulement canonique des configurations récurrentes se traduit par un chemin bondissant dans le polyomino parallélogramme associé. Nous définissons une famille de polynômes, baptisée de $q, t$-Narayana, à travers la distribution d'une paire de statistique (aire, poidscheminbondissant) sur les polyominos parallélogrammes similaire à celle de Haglund définissant les polynômes de $q, t$-Catalan sur les chemins de Dyck. Ainsi nous étendons une paire de statistique de Egge et d'autres à l'ensemble des polynominos parallélogrammes. Cela réponds à l'une de leur question sur des généralistations à d'autres objets combinatoires.

Nous conjecturons que les polynômes de $q, t$-Narayana sont symétriques et discutons des preuves de plusieurs cas particuliers. Nous montrons également une relation avec les polynômes de $q, t$-Catalan en restreignant notre paire de statistique à un sous-ensemble des polyominos parallélogrammes.

<footnote>†Supported by grant no. 090038013 from the Icelandic Research Fund.</footnote>

<footnote>‡Thanks the Laboratoire d'informatique Gaspard-Monge, Marne-la-Vallée for their kind hospitality where part of this work was carried out.</footnote>
# 1 Introduction

The abelian sandpile model [6] is a discrete diffusion model whose states are distributions of grains on the vertices of a non-oriented graph. A vertex of a graph is *stable* if the number of grains at the vertex is strictly smaller than its degree, otherwise it is called *unstable*. In addition to a randomised addition of grains, the dynamics of this model requires that an unstable vertex donates a grain via each of its incident edges to its neighbours. This is the so-called toppling or avalanche process of the model, whose terminaison is guaranteed by a distinguished vertex, called the sink, that never topples collecting grains going out of the system. This process defines a Markov chain on stable states. In the particular case of graphs, there exist many bijections from recurrent states to spanning trees of the same graph [6, 3]. Another rich result concerning the model shows that the recurrent states, together with a certain binary operation, form an abelian group called the sandpile group.

In this extended abstract we outline some results from our paper [8] in which we classified recurrent configurations of the sandpile model on the complete bipartite graph $K_{m,n}$ in which a single designated vertex is the sink. Cori & Poulalhon [4] classified recurrent configurations of the complete $(k+1)$-partite graph $K_{p_1, \dots, p_k, 1}$ where the sink is the single vertex that is connected to all other vertices. Our work complements [4] by breaking the symmetry of $K_{p,q,1}$ and showing how recurrent configurations of $K_{m,n}$ that have one sink can be interpreted as parallelogram (or staircase) polyominoes.

Minimal recurrent configurations (those whose number of grains is minimal) correspond to ribbon parallelogram polyominoes (those having minimal area). In the original paper [8] we showed links between some special minimal configurations and other combinatorial structures. We will outline some of these rich connections at the end of Section 2 which are linked to a matrix analogue of set partitions. Such matrices where the subject of several recent papers that presented surprising connections between five seemingly disparate combinatorial objects: (2+2)-free posets, Stoimenov matchings, ascent sequences, permutations avoiding a length-3 bivincular pattern, and a class of upper triangular matrices (see [7, 1, 9, 2]). It was through these structures that we first noticed a connection to the sandpile model and the initial motivation behind this work.

During the last two decades, a series of papers have examined a power series $C_n(q, t)$ that has become known as the *q, t-Catalan function* (or *polynomial/number*). This power series was introduced by Garsia and Haiman [13] and has important links to algebraic geometry and representation theory. In the original paper they showed that two special cases of this polynomial had combinatorial significance. The first was that $C_n(q, 1)$ was the generating function of the area statistic over Dyck paths having semi-length $n$. The second was that $q^{\binom{n}{2}}C_n(q, 1/q)$ is the $n$th *q*-Catalan number.

Haglund introduced a new statistic ‘bounce’ and conjectured that $C_n(q, t)$ was the generating function of the bistatistic (area, hagbounce) on the set of all Dyck path of semi-length $n$. Garsia and Haglund [11, 12] proved this conjecture using methods from the theory of symmetric functions. (See Haglund [14] for a concise overview of these results.) Egge, Haglund, Kremer & Killpatrick [10] asked if the lattice path statistics for $C_n(q, t)$ can be extended, in a way which preserves the rich combinatorial structure, to related combinatorial objects.

We present a pair of statistics (area, parabounce) on parallelogram polyominoes which is one answer to their question. We call the resulting polynomials *q, t*-Narayana polynomials since they specialise to
the Narayana numbers for the case $q = 1 = t$. The bivariate generating function for this pair of statistics $N_{m,n}(q,t)$ appears to be symmetric in both $q, t$ and $m, n$. We conjecture and discuss the symmetry of this bistatistic and prove it for numerous special cases.

A parallelogram polyomino whose bounding rectangle is $[0, m] \times [0, n]$ is a polyomino uniquely described by a pair $(\text{upper}(\mathcal{P}), \text{lower}(\mathcal{P}))$ of paths which begin at $(0, 0)$, end at $(m, n)$, take steps in the set $\{n = (0, 1), e = (1, 0)\}$, and only touch at their endpoints. Let us write $\text{Para}_{m,n}$ for this collection of parallelogram polyominoes. Let $\text{Ribbon}_{m,n}$ be the set of polyominoes $\mathcal{P}$ in $\text{Para}_{m,n}$ whose area is $m+n-1$, the minimal value, which we will call ribbon polyominoes. (See Example 1 for two examples of these polyominoes.)

Given $\mathcal{P} \in \text{Para}_{m,n}$, let Bounce($\mathcal{P}$) be the unique path from $(m-1, n)$ to $(0, 0)$ which is defined as follows: Starting from $(m-1, n)$, the path goes south until it encounters a vertex on the lower path of $\mathcal{P}$. The path then turns to the west and continues straight until it encounters a vertex on the upper path of $\mathcal{P}$. The path turns again to the south until it encounters a vertex on the lower path of $\mathcal{P}$, and so on, until it reaches $(0, 0)$. Let bounce($\mathcal{P}$) = $(c_1, c_2, \dots)$ be the sequence of numbers where $c_1$ is the number of initial south s steps in Bounce($\mathcal{P}$), $c_2$ is the number of contiguous west steps that follow the initial run of south steps in Bounce($\mathcal{P}$), and so forth.

**Example 1** The bounce path is indicated by a thick directed line in the following diagrams:

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

$\mathcal{P}_1 = \text{Para}_{5,5};$

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

$\mathcal{P}_2 = \text{Para}_{7,3}.$

For $\mathcal{P}_1$ we have Bounce($\mathcal{P}_1$) = (s, s, w, w, w, s, w, s, s) and bounce($\mathcal{P}_1$) = (2, 3, 1, 1, 2). For $\mathcal{P}_2$ we have Bounce($\mathcal{P}_2$) = (s, w, w, w, s, s, w, w, w) and bounce($\mathcal{P}_2$) = (1, 3, 2, 3).

## 2 The sandpile model on $D_{m,n}$ and recurrent configurations

In this section we show how recurrent configurations of the sandpile model [6] on $K_{m,n}$ which has a designated vertex that acts as a sink can be classified in terms of parallelogram polyominoes. In what follows we will refer to the the directed bipartite graph $K_{m,n}$ that has a designated vertex, which we will call the *sink*, as $D_{m,n}$. The purpose in doing so is to avoid confusion about two non-equivalent choices for the sink in $K_{m,n}$ (in general if we have many sinks then we merge them into a single one).

For a general (stable) configuration $u$ on $D_{m,n}$ we define a collection of cells $f_{m,n}(u) \subseteq [0, m] \times [0, n] \subseteq \mathbb{R}^2$. A canonical toppling process for checking recurrent configurations is defined (using Dhar's criterion) for the graph $D_{m,n}$, and it is then shown that a configuration being recurrent is equivalent to $f_{m,n}(u)$ being a parallelogram polyomino in $\text{Para}_{m,n}$. During this, we show the canonical toppling process of a recurrent configuration to be intimately linked with the bounce path of the corresponding polyomino $f_{m,n}(u)$.

Let $D_{m,n}$ be the graph $D_{m,n}(V, E)$ with vertex set $V = \{v_0, \dots, v_{m+n-1}\}$ and edge set

$$E = \{(v_i, v_j) : i \in \{0, \dots, m-1\} \text{ and } j \in \{m, \dots, m+n-1\}\}.$$
<figure><img src="image_4.png" /><figcaption>Fig. 1: The graph $D_{m,n}$.</figcaption></figure>

This is illustrated in Figure 1. We call {$v_0, \dots, v_{m-1}$} and {$v_m, \dots, v_{m+n-1}$} the top vertices and bottom vertices of $D_{m,n}$, respectively.

A configuration, or state, $x$ on $D_{m,n}$ is an assignment $x : \{1, \dots, m + n - 1\} \to \mathbb{N}_0 = \mathbb{N} \cup \{0\}$, the collection of non-negative integers. The value $x_i = x(i)$ represents the number of grains of sand on vertex $v_i$. Vertex $v_0$ is treated as the sink and the number of grains of sand on this vertex is generally ignored. There is, however, one benefit to considering the number of grains at the sink and this will be mentioned in the Dhar criterion.

A vertex is said to be stable if the number of grains at that vertex is strictly less than the number of edges exiting that vertex. Otherwise it is called unstable. If all vertices {$v_1, \dots, v_{m+n-1}$} are stable then the configuration is said to be stable. Suppose $x = (x_1, \dots, x_{m+n-1})$ is a state on $D_{m,n}$. If vertex $v_i$ is unstable then it topples: it donates one grain to each of its neighbours. Let $\text{Stable}(D_{m,n})$ be the set of stable states on $D_{m,n}$.

Let us call a configuration $u \in \text{Stable}(D_{m,n})$ increasing if $u_1 \le \dots \le u_{m-1}$ and $u_m \le \dots \le u_{m+n-1}$. Every configuration $u \in \text{Stable}(D_{m,n})$ may be written uniquely as a pair $\text{decomp}_{m,n}(u) = (\text{inc}_{m,n}(u), \text{sperm}_{m,n}(u))$, where $\text{inc}_{m,n}(u) = u'$ is an increasing configuration, $\text{sperm}_{m,n}(u) = \pi$ is the lexicographically smallest permutation such that $\pi : \{1, \dots, m-1\} \to \{1, \dots, m-1\}, \pi : \{m, \dots, m+n-1\} \to \{m, \dots, m+n-1\}$, and $u_i = u'_{\pi(i)}$ for all $i \in \{1, \dots, m+n-1\}$.

**Example 2** Consider $u = (5, 2, 1, 2, 4, 2, 1, 3, 2, 2, 1) \in \text{Stable}(D_{5,7})$. We have $\text{inc}_{5,7}(u) = (1, 2, 2, 5, 1, 1, 2, 2, 2, 3, 4)$ and $\text{sperm}_{5,7}(u) = (4, 2, 1, 3, 11, 7, 5, 10, 8, 9, 6)$.

Let $\sigma(x)$ be the stable state the results from initial state $x$. A stable state is *recurrent* if it results as the stable outcome of an state where all vertices were unstable. Let $\text{Rec}(D_{m,n})$ be the set of recurrent states on $D_{m,n}$ and let $\text{Rec}^*(D_{m,n})$ be the set of increasing recurrent states. Recurrent states may be classified for general graphs as follows:

**Dhar's Criterion:** a stable state $u$ on a graph $G$ is recurrent if and only if the stable state that results from an initial toppling of the sink results once again in $u$ (see [4, 6]).
Applying this to the graph $D_{m,n}$ gives us that a stable configuration $u \in \text{Stable}(D_{m,n})$ is recurrent iff

$$ \sigma(u_1, \dots, u_{m-1}, 1 + u_m, \dots, 1 + u_{m+n-1}) = (u_1, \dots, u_{m-1}, u_m, \dots, u_{m+n-1}). \quad (1) $$

The order of topplings is unimportant when checking that the Dhar criterion (1) holds. However, for our purposes it will prove useful to fix a canonical toppling process as follows: Let $Q_1$ be the set of all unstable vertices in the bottom row of $D_{m,n}$ (as a result of adding 1 to the height of each vertex in this bottom row). Topple all vertices in $Q_1$ and then let $P_1$ be the set of all unstable vertices in the top row of $D_{m,n}$. Topple all vertices in $P_1$ and then let $Q_2$ be the set of all unstable vertices in the bottom row of $D_{m,n}$. Continue this process until all vertices of $D_{m,n}$ are stable. Let

$$ \text{CanonTop}(u) = (Q_1, P_1, Q_2, P_2, \dots) \quad \text{and} \quad \text{canontop}(u) = (|Q_1|, |P_1|, |Q_2|, |P_2|, \dots). $$

We note of course that it is possible for $\text{CanonTop}(u) = \text{canontop}(u) = ()$, the empty sequence.

**Example 3** Consider $u = (0, 2, 1, 2, 1, 2) \in \text{Stable}(D_{3,4})$. Adding one grain to every vertex in the bottom row gives $w = (0, 2, 2, 3, 2, 3)$, which topples as follows: $(0, 2, 2, 3, 2, 3) \to (2, 4, 2, 0, 2, 0) \to (2, 0, 3, 1, 3, 1) \to (4, 2, 0, 1, 0, 1) \to (0, 2, 1, 2, 1, 2)$. Since $\sigma(w) = u$ we have that $u \in \text{Rec}(D_{3,4})$. The toppling process is $\text{CanonTop}(u) = (\{4, 6\}, \{2\}, \{3, 5\}, \{1\})$.

Given $u = (u_1, \dots, u_{m+n-1}) \in \text{Stable}(D_{m,n})$ with $\text{CanonTop}(u) = (Q_1, P_1, Q_2, P_2, \dots)$ and $\text{inc}_{m,n}(u) = (a_1, \dots, a_{m-1}, b_1, \dots, b_n)$ we define two collections of cells in the plane:

$$ \text{Bottom}(u) = \bigcup_{i=1}^{n} [0, 1 + b_i] \times [i - 1, i] $$

and

$$ \text{Top}(u) = [m-1, m] \times [0, n] \cup \bigcup_{i=1}^{m-1} [i-1, i] \times [0, 1 + a_i] $$

$$ \text{Let } f_{m,n}(u) = \text{Top}(u) \cap \text{Bottom}(u). $$

**Example 4** Given $u = (2, 1, 2, 0, 0, 2, 6, 1, 5, 1) \in \text{Stable}(D_{7,4})$, we have

$$ \text{inc}_{7,4}(u) = (a_1, \dots, a_6, b_1, \dots, b_4) = (0, 0, 1, 2, 2, 2, 1, 1, 5, 6). $$

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

The next theorem is the main classification theorem of [8]. Part (a) of its proof relies on a careful analysis of the topplings in Dhar's criterion, and the canonical toppling or a recurrent configuration leads one to consider the bounce path within the corresponding polyomino.

**Theorem 5** Let $u = (u_1, \dots, u_{m+n-1}) \in \text{Stable}(D_{m,n})$.

(a) $u \in \text{Rec}(D_{m,n})$ iff $f_{m,n}(u) \in \text{Para}_{m,n}$.

(b) If $u \in \text{Rec}(D_{m,n})$ then $\text{bounce}(f_{m,n}(u)) = \text{canontop}(u)$.
One may give a bijection from $\mathrm{Rec}(D_{m,n})$ to the set of all parallelogram polyominoes whose bounce paths have been decorated with an ordered set partition $X$. There are two restrictions on the set partitions (i) the size of the $i$th set in this partition must correspond to the length of the $i$th segment of the bounce path, and (ii) the sets associated with the horizontal steps must partition $\{1, \dots, m-1\}$ and the sets associated with vertical steps must partition $\{m, \dots, m+n-1\}$. Let $\mathrm{SetPara}_{m,n}$ be the set of all pairs $(\mathcal{P}, X)$ where $\mathcal{P} \in \mathrm{Para}_{m,n}$ and $X$ satisfies conditions (i) and (ii).

**Example 6** Let $\mathcal{P}$ be $\mathcal{P}_2$ in Example 1. Let $X = (\{8\}, \{1, 4, 5\}, \{7, 9\}, \{2, 3, 6\})$. Then $(\mathcal{P}, X) \in \mathrm{SetPara}_{7,3}$ and may be represented in the following way:

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

Given $u \in \mathrm{Stable}(D_{m,n})$ let $\Omega(u) = (f_{m,n}(u), \mathrm{CanonTop}(u))$. This construction, combined with parts (a) and (b) of Theorem 5, gives:

**Corollary 7** $\Omega: \mathrm{Rec}(D_{m,n}) \to \mathrm{SetPara}_{m,n}$ is a bijection.

It is well-known from the literature on the sandpile model that recurrent configurations on a graph $G$ are in one-to-one correspondence with spanning trees of $G$. Thus the number of recurrent configurations on $D_{m,n}$ is the number of spanning trees of $K_{m,n}$, which is $m^{n-1}n^{m-1}$. Furthermore, Narayana [15] enumerated the class of parallelogram polyominoes according to width and height. Thus

**Corollary 8** For all $m, n \ge 1$, $|\mathrm{Rec}(D_{m,n})| = m^{n-1}n^{m-1}$ and $|\mathrm{Rec}^*(D_{m,n})| = \mathrm{Nara}(m+n-1, m)$, where $\mathrm{Nara}(a, b) = \binom{a}{b} \binom{a}{b-1}$ are the Narayana numbers.

The correspondence between recurrent configurations and parallelogram polyominoes is shown to have several special cases of interest. The details can be found in the main paper [8] but we summarise some of the points here.

* Minimal recurrent configurations correspond to ribbon polyominoes. Configurations which are non-zero everywhere are a natural class to ask questions about. However there are no recurrent configurations that are both minimal and non-zero. The next natural class to look at are those configurations that are almost non-zero: call a configuration $u \in \mathrm{Rec}(D_{m,n})$ almost non-zero if

$$u_1, \dots, u_{m-1}, u_{m+1}, \dots, u_{m+n-1} > 0.$$

Configurations that are both minimal and almost non-zero are called *minanz configurations*.

* We call a configuration $u \in \mathrm{Rec}(D_{m,n})$ square if $m = n$. Square minanz configurations are in one-to-one correspondence with square matrices which have no rows or columns of empty sets, and whose entries form a set partition of $\{1, 2, \dots, n-1\}$, which are termed *bicomposition matrices* of size $n-1$.
* Let $u \in \text{Rec}(D_{n,n})$ be minanz and suppose that $\text{CanonTop}(u) = (Q_1, P_1, \dots, Q_{k+1} = \{n\})$. If $x \in P_i \cup Q_i$ then we say that vertex $v_x$ is in the $i$th wave of $u$, and write this as $\text{wave}_u(v_x) = i$. The collection of minanz configurations $u \in \text{Rec}(D_{n,n})$ which satisfy the following wave property:

$$ \text{wave}_u(v_{n+x}) \le \text{wave}_u(v_x) \quad \text{for all } 1 \le x < n $$

are in one-to-one correspondence with upper-triangular bicomposition matrices of size $n-1$. Upper-triangular bicomposition matrices on $n-1$ have recently been shown to be in 1-1 correspondence with (2+2)-free partially ordered sets on $\{1, \dots, n-1\}$. We show the composition of these two correspondences, and how to read a recurrent configuration from the corresponding (2+2)-free poset.

## 3 q, t-Narayana polynomials and their symmetry

In this section we will introduce a polynomial that we call the q, t-Narayana polynomial. The polynomial is the generating function for the bistatistic (area, parabounce) on the set of parallelogram polyominoes. In terms of recurrent configurations of the sandpile model, the area statistic is up to a constant the level of the configuration:

$$ \text{level}(u) = u_1 + \dots + u_{m+n-1} - n(m-1), $$

and the hagbounce statistic is related to the canonical toppling process. When viewed in the parallelogram polyomino, the bounce path is almost identical to the bounce path that Haglund defined for Dyck paths. Our polynomial is a natural extension of the area and bounce path statistics to the class of parallelogram polyominoes. More will be discussed about this in the subsections that follow.

For any polyomino $\mathcal{P} \in \text{Para}_{m,n}$, define its *bounce weight* to be

$$ \text{parabounce}(\mathcal{P}) = \sum_{i=1}^{k} \lceil i/2 \rceil c_i, $$

where $\text{bounce}(\mathcal{P}) = (c_1, \dots, c_k)$.

This weight may also be described by summing weights on each step of the bounce path. The initial step has a weight of 1, and the weight of subsequent steps is incremented by 1 after each turn on the upper boundary path of the polyomino. Consider the following two polyominoes:

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

The bounce weights are

$$ \begin{aligned} \text{parabounce}(\mathcal{P}_1) &= (1) + (1+1+1) + (2) + (2) + (3+3) + (3+3+3) + (4) + (4) + (5+5) \\ &= 41, \text{ and} \end{aligned} $$

$$ \text{parabounce}(\mathcal{P}_2) = (1) + (1 + 1 + 1 + 1) + (2) + (2 + 2 + 2) = 13. $$
The distribution of the bistatistic (area, parabounce) on polyominoes in $Para_{m,n}$ is represented by the generating function

$$N_{m,n}(q,t) = \sum_{P \in Para_{m,n}} q^{\text{area}(P)} t^{\text{parabounce}(P)}.$$

We call these polynomials $q, t$-Narayana polynomials because $\{N_{m,n}(1,1)\}_{m,n \ge 1}$ are the Narayana numbers that were mentioned in Corollary 8. The following conjecture has been verified for all pairs $(m, n)$ with $m \le 11$ and $n \in \mathbb{N}$ by using generating functions resulting from the classical transfer-matrix method.

**Conjecture 9** For all positive integers $m$ and $n$, the distribution of the bistatistic (area, parabounce) on polyominoes in $Para_{m,n}$ is symmetric: $N_{m,n}(q,t) = N_{m,n}(t,q)$.

Further to this we posit another symmetry (which has been checked for all pairs $(m, n)$ with $\max(m, n) \le 9$).

**Conjecture 10** For all positive integers $m$ and $n$ we have $N_{m,n}(q,t) = N_{n,m}(q,t)$.

Symmetry along the main diagonal of parallelogram polyominoes provides a bijection from polyominoes of $Para_{m,n}$ to $Para_{n,m}$ that preserves the area statistic. This mapping gives the following special case of Conjecture 10:

**Theorem 11** For all positive integers $m$ and $n$ we have $N_{m,n}(q, 1) = N_{n,m}(q, 1)$.

Define the generating function for the bistatistic of all these polyominoes, adding a variable $z$ to record the height $n$ of polyominoes:

$$N_{k,\star}(q,t;z) = \sum_{n \ge 1} N_{k,n}(q,t)z^n.$$

Representing polyominoes as regular expressions is useful in evaluating $N_{k,\star}(q, t; z)$. For example, one finds

$$N_{2,\star}(q,t;z) = \frac{t^2 q^2 z}{(1 - qtz)(1 - q^2tz)(1 - qtz^2)} = N_{\star,2}(q,t;z)$$

$$N_{3,\star}(q,t;z) = q^3 t^3 z \left( 1 + \frac{q^3 t z}{1 - q^3 t z} + \frac{qt^3 z}{1 - q^3 t^3 z} \right) = N_{\star,3}(q,t;z).$$

Conjecture 9 also holds for minimal values of one of the two statistics:

**Theorem 12** In $Para_{m,n}$, for any $i$, there are as many polyominoes whose bistatistic (area, parabounce) is $(m+n-1, i)$ as there are polyominoes whose bistatistic (area, parabounce) is $(i, m+n-1)$.

This theorem is proved by showing that there exists a bijection

$$\Upsilon: \{P \in Para_{m,n} : \text{parabounce}(P) = m+n-1\} \to \{P \in Para_{m,n} : \text{area}(P) = m+n-1\}.$$

The definition of this bijection is lengthy and is included in the longer version of this paper. The function $\Upsilon$ on our polyominoes has the effect of swapping the two statistics.
**Example 13** An example of the bijection from Theorem 12. In this case $m = n = 6$. The sequence of diagonal lengths $(d_1, \dots, d_{m+n-1}) = (1, 2, 3, 3, 3, 4, 3, 3, 3, 2, 1)$ give $(x_0, \dots, x_4) = (1, 1, 4, 5, 6)$ and $(y_0, \dots, y_4) = (0, 1, 4, 5, 6)$. The ribbon $\Upsilon(P)$ is characterized among ribbons by the fact that its horizontal bounce steps from left to right are weighted by $(d_1, \dots, d_{m-1})$ while its vertical bounce steps from bottom to top are weighted by $(d_m, \dots, d_{n+m-1})$.

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

## 4 The sandpile model on $K_n$, special parallelogram polyominoes, and Haglund's bounce statistic

In this subsection we will show a connection (Theorem 17) between a class of polyominoes, the sandpile model on the complete graph $K_n$ having one sink, and Haglund's bistatistic (area, hagbounce) on the set of all Dyck paths. We first need to introduce some notation relevant to Haglund's statistics.

A Dyck path of length $n$ is a path from $(n, n)$ to $(0, 0)$ that does not go above the main diagonal and takes steps in $\{s = (0, -1), w = (-1, 0)\}$. Let $Dyck_n$ be the set of all such Dyck paths of semi-length $n$. A general $D \in Dyck_n$ may be represented as a word $D = d_1d_2\dots d_n$ where $d_i \in \{s, w\}$. Given $D \in Dyck_n$, let area($D$) be the number of complete unit squares contained between $D$ and the diagonal line $x = y$. (The shaded triangular regions adjacent to the diagonal are not counted.) If Haglund's bounce path on $D$ is $s^{a(1)}w^{a(1)}s^{a(2)}w^{a(2)}\dots s^{a(k)}w^{a(k)}$ then we will write $\text{HagBounce}(D) = (a(1), a(2), \dots, a(k))$. Haglund's bounce statistic, in this setup, is $\text{hagbounce}(D) = a(2) + 2a(3) + \dots + (k-1)a(k)$. Let

$$H_n(q, t) = \sum_{D \in \text{Dyck}_n} q^{\text{area}(D)} t^{\text{hagbounce}(D)}.$$

**Example 14** Let $D = \text{sswswwsw} = s^2w^1s^1w^1s^1w^2s^1w^1 \in \text{Dyck}_5$. Then area($D$) = 3, HagBounce($D$) = (2, 2, 1) and hagbounce = 2 + 2(1) = 4.

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

Recurrent configurations of the sandpile model on the graph $K_n$ were studied in Cori & Rossin [5] and are classified in terms of parking functions. Let $D_n$ be the graph on the vertices $V = \{v_0, \dots, v_{n-1}\}$ with
edges $E = \{(v_i, v_j) : 0 \le i, j \le n-1 \text{ and } i \neq j\}$ where $v_0$ is a sink. The set of all stable configurations is

$$ \text{Stable}(D_n) = \{(x_1, \dots, x_{n-1}) : 0 \le x_i \le n-2 \text{ for all } 1 \le i \le n-1\}. $$

An integer sequence $(t_1, \dots, t_n)$ is a parking function if there exists a permutation $\pi$ of $\{1, \dots, n\}$ such that $i \ge t_{\pi(i)}$ for all $1 \le i \le n$. Cori and Rossin [5, Prop. 2.8] proved that a stable configuration $(x_1, \dots, x_{n-1})$ is recurrent iff $(n-1-x_1, \dots, n-1-x_{n-1})$ is a parking function. Let $\text{Park}_n$ be the set of all parking functions of length $n$. The recurrent configurations are

$$ \text{Rec}(D_n) = \{x \in \text{Stable}(D_n) : (n-1-x_1, \dots, n-1-x_{n-1}) \in \text{Park}_{n-1}\}. $$

Let us call a configuration $x \in \text{Stable}(D_n)$ sorted if it is weakly decreasing, and let $\text{Rec}^{\dagger}(D_n) = \{x \in \text{Rec}(D_n) : x \text{ is sorted}\}$. For example, $\text{Stable}(D_3) = \{(0,0), (0,1), (1,0), (1,1)\}$, $\text{Rec}(D_3) = \{(0,1), (1,0), (1,1)\}$, and $\text{Rec}^{\dagger}(D_3) = \{(1,0), (1,1)\}$. Using Cori & Rossin's [5] classification we have:

$$ \text{Rec}^{\dagger}(D_n) = \{(x_1, \dots, x_{n-1}) : x_i \ge n-1-i \text{ for all } i \in \{1, \dots, n-1\}\}. $$

Section 2 defined a canonical toppling process for every recurrent configuration. This canonical toppling process was an ordered set partition of the vertices and recorded the order in which vertices toppled in parallel. We now extend the same definition to recurrent configurations of $K_n$: given $x \in \text{Rec}(K_n)$, let $\text{CanonTop}(x) = (Q_1, Q_2, \dots, Q_k)$ be the ordered set partition of $\{1, \dots, n-1\}$, whereby vertices in $Q_i$ topples at time $i$.

**Example 15** Let $x = (4, 4, 3, 2, 0) \in \text{Rec}^{\dagger}(K_6)$. The canonical toppling process of this configuration happens as follows:

$$ x + (1, 1, 1, 1, 1) = (\dot{5}, \dot{5}, 4, 3, 1) \rightarrow (1, 1, \dot{6}, \dot{5}, 3) \rightarrow (3, 3, 2, 1, \dot{5}) \rightarrow (4, 4, 3, 2, 0) = x. $$

A dot above the number denotes an unstable vertex that will topple. Thus $\text{CanonTop}(x) = (\{1, 2\}, \{3, 4\}, \{5\})$.

Given $x \in \text{Stable}(K_n)$, define the diagram of $x$ as

$$ \text{diag}(x) = \bigcup_{i=1}^{n-1} [n-1-i, 2+x_i] \times [n-1-i, n-i] \subset \mathbb{R}^2. $$

Diagrams of sorted recurrent configurations in $K_n$ are precisely those diagrams which are polyominoes in $\text{Para}_{n,n-1}$. Let

$$ \text{LowerPara}_{n,n-1} = \{\text{diag}(x) : x \in \text{Rec}^{\dagger}(K_n)\}. $$

Every element $P \in \text{LowerPara}_{n,n-1}$ is uniquely described by a Dyck path dyck($P$) of semi-length $n-1$ which is the path of the boundary of $P$ from $(n, n-1)$ to $(1, 0)$ since its upper path is a word of $(ne)^*$e. See Figure 2 for an example of this simple transformation.

**Theorem 16** Let $u \in \text{Rec}^{\dagger}(K_n)$, $P = \text{diag}(x) \in \text{LowerPara}_{n,n-1}$ and $D = \text{dyck}(P) \in \text{Dyck}_{n-1}$. Then the following are equivalent:

(i) $\text{CanonTop}(u) = (Q_1, \dots, Q_k)$,

(ii) $\text{Bounce}(P) = (|Q_1|, |Q_1|, |Q_2|, |Q_2|, \dots, |Q_k|, |Q_k|)$, and
<figure><img src="image_10.png" /><figcaption>**Fig. 2:** On the left is shown $P = \text{diag}(x)$ where $x = (5, 5, 3, 2, 2, 1) \in \text{Rec}^{\dagger}(K_7)$. The Dyck path dyck($P$) = $s^2w^2sws^2wsw^2$ is shown on the right.</figcaption></figure>

$$ (iii) \text{ HagBounce}(D) = (|Q_1|, |Q_2|, \dots, |Q_k|). $$

Furthermore:

$$ (iv) \text{ area}(P) = (x_1 + \dots + x_n) - (n-1)(n-6)/2 = \text{area}(D) + 2n, \text{ and} $$

$$ (v) \text{ parabounce}(P) = 2(\text{hagbounce}(D) + n). $$

$$ \textbf{Theorem 17} \quad \sum_{P \in \text{LowerPara}_{n,n-1}} q^{\text{area}(P)} t^{\text{parabounce}(P)} = (qt)^{2n} H_{n-1}(q, t^2). $$

One is led to Conjecture 9 by considering two configuration statistics pertaining to (sorted) recurrent configurations on $D_n$. For the sandpile model on $D_n$, the area of a Dyck path $D$ is related to the number of grains in the mapped sorted recurrent configuration $u$ since

$$ \text{area}(D) + \sum_{i=0}^{n-2} i = \sum_{i=1}^{n-1} u_i. $$

Also, the Haglund bounce statistic of a Dyck path $D$ may be interpreted as the sum over all vertices of the number of times a vertex is observed stable before it topples during the parallel toppling process $\text{CanonTop}(u)$. More precisely, all vertices in $Q_i$ are observed $i$ times as stable: during the initial toppling of the sink and the toppling of each set $Q_1, \dots, Q_{i-1}$. Conjecture 9 is the result of translating these configuration statistics to the sandpile model on the graph $D_{m,n}$.

## References

[1] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev. (2+2)-free posets, ascent sequences and pattern avoiding permutations. *Journal of Combinatorial Theory Series A* 117, no. 7 (2010): 884–909.

[2] A. Claesson, M. Dukes, and M. Kubitzke. Partition and composition matrices. *Journal of Combinatorial Theory Series A* 118, no. 5 (2011): 1624–1637.

[3] R. Cori and Y. Le Borgne. The sandpile model and Tutte polynomials. *Advances in Applied Mathematics* 30, no. 1-2 (2003): 44–52.
[4] R. Cori and D. Poulalhon. Enumeration of $(p, q)$-parking functions. *Discrete Mathematics* 256 (2002): 609–623.

[5] R. Cori and D. Rossin. On the sandpile group of dual graphs. *European Journal of Combinatorics* 21 (2000): 447–459.

[6] D. Dhar. Theoretical studies of self-organized criticality. *Physica A. Statistical Mechanics and its Applications* 369, no. 1 (2006): 29–70.

[7] M. Dukes, V. Jelínek, and M. Kubitzke. Composition matrices, (2+2)-free posets and their specializations. *Electronic Journal of Combinatorics* 18, no. 1 (2011): P44.

[8] M. Dukes and Y. Le Borgne. Parallelogram polyominoes, the sandpile model on a bipartite graph, and a $q, t$-Narayana polynomial. Preprint (2011).

[9] M. Dukes and R. Parviainen. Ascent sequences and upper triangular matrices containing non-negative integers. *Electronic Journal of Combinatorics* 17, no. 1 (2010): R53.

[10] E. Egge, J. Haglund, D. Kremer, and K. Killpatrick. A Schröder generalization of Haglund's statistic on Catalan paths. *Electronic Journal of Combinatorics* 10 (2003): P16.

[11] A. M. Garsia and J. Haglund. A positivity result in the theory of Macdonald polynomials. *Proceedings of the National Academy of Sciences* 98, no. 8 (2001): 4313–4316.

[12] A. M. Garsia and J. Haglund. A proof of the $q, t$-Catalan positivity conjecture. *Discrete Mathematics* 256, no. 3 (2002): 677–717.

[13] A. M. Garsia and M. Haiman. A remarkable $q, t$-Catalan sequence and $q$-Lagrange inversion. *Journal of Algebraic Combinatorics* 5, no. 3 (1996): 191–244.

[14] J. Haglund. *The $q, t$-Catalan numbers and the space of diagonal harmonics*. With an appendix on the combinatorics of Macdonald polynomials. University Lecture Series, 41. American Mathematical Society, Providence, RI, 2008.

[15] V. T. Narayana. Sur les treillis formés par les partitions d'un entier et leurs applications à la théorie des probabilités. *Comptes rendus de l'Académie des sciences* 240 (1955): 1188–1189.