Arc Permutations (extended abstract)

Sergi Elizalde<fnref n="1" />†and Yuval Roichman<fnref n="2" />

**Abstract.** Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. In this paper we describe combinatorial properties of these permutations, including characterizations in terms of pattern avoidance, connections to Young tableaux, and an affine Weyl group action on them.

**Résumé.** Les permutations arc et les permutations unimodales ont été introduites dans l'étude des triangulations et des caractères. Dans cet article, on décrit les propriétés combinatoires de ces permutations, y compris des caractérisations en termes de motifs interdits, des connexions avec des tableaux de Young, et une action du groupe de Weyl affine.

**Keywords:** arc permutation, pattern avoidance, unimodal permutation, Young tableau, weak order, affine Weyl group

# 1 Introduction

A permutation in the symmetric group $S_n$ is an *arc permutation* if every prefix forms an interval in $\mathbb{Z}_n$. It was found recently that arc permutations play an important role in the study of graphs of triangulations of a polygon [2]. A familiar subset of arc permutations is that of unimodal arc permutations, which are those permutations whose inverses have one local maximum or one local minimum. These permutations appear in the study of Hecke algebra characters [3, 11]. In this paper we study combinatorial properties and structures on these sets of permutations.

In Section 3 we show that both arc and unimodal permutations may be characterized by pattern avoidance, as described in Theorem 3.2 and Proposition 3.4 below.

In Section 4 we describe a bijection between unimodal permutations and certain shifted shapes. The shifted shape corresponding to a permutation $\pi$ has the property that standard Young tableaux of that shape encode all reduced words of $\pi$. As a consequence, domination in the weak order on unimodal permutations is characterized by inclusion of the corresponding shapes (Theorem 5.1), and thus this order is a modular lattice (Proposition 5.3). Another consequence is that the number of maximal chains in this order is equal to twice the number of staircase shifted Young tableaux, that is, $2\binom{n}{2}! \cdot \prod_{i=0}^{n-2} \frac{i!}{(2i+1)!}$ (Corollary 5.5). This formula is analogous to a well-known result of Stanley [13] stating that the number of maximal chains in the weak order on $S_n$ equals the number of standard Young tableaux of triangular shape.

A transitive affine Weyl group action on the set of arc permutations is studied in Section 6. It is shown that the resulting Schreier graph has the following property: an arc permutation is unimodal if and only

<footnote n="1">¹Department of Mathematics, Dartmouth College, Hanover, NH 03755, USA</footnote>

<footnote n="2">²Department of Mathematics, Bar-Ilan University, 52900 Ramat-Gan, Israel</footnote>

<footnote>†Partially supported by NSF grant DMS-1001046.</footnote>
if its coset appears in a geodesic between two distinguished antipodes. Hence the number of geodesics between these antipodes is, again, $2(\binom{n}{2})! \cdot \prod_{i=0}^{n-2} \frac{i!}{(2i+1)!}$. This result is analogous to [2, Theorem 9.9], see also [10, Theorem 2].

The set of non-unimodal arc permutations is not a union of Knuth classes. However, it carries surprising Knuth-like properties, which are described in Section 7. We present a bijection between non-unimodal arc permutations and standard Young tableaux of hook shape plus one box, which preserves the descent set (Theorem 7.1). A representation-theoretic explanation of this equidistribution of descent sets is hinted in Section 7.3. Finally, in Section 8 we describe another set of permutations, generated by shuffles of two increasing sequences, that have many properties similar to those of unimodal and arc permutations.

The proofs omitted in this extended abstract appear in the full version [6], together with more results.

# 2 Basic concepts

In the following definitions, an interval in $\mathbb{Z}$ is a subset $[a, b] = \{a, a+1, \dots, b\}$ for some $a \le b$, and an interval in $\mathbb{Z}_n$ is a subset of the form $[a, b]$ or $[b, n] \cup [1, a]$ for some $1 \le a \le b \le n$.

## 2.1 Unimodal permutations

**Definition 2.1** A permutation $\pi \in S_n$ is left-unimodal if, for every $1 \le k \le n$, the first $k$ letters in $\pi$ form an interval in $\mathbb{Z}$. Denote by $\mathcal{L}_n$ the set of left-unimodal permutations in $S_n$.

For example, 342561 is left-unimodal, but 3412 is not. Clearly, $|\mathcal{L}_n| = 2^{n-1}$, since when building a permutation $\pi \in \mathcal{L}_n$ from left to right, one has two choices for each of $\pi(n), \pi(n-1), \dots, \pi(2)$.

We denote by $\text{Des}(\pi)$ the descent set of a permutation $\pi$, and by $\text{RSK}(\pi) = (P, Q)$ the pair of standard Young tableaux associated to $\pi$ by the RSK correspondence. Recall that $\text{Des}(\pi)$ equals the descent set of $Q$, and $\text{Des}(\pi^{-1})$ equals the descent set of $P$.

