# Enumeration of permutations sorted with two passes through a stack and $D_8$ symmetries

Mathilde Bouvel$^{1,2}$ and Olivier Guibert$^1$

$^1$LaBRI UMR 5800, Univ. Bordeaux and CNRS, Talence, France.

$^2$partially supported by ANR grants PSYCO (ANR 2011-JS02-001) and MAGNUM (ANR 2010-BLAN-0204)

**Abstract.** We examine the sets of permutations that are sorted by two passes through a stack with a $D_8$ operation performed in between. From a characterization of these in terms of generalized excluded patterns, we prove two conjectures on their enumeration, that can be refined with the distribution of some statistics. The results are obtained by generating trees.

**Résumé.** On étudie les ensembles de permutations qui sont triées par deux passages dans une pile séparés par une opération du groupe $D_8$. À partir d'une caractérisation de ces ensembles en termes de motifs exclus généralisés, on démontre deux conjectures sur leur énumération, qui peuvent être raffinées par la distribution de certaines statistiques. Ces résultats sont obtenus à l'aide d'arbres de génération.

**Keywords:** permutations, generalized patterns, stack sorting, symmetries of the square, Baxter permutations, generating trees

# 1 Introduction

## 1.1 Permutations, diagrams and patterns

A permutation of $S_n$ is a bijective map from $\{1, 2, \dots, n\}$ to itself, $n$ being called the *size* of the permutation. In our context, we will view permutations in two different ways. A permutation $\sigma$ of $S_n$ can be seen as a word $\sigma_1\sigma_2\dots\sigma_n$ where $\sigma_i = \sigma(i)$ for all $i \in \{1, \dots, n\}$, containing exactly once each letter from 1 to $n$. It can also be seen as what we call its *diagram*: an $n \times n$ grid with exactly one dot per row and per column, the dots being placed in cells of coordinates $(i, \sigma(i))$. For every element of a permutation $\sigma$, corresponding to the dot at coordinates $(i, \sigma(i))$ in its diagram, we call it its *index* and $\sigma(i)$ its *value*.

Recall that for $\sigma \in S_n$, its *reverse* (resp. *complement*, resp. *inverse*) is the permutation $r(\sigma)$ (resp. $c(\sigma)$, resp. $i(\sigma)$) defined by $r(\sigma)(i) = \sigma(n+1-i)$ (resp. $c(\sigma)(i) = n+1-\sigma(i)$, resp. $i(\sigma)(i) = j$ such that $\sigma(j) = i$). These operations correspond respectively to symmetries w.r.t. a vertical axis, a horizontal axis and the south-west to north-east diagonal on the diagrams of the permutations (see Figure 1). Hence, these three operations generate the eight element group $D_8$ of the symmetries of the square.

From the word representation of permutations, we inherit basic concepts like word concatenation, or subwords. A subword (with $k$ letters) of a permutation is however not a permutation in general, as its
<figure><img src="image_1.png" /><figcaption>Fig. 1: The diagram of permutation $\sigma = 416253$, and its symmetries under $r, c$ and $i$.</figcaption></figure>

letters may not consist of all integers of $\{1, 2, \dots, k\}$. Each subword of a permutation $\sigma$ can be *nor- malized* to a permutation, that is then called a (classical) *pattern* of $\sigma$. More precisely, a permutation $\pi = \pi_1\pi_2 \dots \pi_k$ is a (classical) *pattern* of a permutation $\sigma = \sigma_1\sigma_2\dots\sigma_n$ if and only if there exist inte- gers $1 \le i_1 < i_2 < \dots < i_k \le n$ such that $\sigma_{i_1} \dots \sigma_{i_k}$ is order-isomorphic to $\pi$, i.e. such that $\sigma_{i_\ell} < \sigma_{i_m}$ whenever $\pi_\ell < \pi_m$. The subsequence $\sigma_{i_1} \dots \sigma_{i_k}$ is called an *occurrence* of $\pi$ in $\sigma$. A permutation $\sigma$ that does not contain $\pi$ as a pattern is said to *avoid* $\pi$.

Some generalizations of permutation patterns are frequent in the literature, and we will make use of two of them here. When introducing dashes in a pattern $\pi$, we impose adjacency constraints on the elements $\sigma_{i_\ell}$ of $\sigma$ that form an occurrence of $\pi$. Namely, a permutation $\pi = \pi_1\pi_2\dots\pi_k$ with dashes between some pairs $\pi_\ell\pi_{\ell+1}$ is a *dashed pattern* of a permutation $\sigma = \sigma_1\sigma_2\dots\sigma_n$ if and only if there exist integers $1 \le i_1 < i_2 < \dots < i_k \le n$ such that $\sigma_{i_1} \dots \sigma_{i_k}$ is order-isomorphic to $\pi$ and $i_{\ell+1} = i_\ell + 1$ whenever there is no dash between $\pi_\ell$ and $\pi_{\ell+1}$ in $\pi$. Notice that classical patterns can be viewed as dashed patterns with dashes between $\pi_\ell$ and $\pi_{\ell+1}$ for any $\ell \in \{1, \dots, n-1\}$, and that a dashed pattern with no dash corresponds to a normalized *factor* of the permutation. However, in this article, we take the convention that a pattern written with no dash is always a classical pattern. Pattern avoidance of dashed patterns is defined as in the classical case.

