# Type C parking functions and a zeta map

Robin Sulzgruber, Marko Thiel

► To cite this version:

Robin Sulzgruber, Marko Thiel. Type C parking functions and a zeta map. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.475-486, 10.46298/dmtcs.2496 . hal-01337800

HAL Id: hal-01337800

https://hal.science/hal-01337800

Submitted on 27 Jun 2016

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Type C parking functions and a zeta map

Robin Sulzgruber† and Marko Thiel‡

Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria

**Abstract** We introduce type C parking functions, encoded as vertically labelled lattice paths and endowed with a statistic dinv'. We define a bijection from type C parking functions to regions of the Shi arrangement of type C, encoded as diagonally labelled ballot paths and endowed with a natural statistic area'. This bijection is a natural analogue of the zeta map of Haglund and Loehr and maps dinv' to area'. We give three different descriptions of it.

**Résumé** Nous introduisons les fonctions de stationnement de type C, encodées par des chemins étiquetés verticalement et munies d'une statistique dinv'. Nous définissons une bijection entre les fonctions de stationnement de type C et les régions de l'arrangement de Shi de type C, encodées par des chemins étiquetés diagonalement et munies d'une statistique naturelle area'. Cette bijection est un analogue naturel à la fonction zeta de Haglund et Loehr, et envoie dinv' sur area'. Nous donnons trois différentes descriptions de celle-ci.

**Keywords:** parking functions, Shi arrangement, zeta map, dinv statistic

# 1 Introduction and Motivation

One of the most well-studied objects in algebraic combinatorics is the space of diagonal harmonics of the symmetric group $S_n$. Its Hilbert series has two (conjectural) combinatorial interpretations:

$$ \mathcal{D}\mathcal{H}(n; q, t) = \sum_{P \in \text{Park}_n} q^{\text{dinv}'(P)} t^{\text{area}(P)} = \sum_{R \in \text{Diag}_n} q^{\text{area}'(R)} t^{\text{bounce}(R)}, $$

where $\text{Park}_n$ is the set of parking functions of length $n$, viewed as vertically labelled Dyck paths, and $\text{Diag}_n$ is the set of diagonally labelled Dyck paths with $2n$ steps. There is a bijection $\zeta$ due to Haglund and Loehr (2005) that maps $\text{Park}_n$ to $\text{Diag}_n$ and sends the bistatistic (dinv', area) to (area', bounce), demonstrating the second equality.

The combinatorial objects $\text{Park}_n$ and $\text{Diag}_n$ may be viewed as the type $A_{n-1}$ cases of more general objects associated to any crystallographic root system $\Phi$. These are, respectively, the finite torus $\tilde{Q}/(h+1)\tilde{Q}$ and the set of regions of the Shi arrangement of $\Phi$. Here $\tilde{Q}$ is the coroot lattice and $h$ is the Coxeter number of $\Phi$. Both of these objects have the same cardinality $(h+1)^r$, where $r$ is the rank of

<footnote>†Email: robin.sulzgruber@univie.ac.at.</footnote>

<footnote>‡Email: marko.thiel@univie.ac.at.</footnote>

<footnote>Research supported by the Austrian Science Fund (FWF), grant S50-N15 in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics” (SFB F50).</footnote>
$\Phi$, so there should be a uniform “zeta map” giving a bijection between them. This map does in fact exist, and will be described in future work.

In the present extended abstract we focus on the root system of type $C_n$. In Section 2 we present the necessary background on Weyl groups and the Shi arrangement. In Section 3 we introduce combinatorial models for the finite torus of type $C$ in terms of vertically labelled lattice paths and for the set of regions of the Shi arrangement of type $C$ in terms of diagonally labelled ballot paths. We also introduce a statistic dinv' on vertically labelled lattice paths and a statistic area' on diagonally labelled ballot paths. These statistics are natural analogues of the corresponding statistics in type $A$.

In Section 4 we describe a map between these two combinatorial models that we call the type $C$ zeta map. We give three descriptions of this map, all similar in style to different descriptions of the classical zeta map. The first description in terms of area vectors follows Haglund and Loehr (2005). The second description in terms of ascents and valleys resembles that of (Armstrong et al., 2014a, Section 5.2). The third description as a sweep map is in the spirit of Armstrong et al. (2014b). Our main result (Theorem 4.2) is that the zeta map of type $C$ is a bijection that sends the dinv' statistic to the area' statistic.

We prioritise examples and prefer to include an adequate presentation of the known combinatorial objects of type $A$ rather than presenting proofs. A full version of this extended abstract containing all proofs is in preparation.

# 2 Definitions and Preliminaries

## 2.1 Weyl groups

Let $\Phi$ be an irreducible crystallographic root system of rank $r$, with simple system $\Delta = \{\alpha_1, \alpha_2, \dots, \alpha_r\}$, positive system $\Phi^+$ and ambient space $V$. For background on root systems and reflection groups see Humphreys (1990). For $\alpha \in \Phi$, let $s_\alpha$ be the reflection in the hyperplane