**Remark 2.2** A permutation $\pi$ is left-unimodal if and only if $\text{Des}(\pi^{-1}) = \{1, 2, \dots, i\}$ for some $i$. In particular, if $\text{RSK}(\pi) = (P, Q)$, then $P$ is a hook with entries $1, 2, \dots, i+1$ in the first column, and $Q$ is any hook with the same shape. It follows that left-unimodal permutations are a union of Knuth classes.

**Definition 2.3** A permutation $\pi \in S_n$ is unimodal if either every prefix forms an interval in $\mathbb{Z}$, or every suffix forms an interval in $\mathbb{Z}$. Denote by $\mathcal{U}_n$ the set of unimodal permutations in $S_n$.

For example, the permutation 165243 is unimodal. It is clear that $|\mathcal{U}_n| = 2^n - 2$ for $n \ge 2$, since for each $\pi \in \mathcal{U}_n$, either $\pi$ or its reversal is left-unimodal, but not both unless $\pi = 12 \dots n$ or $\pi = n \dots 21$.

**Remark 2.4** A permutation $\pi \in S_n$ is unimodal if and only if $\text{Des}(\pi^{-1})$ equals $\{1, 2, \dots, i\}$ or $\{i+1, i+2, \dots, n-1\}$ for some $i$. If $\pi \in \mathcal{U}_n$ and $\text{RSK}(\pi) = (P, Q)$, then $P$ is a hook with entries of $1, 2, \dots, i+1$ in the first column or in the first row, and $Q$ is any hook with the same shape as $P$. Thus unimodal permutations are a union of Knuth classes.

## 2.2 Arc permutations

**Definition 2.5** A permutation $\pi \in S_n$ is an arc permutation if, for every $1 \le k \le n$, the first $k$ letters in $\pi$ form an interval in $\mathbb{Z}_n$. Denote by $\mathcal{A}_n$ the set of arc permutations in $S_n$.

**Example:** The permutation 12543 is an arc permutation in $S_5$, but 125436 is not an arc permutation in $S_6$, since $\{1, 2, 5\}$ is an interval in $\mathbb{Z}_5$ but not in $\mathbb{Z}_6$.
It is easy to see that $|A_n| = n2^{n-2}$ for $n \ge 2$, because when building a permutation $\pi \in A_n$ from left to right, one has $n$ choices for $\pi(1)$ and two choices for each of $\pi(2), \pi(3), \dots, \pi(n-1)$.

**Remark 2.6** Arc permutations are not a union of Knuth classes. However, they may be characterized in terms of descent sets: $\pi \in S_n$ is an arc permutation if and only if either $\mathrm{Des}(\pi^{-1}) = [1, i] \cup [j+1, n-1]$ and $\pi^{-1}(1) < \pi^{-1}(n)$, or $\mathrm{Des}(\pi^{-1}) = [i+1, j]$ and $\pi^{-1}(1) > \pi^{-1}(n)$, for some $i \le j$.

It is clear from the definition that the sets of left-unimodal, unimodal and arc permutations satisfy $\mathcal{L}_n \subset \mathcal{U}_n \subset \mathcal{A}_n$. We denote by $\mathcal{Z}_n = \mathcal{A}_n \setminus \mathcal{U}_n$ the set of non-unimodal arc permutations. It follows from Remarks 2.4 and 2.6 that $\mathcal{Z}_n$ is not a union of Knuth classes. However, $\mathcal{Z}_n$ has some surprising Knuth-like properties, which will be described in Section 7.

# 3 Characterization by pattern avoidance

In this section the sets of left-unimodal permutations, arc permutations, and unimodal permutations are characterized in terms of pattern avoidance. Given a set of patterns $\sigma_1, \sigma_2, \dots$, denote by $S_n(\sigma_1, \sigma_2, \dots)$ the set of permutations in $S_n$ that avoid all of the $\sigma_i$, that is, that do not contain a subsequence whose entries are in the same relative order as those of $\sigma_i$. Define $A_n(\sigma_1, \sigma_2, \dots)$ analogously.

## 3.1 Left-unimodal permutations

It will be convenient to use terminology from *geometric grid classes*. Studied by Albert el al. [4], a geometric grid class consists of those permutations that can be drawn on a specified set of line segments of slope $\pm 1$ arranged as a matrix. More precisely, such a permutation can be obtained by placing $n$ dots on the segments in such a way that there are no two dots on the same vertical or horizontal line, labeling the dots with $1, 2, \dots, n$ by increasing $y$-coordinate, and then reading them by increasing $x$-coordinate. Although not true for all geometric grid classes, all the geometric grid classes that we consider in this paper are also profile classes in the sense of Murphy and Vatter [9].

Left-unimodal permutations are those that can be drawn on the shape on the left of Fig. 1, which consists of a segment of slope 1 above a segment of slope -1. The picture on the right shows a drawing of the permutation 32415. The grid class of permutations that can be drawn on this shape is denoted by

$$ G \begin{pmatrix} 1 \\ -1 \end{pmatrix}, \text{ so we have that } \mathcal{L}_n = \mathcal{G}_n \begin{pmatrix} 1 \\ -1 \end{pmatrix} = \mathcal{G} \begin{pmatrix} 1 \\ -1 \end{pmatrix} \cap S_n. $$

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** The grid for left-unimodal permutations, and a drawing of the permutation 32415. For aesthetic reasons, figures in this paper have different scaling on the axes.</figcaption></figure>