The other generalization of pattern avoidance we consider is the one of patterns with one barred element (or barred patterns for short). Consider a permutation $\pi$ with one barred element, and denote by $\pi \sim$ the normalization of the subword of $\pi$ obtained when deleting the barred element. We say that a permutation $\sigma$ *contains* the *barred pattern* $\pi$ if there exists a (classical) occurrence of $\pi \sim$ in $\sigma$ that cannot be extended into a (classical) occurrence of $\pi$ in $\sigma$. Consequently, a permutation $\sigma$ *avoids* the barred pattern $\pi$ if every occurrence of $\pi \sim$ in $\sigma$ can be extended into an occurrence of $\pi$ in $\sigma$.

We denote by $Av(\pi', \pi'', \dots, \pi''')$ the set of permutations that simultaneously avoid $\pi', \pi'', \dots$ and $\pi''''$.

**Example 1.1** Permutation $\sigma = 316452$ avoids the classical pattern 2413 but contains the classical pat- tern $\pi = 2431$, and the subwords 3642 and 3652 are its two occurrences in $\sigma$. Furthermore $\sigma$ avoids 24-3-1 as a dashed pattern, as the elements corresponding to 2 and 4 are never at consecutive indices in an occurrence of $\pi$ in $\sigma$. Finally, $\sigma$ avoids the barred pattern $\tau = 31542$ as all the occurrences of $\tau \sim = \pi$ can be extended with a smallest element to account for $\bar{1}$.
## 1.2 Some sorting operators on permutations

Barred patterns have been introduced for characterizing the permutations that can be sorted by two passes of the stack sorting operator $\mathbf{S}$ in [West(1993)] (see Theorem 1.2 below). We say that a permutation $\sigma \in \mathfrak{S}_n$ is sorted by an operator $\mathbf{Sort}$ when $\mathbf{Sort}(\sigma) = 12...n$.

The operation of sorting a permutation $\sigma = \sigma_1...\sigma_n$ through a stack is defined as follows. Consider a stack that satisfies the Hanoi condition, i.e. such that the elements in the stack are in increasing order from the top to the bottom of the stack. Starting from $w = \sigma_1...\sigma_n$ and an empty stack, either put the first letter of $w$ on the stack (if this respects the Hanoi condition), or otherwise pop the element at the top of the stack. When $w$ and the stack are empty, a permutation has been output, which is the result of the stack sorting of $\sigma$. More formally, the stack sorting operator is also classically characterized recursively by $\mathbf{S}(\varepsilon) = \varepsilon$ and $\mathbf{S}(LnR) = \mathbf{S}(L)\mathbf{S}(R)n$ where $n$ is the maximum of the word $LnR$ of distinct integers (which is not necessarily a permutation) and $\varepsilon$ denotes the empty word. Other sorting operators on permutations have been studied in the literature, in connexion with permutation patterns. This is the case in [Claesson et al.(2007)] for the tack sorting operator $\mathbf{T}$ defined by $\mathbf{T}(\varepsilon) = \varepsilon$ and $\mathbf{T}(LnR) = \mathbf{T}(R)\mathbf{T}(L)n$ or in [Albert et al.(2011)] for the bubble sort operator $\mathbf{B}$ defined by $\mathbf{B}(\varepsilon) = \varepsilon$ and $\mathbf{B}(LnR) = \mathbf{B}(L)Rn$.

The tack sorting operator can be easily characterized by the identity $\mathbf{T}(\sigma) = \mathbf{S}(\mathbf{r}(\sigma))$ for every permutation $\sigma$. Therefore, the compositions of these two sorting operators can be interpreted as $\mathbf{S} \circ \mathbf{T} = \mathbf{S} \circ \mathbf{S} \circ \mathbf{r}$ and $\mathbf{T} \circ \mathbf{S} = \mathbf{S} \circ \mathbf{r} \circ \mathbf{S}$. Similarly, $\mathbf{T} \circ \mathbf{T} = \mathbf{S} \circ \mathbf{r} \circ \mathbf{S} \circ \mathbf{r}$. Hence, following the line of [West(1993)] and looking for a characterization of the permutations that are sorted by these compositions of sorting operators, we are lead to the analysis of the permutations that are sorted by $\mathbf{S} \circ \mathbf{r} \circ \mathbf{S}$. We actually address a rather more general question here: we characterize and enumerate permutations that are sorted by $\mathbf{S} \circ \alpha \circ \mathbf{S}$ for any $\alpha$ in the group $D_8$.

## 1.3 Permutations sorted by the composition of two sorting operators

For any sorting operator $\mathbf{Sort}$, let us denote by $\mathrm{Id}(\mathbf{Sort})$ the set of permutations that are sorted by $\mathbf{Sort}$, i.e. $\mathrm{Id}(\mathbf{Sort}) = \cup_n\{\sigma \in \mathfrak{S}_n : \mathbf{Sort}(\sigma) = 12...n\}$. It has been known since [Knuth(1973)] that $\mathrm{Id}(\mathbf{S}) = \mathrm{Av}(231)$, and [West(1993)] has proved that $\mathrm{Id}(\mathbf{S} \circ \mathbf{S}) = \mathrm{Av}(2341, 3\bar{5}241)$. Theorem 1.2 below has been proved by [Albert et al.(2010)].

**Theorem 1.2** *The sets of permutations that are sorted by $S \circ \alpha \circ S$, for any $\alpha$ in $D_8$ are characterized by:*

$$ (i) \mathrm{Id}(\mathbf{S} \circ \mathbf{S}) = \mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{c} \circ \mathbf{r} \circ \mathbf{S}) = \mathrm{Av}(2341, 3\bar{5}241); $$

$$ (ii) \mathrm{Id}(\mathbf{S} \circ \mathbf{c} \circ \mathbf{S}) = \mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{r} \circ \mathbf{S}) = \mathrm{Av}(231); $$

$$ (iii) \mathrm{Id}(\mathbf{S} \circ \mathbf{r} \circ \mathbf{S}) = \mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{c} \circ \mathbf{S}) = \mathrm{Av}(1342, 314-2) = \mathrm{Av}(1342, 3\bar{5}142); $$

$$ (iv) \mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S}) = \mathrm{Id}(\mathbf{S} \circ \mathbf{r} \circ \mathbf{c} \circ \mathbf{S}) = \mathrm{Av}(3412, 34-21). $$

A natural question is then to look at the enumeration sequences $(c_n)$ of the sets $\mathcal{C}$ of pattern avoiding permutations that appear in Theorem 1.2. Of course, the set $\mathrm{Av}(231)$ (which corresponds to one-stack sortable permutations) is enumerated by the Catalan numbers $\mathrm{Cat}_n = \frac{1}{n+1}\binom{2n}{n}$ (see [Knuth(1973)]); and [Dulucq et al.(1998)] proved that the set $\mathrm{Av}(2341, 3\bar{5}241)$ of two-stack sortable permutations is enumerated by $\frac{2(3n)!}{(n+1)!(2n+1)!}$. For the two other sets, conjectures on their enumeration have been proposed by [Claesson et al.(2007)], and refined with the distribution of some statistics. These conjectures are
stated as Theorems 1.3 and 1.4 and Conjecture 1.5 below. Theorems 1.3 and 1.4 are proved in the rest of this article, and the proof of Conjecture 1.5 is a work in progress.

**Theorem 1.3** The two sets $\text{Id}(\mathbf{S} \circ \mathbf{S})$ and $\text{Id}(\mathbf{S} \circ \mathbf{r} \circ \mathbf{S})$ are enumerated according to the size of the permutations by the same sequence. Moreover, the 15-tuple of statistics (des, maj, rmax, lmax, valley, peak, ddes, dasc, zeil, indmax, rir, rdr, lir, ldr, slmax) has the same distribution on both sets.

**Theorem 1.4** The set $\text{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$ is enumerated by the Baxter numbers.

**Conjecture 1.5** The triple of statistics (des, lmax, comp) has the same distribution on $\text{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$ and on the set of Baxter permutations.

The definitions of the statistics of Theorem 1.3 and Conjecture 1.5 are briefly recalled in Table 1. More detailed definitions can be found in [Claesson and Kitaev(2008)] for instance.

<table><caption>**Tab. 1:** Some classical statistics on permutations.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>des</td><td>Number of descents</td></tr><tr><td>maj</td><td>Major index, i.e. sum of the indices of the descents</td></tr><tr><td>comp</td><td>Number of components<br>Largest k such that π can be written as the concatenation π = α<sub>1</sub> ... α<sub>k</sub><br>with for all i < j, for all a<sub>i</sub> ∈ α<sub>i</sub> and a<sub>j</sub> ∈ α<sub>j</sub>, a<sub>i</sub> < a<sub>j</sub>.<br>The segments α<sub>i</sub> are called the components of π.</td></tr><tr><td>rmax, rmin, lmax, lmin</td><td>Number of right-to-left (resp. left-to-right) maxima (resp. minima)</td></tr><tr><td>valley, peak, ddes, dasc</td><td>Number of valleys (resp. peaks, double descents, double ascents)</td></tr><tr><td>rir, rdr, lir, ldr</td><td>Length of the rightmost (resp. leftmost) increasing (resp. decreasing) run</td></tr><tr><td>indmax</td><td>Index of the maximal element</td></tr><tr><td>zeil</td><td>Largest k such that n(n − 1) ... (n − k + 1) is a subword of π with n = |π|</td></tr><tr><td>slmax</td><td>Largest k such that π<sub>1</sub> ≥ π<sub>i</sub> for all i ∈ [1..k]</td></tr></tbody></table>

The set $Bax$ of Baxter permutations has been first defined in [Baxter(1964)] and can be characterized by excluded dashed patterns as $Bax = Av(2-41-3, 3-14-2)$ (see [Ouchterlony(2005)] for example). In this article, we take this as the definition of Baxter permutations. The Baxter numbers $(b_n)$ enumerate the set of Baxter permutations, and we have $b_n = \frac{2}{n(n+1)^2} \sum_{k=1}^{n} \binom{n+1}{k-1} \binom{n+1}{k} \binom{n+1}{k+1}$ (see [Chung et al.(1978)]).

Theorems 1.3 and 1.4 are proved using generating trees, and we recall the guidelines of this method in Section 2. Theorem 1.3 is then proved in Section 3. Section 4 proves the enumerative result of Theorem 1.4 by establishing a bijective correspondence (via a generating tree) between $\text{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$ and $Av(2-14-3, 2-41-3)$, this set being enumerated by the Baxter numbers (see [Guibert(1995)] or more recently [Giraudo(2011)]). But this does not allow to follow the three statistics (des, lmax, comp) of Conjecture 1.5 directly. Going into further details of the bijection described by [Giraudo(2011)] and examining how the statistics are transformed by this bijection is a promising path to a proof of Conjecture 1.5.

## 2 Rewriting systems and generating trees

*Generating trees* have been first introduced by [West(1995)] in the context of pattern avoiding permutations. [Barcucci et al.(1999)] have extended the definition of generating trees to other combinatorial
objects, as well as formalized it by means of the *ECO-method*. Here, we only recall some basics on generating trees and rewriting systems, before we apply this method in the proofs of Theorems 1.3 and 1.4.

## 2.1 Generating trees

A *generating tree* is an infinite rooted tree associated to a set $\mathcal{C}$ of permutations, whose vertices are permutations. The root is the permutation $1 \in \mathcal{C}$, and permutations at distance $n-1$ from the root are exactly the permutations of size $n$ in $\mathcal{C}$, whose set is denoted by $C_n$.

There are several possible definitions of the edges of a generating tree. The four usual ones are as follow: the parent of a permutation $\pi \in C_n$ is the permutation of $C_{n-1}$ obtained from $\pi$ by removing the largest (resp. smallest, rightmost, leftmost) element of the permutation, and normalizing. This obviously defines uniquely the parent of a permutation $\pi \neq 1$. Of course, depending on $\mathcal{C}$ and on the operation of removing and normalizing that is chosen, it may result in a permutation that does not belong to $\mathcal{C}$. This is never the case when $\mathcal{C}$ is a pattern class, i.e. when the excluded patterns are classical patterns, but it may happen when the excluded patterns are generalized patterns. In the case of barred patterns, the situations in which it does not happen have been characterized in [Dulucq et al. (1998), Prop. 6].

The above describes the way a parent is obtained from any of its children in the generating tree. In order to build the tree efficiently from its root, it is certainly more convenient to describe instead how the children of a permutation $\pi$ are built from $\pi$. There are of course four possible *insertion rules* corresponding to the four possibilities of removing an element that have been described earlier. For each insertion rule, we define the *sites* of a permutation $\pi \in \mathcal{C}$ to be the places in which a new element may be inserted, resulting in a permutation $\pi'$. The locations of these sites that are described below are intended with respect to the diagram that represents permutation $\pi$. A site is said *active* when $\pi' \in \mathcal{C}$.

**Insertion rule Largest** The sites of a permutation $\pi \in C_n$ are above $\pi$, and are located at the beginning, at the end and between any two consecutive indices $i$ and $i+1$ of $\pi$. The children of $\pi$ are the permutations of $C_{n+1}$ obtained when inserting a largest element in an active site of $\pi$.

**Insertion rule Smallest** The sites of a permutation $\pi \in C_n$ are below $\pi$, and are located at the beginning, at the end and between any two consecutive indices $i$ and $i+1$ of $\pi$. The children of $\pi$ are the permutations of $C_{n+1}$ obtained when inserting a smallest element in an active site of $\pi$.

**Insertion rule Rightmost** The sites of a permutation $\pi \in C_n$ are to the right of $\pi$, and are located below, above and between any two consecutive values $i$ and $i+1$ of $\pi$. The children of $\pi$ are the permutations of $C_{n+1}$ obtained when inserting a rightmost element in an active site of $\pi$.

**Insertion rule Leftmost** The sites of a permutation $\pi \in C_n$ are to the left of $\pi$, and are located below, above and between any two consecutive values $i$ and $i+1$ of $\pi$. The children of $\pi$ are the permutations of $C_{n+1}$ obtained when inserting a leftmost element in an active site of $\pi$.

Notice that each of the four insertion rules corresponds to adding a new element on one of the four sides of the square around the diagram that represent the permutation (see Figure 2).

## 2.2 Rewriting system

The shape of a generating tree associated to a set $\mathcal{C}$ of permutations contains information, even without the permutations labeling the vertices, in particular for enumeration. Indeed, even when considering a generating tree where the permutations labeling the vertices have been erased, we still have a bijection between the vertices of this infinite tree and the permutations of $\mathcal{C}$, which maps the size of a permutation to the level a vertex in the tree (the level denoting the distance to the root +1 here).
<figure><img src="image_2.png" /><figcaption>**Fig. 2:** The sites corresponding to each insertion rule, on the diagram representation of permutation $\pi = 3241$, and the permutations resulting from the four insertion rules.</figcaption></figure>

Rewriting systems are a way to describe the shape of a generating tree without the need of labeling each vertex by a permutation. Instead, we can label the vertices of the tree by tuples -that are called *labels*-, in such a way that the label of each vertex contains enough information on the corresponding permutation $\pi$ to build the labels of all the children of $\pi$. In general, these tuples indicate the values of some statistics on $\pi$, such as the size, the number of active sites, ... The shape of the tree is then completely described by a rewriting system on the labels, that encapsulate the parent-child relation on the permutations.

Such a rewriting system consists of a starting point $\ell_0$ (the label of permutation 1) and a set of rewriting rules of the form $\ell \rightsquigarrow L$ with $L = \{\ell_a, \dots, \ell_p\}$, that describe the labels $\ell_a, \dots, \ell_p$ of the children of a permutation whose label is $\ell$. Therefore, there is a bijection between permutations of size $n$ in $C$ and sequences of labels $(\ell_0, \ell_1, \ell_2, \dots, \ell_{n-1})$ such that for any $i$, there is a rewriting rule $\ell_i \rightsquigarrow L_i$ in the system such that $\ell_{i+1} \in L_i$. Consequently, when the same rewriting system is obtained for two sets $C$ and $D$ of permutations, this implies that there is a bijection between $C$ and $D$, that preserves the size of the permutation. Notice that it is also possible to enrich the labels of the vertices to take into account the value of one or more statistics on the corresponding permutations. In the case there is a common rewriting system for $C$ and $D$ where the labels take into account statistics $(s_1, \dots, s_k)$ in $C$ and $(r_1, \dots, r_k)$ in $D$, then these statistics are equidistributed. Section 3 and 4 provide examples of this use of generating trees.
# 3 Permutations sorted by $S \circ r \circ S$

## 3.1 A simple rewriting system

We prove that $\mathrm{Id}(S \circ r \circ S)$ is enumerated by the same sequence than $\mathrm{Id}(S \circ S)$, by describing a generating tree that is common for $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$. This tree is in fact identical to the common generating tree for $\mathrm{Av}(3214, \bar{2}4135)$ and $\mathrm{Av}(3241, \bar{2}4153)$ given in [Dulucq et al. (1998)]. Indeed, we have the following correspondence:

**Proposition 3.1** *The $c \circ i$ operation provides a bijection between $\mathrm{Id}(S \circ S)$ (resp. $\mathrm{Id}(S \circ r \circ S)$) and $\mathrm{Av}(3214, \bar{2}4135)$ (resp. $\mathrm{Av}(3241, \bar{2}4153)$).*

Because of the $c \circ i$ transformation, the insertion rule *Largest* that was used in the generating tree of [Dulucq et al. (1998)] is naturally transformed into the insertion rule *Rightmost* in the generating tree for $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$. This incremental construction of permutations where active sites are on the right is also known in the literature under the name of *staff representation* of permutations (see [Bernini et al. (2005)] for example). Furthermore, for the same reason, the sites on the right for $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$ are numbered from top to bottom, so that it mimics the numbering from left to right for $\mathrm{Av}(3214, \bar{2}4135)$ and $\mathrm{Av}(3241, \bar{2}4153)$.

**Theorem 3.2** *The generating trees for both $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$ with the insertion rule *Rightmost* are characterized by the following rewriting system*

$$ \mathcal{R}_{\Phi} \left\{ \begin{array}{ll} (2, 1, (1)) & \rightsquigarrow (2 + p_j, j, (p_1, \dots, p_{j-1}, i)) & \text{for } 1 \le j \le k \text{ and } p_{j-1} < i \le p_j \\ (x, k, (p_1, \dots, p_k)) & \rightsquigarrow (x + 1, k + 1, (p_1, \dots, p_k, i)) & \text{for } p_k < i \le x \end{array} \right. $$

where in the label $(x, k, (p_1, \dots, p_k))$ of a permutation $\pi$, $x$ denotes the number of active sites of $\pi$, $k$ is the number of right-to-left maxima in $\pi$, and $p_\ell$ denotes the number of active sites above the $\ell$-th right-to-left maximum in $\pi$ (for the decreasing order of their values).

In Theorem 3.2 and in its proof, we use the convention that $p_0 = 0$.

Figure 3 shows the first few levels of the generating tree corresponding to the rewriting system $\mathcal{R}_{\Phi}$.

An immediate consequence of Theorem 3.2 is that the rewriting system $\mathcal{R}_{\Phi}$ provides a bijection $\Phi$ between $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$ that preserves the size and the number of right-to-left maxima.

**Proof:** It is enough to use the bijective correspondence via the $c \circ i$ transformation between respectively $\mathrm{Id}(S \circ S)$ and $\mathrm{Av}(3214, \bar{2}4135)$, and $\mathrm{Id}(S \circ r \circ S)$ and $\mathrm{Av}(3241, \bar{2}4153)$. Indeed, Theorem 3.2 is a direct translation of Proposition 11 of [Dulucq et al. (1998)] in this context. We however give the construction used in the proof, since it will have to be further analyzed in the next subsection. We omit the proof that this construction is correct, and refer the reader to [Dulucq et al. (1998)] for details.

Permutation 1 belongs to $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$, has two active sites, one right-to-left maximum, and one active site above this right-to-left maximum. Let us now examine the permutations that are obtained when inserting a rightmost element into the active site of a permutation $\pi$ of $\mathrm{Id}(S \circ S)$ (resp. $\mathrm{Id}(S \circ r \circ S)$) labeled $(x, k, (p_1, \dots, p_k))$.

Consider $\pi \in \mathrm{Id}(S \circ S)$ (resp. $\mathrm{Id}(S \circ r \circ S)$), and one of its active site $s$, which is the $i$-th active site in the numbering from top to bottom. Denote by $\pi'$ the permutation obtained from $\pi$ by the insertion of a rightmost element in site $s$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: The first levels of the generating tree corresponding to the rewriting system $R_{\Phi}$.</figcaption></figure>

Suppose first that site $s$ is above the rightmost element of $\pi$. Then define $j$ such that the largest right-to-left maximum of $\pi$ that is below $s$ is the $j$-th one, and $s_j$ to be the site that immediately below (resp. above) the $j$-th right-to-left maximum. Notice that in the case of $\mathrm{Id}(S \circ S)$, the site $s_j$ is always active in $\pi$. Then any site above $s_j$ (included) is active in $\pi'$ if and only if it was active in $\pi$, and the two sites that have been created around the inserted element are both active. As for the sites below $s_j$, they all become inactive (resp. all but the bottommost site, which is always active).

If on the contrary site $s$ is below the rightmost element of $\pi$, then any site is active in $\pi'$ if and only if it was active in $\pi$, and the two sites that have been created around the inserted element are both active.

Figure 4 gives a graphical view of these two cases of insertion. In the first case, we have that $1 \le j$, and $p_{j-1} < i \le p_j$, and the label of $\pi'$ is $(2 + p_j, j, (p_1, \dots, p_{j-1}, i))$. In the second case, we have $p_k < i \le x$ and the label of $\pi'$ is $(x + 1, k + 1, (p_1, \dots, p_k, i))$. $\square$

We can notice that in the above construction for $\mathrm{Id}(S \circ S)$ (resp. $\mathrm{Id}(S \circ r \circ S)$), the first, second and third (resp. last) sites, and the site above any right-to-left maximum are active (see [Dulucq et al. (1998), Lemma 12, (i) and (ii)] for the proof).

## 3.2 Refinements of the rewriting system

The rewriting system given by [Dulucq et al. (1998)] for $Av(3241, \bar{2}4153)$ and $Av(3214, \bar{2}4135)$ is actually more precise, and takes into account the number of left-to-right maxima of a permutation $\pi$ but also the number of ascents in $i(\pi)$. After the $c \circ i$ transformation, these statistics correspond to the number of right-to-left maxima and the number of descents for permutations in $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$. Hence, these two statistics are preserved by the bijection $\Phi$ between $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$. Actually every statistic $\mathrm{stat}$ of Theorem 1.3 is preserved by $\Phi$: for each of them, we can provide a refinement $R_{\Phi}^{\mathrm{stat}}$ of the rewriting system $R_{\Phi}$, thus completing the proof of Theorem 1.3. Some of these rewriting systems are given below; the others are omitted for the sake of brevity but are obtained in a similar fashion.
<figure><img src="image_4.png" /><figcaption>Fig. 4: The two cases of insertion of a rightmost element into a permutation of $\mathrm{Id}(S \circ S)$ and $\mathrm{Id}(S \circ r \circ S)$.</figcaption></figure>

**Number of left-to-right maxima** The rewriting system $\mathcal{R}_{\Phi}$ can be refined as follows to account for the number of left-to-right maxima, in the part of the label denoted by $q$:

$$ \mathcal{R}_{\Phi}^{\mathrm{lmax}} \left\{ \begin{array}{ll} (2, 1, (1), 1) & \rightsquigarrow (2 + p_1, 1, (1), q + 1) \\ (x, k, (p_1, \dots, p_k), q) & \quad (2 + p_j, j, (p_1, \dots, p_{j-1}, i), q) \quad \begin{array}{l} \text{for } 1 \le j \le k \\ \text{and } p_{j-1} < i \le p_j, i \ne 1 \end{array} \\ & \\ & (x + 1, k + 1, (p_1, \dots, p_k, i), q) \quad \begin{array}{l} \text{for } p_k < i \le x \end{array} \end{array} \right. $$

**Proof:** The insertion into an active site does not change the number of left-to-right maxima of $\pi$, unless the insertion takes place in the topmost site of $\pi$. This site is always active, and in this case (corresponding to $i = j = 1$), one left-to-right maximum is created. $\square$

**Length of the leftmost decreasing run** The rewriting system $\mathcal{R}_{\Phi}$ can be refined as follows to account for the length of the leftmost decreasing run, in the part of the label denoted by $q$:

$$ \mathcal{R}_{\Phi}^{\mathrm{ldr}} \left\{ \begin{array}{ll} (2, 1, (1), 1, 1) & \rightsquigarrow (2 + p_j, j, (p_1, \dots, p_{j-1}, i), n + 1, q) \quad \begin{array}{l} \text{for } 1 \le j \le k \\ \text{and } p_{j-1} < i \le p_j \end{array} \\ (x, k, (p_1, \dots, p_k), n, q) & \quad (x + 1, k + 1, (p_1, \dots, p_k, i), n + 1, q) \quad \begin{array}{l} \text{for } p_k < i < x \\ (x + 1, k + 1, (p_1, \dots, p_k, x), n + 1, q + \delta_{n,q}) \end{array} \\ & \\ & \quad \text{where } \delta_{n,q} \text{ is 1 if } n = q \text{ and } 0 \text{ otherwise} \end{array} \right. $$
It is necessary in this case to also account for more than just the value of the considered statistics in the label. Here, we furthermore introduced the size of the permutations, denoted by $n$.

**Proof:** The only case where the length of the leftmost decreasing run may change (being increased by 1) is when $\pi$ is $n(n-1)\dots21$ and the insertion is performed in the bottommost site of $\pi$. For $\pi = n(n-1)\dots21$, the bottommost site is always active, for $\mathrm{Id}(\mathbf{S}\circ\mathbf{S})$ and $\mathrm{Id}(\mathbf{S}\circ\mathbf{r}\circ\mathbf{S})$. An insertion in this special case is always an insertion in the $x$-th active site of $\pi$ and corresponds to the case where $q = n$. $\square$

**The slmax statistics** Recall that the slmax statistics is defined, for any permutation $\pi$, as the largest $k$ such that $\pi_1 \ge \pi_i$ for all $i \in [1..k]$. The rewriting system $\mathcal{R}_\Phi$ can be refined as follows to account for the slmax statistics in the part of the label denoted by $q$:

$$ \mathcal{R}_{\Phi}^{\text{slmax}} \left\{ \begin{array}{ll} (2, 1, (1), 1, 1) & \rightsquigarrow (2 + p_1, 1, (1), q, n + 1) \\ (x, k, (p_1, \dots, p_k), q, n) & \rightsquigarrow (2 + p_j, j, (p_1, \dots, p_{j-1}, i), q + \delta_{q,n}, n + 1) \quad \text{for } 1 \le j \le k \\ & \text{and } p_{j-1} < i \le p_j, i \ne 1 \\ & \rightsquigarrow (x + 1, k + 1, (p_1, \dots, p_k, i), q + \delta_{q,n}, n + 1) \quad \text{for } p_k < i \le x \\ & \text{where } \delta_{q,n} \text{ is 1 if } q = n \text{ and 0 otherwise} \end{array} \right. $$

Here, we also introduced the size of the permutations, denoted by $n$.

**Proof:** The insertion in the topmost site of $\pi$ (which is always active) does not change the value of the slmax statistics. The insertion in any other site may change the value of this statistics, increasing it by 1. This happens exactly when $\pi$ starts with its maximum, and this situation is characterized by the equality $q = n$. $\square$

# 4 Permutations sorted by $\mathbf{S} \circ \mathbf{i} \circ \mathbf{S}$: enumerative result

We describe a common generating tree for $\mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$ and $\mathrm{Av}(2-14-3, 2-41-3)$. This is not the class of Baxter permutations, but they are equi-enumerated, as proved in [Guibert(1995)] or [Giraudo(2011)]. This will prove Theorem 1.4.

**Theorem 4.1** *The generating trees for both $\mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$ and $\mathrm{Av}(2-14-3, 2-41-3)$, with the insertion rules* **Smallest and Largest respectively, are characterized by the following rewriting system:**

$$ \mathcal{R}_{\Psi} \left\{ \begin{array}{ll} (2, 0) & \rightsquigarrow (i + 1, r + s - i) \text{ for } 1 \le i \le r \\ (r, s) & \rightsquigarrow (r, s - j) \text{ for } 1 \le j \le s \end{array} \right. $$

where the labels $(r, s)$ of a permutation $\pi$ are interpreted as follows:

For any permutation $\pi$ of size $n$ in $\mathrm{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$:

* $r$ is the index of the second element in the first ascent of $\pi$ (or $n+1$ if $\pi = n(n-1)\dots21$),

* $s$ is the number of active sites to the right of the first ascent of $\pi$.

For any permutation $\pi$ of size $n$ in $\mathrm{Av}(2-14-3, 2-41-3)$:
• *r* is the number of active sites to the left of *n* plus 1 (the site following *n* immediately),

• *s* is the number of active sites to the right of *n* minus 1 (the site following *n* immediately).

**Proof:** Let us first study $\text{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S}) = \text{Av}(3412, 3-4-21)$ with the insertion rule *Smallest*. It is readily checked that if $\pi$ avoids 3412 and 3-4-21, then so does the permutation obtained from $\pi$ by deleting its smallest element and normalizing. This justifies that we have a generating tree, whose root 1 is labeled (2, 0) according to the interpretation of the labels given in Theorem 4.1. It can further be noticed that a site which is inactive in $\pi$ cannot be active in any child of $\pi$.

It is easily proved that a site $x$ of $\pi$ is inactive if and only if there are elements $a < b < c$ such that *bca* is a subsequence of $\pi$ and $x$ is either between $c$ and $a$ or follows $a$ immediately. In particular, every site that precedes the first ascent of $\pi$ and the site inside this first ascent are active.

The number of such active sites correspond to *r* in the label of $\pi$. The insertion of 1 in such a site of $\pi$ (say the *i*-th such site) does not deactivate any site that was active in $\pi$, and the sites that were inactive in $\pi$ remain inactive. Hence, *r* children of $\pi$ are obtained by insertions of this first type, whose labels are $(i+1, s+r-i)$ for $1 \le i \le r$.

The other children $\pi'$ of $\pi$ are obtained by insertion of 1 in active sites that are to the right of the first ascent of $\pi$, that we denote by *bc*. The insertion of 1 in such a site (say the *j*-th such site) creates a subsequence *bc1* in $\pi'$ so that the sites between *c* and 1 and just after 1 are inactive in $\pi'$. So *j* active sites to the right of the first ascent become inactive. For the other sites, as before they are active in $\pi'$ if and only if they were active in $\pi$. Hence, *s* children of $\pi$ are obtained by insertions of this second type, whose labels are $(r, s-j)$ for $1 \le j \le s$.

We now turn to the study of $\text{Av}(2-14-3, 2-41-3)$ with the insertion rule *Largest*. As above, if $\pi$ avoids 2-14-3 and 2-41-3, then so does the permutation obtained from $\pi$ by deleting its largest element, so that we have a generating tree. Its root 1 is labeled (2, 0) according to the interpretation of the labels. Furthermore, denoting *n* the size of $\pi$, the followings can be readily proved:

• the site immediately to the right of *n* is active;

• when inserting $n+1$ into an active site of $\pi$, the sites to the right of $n+1$ are active if and only if they were active in $\pi$;

• the sites to the left of *n* are active if and only if they are located between two adjacent left-to-right maxima of $\pi$.

With these three facts, a careful examination allows to prove that the insertion of $n+1$ in the *i*-th active site to the left of *n*, for $1 \le i \le r-1$ (resp. in the site immediately to the right of *n*, resp. in the *j*+1-th active site to the right of *n*, for $1 \le j \le s$), produces a child of $\pi$ labeled by $(i+1, r+s-i)$ (resp. $(r+1, s)$, resp. $(r, s-j)$). $\square$

We claim that as in the case of Theorem 1.3, and although it requires to introduce additional statistics in the label, this rewriting system for $\text{Id}(\mathbf{S} \circ \mathbf{i} \circ \mathbf{S})$ can be refined to follow the triple of statistics (des, lmax, comp). This however does not prove Conjecture 1.5, as we need first to examine how these statistics on Baxter permutations are transported on permutations avoiding 2-14-3 and 2-41-3, and second to refine the rewriting system for $\text{Av}(2-14-3, 2-41-3)$ according to these new statistics. The second part is likely to be solved when the statistics on $\text{Av}(2-14-3, 2-41-3)$ are known. However, they seem hard to characterize with the bijection of [Guibert(1995)]: because it relies on a generating tree, the one-to-one correspondence is not effective. On the contrary, [Giraudo(2011)] has recently given a *constructive bijection* between $\text{Av}(2-14-3, 2-41-3)$ and the set of Baxter permutations. This bijection actually establishes a
one-to-one correspondence from each of these to pairs of twin binary trees. Hence, a promising path to conclude the proof of Conjecture 1.5 is to interpret the statistics (des, lmax, comp) on Baxter permutations as some triple of statistics on pairs of twin binary tree, and then to interpret these new statistics on the permutations of $Av(2-14-3, 2-41-3)$. This is indeed a work in progress.

## Acknowledgements

We thank Anders Claesson, Mark Dukes, and Einar Steingrímsson for bringing this problem to our attention, and for sharing their conjectures in [Claesson et al.(2007)]. We also thank Michael Albert, Mike Atkinson, Anders Claesson and Mark Dukes, with whom this research project started, during a visit of Mathilde Bouvel to Otago University.

## References

[Albert et al.(2010)] M. H. Albert, M. D. Atkinson, M. Bouvel, A. Claesson, and M. Dukes. Private communication. 2010.

[Albert et al.(2011)] M. H. Albert, M. D. Atkinson, M. Bouvel, A. Claesson, and M. Dukes. On the inverse image of pattern classes under bubble sort. *Journal of Combinatorics*, 2(2), 2011.

[Barcucci et al.(1999)] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. ECO: A methodology for the enumeration of combinatorial objects. *J. Difference Equ. Appl.*, 5:435–490, 1999.

[Baxter(1964)] G. Baxter. On fixed points of the composite of commuting functions. *Proceedings of the American Mathematical Society*, 15:851–855, 1964.

[Bernini et al.(2005)] A. Bernini, L. Ferrari, and R. Pinzani. Enumerating permutations avoiding three Babson-Steingrímsson patterns. *Annals of Combinatorics*, 9:137–162, 2005.

[Chung et al.(1978)] F. R. K. Chung, R. L. Graham, V. E. J. Hoggatt, and M. Kleiman. The number of Baxter permutations. *J. Combin. Theory Ser. A*, 24(3):382–394, 1978.

[Claesson and Kitaev(2008)] A. Claesson and S. Kitaev. Classification of bijections between 321- and 132-avoiding permutations. *Séminaire Lotharingien de Combinatoire*, 60, 2008. Article B60d.

[Claesson et al.(2007)] A. Claesson, M. Dukes, and E. Steingrímsson. Private communication. 2007.

[Dulucq et al.(1998)] S. Dulucq, S. Gire, and O. Guibert. A combinatorial proof of J. West's conjecture. *Discrete Mathematics*, 187:71–96, 1998.

[Giraudo(2011)] S. Giraudo. Algebraic and combinatorial structures on Baxter permutations. In *FPSAC 2011, DMTCS proc. AO*, pages 387–398, 2011. Full version available at http://arxiv.org/abs/1011.4288.

[Guibert(1995)] O. Guibert. *Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young*. PhD thesis, Université Bordeaux 1, 1995.

[Knuth(1973)] D. E. Knuth. *Fundamental Algorithms*, volume 1 of *The Art of Computer Programming*. Addison-Wesley, Reading MA, 3rd edition, 1973.

[Ouchterlony(2005)] E. Ouchterlony. *On Young tableau involutions and patterns in permutations*. PhD thesis, Linköpings Universitet, 2005.

[West(1993)] J. West. Sorting twice through a stack. *Theoretical Computer Science*, 117(1-2):303–313, 1993.

[West(1995)] J. West. Generating trees and the Catalan and Schröder numbers. *Discrete Mathematics*, 146:247–262, 1995.