$$H_\alpha = \{x \in V : \langle x, \alpha \rangle = 0\}.$$

Then the Weyl group $W$ of $\Phi$ is the group of automorphisms of $V$ generated by all the $s_\alpha$ with $\alpha \in \Phi$. Define the *Coxeter arrangement* of $\Phi$ as the central hyperplane arrangement in $V$ given by all the hyperplanes $H_\alpha$ for $\alpha \in \Phi$. The connected components of the complement of the union of these hyperplanes are called *chambers*. The Weyl group $W$ acts simply transitively on the chambers, so if we define the *dominant chamber* as

$$C = \{x \in V : \langle x, \alpha \rangle > 0 \text{ for all } \alpha \in \Delta\},$$

we may write every chamber as $wC$ for a unique $w \in W$.

For $\alpha \in \Phi$ and $d \in \mathbb{Z}$, let $s_\alpha^d$ be the reflection in the affine hyperplane

$$H_\alpha^d = \{x \in V : \langle x, \alpha \rangle = d\}.$$

Then the affine Weyl group $\tilde{W}$ of $\Phi$ is the group of affine transformations of $V$ generated by all the $s_\alpha^d$ for $\alpha \in \Phi$ and $d \in \mathbb{Z}$. Define the *affine Coxeter arrangement* as the affine hyperplane arrangement in $V$ given by all the $H_\alpha^d$ for $\alpha \in \Phi$ and $d \in \mathbb{Z}$. The connected components of the complement of the union of
these hyperplanes are called alcoves. The affine Weyl group $\tilde{W}$ acts simply transitively on the alcoves, so if we write $\tilde{\alpha}$ for the highest root of $\Phi$ and define the fundamental alcove as

$$A_{\circ} = \{x \in V : \langle x, \alpha \rangle > 0 \text{ for all } \alpha \in \Delta \text{ and } \langle x, \tilde{\alpha} \rangle < 1\},$$

we may write every alcove as $w_a A_\circ$ for a unique $w_a \in \tilde{W}$. The affine Weyl group $\tilde{W}$ acts on the coroot lattice $\tilde{Q}$, and if we identify $\tilde{Q}$ with its translation group we may write $\tilde{W} = W \ltimes \tilde{Q}$ as a semidirect product.

If $\alpha \in \Phi^+$ and $w_a \in \tilde{W}$, there is a unique integer $k$ such that $k < \langle x, \alpha \rangle < k + 1$ for all $x \in w_a A_\circ$. We denote this integer by $k(w_a, \alpha)$.

## 2.2 The Shi arrangement

Define the Shi arrangement as the hyperplane arrangement given by the hyperplanes $H_\alpha^d$ for $\alpha \in \Phi^+$ and $d = 0, 1$. Then the complement of the union of these hyperplanes falls apart into connected components, which are called the regions of the arrangement. The hyperplanes that support facets of a region $R$ are called the walls of $R$. Those walls of $R$ that do not contain the origin and separate $R$ from the origin are called the floors of $R$. Define the walls and floors of an alcove similarly. Notice that every wall of a region is a hyperplane of the Shi arrangement, but the walls of an alcove need not be. We call a region or alcove dominant if it is contained in the dominant chamber.

**Theorem 2.1** (Shi, 1987, Prop 7.1) Every region $R$ of the Shi arrangement has a unique minimal alcove $w_R A_\circ \subseteq R$, which is the alcove in $R$ closest to the origin. That is, for any $\alpha \in \Phi^+$ and $w_a \in \tilde{W}$ such that $w_a A_\circ \subseteq R$, we have $|k(w_R, \alpha)| \le |k(w_a, \alpha)|$.

We define $W_{\text{Shi}} = \{w_R : R$ is a Shi region$\}$. The corresponding alcoves $w_R A_\circ$ we call Shi alcoves. That is, we call an alcove a Shi alcove if it is the minimal alcove of the Shi region containing it.

**Theorem 2.2** (Shi, 1987, Prop 7.3) The alcove $w_a A_\circ$ is a Shi alcove if and only if all floors of $w_a A_\circ$ are hyperplanes of the Shi arrangement.

The following theorem is already known for dominant regions (Athanasiadis, 2005, Prop 3.11).

**Theorem 2.3** The floors of the minimal alcove $w_R A_\circ$ of a Shi region $R$ are exactly the floors of $R$.

The following lemma describes what the Shi arrangement looks like in each chamber.

**Lemma 2.4** (Armstrong et al., 2012, Lemma 10.2) For $w \in W$, the hyperplanes of the Shi arrangement that intersect the chamber $wC$ are exactly those of the form $H_{w(\alpha)}^1$ where $\alpha \in \Phi^+$ and $w(\alpha) \in \Phi^+$.