It is clear from the description that geometric grid classes are always closed under pattern containment, so they are characterized by the set of minimal forbidden patterns. In the case of left-unimodal permutations, we get the following description.
**Claim 3.1** $\mathcal{L}_n = \mathcal{S}_n(132, 312)$.

**Proof:** Every prefix of $\pi$ is an interval in $\mathbb{Z}$ if and only if there is no pattern $\pi(i)\pi(j)\pi(k)$ (with $i < j < k$) where the value of $\pi(k)$ is between $\pi(i)$ and $\pi(j)$, that is, $\pi$ avoids 132 and 312. $\square$

## 3.2 Arc permutations

Arc permutations can be characterized as those avoiding the eight patterns $\sigma \in \mathcal{S}_4$ with $|\sigma(1) - \sigma(2)| = 2$.

**Theorem 3.2** $\mathcal{A}_n = \mathcal{S}_n(1324, 1342, 2413, 2431, 3124, 3142, 4213, 4231)$.

**Proof:** Let $\pi \in \mathcal{S}_n$, and suppose that $\pi \notin \mathcal{A}_n$. Let $i > 1$ be the smallest number with the property that $\{\pi(1), \pi(2), \dots, \pi(i)\}$ is not an interval in $\mathbb{Z}_n$. By minimality of $i$, the set $\{\pi(1), \pi(2), \dots, \pi(i-1)\}$ contains neither $\pi(i)+1$ nor $\pi(i)-1 \bmod n$. Letting $j < k$ be such that $\{\pi(j), \pi(k)\} = \{\pi(i)+1, \pi(i)-1\} \bmod n$, it follows that $\pi(i-1)\pi(i)\pi(j)\pi(k)$ is an occurrence of one of the eight patterns above.

Conversely, if $\pi \in \mathcal{S}_n$ contains one of the eight patterns, let $\pi(h)\pi(i)\pi(j)\pi(k)$ be such an occurrence, where $h < i < j < k$. Then $\{\pi(1), \pi(2), \dots, \pi(i)\}$ is not an interval in $\mathbb{Z}_n$. $\square$

**Corollary 3.3** $|\mathcal{S}_n(1324, 1342, 2413, 2431, 3124, 3142, 4213, 4231)| = n2^{n-2}$ for $n \ge 2$.

Arc permutations can also be described in terms of grid classes, as those permutations that can be drawn in one of the two shapes in Fig. 2. We write

$$ \mathcal{A}_n = \mathcal{G}_n \begin{pmatrix} 1 & 0 \\ -1 & 0 \\ 0 & -1 \\ 0 & 1 \end{pmatrix} \cup \mathcal{G}_n \begin{pmatrix} 0 & -1 \\ 0 & 1 \\ 1 & 0 \\ -1 & 0 \end{pmatrix}. $$

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Grids for arc permutations.</figcaption></figure>

## 3.3 Unimodal permutations

Unimodal permutations are those that can be drawn in one of the two shapes in Fig. 3, that is,

$$ \mathcal{U}_n = \mathcal{G}_n \begin{pmatrix} 1 \\ -1 \end{pmatrix} \cup \mathcal{G}_n \begin{pmatrix} -1 \\ 1 \end{pmatrix}. $$
<figure><img src="image_3.png" /><figcaption>Fig. 3: Grids for unimodal arc permutations.</figcaption></figure>

**Proposition 3.4** $U_n = A_n(2143, 3412)$.

**Proof:** If $\pi$ contains 2143 or 3412, then it is clear that $\pi$ is not unimodal. For the converse, we show that every arc permutation $\pi \in A_n$ that is not unimodal must contain one of the patterns 2143 or 3412. Since $\pi \in A_n$, it can be drawn in one of the two shapes in Fig. 2. Suppose it can be drawn on the left shape. Since $\pi$ is not unimodal, any drawing of $\pi$ on the left shape requires some element $\pi(i)$ with $i > 1$ to be on the first increasing slope (if $i = 1$, then the dot could be moved to the decreasing slope without changing the permutation), and some element $\pi(j)$ with $j < n$ to be on the second increasing slope. Then $\pi(1)\pi(i)\pi(j)\pi(n)$ is an occurrence of 3412. An analogous argument shows that if $\pi$ can be drawn on the right shape of Fig. 2 but it is not unimodal, then it contains 2143. $\square$

**Corollary 3.5** $|S_n(1324, 1342, 2143, 2413, 2431, 3124, 3142, 3412, 4213, 4231)| = 2^n - 2$ for $n \ge 2$.

## 4 Prefixes associated to the shifted staircase shape

Consider the shifted staircase shape $\Delta_n$ with rows labeled 1, 2, ..., $n-1$ from top to bottom, and columns labeled 2, 3, ..., $n$ from left to right. Given a filling with the numbers from 1 to $n(n-1)/2$, with increasing entries in each row and column, erase the numbers greater than $k$, for some $k$, obtaining a *partial filling* of $\Delta_n$. For each of the remaining entries $1 \le \ell \le k$, if $\ell$ lies in row $i$ and column $j$, let $t_\ell$ be the transposition $(i, j)$. Associate to the partial filling the permutation $\pi = t_1t_2...t_k$.

**Example:** The partial filling on the left of Fig. 4 corresponds to the product of transpositions

$$ (1, 2)(1, 3)(1, 4)(2, 3)(2, 4)(1, 5)(3, 4)(1, 6)(2, 5)(2, 6) = 4356217. $$

<figure><img src="image_4.png" /><figcaption>Fig. 4: Two partial fillings of the shifted staircase shape $\Delta_7$.</figcaption></figure>
**Theorem 4.1** The set of permutations obtained as products of transpositions associated to a partial filling of the shifted staircase shape $\Delta_n$ is exactly $\mathcal{L}_n$.

**Proof:** The first observation is that if two boxes in the tableau are in different rows and columns, the associated transpositions commute. It follows that the resulting permutation depends only on what boxes of the tableaux are filled, but not on the order in which they were filled. For example, the partial filling on the right of Fig. 4 yields again the permutation 4356217, just as the one on the left, since both have the same set of filled boxes.

We claim that, from the set of filled boxes, the corresponding permutation can be read as follows. Let $i$ be the largest such that the box $(i, i+1)$ is filled. Then, starting at the bottom-left corner of that box, consider the path with north and east steps (along the edges of the boxes of the tableau) that separates the filled and unfilled boxes, ending at the top-right corner. At each east step, read the label of the corresponding column, and at each north step, read the label of the corresponding row. This claim can be easily proved by induction on the number of filled boxes. The permutations obtained by reading the labels of such paths are precisely the left-unimodal permutations. $\square$

The above proof gives a bijection between $\mathcal{L}_n$ and the set of shifted shapes of size at most $\binom{n}{2}$, which consist of the filled boxes in partial fillings.

**Definition 4.2** For $\pi \in \mathcal{L}_n$, denote by $\mathrm{sh}(\pi)$ the shifted shape corresponding to any partial filling of $\Delta_n$ associated to $\pi$.

# 5 The weak order on $U_n$

## 5.1 A criterion for domination

Let $\ell(\cdot)$ be the length function on $S_n$ with respect to the Coxeter generating set $S$ (see Section 6.1). Recall the definition of the (right) weak order on $S_n$: for every pair $\pi, \sigma \in S_n$, $\pi \le \sigma$ if and only if $\ell(\pi) + \ell(\pi^{-1}\sigma) = \ell(\sigma)$. Denote this poset by $\mathrm{Weak}(S_n)$. Recall that $\mathrm{Weak}(S_n)$ is a lattice, which is not modular. First, we give a combinatorial criterion for weak domination of unimodal permutations.

The concept of shifted shape from Definition 4.2 can be extended to all unimodal permutation as follows: for $\pi \in U_n \setminus \mathcal{L}_n$ let $\mathrm{sh}(\pi) = \mathrm{sh}(w_0\pi w_0)$, where $w_0$ denotes the longest permutation $n \dots 21$, which is the maximum in $\mathrm{Weak}(U_n)$. Denote by $e = 12 \dots n$ the minimum element in $\mathrm{Weak}(u_n)$. Note that $w_0\mathcal{L}_nw_0 = U_n \setminus \mathcal{L}_n \cup \{e, w_0\}$.

**Theorem 5.1** For every pair $\pi, \sigma \in U_n$, $\pi \le \sigma$ in $\mathrm{Weak}(S_n)$ if and only if

(i) either $\pi, \sigma \in \mathcal{L}_n$ or $\pi, \sigma \in U_n \setminus \mathcal{L}_n \cup \{e, w_0\}$, and

(ii) $\mathrm{sh}(\pi) \subseteq \mathrm{sh}(\sigma)$.

**Proof:** By [5, Cor. 1.5.2, Prop. 3.1.3], if $\pi \le \sigma$ in $\mathrm{Weak}(S_n)$, then $\mathrm{Des}(\pi^{-1}) \subseteq \mathrm{Des}(\sigma^{-1})$. Combining this with the characterizations of left-unimodal and unimodal permutations by descent sets, given in Remarks 2.2 and 2.4, condition (i) follows.

Now we may assume, without loss of generality, that $\pi, \sigma \in \mathcal{L}_n$. It suffices to show that domination in weak order is equivalent to inclusion of the corresponding shapes. Indeed, recall the bijection described in Section 4 from $\mathcal{L}_n$ to the set of shifted shapes inside $\Delta_n$. By this bijection, for any permutation
$\pi \in \mathcal{L}_n \setminus \{w_0\}$, an addition of a box in the border of $\mathrm{sh}(\pi)$ corresponds to a switch of two adjacent increasing letters in $\pi$ giving a permutation in $\mathcal{L}_n$. This is precisely the covering relation in $\mathrm{Weak}(\mathcal{U}_n)$. $\square$