Thus if $w_R A_\circ$ is a Shi alcove contained in the Weyl chamber $wC$, then by Theorem 2.2 and Lemma 2.4 all its floors are of the form $H_{w(\alpha)}^1$ where $\alpha \in \Phi^+$ and $w(\alpha) \in \Phi^+$. So $w^{-1}w_R A_\circ$ is a dominant alcove and its floors are of the form $w^{-1}(H_{w(\alpha)}^1) = H_\alpha^1$ with $\alpha \in \Phi^+$. It is thus a Shi alcove by Theorem 2.2. Conversely, if $w_R A_\circ$ is a dominant Shi alcove and $w \in W$, then $ww_R A_\circ$ is a Shi alcove if and only if $w(\alpha) \in \Phi^+$ whenever $H_\alpha^1$ is a floor of $w_R A_\circ$. Thus the map

$$\Theta : w_R \mapsto (w^{-1}w_R, w)$$

where $w_R A_\circ \subseteq wC$, is a bijection from $W_{\text{Shi}}$ to the set of pairs $(w_R, w)$ such that $w_R A_\circ$ is a dominant Shi alcove, $w \in W$ and $w(\alpha) \in \Phi^+$ whenever $H_\alpha^1$ is a floor of $w_R A_\circ$.
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** A ballot path $\beta \in \mathcal{B}_3$ (left) with one valley (1, 2) and two rises 2, 3, and a Dyck path $\pi \in \mathcal{D}_6$ (right) with valleys (2, 5), (3, 6) and rises 1, 2, 3. We have $A_\beta = \{e_3 - e_2, 2e_2\}$ and $A_\pi = \{e_2 - e_5, e_3 - e_6\}$</figcaption></figure>

Define a partial order on $\Phi^+$ by $\alpha \le \beta$ if and only if $\beta - \alpha$ can be written as a linear combination of simple roots with nonnegative integer coefficients. The set of positive roots $\Phi^+$ with this partial order is called the *root poset*. It turns out that the map

$$FL : R \mapsto \{\alpha \in \Phi^+ : H_\alpha^1 \text{ is a floor of } R\}$$

is a bijection from the set of dominant Shi regions of $\Phi$ to the set of antichains in the root poset of $\Phi$. See Shi (1997). Putting $R \mapsto w_R$, $\Theta$ and $FL$ together and using Theorem 2.3 we get that the map

$$R \mapsto (A, w),$$

where $R \subseteq wC$ and $A = w^{-1}(FL(R))$, is a bijection from the set of Shi regions to the set of pairs $(A, w)$ such that $A$ is an antichain in the root poset, $w \in W$ and $w(A) \subseteq \Phi^+$. A similar bijection using ceilings instead of floors is given in (Armstrong et al., 2012, Prop 10.3).

## 2.3 Types A and C

If $\Phi$ is of type $A_{n-1}$, we take $V = \{(x_1, x_2, \dots, x_n) \in \mathbb{R}^n : \sum_{i=1}^n x_i = 0\}$, $\Phi = \{e_i - e_j : i \neq j\}$ and $\Phi^+ = \{e_i - e_j : i < j\}$. The Weyl group $W$ is the symmetric group $S_n$ that acts on $V$ by permuting coordinates, $\tilde{Q} = \{(x_1, x_2, \dots, x_n) \in \mathbb{Z}^n : \sum_{i=1}^n x_i = 0\}$, $r = n-1$ and $h = n$.

If $\Phi$ is of type $C_n$, we choose $V = \mathbb{R}^n$, $\Phi = \{e_i \pm e_j : i \neq j\} \cup \{\pm 2e_i : i \in [n]\}$ and $\Phi^+ = \{e_i \pm e_j : i > j\} \cup \{2e_i : i \in [n]\}$. The Weyl group $W$ is the hyperoctahedral group $\mathfrak{H}_n$ that acts on $V$ by permuting coordinates and changing signs, $\tilde{Q} = \mathbb{Z}^n$, $r = n$ and $h = 2n$.

## 2.4 Lattice paths

Denote by $\mathcal{L}_{m,n}$ the set of lattice paths from $(0, 0)$ to $(m, n)$ consisting of $n$ North steps $N = (0, 1)$ and $m$ East steps $E = (1, 0)$. Let $\mathcal{D}_n$ denote the set of Dyck paths, that is the subset of $\mathcal{L}_{n,n}$ consisting of the paths that never go below the main diagonal $x = y$. Let $\mathcal{B}_n$ denote the set of ballot paths, that is the set of lattice paths starting at $(0, 0)$, consisting of $2n$ North and/or East steps, and never going below the main diagonal.

A pattern of the form $NN$ is called *rise*. A pattern $EN$ is called *valley*. More precisely, let $\pi$ be any lattice path with steps $s_i \in \{N, E\}$. We say $i$ is a rise of $\pi$ if the $i$-th North step is followed by a North step. We say $(i, j)$ is a valley of $\pi$ if the $i$-th East step is followed by the $j$-th North step. See Figure 1.
If $\pi \in \mathcal{D}_n$ and $\Phi$ is of type $A_{n-1}$, define $A_\pi \subseteq \Phi^+$ by $e_i - e_j \in A_\pi$ if and only if $(i, j)$ is a valley of $\pi$. Then the map $\pi \mapsto A_\pi$ is a bijection from $\mathcal{D}_n$ to the set of antichains in the root poset of $\Phi$.