**Corollary 5.2** For every $\pi \in \mathcal{U}_n$, $\ell(\pi) = |\mathrm{sh}(\pi)|$.

## 5.2 Enumeration of maximal chains in the weak order on $\mathcal{U}_n$

Denote by $\mathrm{Weak}(\mathcal{U}_n)$ the subposet of $\mathrm{Weak}(S_n)$ induced by $\mathcal{U}_n$. Theorem 5.1 implies the following properties of this poset.

**Corollary 5.3** $\mathrm{Weak}(\mathcal{U}_n)$ is a graded self-dual modular lattice.

**Corollary 5.4** For every $\pi \in \mathcal{U}_n \setminus \{w_0\}$, the number of maximal chains in the interval $[e, \pi]$ is equal to the number of standard Young tableaux of shifted shape $\mathrm{sh}(\pi)$, hence given by a hook formula.

**Proof:** By Theorems 4.1 and 5.1, the statement holds for every $\pi \in \mathcal{L}_n \setminus \{w_0\}$. By conjugation by $w_0$ it holds for all elements in $\mathcal{U}_n \setminus \mathcal{L}_n$. $\square$

Using Schur's formula for the number of standard Young tableaux of given shifted shape [12][8, p. 267(2)], we get the following enumeration formula.

**Corollary 5.5** For $n > 2$, the number of maximal chains in $\mathrm{Weak}(\mathcal{U}_n)$ is equal to twice the number of standard Young tableaux of shifted staircase shape, hence equal to $2\binom{n}{2}! \cdot \prod_{i=0}^{n-2} \frac{i!}{(2i+1)!}$.

## 5.3 The Hasse diagram

Let $\Gamma_n$ be the undirected Hasse diagram of $\mathrm{Weak}(\mathcal{U}_n)$.

**Proposition 5.6** (i) The diameter of $\Gamma_n$ is $\binom{n}{2}$.

(ii) The vertices $e$ and $w_0$ are antipodes in $\Gamma_n$.

(iii) The number of geodesics between these antipodes is $2\binom{n}{2}! \cdot \prod_{i=0}^{n-2} \frac{i!}{(2i+1)!}$.

**Proof:** Since $\mathrm{Weak}(\mathcal{U}_n)$ is a modular lattice, the distance between any two vertices is equal to the difference between the ranks of their join and their meet (see [1, Lemma 5.2]). Hence, the diameter is equal to the maximum rank. This proves (i) and (ii). Part (iii) now follows from Corollary 5.5. $\square$

# 6 An affine Weyl group action

## 6.1 The action

In this section we describe an affine Weyl group action on arc permutations, which reduces to an hyper-
octahedral group action on $\mathcal{L}_n$,

Recall that the affine Weyl group $\tilde{C}_n$ is generated by $S = \{s_0, s_1, \dots, s_{n-1}, s_n\}$ subject to the Coxeter relations

$$s_i^2 = 1 \quad (\forall i),$$

$$(s_i s_j)^2 = 1 \quad (|j - i| > 1),$$

$$(s_i s_{i+1})^3 = 1 \quad (1 \le i < n - 1),$$

$$(s_i s_{i+1})^4 = 1 \quad (i = 0, n - 1).$$
The group $\tilde{C}_{n-2}$ acts naturally on $\mathcal{A}_n$ as follows. Denote by $S = \{\sigma_i : 1 \le i \le n-1\}$ the Coxeter generating set of $S_n$, where $\sigma_i$ is identified with the adjacent transposition $(i, i+1)$.

**Definition 6.1** For every $0 \le i \le n-2$, define a map $\rho_i : \mathcal{A}_n \to \mathcal{A}_n$ by:

$$ \rho_i(\pi) = \begin{cases} \pi\sigma_{i+1}, & \text{if } \pi\sigma_{i+1} \in \mathcal{A}_n; \\ \pi, & \text{otherwise.} \end{cases} $$

**Proposition 6.2** The maps $\rho_i$, $0 \le i \le n-2$, when extended multiplicatively, determine a well-defined transitive $\tilde{C}_{n-2}$-action on the set of arc permutations $\mathcal{A}_n$.

**Remark 6.3** The subset of left-unimodal permutations $\mathcal{L}_n$ is invariant under the restriction of the above $\tilde{C}_{n-2}$-action to the maximal parabolic subgroup $W_J$, where $J := S \setminus \{s_{n-2}\} = \{s_0, s_1, \dots, s_{n-3}\}$.

Recall that the parabolic subgroup $W_J$ is isomorphic to the hyperoctahedral group $B_{n-2}$.

**Proposition 6.4** The maps $\rho_i$, $0 \le i < n-2$, when extended multiplicatively, determine a well-defined $B_{n-2}$-action on the set of left-unimodal permutations $\mathcal{L}_n$. The orbits are $\{\pi \in \mathcal{L}_n : \pi(n) = k\}$, $1 \le k \le n$, and the action on each of these orbits is multiplicity-free.

## 6.2 A graph structure on arc permutations