If $\beta \in \mathcal{B}_n$ and $\Phi$ is of type $C_n$, define $A_\beta \subseteq \Phi^+$ by

$$A_{\beta} = \{e_i - e_j : i > j \text{ and } (n+1-i, n+1-j) \text{ is a valley of } \beta\} \\ \cup \{e_i + e_j : i > j \text{ and } (n+1-i, j+n) \text{ is a valley of } \beta\} \\ \cup \{2e_i : \text{ the last step of } \beta \text{ is its } (n+1-i)\text{-th east step}\}.$$

Then the map $\beta \mapsto A_\beta$ is a bijection from $\mathcal{B}_n$ to the set of antichains in the root poset of $\Phi$.

# 3 Shi regions and parking functions

## 3.1 Shi regions as diagonally labelled paths

A diagonally $\mathfrak{S}_n$-labelled Dyck path is a pair $(\pi, \sigma)$ of a Dyck path $\pi \in \mathcal{D}_n$ and a permutation $\sigma \in \mathfrak{S}_n$ such that for each valley $(i, j)$ of $\pi$ we have $\sigma_i < \sigma_j$. See Figure 2. From the considerations at the end of Section 2.2, recall that regions of the Shi arrangement of type $A_{n-1}$ may be indexed by pairs $(A, \sigma)$ with $A$ an antichain in the root poset, $\sigma \in W = \mathfrak{S}_n$ and $\sigma(A) \subseteq \Phi^+$.

**Proposition 3.1** The map $(\pi, \sigma) \mapsto (A_\pi, \sigma)$ is a bijection between diagonally labelled Dyck paths of length $n$ and regions of the Shi arrangement of type $A_{n-1}$.

We provide an interpretation of type C Shi regions as diagonally labelled ballot paths. For any signed permutation $\sigma \in \mathfrak{S}_n$ we define $w^\sigma$ to be the word of length $2n$ given by $w_i^\sigma = \sigma(n+1-i)$ if $1 \le i \le n$ and $w_i^\sigma = \sigma(n-i)$ if $n+1 \le i \le 2n$. For example if $n=3$ then $w^{id} = 321\overline{1}2\overline{3}$.

A diagonally $\mathfrak{S}_n$-labelled ballot path is a pair $(\beta, w^\sigma)$ of a ballot path $\beta \in \mathcal{B}_n$ and a word $w^\sigma$ corresponding to a signed permutation $\sigma$ such that for each valley $(i, j)$ of $\beta$ we have $w_i^\sigma > w_j^\sigma$, and such that $0 < w_i^\sigma$ if the final step of $\beta$ is its $i$-th East step. Hence, if we place the labels $w^\sigma$ in the diagonal then for each valley the label to its right will be smaller than the label below it. Moreover, if the path ends with an East step then the label below will be positive. See Figure 3.

**Proposition 3.2** The map $(\beta, w^\sigma) \mapsto (A_\beta, \sigma)$ is a bijection between diagonally $\mathfrak{S}_n$-labelled ballot paths the regions of the Shi arrangement of type $C_n$.

## 3.2 The area’ statistic

The area of a Dyck path is defined as the number of boxes strictly between the path and the main diagonal. For example the Dyck path in Figure 2 has area$(\pi) = 5$. Haglund and Loehr (2005) defined a related statistic area' for diagonally labelled Dyck paths as follows. Consider a box strictly between the diagonal and the path $\pi$ in column $i$ and row $j$. This box contributes to area'$(\pi, \sigma)$ if and only if the label to its right is larger than the label below it, that is if and only if $\sigma_i < \sigma_j$. For example the labelled Dyck path in Figure 2 has area'$(\pi, \sigma) = 4$ because the nonshaded box in the fifth row and fourth column does not contribute: $\sigma_4 = 5 > \sigma_5 = 4$.

The area of a ballot path is defined as the number of boxes “below” the path (see Figure 4). We now define a type C area' statistic on diagonally labelled ballot paths. Let $(\beta, w^\sigma)$ be such a path and consider a box below $\beta$ in column $i$ and row $j$. This box contributes to area'$(\beta, w^\sigma)$ if and only if the label to
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** A diagonally labelled Dyck path $(\pi, \sigma)$, where $\sigma_1 = 1 < \sigma_2 = 2$ and $\sigma_2 = 2 < \sigma_5 = 4$. We have $\text{area}(\pi) = 5$ and $\text{area}'(\pi, \sigma) = 4$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** A diagonally labelled ballot path $(\beta, w^{\sigma})$, where $w_1 = \sigma_{4-1} = -1 > w_3 = \sigma_{4-3} = -3$ and $0 < w_2 = \sigma_{4-2} = 2$. We have $\text{area}(\beta) = 4$ and $\text{area}'(\beta, w^{\sigma}) = 1$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** All ballot paths of length two and their area squares shaded gray.</figcaption></figure>

its right is smaller than the label below it, that is if and only if $w_i^{\sigma} > w_j^{\sigma}$. The labelled ballot path in Figure 3 has $\text{area}'(\beta, w^{\sigma}) = 1$ since the shaded box in the third row and second column is the only one contributing: $w_2^{\sigma} = 2 > w_3^{\sigma} = -3$. For example the box in the fourth row and second column does not contribute because $w_2^{\sigma} = 2 < w_4^{\sigma} = \sigma_{3-4} = 3$.

Note that these statistics are the type A and C cases of the following uniform statistic. Define the coheight statistic on regions of the Shi arrangement of any irreducible root system $\Phi$ by

$$ \text{coheight}(R) = |\Phi^+| - \# \text{ hyperplanes of the Shi arrangement separating } R \text{ from the origin.} $$

Then the area' statistics correspond to the coheight statistic under the bijections in Section 3.1.

## 3.3 Parking functions

A vector $f = (f_1, \dots, f_n)$ with nonnegative integer entries is called a (classical) parking function of length $n$ if there exists a permutation $\sigma \in \mathfrak{S}_n$ such that $f_{\sigma(i)} \le i - 1$ for $1 \le i \le n$. Equivalently, $f$ is a parking function if $\#\{j : f_j \le i - 1\} \ge i$ for all $1 \le i \le n$.

There is a natural $\mathfrak{S}_n$-isomorphism between the set of parking functions of length $n$ and the finite torus $\tilde{Q}/(h+1)\tilde{Q}$ of the root system of type $A_{n-1}$. Thus classical parking functions may be seen as objects of type $A$.

We define a type C parking function of length $n$ to be an integer vector $f = (f_1, \dots, f_n)$ where $-n \le f_i \le n$ for all $1 \le i \le n$. Thus type C parking functions of length $n$ are a natural set of representatives for the finite torus $\tilde{Q}/(h+1)\tilde{Q} = \mathbb{Z}^n/(2n+1)\mathbb{Z}^n$ of the root system of type $C_n$.
<figure><img src="image_6.png" /><figcaption>Fig. 5: All six paths in $\mathcal{L}_{2,2}$ and the conditions on their labellings.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6: Constructing an $\mathfrak{H}_4$-labelled path from the parking function $f = (4, 0, -1, -4)$.</figcaption></figure>

## 3.4 Vertically labelled paths

Type A parking functions are commonly represented as Dyck paths with labelled North steps (Haglund, 2008, Chap. 5). An $\mathfrak{S}_n$-labelled Dyck path is a pair $(\pi, \sigma)$ of a Dyck path $\pi \in \mathcal{D}_n$ and a permutation $\sigma \in \mathfrak{S}_n$ such that $\sigma_i < \sigma_{i+1}$ whenever $i$ is a rise of $\pi$. Thus, if the label $\sigma_i$ is placed in the box to the right of the $i$-th North step then labels increase along columns from bottom to top. For example in Figure 7 we have $\sigma_1 = 1 < \sigma_2 = 2 < \sigma_3 = 4$.

We show how type C parking functions can be regarded as labelled lattice paths in a similar fashion. An $\mathfrak{H}_n$-labelled path $(\pi, \sigma)$ is a pair of a lattice path $\pi \in \mathcal{L}_{n,n}$ and a signed permutation $\sigma \in \mathfrak{H}_n$ such that $\sigma_i < \sigma_{i+1}$ whenever $i$ is a rise of $\pi$ and such that $0 < \sigma_1$ if $\pi$ begins with a North step. Thus, if we place the label $\sigma_i$ to the left of the $i$-th North step then the labels increase along columns from bottom to top, and all labels in the zeroth column (that is left of the starting point) are positive. See Figure 5.

Given a parking function $f = (f_1, \dots, f_n)$ we obtain a labelled path as follows. For all $1 \le i \le n$ if $f_i$ is non-negative, place the label $i$ in the $f_i$-th column. If $f_i$ is negative, place the label $-i$ in column $-f_i$. Rearrange the labels in each column in increasing order and draw a path as in Figure 6.

Conversely, let $(\pi, \sigma)$ be a labelled path. We define a parking function $g$ as follows. If a positive label $i$ occurs in the $j$-th column then set $g_i = j$. If a negative label $i$ occurs in the $j$-th column instead set $g_{-i} = -j$. In summary we have the following result.

**Proposition 3.3** *The above correspondence defines a bijection between type C parking functions of length $n$ and vertically $\mathfrak{H}_n$-labelled lattice paths.*

## 3.5 The dinv statistic