Let $X_n$ be the subgraph of the Cayley graph $X(S_n, S)$ induced by $\mathcal{A}_n$. In other words, $X_n$ is the graph whose vertex set is $\mathcal{A}_n$; two elements $u, v \in \mathcal{A}_n$ are adjacent if and only if there exists a simple reflection $\sigma_i \in S$, such that $u = v\sigma_i$.

**Lemma 6.5** A permutation in $\mathcal{A}_n$ lies in a geodesic in $X_n$ between $e$ and $w_0$ if and only if it is unimodal.

The following theorem shows that $X_n$ and $\Gamma_n$ share similar properties.

**Theorem 6.6** (i) The diameter of $X_n$ is $\binom{n}{2}$.

(ii) The vertices $e$ and $w_0$ are antipodes in $X_n$.

(iii) The number of vertices in geodesics between $e$ and $w_0$ is $2^n - 2$.

(iv) The number of geodesics between these antipodes is $2\binom{n}{2}! \cdot \prod_{i=0}^{n-2} \frac{i!}{(2i+1)!}$.

**Proof sketch:** First, observe that the graph $X_n$ is isomorphic (up to loops) to the Schreier graph determined by the $\tilde{C}_{n-2}$-action on $\mathcal{A}_n$. One can then show that this Schreier graph is a quotient of a certain interval in the weak order on $\tilde{C}_{n-2}$, which is a modular lattice. By similar arguments to those given in [1], it is then proved that the diameter is $\binom{n}{2}$. Clearly, the distance between $e$ and $w_0$ is not less than $\binom{n}{2}$, thus (ii) follows from (i). To prove (iii) and (iv) one applies Lemma 6.5 and Corollaries 3.5 and 5.5. $\square$

## 7 Equidistribution

In this section we show that the descent set is equidistributed on arc permutations that are not unimodal and on the set of standard Young tableaux obtained from hooks by adding one box in position (2, 2). Recall that these sets are denoted by $\mathcal{Z}_n$ and $\mathcal{T}_n$, respectively.
## 7.1 Non-unimodal arc permutations

For a set $D = \{i_1, \dots, i_k\}$, define $\mathbf{x}^D = x_{i_1} \dots x_{i_k}$.

**Theorem 7.1** For $n \ge 4$,

$$ \sum_{\pi \in \mathcal{Z}_n} \mathbf{x}^{\mathrm{Des}(\pi)} = \sum_{T \in \mathcal{T}_n} \mathbf{x}^{\mathrm{Des}(T)}. $$

**Proof:** We describe a bijection $\phi$ between $\mathcal{Z}_n$ and $\mathcal{T}_n$ that preserves the descent set. Let $\pi \in \mathcal{Z}_n$.

If $\pi^{-1}(1) > \pi^{-1}(n)$, let $j = \pi^{-1}(1)$, and let

$$ A = \{i : \pi(i) \ge \pi(1)\} \cup \{i : i > j + 1 \text{ and } \pi(i-1) < \pi(n)\}. $$

Then $\phi(\pi) \in \mathcal{T}_n$ is the tableau having the elements of $A$ in the first row, having $j + 1$ in the box in the second row and column, and having the rest of the elements in $[n]$ in the first column.

If $\pi^{-1}(1) < \pi^{-1}(n)$, let $j = \pi^{-1}(n)$, and let

$$ A = \{i : \pi(i) \le \pi(1)\} \cup \{i : i > j + 1 \text{ and } \pi(i-1) > \pi(n)\}. $$

Then $\phi(\pi) \in \mathcal{T}_n$ is the tableau having the elements of $A$ in the first column, having $j + 1$ in the box in the second row and column, and having the rest of the elements in $[n]$ in the first row. $\square$

**Example:** If

$$ \pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 8 & 9 & 10 & 7 & 11 & 1 & 2 & 6 & 5 & 3 & 4 \end{pmatrix} $$

in two-line notation, then $j = 6 = \pi^{-1}(1) > \pi^{-1}(n) = 5$, $A = \{1, 2, 3, 5, 8, 11\}$, and $\phi(\pi)$ is the tableau

<table><tr><td>1</td><td>2</td><td>3</td><td>5</td><td>8</td><td>11</td></tr><tr><td>4</td><td>7</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>6</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>9</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>10</td><td></td><td></td><td></td><td></td></tr></table>

Letting $q = 1$ in Theorem 7.1 we obtain the following.

**Corollary 7.2** For $n \ge 4$,

$$ |\mathcal{Z}_n| = \sum_{k=2}^{n-2} f^{(k,2,1^{n-k-2})}. $$

A direct proof of Corollary 7.2 can also be given as follows. Using that $|\mathcal{U}_n| = 2^n - 2$ and $|\mathcal{A}_n| = n2^{n-2}$, we have

$$ |\mathcal{Z}_n| = n2^{n-2} - 2^n + 2 = 2^{n-2}(n-4) + 2. $$

On the other hand, using the hook-length formula, we obtain