The dinv statistic was first defined by Haiman to provide an (at the time conjectural) combinatorial model for the $q, t$-Catalan numbers (Haglund, 2008, Chap. 3). For each Dyck path $\pi \in \mathcal{D}_n$ define the area vector $(a_1, a_2, \dots, a_n)$ by letting $a_i$ be the number of boxes in the $i$-th row, strictly between $\pi$ and the main diagonal. For example the Dyck path in Figure 7 has area vector $(0, 1, 2, 1, 1)$. The dinv statistic is
<figure><img src="image_8.png" /><figcaption>Fig. 7: A vertically labelled Dyck path $(\pi, \sigma)$ with area vector $(0, 1, 2, 1, 1)$ and $\text{dinv}(\pi) = 5$ and $\text{dinv}'(\pi, \sigma) = 4$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 8: A vertically labelled path $(\beta, \sigma)$ with area vector $(1, -2, -1, 0, 1, 2)$ and $\text{dinv}(\beta) = 9$ and $\text{dinv}'(\pi, \sigma) = 6$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9: Paths with type C area vectors $(0, 0, 0, 0)$, $(1, 1, -1, 0)$ and $(-2, -1, 0, 1)$.</figcaption></figure>

defined as

$$ \text{dinv}(\pi) = \#\{(i, j) : i < j, a_i = a_j\} + \#\{(i, j) : i < j, a_i = a_j + 1\}. $$

A pair $(i, j)$ contributing to $\text{dinv}$ is called a *diagonal inversion*. Haglund and Loehr (2005) defined a generalised statistic $\text{dinv}'$ on vertically $\mathfrak{S}_n$-labelled Dyck paths. A pair $(i, j)$ with $a_i = a_j$ contributes if and only if $\sigma_i < \sigma_j$. On the other hand, a pair $(i, j)$ with $a_i = a_j + 1$ contributes if and only if $\sigma_i > \sigma_j$. Compare with Figure 7.

We define an area vector and a $\text{dinv}$ statistic of type C for lattice paths $\pi \in \mathcal{L}_{n,n}$. The area vector $(a_1, a_2, \dots, a_n)$ is given by $a_i = i - b_i$ where $b_i$ is the number of boxes in the i-th row left of $\pi$. See Figures 8 and 9. Moreover, we define

$$ \begin{aligned} \text{dinv}(\pi) = & \#\{(i, j) : i < j, a_i = a_j\} + \#\{(i, j) : i < j, a_i = a_j + 1\} \\ & + \#\{(i, j) : i < j, a_i = -a_j\} + \#\{(i, j) : i < j, a_i = -a_j + 1\} \\ & + \#\{i : a_i = 0\}. \end{aligned} $$

Next, we define a $\text{dinv}$ statistic for vertically $\mathfrak{H}_n$-labelled lattice path $(\pi, \sigma)$. As in type A above, a pair $(i, j)$ of candidate rows contributes if and only if the labels $\sigma_i$ and $\sigma_j$ satisfy a certain inequality. More precisely,

$$ \begin{aligned} \text{dinv}'(\pi, \sigma) = & \#\{(i, j) : i < j, a_i = a_j, \sigma_i < \sigma_j\} + \#\{(i, j) : i < j, a_i = a_j + 1, \sigma_i > \sigma_j\} \\ & + \#\{(i, j) : i < j, a_i = -a_j, \sigma_i < -\sigma_j\} + \#\{(i, j) : i < j, a_i = -a_j + 1, \sigma_i > -\sigma_j\} \\ & + \#\{i : a_i = 0, \sigma_i < 0\}. \end{aligned} $$
<figure><img src="image_11.png" /><figcaption>**Fig. 10:** The classical zeta map: A vertically labelled Dyck path $(\pi, \sigma)$ (left), the construction of $\zeta(\pi)$ (middle), and $\zeta(\pi, \sigma)$ (right).</figcaption></figure>

Note that the two definitions of $\text{dinv}(\pi)$ agree if $\pi$ is a Dyck path.

Consider the $\mathfrak{H}_6$-labelled path $(\pi, \sigma)$ in Figure 8. Its area vector is given by $(1, -2, -1, 0, 1, 2)$. There is one diagonal inversion of type $a_i = a_j$, namely $(1, 5)$, one diagonal inversion of type $a_i = a_j + 1$, namely $(1, 4)$, three diagonal inversions of type $a_i = -a_j$, namely $(1, 3)$, $(2, 6)$ and $(3, 5)$, three diagonal inversions of type $a_i = -a_j + 1$, namely $(1, 4)$, $(3, 6)$ and $(4, 5)$, and one row of length zero, namely $i = 4$. In total we have 9 diagonal inversions, so $\text{dinv}(\pi) = 9$. Note that the inversion $(1, 4)$ is counted twice!

If we wish to take labels into account we find that $\sigma_4 = 2 > 0$, so the row of length zero does not contribute. Moreover $\sigma_1 = 1 < \sigma_4 = 2$, thus $(1, 4)$ is not a d'-inversion of type $a_i = a_j + 1$, and $\sigma_2 = -5 > -\sigma_6 = -6$, thus $(2, 6)$ is not a d'-inversion of type $a_i = -a_j$. The labels of all other diagonal inversions fit our requirements, so $\text{dinv}'(\pi, \sigma) = 6$.

# 4 The zeta map

The original zeta map is a bijection $\zeta : \mathcal{D}_n \to \mathcal{D}_n$ on Dyck paths and appears in a paper of Andrews et al. (2002). A more explicit treatment including the compatibility with the statistics on Dyck paths defined in the previous sections can be found in (Haglund, 2008, Thrm. 3.15). Let us start by recalling the definition of the zeta map.

Given a Dyck path $\pi \in \mathcal{D}_n$ with area vector $(a_1, a_2, \dots, a_n)$, set $i=0$ and place your pen at $(0, 0)$. Now read the area vector from left to right drawing an East step for each $i-1$ you encounter and a North step for each $i$. Replace $i$ by $i+1$ and repeat until you reach the point $(n, n)$. See Figure 10.

We describe a bijection $\zeta_C : \mathcal{L}_{n,n} \to \mathcal{B}_n$ which is an analogue of the classical zeta map.

Given a path $\pi \in \mathcal{L}_{n,n}$ with type C area vector $(a_1, a_2, \dots, a_n)$, set $i=n$ and start with your pen at $(0, 0)$. Read the area vector from left to right drawing an East step for each $-i-1$ you encounter and a North step for each $-i$. Then read the area vector from right to left drawing an East step for each $i+1$ you encounter and a North step for each $i$. Now replace $i$ by $i-1$ and repeat the process until $2n$ steps are drawn. See Figure 11.

It is clear from the construction that $\zeta_C(\pi)$ never goes below the main diagonal. Moreover when $\pi$ is a Dyck path, then $\zeta_C(\pi)$ is just the reverse path of $\zeta(\pi)$. In particular $\zeta_C$ sends Dyck paths to Dyck paths.

The following is our first main result.
<figure><img src="image_12.png" /><figcaption>**Fig. 11:** The type *C* zeta map: A vertically labelled lattice path $(\pi, \sigma)$ (left), the construction of $\zeta_C(\pi)$ (middle), and $\zeta(\pi, \sigma)$ (right). Note that $\text{dinv}'(\pi, \sigma) = 6 = \text{area}'(\zeta(\pi, \sigma))$.</figcaption></figure>

**Theorem 4.1** *The map $\zeta_C : \mathcal{L}_{n,n} \to \mathcal{B}_n$ is a bijection such that $\text{dinv}_C(\pi) = \text{area}(\zeta_C(\pi))$.*

The zeta map can be inverted using the bounce path of a ballot path. A detailed proof will appear in the full version.

## 4.1 The Haglund–Loehr zeta map

Haglund and Loehr (2005) extended the classical zeta map to a bijection from vertically labelled Dyck paths to diagonally labelled Dyck paths that sends the dinv' statistic to the area' statistic. We start out by recalling their definition. If $(\pi, \sigma)$ is a vertically $\mathfrak{S}_n$-labelled path, then $\zeta(\pi, \sigma)$ is simply the diagonal labelling of $\zeta(\pi)$ obtained as follows. For $i = 0, 1, \dots, n$ read the labels of rows with area equal to $i$ from bottom to top and insert them in the diagonal. Compare with Figure 10.

Similarly, in type *C* we start with a vertically $\mathfrak{H}_n$-labelled path $(\pi, \sigma)$ and construct a diagonally labelled ballot path $\zeta(\pi, \sigma) = (\beta, w)$. The ballot path is given by $\beta = \zeta_C(\pi)$. The labelling is obtained as follows. For $i = n, n-1, \dots, 1$ read the labels of the rows with area $i$ from top to bottom and insert them in the diagonal, then read the labels of rows with area equal to $-i+1$ from bottom to top and insert their negatives in the diagonal. In the end complement the $n$ labels by adding their negatives in reverse order. See Figures 11, 12 and 13.

The theorem below is the main result of this paper.

**Theorem 4.2** *The type *C* zeta map is a bijection from vertically $\mathfrak{H}_n$-labelled paths to diagonally $\mathfrak{H}_n$-labelled ballot paths that sends the dinv' statistic to the area' statistic.*

Combining Theorem 4.2 with Propositions 3.2 and 3.3 we obtain a new proof of the well known result that the Shi arrangement of type $C_n$ has $(2n+1)^n$ regions.

## 4.2 The zeta maps via valleys

The Haglund–Loehr zeta map has another simple description given in Armstrong et al. (2014a). Let us fix the following convention. If $(\pi, \sigma)$ is a vertically $\mathfrak{S}_n$-labelled Dyck path with rise $i$ then we say the rise
<figure><img src="image_13.png" /><figcaption>**Fig. 12:** The area vector of $\pi$ is (1, 0, 1). The diagonal inversions are (1, 2), (1, 2), (1, 3), (2, 3), $i = 2$, and $\text{dinv}'(\pi, \sigma) = 5 = \text{area}'(\beta, w)$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>**Fig. 13:** The area vector of $\pi$ is (1, -1, 0). The diagonal inversions are (1, 2), (1, 3), (1, 3), $i = 3$ but only (1, 3) (as inversion of type $a_i = -a_j + 1$) contributes to $\text{dinv}'(\pi, \sigma) = 1$.</figcaption></figure>

has label $(\sigma_i, \sigma_{i+1})$. If $(\pi, \sigma)$ is a diagonally labelled Dyck path with valley $(i, j)$ then we say the valley has label $(\sigma_i, \sigma_j)$.