$$ \sum_{k=2}^{n-2} f^{(k,2,1^{n-k-2})} = \sum_{k=2}^{n-2} \frac{(k-1)(n-k-1)}{n-1} \binom{n}{k} = 2^{n-2}(n-4) + 2, $$

where the last step follows from easy manipulations of binomial coefficients. $\square$

We now provide another equidistribution result related to Theorem 7.1.
**Definition 7.3** For $\pi \in \mathcal{A}_n$, let $C(\pi)$ be the set of values $i \in \{3, 4, \dots, n\}$ such that in $\mathbb{Z}_n$, $\pi(i-1) - 1$ belongs to the interval $\{\pi(1), \pi(2), \dots, \pi(i-2)\}$.

**Definition 7.4** For a standard Young tableau $T$ of size $n$ and an integer $1 \le i \le n$, let $B_{\ge i}(T)$ be the subset of entries in $T$ that are weakly north and strictly east of $i$.

We have also found a different bijection between $\mathcal{Z}_n$ and $\mathcal{T}_n$ that proves the following.

**Proposition 7.5** For $n \ge 4$,

$$ \sum_{\pi \in \mathcal{Z}_n} \mathbf{x}^{C(\pi)} = \sum_{T \in \mathcal{T}_n} \mathbf{x}^{B_{\ge 2}(T)}. $$

## 7.2 Enumeration of arc permutations by descent set

Here we enumerate arc permutations and non-unimodal arc permutations according to their descent set.

**Proposition 7.6** For $n \ge 2$,

$$ \sum_{\pi \in \mathcal{A}_n} \mathbf{x}^{\mathrm{Des}(\pi)} = (1+x_1)\dots(1+x_{n-1}) \left( 1 + \sum_{i=1}^{n-2} \frac{x_i + x_{i+1}}{(1+x_i)(1+x_{i+1})} \right), \\ \sum_{\pi \in \mathcal{Z}_n} \mathbf{x}^{\mathrm{Des}(\pi)} = \sum_{\pi \in \mathcal{A}_n} \mathbf{x}^{\mathrm{Des}(\pi)} - 2(1+x_1)\dots(1+x_{n-1}) + 1 + x_1\dots x_{n-1}. $$

**Corollary 7.7** Let $\mathrm{maj}(\pi)$ denote the major index of $\pi$. For $n \ge 2$,

$$ \sum_{\pi \in \mathcal{A}_n} q^{\mathrm{maj}(\pi)} = (1+q)\dots(1+q^{n-2})[n]_q, \\ \sum_{\pi \in \mathcal{Z}_n} q^{\mathrm{maj}(\pi)} = (1+q)\dots(1+q^{n-2})[n]_q - 2(1+q)\dots(1+q^{n-1}) + 1 + q^{\binom{n}{2}}. $$

## 7.3 Representation-theoretic proof

The sets $\mathcal{L}_n$ and $\mathcal{U}_n$ are unions of Knuth classes, hence they carry the associated symmetric group representation. As noted above, the set $\mathcal{Z}_n$ of non-unimodal arc permutations is not a union of Knuth classes. However, by Corollary 7.2, its size is equal to the number of standard Young tableaux of hook shape plus one box. Here we present a short representation-theoretic proof of Corollary 7.2.

Consider the natural action of the symmetric group $S_{n-1}$ on an $n-1$-dimensional space $V$. The exterior algebra $\wedge V$ is equivalent as an $S_{n-1}$-module to a direct sum of all Specht modules indexed by hooks, see e.g. [7, Ex. 4.6]. By the branching rule, the decomposition of the induced exterior algebra $\wedge V \uparrow^{S_n}$ into irreducibles is then given by

$$ \chi^{(n)} + \chi^{(1^n)} + 2 \sum_{k=2}^{n-1} \chi^{(k,1^{n-k})} + \sum_{k=2}^{n-2} \chi^{(k,2,1^{n-k-2})}. $$

Hence

$$ f^{(n)} + f^{(1^n)} + 2 \sum_{k=2}^{n-1} f^{(k,1^{n-k})} + \sum_{k=2}^{n-2} f^{(k,2,1^{n-k-2})} = \dim \wedge V \uparrow^{S_n} = n \cdot \dim \wedge V = n 2^{n-2} = |\mathcal{A}_n|. $$
On the other hand, by Remark 2.4, $|\mathcal{U}_n| = f^{(n)} + f^{(1^n)} + 2 \sum_{k=2}^{n-1} f^{(k, 1^{n-k})}$. Since $\mathcal{U}_n \subseteq \mathcal{A}_n$, one concludes

$$|\mathcal{Z}_n| = |\mathcal{A}_n \setminus \mathcal{U}_n| = \sum_{k=2}^{n-2} f^{(k, 2, 1^{n-k-2})},$$

completing the proof.

A representation-theoretic explanation of Theorem 7.1 and Proposition 7.5 is desired.

# 8 Shuffles

The purpose of this final section is to point out that permutations obtained as shuffles of two increasing sequences share many properties with the above families of permutations.