The image $\zeta(\pi, \sigma)$ of a vertically labelled Dyck path under the zeta map can now be defined as follows. First insert the diagonal labelling as described in the previous section. The Dyck path is the unique path which has a valley labelled $(a, b)$ if and only if $(\pi, \sigma)$ has a rise labelled $(a, b)$. See Figure 10.

There is a similar description of the zeta map in type C provided by the following proposition. If $(\pi, \sigma)$ is a vertically $\mathfrak{S}_n$-labelled path with rise $i$ then we say the rise has label $(\sigma_i, \sigma_{i+1})$. If $(\beta, w)$ is a diagonally labelled ballot path with valley $(i, j)$ then we say the valley has label $(w_i, w_j)$.

**Proposition 4.3** Let $(\pi, \sigma)$ be a vertically $\mathfrak{S}_n$-labelled lattice path. Then $\zeta(\pi, \sigma)$ has valley labelled $(a, b)$ if and only if $(\pi, \sigma)$ has a rise labelled $(b, a)$ or $(-a, -b)$. Moreover, $\zeta(\pi, \sigma)$ ends with an East step in the same column as label $a$ if and only if $(\pi, \sigma)$ begins with a North step labelled $a$.

Compare with Figures 11, 12 and 13.

<figure><img src="image_15.png" /><figcaption>**Fig. 14:** The labelling of the steps of a path $\pi$ (left), the set $X$ of labelled steps (middle), and the path $\text{sw}(\pi)$ of steps in increasing order (right).</figcaption></figure>
## 4.3 The sweep map

A generalisation of the zeta map to rational Dyck paths called the sweep map was defined by Armstrong et al. (2014b). The concept of the sweep map is as follows. Given a path one assigns to each step a label, the labels being distinct integers. To obtain the image of a path under the sweep map, one rearranges the steps such that the labels are in increasing order.

We now give a description of the zeta map of type C similar to the sweep map on Dyck paths. Given a path $\pi = s_1s_2, \dots, s_{2n} \in \mathcal{L}_{n,n}$ assign a label to each step by setting $\ell(s_1) = 0$, $\ell(s_{i+1}) = \ell(s_i) + 2n + 1$ if $s_i = N$, and $\ell(s_{i+1}) = \ell(s_i) - 2n$ if $s_i = E$. Now define a collection $X$ of labelled steps as follows. If $\ell(s_i) < 0$ then add $(s_i, \ell(s_i))$. If $\ell(s_i) > 0$ then add $(s_{i-1}, -\ell(s_i))$. Finally, for the step $s_1$ which is the only step labelled 0, add $(s_{2n}, -n)$. Thus, $X$ contains $2n$ labelled steps.

Finally, draw a path as follows. Choose $(s, \ell) \in X$ such that $\ell$ is the minimal label among all pairs in $X$. Draw the step $s$ and remove $(s, \ell)$ from $X$. Repeat until $X$ is empty. We denote the path obtained in this way by $\mathrm{sw}(\pi)$. See Figure 14. We conclude with the following theorem.

**Theorem 4.4** For each lattice path $\pi \in \mathcal{L}_{n,n}$ we have $\mathrm{sw}(\pi) = \zeta_C(\pi)$. In particular, the sweep map $\mathrm{sw} : \mathcal{L}_{n,n} \to \mathcal{B}_n$ is a bijection.

## References

G. Andrews, C. Krattenthaler, L. Orsina, and P. Papi. ad-nilpotent b-ideals in $sl(n)$ having fixed class of nilpotence: Combinatorics and enumeration. *Trans. Amer. Math. Soc.*, 354:3835–3853, 2002.

D. Armstrong, V. Reiner, and B. Rhoades. Parking spaces. 2012. arXiv:1204.1760.

D. Armstrong, N. A. Loehr, and G. S. Warrington. Rational parking functions and Catalan numbers. 2014a. arXiv:1403.1845.

D. Armstrong, N. A. Loehr, and G. S. Warrington. Sweep maps: A continuous family of sorting algorithms. 2014b. arXiv:1406.1196.

C. A. Athanasiadis. On a refinement of the generalized Catalan numbers for Weyl groups. *Trans. Amer. Math. Soc.*, 357:179–196, 2005.

J. Haglund. *The q, t-Catalan numbers and the space of diagonal harmonics*, volume 41 of *Univ. Lecture Ser. Amer. Math. Soc.*, 2008.

J. Haglund and N. A. Loehr. A conjectured combinatorial formula for the Hilbert series for diagonal harmonics. *Discrete Math.*, 298:189–204, 2005.

J. E. Humphreys. *Reflection groups and Coxeter groups*, volume 29 of *Cambridge Stud. Adv. Math*. Cambridge Univ. Press, Cambridge, 1990.

J. Shi. Sign types corresponding to an affine weyl group. *J. Lond. Math. Soc.*, s2-35 (1):56–74, 1987.

J. Shi. The number of $\oplus$-sign types. *Q. J. Math.*, 48 (1):93–105, 1997.