Similarly to the partial fillings of the shifted staircase in Section 4, we will now consider partial fillings of a $k \times m$ rectangle with rows labeled $k, \dots, 2, 1$ from top to bottom, and columns labeled $k+1, k+2, \dots, k+m$ from left to right. Again, to each of the entries $\ell$ in the partial filling, if $\ell$ lies in row $i$ and column $j$, we associate the transposition $(i, j)$. The product of these transpositions gives a permutation, and the set of permutations obtained in this way is denoted by $\mathcal{F}_{k,m}$.

It is easy to see that $\mathcal{F}_{k,m}$ is also the set of permutations $\pi \in S_{m+k}$ which are a shuffle of the two sequences $1, 2, \dots, k$ and $k+1, k+2, \dots, k+m$ (that is, both appear as subsequences of $\pi$ from left to right). As is the case for $\mathcal{L}_n$, $\mathcal{U}_n$ and $\mathcal{A}_n$, the set $\bar{\mathcal{F}}_n = \bigcup_{k+m=n} \mathcal{F}_{k,m}$ can be characterized in terms of pattern avoidance.

**Proposition 8.1** $\bar{\mathcal{F}}_n = S_n(321, 2143, 2413)$.

Shuffles can be easily enumerated, obtaining that $|S_n(321, 2143, 2413)| = |\bar{\mathcal{F}}_n| = 2^n - n$ for $n \ge 2$.

As in Section 3, it is also the case here that shuffles are a grid class, consisting of those permutations that can be drawn in the shape in Fig. 5, so we have $\bar{\mathcal{F}}_n = \mathcal{G}_n \begin{pmatrix} 1 \\ 1 \end{pmatrix}$.

<figure><img src="image_5.png" /><figcaption>**Fig. 5:** Grid for shuffles.</figcaption></figure>

Shuffles can be characterized as those permutations $\pi$ with $\mathrm{Des}(\pi^{-1}) = \{k\}$ for some $k$. For $\pi \in \bar{\mathcal{F}}_n$, if $\mathrm{RSK}(\pi) = (P, Q)$, then $P$ is a two-row tableau with consecutive entries $k+1, k+2, \dots, k+\ell$ in the second row, and $Q$ is any two-row tableau with the same shape as $P$. It follows that shuffles are a union of Knuth classes.

Let $\mathrm{Weak}(\bar{\mathcal{F}}_n)$ be the subposet of $\mathrm{Weak}(S_n)$ induced by the subset $\bar{\mathcal{F}}_n = S_n(321, 2143, 2413)$. The following result follows from arguments analogous to the ones used in Section 5.
**Corollary 8.2** The poset Weak($\bar{F}_n$) has the following properties.

1. The local maxima are exactly the permutations $\pi_k := (k+1)(k+2)\dots n!$ for some $k$.

2. A permutation is in the interval $[e, \pi_k]$ if and only if it belongs to $\mathcal{F}_{k,n-k}$; hence, the number of elements in this interval is $\binom{n}{k}$.

3. The number of maximal chains in $[e, \pi_k]$ is equal to the number of standard Young tableaux of rectangular shape $k \times (n-k)$.

**References**

[1] R.M. Adin, M. Firer and Y. Roichman, Triangle-free triangulations, *Adv. in Appl. Math.* 45 (2010), no. 1, 77–95.

[2] R.M. Adin and Y. Roichman, Triangle-free triangulations, hyperplane arrangements and shifted tableaux, arXiv:1009.2628.

[3] R.M. Adin, A. Postnikov and Y. Roichman, Combinatorial Gelfand models, *J. Algebra* 320 (2008), no. 3, 1311–1325.

[4] M.H. Albert, M.D. Atkinson, M. Bouvel, N. Ruskuc and V. Vatter, Geometric grid classes of permutations, arXiv:1108.6319.

[5] A. Björner and F. Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005.

[6] S. Elizalde, Y. Roichman, Arc permutations, preprint.

[7] W. Fulton and J. Harris, Representation theory. A first course. Graduate Texts in Mathematics, 129. Readings in Mathematics. Springer-Verlag, New York, 1991.

[8] I.G. Macdonald, Symmetric Functions and Hall Polynomials, second ed., Oxford Math. Monographs, Oxford Univ. Press, Oxford, 1995.

[9] M.M. Murphy and V. Vatter, Profile classes and partial well-order for permutations, *Electron. J. Combin.* 9 (2003), Research paper 17, 30 pp.

[10] G. Panova, Truncated tableaux and plane partitions, arXiv:1011.0795.

[11] Y. Roichman, On permutation statistics and Hecke algebra characters, *Combinatorial methods in representation theory* (Kyoto, 1998), 287–304, Adv. Stud. Pure Math., 28, Kinokuniya, Tokyo, 2000.

[12] I. Schur, On the representation of the symmetric and alternating groups by fractional linear substitutions, Translated from the German [J. Reine Angew. Math. 139 (1911), 155–250] by Marc-Felix Otto. *Internat. J. Theoret. Phys.* 40 (2001), 413–458.

[13] R.P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, *European J. Combin.* 5 (1984), no. 4, 359–372.