# Adjacent transformations in permutations

Adeline Pierrot<fnref n="1" />, Dominique Rossin<fnref n="2" />† and Julian West<fnref n="3" />

**Abstract.** We continue a study of the equivalence class induced on $S_n$ when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order. For each possible set of allowed replacements, we characterise and/or enumerate the set of permutations reachable from the identity. In some cases we also count the number of equivalence classes.

**Résumé.** Nous étudions dans cet article les classes d'équivalence sur les permutations obtenues en remplaçant un ensemble consécutif de valeurs par ces même valeurs mais dans un ordre différent. Nous étudions l'ensemble des remplacements possibles de longueur 3 et pour chacun d'entre eux caractérisons et énumérons les permutations de la classe de l'identité. Pour certains ensembles, nous calculons de même le nombre de classes d'équivalence.

**Keywords:** permutation patterns, equivalence classes, integer sequences, Catalan numbers, sorting permutations

## 1 Introduction

In [LPRW10], the authors consider the equivalence class induced on $S_n$ when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order, where the sequence removed and the sequence replacing it must each match as a pattern any sequence in a given replacement set, which is a subset of some $S_k$. Here match as a pattern means to have all the same order relations. For instance, if the given replacement set is {123, 132}, then 12453 is equivalent to 14235, because we can perform the replacement 12453 → 14253 followed by 14253 → 14235.

We write `#Classes(n; {A})` to denote the number of equivalence classes into which $S_n$ is divided by the replacement set $A$. We use $C_n(A)$ to denote the equivalence class of the identity, and $c_n(A)$ its size.

In [LPRW10], the authors restricted their attention to replacement sets selected from $S_3$, in which each replacement can be viewed as fixing one of the three elements and exchanging the other two. We look at sets of patterns, such as {123, 231}, which do not meet this condition, and were therefore excluded from their paper. We focus on the characterization and enumeration of the class containing the identity permutation, and indeed with our new results we now know the enumeration of this class in all cases.

One of the earliest references for transformations in permutations is in Knuth's *Art of Computer Programming* [Knu73] where we find the idea of sorting a permutation by passage through a stack, illustrated by a chain of railway wagons which can be interchanged by the instrument of a spur of track.

<footnote n="1">¹LIAFA, Université Paris Diderot, Paris, France</footnote>

<footnote n="2">²LIX, École Polytechnique, Palaiseau, France</footnote>

<footnote n="3">³Heilbronn Institute for Mathematical Research, University of Bristol, Bristol, UK</footnote>

<footnote>†This work was supported by ANR Gama and Magnum</footnote>
Because in the present case we are almost always concerned with the question of whether or not a given permutation can be restored to the identity, it is perhaps not too fanciful to imagine a similar context, where we are examining whether a permutation can be sorted, with some local (mechanical or logical) circuits but under global control.

We have divided our paper into sections based on the number of patterns contained in the replacement set, and in an appendix we give a summary table of $c_n(A)$ for all replacement sets A, both those enumerated in the present work, and those known previously.

Two operations familiar from the literature of permutation patterns, reversal and complementation, have a natural role in this context. It is clear that two permutations are equivalent with respect to a given replacement set if and only if their reversals (complements) are equivalent with respect to the reversal (complement) of the replacement set. Thus a result cited in the summary table may actually be the reversal (R), or reverse complement (RC), of another entry. In particular, since 123 is its own reverse complement, one can always try applying reverse-complementation to one class containing 123 to obtain another one.

## 2 Replacement sets of size 2

### 2.1 $123 \leftrightarrow 231$

**Definition 2.1** Let $\sigma = \sigma_1 \dots \sigma_n$ be a permutation, $\sigma$ satisfies the position parity condition if for all $i \in \{1 \dots n\}$, then, taking the set $\{\sigma_1 \dots \sigma_i\}$ in increasing order, the rank of $\sigma_i$ is congruent to $i \pmod 2$.

**Example 2.1** The permutation $\sigma = 45123$ satisfies position parity, because $\sigma_1 = 4$ is the smallest element of $\{4\}$, $\sigma_2 = 5$ is the 2nd-smallest element of $\{4, 5\}$, $\sigma_3 = 1$ is the smallest element of $\{4, 5, 1\}$, $\sigma_4 = 2$ is the 2nd-smallest element of $\{4, 5, 1, 2\}$ and $\sigma_5 = 3$ is the 3rd-smallest element of $\{4, 5, 1, 2, 3\}$. The permutation 4612375 also satisfies position parity, but 21 does not.

**Proposition 2.1** Let $\sigma \in S_n$. Then $\sigma \in C_n(123, 231)$ if and only if it satisfies position parity. Moreover it is possible to step from the identity permutation to $\sigma$ using only steps of form $123 \to 231$.

*Proof:* Let $\sigma = \sigma_1 \dots \sigma_n$ be a permutation satisfying position parity. To obtain $\sigma$ from the identity, begin by placing the rightmost element, $\sigma_n$. By position parity, $\sigma_n$ must have the same parity as $n$, and since it occupies position $\sigma_n$ in the identity, it needs to move an even number of positions, $n - \sigma_n$. We move it forward two steps at a time, using only moves $123 \to 231$ (where $\sigma_n$ plays the role of 1), which we can do because the identity permutation has all its elements in increasing order. We call the permutation which results $\sigma^{(n)}$; the element in position $n$ is the correctly-placed $\sigma_n$, and the elements in the other $n-1$ positions are in increasing order.

Now do the same thing to place $\sigma_{n-1}$ in position $n-1$, obtaining a permutation $\sigma^{(n-1)}$, and in general at step $k$ a permutation $\sigma^{(n-k+1)}$, in which the final $k$ elements are correctly placed, and the first $n-k$ elements are in increasing order, from which it follows that the next element to be placed, $\sigma_{n-k}$, occupies the position corresponding to its rank in the set $\{\sigma_1 \dots \sigma_{n-k}\}$ written in increasing order. So it has to move an even number of positions and we place it with moves $123 \to 231$. At the $n$th step, we have obtained the permutation $\sigma = \sigma^{(0)}$.

Conversely, let $\sigma \in C_n(123, 231)$. A case study proves that position parity is kept under the transformations $123 \leftrightarrow 231$. As $\sigma$ can be reached from the identity which has position parity this concludes the proof. $\square$
**Remark 2.1** Let $\sigma \in C_n(123, 231)$, then the proof gives us a canonical path to obtain $\sigma$ from the identity, using only steps of form $123 \rightarrow 231$: we start by placing $\sigma_n$, then $\sigma_{n-1}$, etc.

**Corollary 2.1** The number of permutations in the equivalence class of the identity on $n$ elements is $c_n(123, 231) = \lceil \frac{1}{2} \rceil \cdot \lceil \frac{2}{2} \rceil \dots \lceil \frac{n}{2} \rceil = 1^2 \cdot 2^2 \dots \lceil \frac{n}{2} \rceil$ (n terms).

*Proof:* We will place elements from right to left. Let $\sigma \in C_n(123, 231)$, then the rank of $\sigma_n$ in $\{\sigma_1 \dots \sigma_n\}$ is of the same parity as $n$, which gives $\lceil \frac{n}{2} \rceil$ choices for $\sigma_n$, $\lceil \frac{n-1}{2} \rceil$ choices for $\sigma_{n-1}$, and so forth. $\square$

### 3 Replacement sets of size 3

#### 3.1 $123 \leftrightarrow 213 \leftrightarrow 231$

We will characterize and enumerate $C_n(123, 213, 231)$ in Proposition 3.1 and Corollary 3.1. We will first need the following two lemmas.

**Lemma 3.1** Let $\sigma$ be a permutation of size $n$ such that $n$ is immediately to the right of $n-1$. Then $\sigma$ can be obtained from the identity using transformations $123 \leftrightarrow 213 \leftrightarrow 231$.

*Proof:* Let $\tau$ be the pattern obtained by deleting $n-1$ and $n$ from $\sigma$. We will first construct $\tau(n-1)n$, then position $n-1$ and $n$ appropriately. Because $(n-1)$ and $n$ are the two largest elements in the permutation, they can always be moved together as far as desired to the left using $123 \rightarrow 231$, or to the right using $231 \rightarrow 123$, as long as they remain together.

So, beginning with the identity permutation, first advance $(n-1)$ and $n$ so that they are just to the right of $\tau_1$. Now, letting $n-1$ play the role of $3$, and using either $123 \rightarrow 213$ or $213 \rightarrow 123$ as appropriate, $\tau_1$ can be moved one position to the left (if it is not already at the leftmost position). And $(n-1)$ and $n$ can then be repositioned so that they remain just to its right. Repeat until $\tau_1$ is in the leftmost position.

Now reposition $(n-1)$ and $n$ just to the right or $\tau_2$ and, as before, advance $\tau_2$ to where it belongs, in the second position. Continue until we have built up $\tau(n-1)n$, one element at a time. Since $(n-1)$ and $n$ remain free to move as a block, advance them as necessary to obtain the permutation $\sigma$. $\square$

**Lemma 3.2** Given a permutation $\alphaijk\sigma\gamma$ such that the elements of $\sigma$ are all less than $k$ and $k < i < j$, it is possible to move to any permutation $\alpha i\sigma'kjl\sigma''\gamma$ using transformations $123 \leftrightarrow 213 \leftrightarrow 231$, where $\sigma = \sigma' \cup \sigma'' \cup \{l\}$ and $l = \max \sigma - \sigma'$.

*Proof:* We begin by applying $231 \rightarrow 213$ to $ijk$ to obtain $\alpha ikj\sigma\gamma$. Now, if $kj\sigma$ is considered as a permutation having $n$ elements, $k$ and $j$ represent the largest elements, $n-1$ and $n$. But Lemma 3.1 says that any permutation having $n$ immediately following $n-1$ is equivalent to any other, and we can therefore obtain $\sigma'kjl\sigma''$ from $kj\sigma$, and therefore $\alpha i\sigma'kjl\sigma''\gamma$ from $\alpha ikj\sigma\gamma$. $\square$

**Proposition 3.1** Let $\sigma$ be a permutation of size $n$. Then $\sigma \in C_n(123, 213, 231)$ if and only if $n-1$ is to the left of $n$ in $\sigma$.

*Proof:* Since $n-1$ is to the left of $n$ in the identity, and since in each of the patterns $123$, $213$, and $231$, the relative order of the two largest elements is preserved, then $n-1$ must remain to the left of $n$.

Now suppose that $\sigma$ is of size $n$ and has $n-1$ to the left of $n$. We will show that $\sigma$ can be reached from the identity. If $n-1$ is immediately to the left of $n$, we have the result by Lemma 3.1. If not, decompose $\sigma$ as $\alpha(n-1)\beta n\gamma$. By Lemma 3.1, we can reach $\alpha(n-1)nk\beta'\gamma$, where $k = \max\beta$ and $\beta' = \beta - \{k\}$.
Now, to obtain $\sigma$, we proceed by induction on the number of right-to-left maxima of $\beta$, using Lemma 3.2. Let $k_1, k_2, \dots$ be the right-to-left maxima of $\beta$, such that $\beta = \beta^{(1)}k_1\beta^{(2)}k_2, \dots$ and set $\beta^{(-i)} = \beta^{(i)}\beta^{(i+1)}k_{i+1}, \dots$. Then we have $\alpha(n-1)n k \beta' \gamma = \alpha(n-1)n k_1 \beta^{(-1)}\gamma$. By Lemma 3.2, from $\alpha(n-1)n k_1 \beta^{(-1)}\gamma$ we can reach $\alpha(n-1)\beta^{(1)}k_1 n k_2 \beta^{(-2)}\gamma$. Setting $\alpha' = \alpha(n-1)\beta^{(1)}k_1 \beta^{(2)}k_2 n k_3 \beta^{(-3)}\gamma$, we can apply again Lemma 3.2 to reach $\alpha(n-1)\beta^{(1)}k_1 \beta^{(2)}k_2 n k_3 \beta^{(-3)}\gamma$, and so we can reach $\sigma$ by applying Lemma 3.2 as many times as there are right-to-left maxima in $\beta$. $\square$

**Corollary 3.1** *The number of permutations of size $n$ equivalent to the identity is* $c_n(123, 213, 231) = \frac{n!}{2}$.

3.2 $123 \leftrightarrow 132 \leftrightarrow 231$

**Proposition 3.2** Let $\sigma$ be a permutation of size $n$. Then $\sigma \in C_n(123, 132, 231)$ if and only if the left-to-right minima of $\sigma$ are all in odd positions.

*Proof:* The identity has only one left-to-right minimum, namely in position 1, which is an odd position. Now consider applying the permitted transformations to a permutation. A move $123 \to 132$ neither adds nor removes a left-to-right minimum. However, a move $123 \to 231$ may either displace a left-to-right minimum or create a new one, but in either case does so two places to the right of an existing left-to-right minimum (and, conversely, the reverse move might either displace or create a left-to-right minimum two places to the left). Exactly the same is true for moves $132 \leftrightarrow 231$. Therefore repeated application of these rules to a permutation (such as the identity) which has all its left-to-right minima in odd positions can never introduce a left-to-right minimum in an even position.

Now we need to show that all such permutations can be obtained beginning with the identity. Let $\sigma$ be a permutation with all left-to-right minima in odd positions. We will show by induction that we can obtain the permutations $\sigma^{(k)}$ in which the final $k$ elements match those of $\sigma$, and the remaining $n-k$ elements are in increasing order. When $k=0$, we have the identity.

Suppose we have obtained from the identity a permutation $\tau$ in which the final $k$ elements are the same as those of $\sigma$ and in which the first $n-k$ elements are in increasing order. We will place $\sigma_{n-k}$ in position $n-k$. If $\sigma_{n-k}$ is the smallest (and therefore leftmost) of the first $n-k$ elements of $\tau$, then $\sigma_{n-k}$ is a left-to-right minimum of $\sigma$, and therefore $n-k$ is odd. Since $\sigma_{n-k} = \tau_1$ and the first $n-k$ elements of $\tau$ are increasing, we can move it to position $n-k$ by repeated moves of type $123 \to 231$. If $\sigma_{n-k}$ is not the smallest of the first $n-k$ elements of $\tau$, then $\sigma_{n-k} = \tau_i$ with $i > 1$. If $i$ is of the same parity as $n-k$, it is easy to move $\sigma_{n-k}$ using $123 \to 231$. Otherwise, we place $\sigma_{n-k} = \tau_i$ in position $n-k-1$, then place $\tau_{i-1}$ in position $n-k-2$. At this point, $\tau_{i-1}\tau_i\tau_{n-k}$ forms a pattern 123, so we can use $123 \to 132$ to place $\tau_i = \sigma_{n-k}$ in position $n-k$. Finally, we can use $231 \to 123$ (letting $\tau_{i-1}$ play the role of 1) to return $\tau_{i-1}$ to position $i-1$, so that the initial $n-k-1$ elements are again in increasing order. The resulting permutation matches $\sigma$ in the final $k+1$ positions, and has the initial $n-k-1$ elements in increasing order. $\square$

3.3 $123 \leftrightarrow 231 \leftrightarrow 312$

**Definition 3.1** For convenience we will refer to the permutations in equivalence classes of size 1 as isolated permutations. That is, an isolated permutation is carried to nothing under any of the permitted transformations, equivalently, it does not contain any pattern in the replacement set.
**Proposition 3.3** Let $\sigma$ be a permutation of size $n$. Then $\sigma \in C_n(123, 231, 312)$ if and only if $\sigma$ is an even permutation which is not isolated.

*Proof:* The transformations $123 \leftrightarrow 213 \leftrightarrow 312$ conserve the parity of the number of inversions, so each class contains only permutations of the same parity. In particular, if $\sigma \in C_n(123, 231, 312)$ then $\sigma$ is even.

Conversely suppose that $\sigma$ is an even permutation which is not isolated. Let $K$ be the equivalence class containing $\sigma$ and let $\tau$ be an element of $K$ with a minimal number of inversions. We will show that $\tau$ is the identity. We know that $\tau$ does not contain a 231 or a 312, because replacing these by 123 reduces the number of inversions. Since $K$ does not consist of a single isolated permutation, it is possible to make a move from $\tau$, so it contains a 123.

Suppose there is an index $i$ such that $\tau_{i-2} < \tau_{i-1} < \tau_i > \tau_{i+1} > \tau_{i+2}$. As $\tau$ avoids 231, $\tau_{i-1}\tau_i\tau_{i+1}$ must be a 132, and so $\tau_{i-2}\tau_{i-1}\tau_i\tau_{i+1}$ is a 1243. Since $1243 \rightarrow 2413 \rightarrow 2134$, we can move from $\tau$ to $\tau' = \tau_1 \dots \tau_{i-3}\tau_{i-1}\tau_{i-2}\tau_{i+1}\tau_i\tau_{i+2} \dots \tau_n$, which has the same number of inversions as $\tau$. But $\tau_{i+1}\tau_i\tau_{i+2}$ forms a 231, and so using $231 \rightarrow 123$ we can obtain a permutation with strictly fewer inversions, contradicting the minimality of $\tau$.

Similarly, if there is an index $i$ such that $\tau_{i-2} > \tau_{i-1} > \tau_i < \tau_{i+1} < \tau_{i+2}$, and using the fact that $\tau$ avoids 312, we can again obtain a permutation with strictly fewer inversions than $\tau$.

We will say that $\tau$ satisfies property $P(i, k)$ if $\tau_i < \tau_{i+1} < \dots < \tau_{i+k-1} < \tau_{i+k}$, $\tau_{i-1} > \tau_i$ and $\tau_{i+k} > \tau_{i+k+1}$. Suppose that there exists an index $i$ and a $k \ge 2$ such that $\tau$ satisfies $P(i, k)$. Since $\tau$ avoids 312, $\tau_{i-1}\tau_i\tau_{i+1}$ forms a 213, and since $\tau$ avoids 231, $\tau_{i+k-1}\tau_{i+k}\tau_{i+k+1}$ forms a 132. Thus $\tau_{i+k-2}\tau_{i+k-1}\tau_{i+k}\tau_{i+k+1}$ forms a 1243. Since $1243 \rightarrow 2413 \rightarrow 2134$, we can move from $\tau$ to $\tau' = \tau_1 \dots \tau_{i+k-3}\tau_{i+k-1}\tau_{i+k-2}\tau_{i+k+1}\tau_{i+k}\tau_{i+k+2} \dots \tau_n$, which has the same number of inversions as $\tau$, and satisfies $P(i, k-2)$. By induction this allows us to assume that $\tau$ satisfies $P(i, k)$ for $k=2$ or $k=3$. First, suppose $k=2$, so that $\tau_{i-1}\tau_i\tau_{i+1}\tau_{i+2}\tau_{i+3}$ forms a 21354. Via $21354 \rightarrow 25134 \rightarrow 12534 \rightarrow 12345$, we can obtain a permutation with fewer inversions, a contradiction. Then suppose $k=3$, so that $\tau_{i-1}\tau_i\tau_{i+1}\tau_{i+2}\tau_{i+3}\tau_{i+4}$ forms a 213465. Again we can obtain a permutation with fewer inversions, via $213465 \rightarrow 241365 \rightarrow 246135 \rightarrow 246513 \rightarrow 462513 \rightarrow 461253 \rightarrow 146253 \rightarrow 145623 \rightarrow 156423 \rightarrow 156234 \rightarrow 125634 \rightarrow 123564 \rightarrow 123456$.

Recall that $\tau$ contains some 123. Let $j$ be the smallest index with $\tau_j < \tau_{j+1} < \tau_{j+2}$. Then either $j=1$ or $\tau_{j-1} > \tau_j$ (for otherwise we could have used $j-1$). Let $m$ be the largest integer with $\tau_j < \tau_{j+1} < \dots < \tau_{j+m-1} < \tau_{j+m}$. By construction, $m \ge 2$, and $j+m=n$ or $\tau_{j+m+1} < \tau_{j+m}$ (by the maximality of $m$).

If $j \ne 1$ and $j+m \ne n$ then $\tau$ satisfies $P(j, m)$, contrary to our assumption.

Now suppose that $j \ne 1$ and $j+m=n$. Then we know that $\tau_{j-1} > \tau_j < \tau_{j+1}$, and since $\tau$ avoids 312, $\tau_{j-1}\tau_j\tau_{j+1}$ forms a 213. If $j-1=1$ then $\tau$ has only one inversion, which is impossible as $\tau$ is even. So $j-2 \ge 1$. If $\tau_{j-2} > \tau_{j-1}$ then the index $j$ satisfies $\tau_{j-2} > \tau_{j-1} > \tau_j < \tau_{j+1} < \tau_{j+2}$, which we know is not the case. Thus $\tau_{j-2} < \tau_{j-1} > \tau_j$ and since $\tau$ avoids 231, $\tau_{j-2}\tau_{j-1}\tau_j$ forms a 132. If $j-2=1$ then $\tau$ again has one inversion, which is impossible. Thus $j-3 \ge 1$ and $\tau_{j-3} > \tau_{j-2}$, otherwise the index $j-3$ contradicts the minimality of $j$. Furthermore, $\tau_{j-3} < \tau_{j-1}$ because $\tau$ has no 312, and so $\tau_{j-3}\tau_{j-2}\tau_{j-1}\tau_j\tau_{j+1}\tau_{j+2}$ forms a 214356. Now we can use $214356 \rightarrow 214635 \rightarrow 213465$, which by an argument above can be mapped to 123456, thus producing a permutation with fewer inversions than $\tau$.

We show symmetrically that the case $j=1$ and $j+m \ne n$ is impossible. The only other possibility is that $j=1$ and $j+m=n$, which means that $\tau$ is the identity, and we are done. $\square$
Thanks to the preceding proposition, we have a characterization of the set $C_n(123, 231, 312)$. Instead of enumerating this set we compute the complementary one among even permutations $S^e(n)$. This set contains all even permutations that avoid patterns 123, 231 and 312. We will denote by $S_n(123, 231, 312)$ the set of permutations of size $n$ that avoid patterns 123, 231 and 312. Following article [KM05], denote by $s_e(n; i_1; \dots; i_k)$ (resp. $s_o(n; i_1; \dots; i_k)$) the number of even (resp. odd) permutations $\pi \in S_n(123, 231, 312)$ such that $\pi_1\pi_2\dots\pi_k = i_1i_2\dots i_k$. Consider the transformation *rot* on permutations that consists in left multiplying the permutation by $n$ 12...n-1. This transformation *rot* is a bijection of $S_n(123, 231, 312)$. Moreover when the size of a permutation is even, the transformation *rot* flips the parity and we have $s_o(2n; a+1) = s_e(2n; a)$ and $s_e(2n; a+1) = s_o(2n; a)$. When the size of permutation is odd *rot* preserves parity and we have $s_o(2n+1; a+1) = s_o(2n+1; a)$ and $s_e(2n+1; a+1) = s_e(2n+1; a)$.

**Proposition 3.4** For all $n$, $x$ such that $1 \le x \le n$:

$$
\begin{align*}
s_o(2n; 1, 2x) &= s_e(2n; 1, 2x) \quad \text{if } x < n \\
s_o(2n; 1, 2n) &= s_e(2n; 1, 2n) + (-1)^n \\
s_o(2n + 1; 1, 2x) + s_o(2n + 1; 1, 2x + 1) &= s_e(2n + 1; 1, 2x) + s_e(2n + 1; 1, 2x + 1) \quad \text{if } x > 1 \\
s_o(2n + 1; 1, 2) + s_o(2n + 1; 1, 3) &= s_e(2n + 1; 1, 2) + s_e(2n + 1; 1, 3) + (-1)^{n+1}
\end{align*}
$$

*Proof:* The proof is by induction on the size of the permutations. When the result holds for permutations of size $n$, we call this property $\mathcal{H}_n$. Clearly $\mathcal{H}_3$ holds : $s_o(3; 1, 2) + s_o(3; 1, 3) = 1$ and $s_e(3; 1, 2) + s_e(3; 1, 3) = 0$ because 123 is excluded and 132 is odd.

**Proof for permutations of size $2n + 2$** Suppose $\mathcal{H}_{2n+1}$ holds. We prove $\mathcal{H}_{2n+2}$.

We prove the result $s_o(2n+2; 1, 2x) = s_e(2n+2; 1, 2x)$ by induction on $x$. In fact as $s_o(2n+2; 1, 2) = s_e(2n+2; 1, 2) = 0$ the property is true for $x = 1$. Suppose it has been verified for $x < x_0$. We call this property $\mathcal{K}_{x_0}$.

The equality $s_o(2n+2; 1, 2x_0) = s_o(2n+2; 1, 2x_0-2)+s_o(2n+2; 1, 2x_0, 2)+s_o(2n+2; 1, 2x_0, 3)-s_o(2n+2; 1, 2x_0-2, 2n+2)-s_o(2n+2; 1, 2x_0-2, 2n+1)$ holds and is easily proved by considering that permutations $\sigma$ in $S_o(2n+2; 1, 2x_0)$ that do not have 2 or 3 as the third element are in one-to-one correspondence with those in $S_o(2n+2; 1, 2x_0-2)$ that do not have $2n+2$ or $2n+1$ as the third element by rotating twice (i.e. decreasing by 2) every element of $\sigma$ except its first one. Moreover, $s_o(2n+2; 1, 2x_0-2, 2n+2) = 0$ and $s_o(2n+2; 1, 2x_0-2, 2n+1) = 0$ as the first 3 elements of these permutations are in increasing order.

As $s_o(2n+2; 1, i, j) = s_o(2n+1; i-1, j-1) = s_o(2n+1; 1, 2n+2+j-i)$ for $j < i$ the preceding equality can be written as:
$$s_o(2n+2; 1, 2x_0) = s_o(2n+2; 1, 2x_0-2) + s_o(2n+1; 1, 2n+4-2x_0) + s_o(2n+1; 1, 2n+5-2x_0).$$

We also have the same equality with $s_e$ instead of $s_o$.

By property $\mathcal{K}_{x_0}$ we have $s_o(2n+2; 1, 2x_0-2) = s_e(2n+2; 1, 2x_0-2)$. If $x_0 < n+1$, then by property $\mathcal{H}_{2n+1}$ we have $s_o(2n+1; 1, 2n+4-2x_0)+s_o(2n+1; 1, 2n+5-2x_0) = s_e(2n+1; 1, 2n+4-2x_0)+s_e(2n+1; 1, 2n+5-2x_0)$. Hence $s_o(2n+2; 1, 2x_0) = s_e(2n+2; 1, 2x_0)$.

If $x_0 = n+1$, then by property $\mathcal{H}_{2n+1}$ we have $s_o(2n+1; 1, 2)+s_o(2n+1; 1, 3) = s_e(2n+1; 1, 2)+s_e(2n+1; 1, 3)+(-1)^{n+1}$. Hence $s_o(2n+2; 1, 2n+2) = s_e(2n+2; 1, 2n+2)+(-1)^{n+1}$.
**Proof for permutations of size $2n+3$ :** Suppose $\mathcal{H}_{2n+2}$ holds. We prove $\mathcal{H}_{2n+3}$.

$$ 
\begin{aligned}
s_o(2n+3; 1, 2x) + s_o(2n+3; 1, 2x+1) &= \sum_{j=1}^{2x-2} s_o(2n+2; 2x-1, j) + \sum_{j=1}^{2x-1} s_o(2n+2; 2x, j) \\
&= \sum_{j=1}^{2x-2} s_o(2n+2; 1, 2n+2+j-2(x-1)) + \sum_{j=1}^{2x-1} s_e(2n+2; 1, 2n+2+j-(2x-1)) \\
&= \sum_{j=2n+5-2x}^{2n+2} (s_o(2n+2; 1, j) + s_e(2n+2; 1, j)) + s_e(2n+2; 1, 2n+4-2x)
\end{aligned}
$$

If $x > 1$ as $2n+4-2x$ is even and $2n+4-2x < 2n+2$ by induction we have $s_e(2n+2; 1, 2n+4-2x) = s_o(2n+2; 1, 2n+4-2x)$. Thus we finally have if $x > 1$:

$$ 
\begin{aligned}
s_o(2n+3; 1, 2x) + s_o(2n+3; 1, 2x+1) \\
&= \sum_{j=2n+5-2x}^{2n+2} (s_o(2n+2; 1, j) + s_e(2n+2; 1, j)) + s_o(2n+2; 1, 2i+4-2x) \\
&= s_e(2n+3; 1, 2x) + s_e(2n+3; 1, 2x+1)
\end{aligned}
$$

If $x = 1$ the same calculus leads to a difference of $(-1)^{n+2}$. $\square$

**Theorem 3.1** *The number of even permutations $s_e(n)$ and the number of odd permutations $s_o(n)$ in $S_n(123, 231, 312)$ satisfy the following equations :*

$$ 
\begin{aligned}
s_o(2k) &= s_e(2k) = E_{2k-1}/2 \\
s_o(2k+1) + s_e(2k+1) &= E_{2k} \quad , \quad s_o(2k+1) = s_e(2k+1) + (2k+1)(-1)^k
\end{aligned}
$$

*Proof:* By [KM05], $|S_n(123, 231, 312)| = E_{n-1}$ where $E_n$ is the $n$-Euler number (Sloane A000111). In particular $s_o(2k+1) + s_e(2k+1) = E_{2k}$.

When the size of permutation is even, the transformation *rot* flips the parity hence $s_o(2k) = ks_e(2k; 1)+ks_o(2k; 1) = s_e(2k)$. But $s_o(2k) + s_e(2k) = E_{2k-1}$ so $s_o(2k) = s_e(2k) = E_{2k-1}/2$

When the size of the permutation is odd, transformation *rot* preserves parity. Permutations in $S_{2k+1}(123, 231, 312)$ can be grouped in sets of size $2k+1$ of permutations of the same parity which are equivalence classes of the relation *rot*. Note that in each class, only one permutation begins with 1. Hence, $s_o(2k+1) = (2k+1)s_o(2k+1; 1)$ and $s_e(2k+1) = (2k+1)s_e(2k+1; 1)$. But $s_o(2k+1; 1) = \sum_{i=2}^{2k+1} s_o(2k+1; 1, i)$ and Proposition 3.4 concludes that $s_o(2k+1) = s_e(2k+1) + (2k+1)(-1)^k$. $\square$

**Corollary 3.2** *The number $c_n(123, 231, 231)$ of permutations of size $n$ equivalent to the identity is* $c_{2k}(123, 231, 231) = \frac{(2k)!-E_{2k-1}}{2}$ and $c_{2k+1}(123, 231, 231) = \frac{(2k+1)!-E_{2k}+(2k+1)(-1)^k}{2}$

# 4 Replacement sets of size 4

## 4.1 $123 \leftrightarrow 132 \leftrightarrow 213 \leftrightarrow 231$

**Lemma 4.1** Let $\sigma \in S_n$ have $\sigma_n = n$. Then $\sigma \in C_n(123, 132, 213, 231)$.
**Proof:** Beginning with the identity, we will show by induction on $k < n - 1$ that we can reach a permutation $\sigma^{(k)}$ in which the first $k$ elements are the same as those of $\sigma$ and the rest are in increasing order. The identity is $\sigma^{(0)}$. Suppose that we have reached $\sigma^{(k)}$. If $\sigma^{(k+1)} = \sigma^{(k)}$, we are done. Otherwise we use $123 \to 231$ as often as necessary to advance $\sigma_{k+1}$ (playing the role of 2), together with the element which follows it, to positions $k+1$ and $k+2$. (We know that there is a following element as $\sigma_n = n$.) Next we use $231 \to 213$ to switch the following element (playing the role of 3) to position $k+3$, when we can begin a chain of $132 \to 123$ to restore it to its original location. $\square$

**Proposition 4.1** Let $\sigma \in S_n$. Then $\sigma \in C_n(123, 132, 213, 231)$ if and only if $\sigma$ does not begin with $n$.

**Proof:** No permutation $\sigma \in C_n(123, 132, 213, 231)$ can begin with $n$ because $n$ can only participate in a transformation as a 3, and none of the transformations places a 3 in the leftmost position.

Conversely, let $\sigma$ be a permutation which does not begin with $n$, and let $\tau$ be the permutation obtained from $\sigma$ by deleting the $n$. By Lemma 4.1, we can obtain $\tau n$ from the identity. To obtain $\sigma$, we merely need to reposition the $n$, which we can do using $123 \to 132$ and $213 \to 231$ as necessary. $\square$

**Corollary 4.1** $c_n(123, 132, 213, 231) = n! - (n-1)! = (n-1) * (n-1)!$

$$4.2 \quad 123 \leftrightarrow 132 \leftrightarrow 231 \leftrightarrow 321$$

**Lemma 4.2** Let $\sigma \in S_n$ have $\sigma_1 = 1$. Then $\sigma \in C_n(123, 132, 231, 321)$.

**Proof:** We will show that we can obtain successively the permutations $\sigma^{(k)}$ in which the last $k$ elements match $\sigma$ and the first $n-k$ elements are in increasing order. The identity is $\sigma^{(0)}$. Suppose that we have obtained $\sigma^{(k)}$. By using $123 \to 231$ repeatedly, we can place $\sigma_{n-k} = \sigma_i^{(k)}$ in position $n-k$ or in position $n-k-1$. We remark that $i \neq 1$ because $\sigma_1^{(k)} = 1 = \sigma_1 \neq \sigma_{n-k}$. If $\sigma_{n-k}$ has arrived in position $n-k$ then we have constructed $\sigma^{(k+1)}$. If conversely it is in position $n-k-1$, then by using $123 \to 231$ repeatedly, we can move $\sigma_{i-1}^{(k)}$ to position $n-k-2$, then we can use $123 \to 132$ on the three elements $\sigma_{i-1}^{(k)}, \sigma_i^{(k)}, \sigma_{n-k}^{(k)}$, which moves $\sigma_i^{(k)} = \sigma_{n-k}$ to position $n-k$. Finally we use $231 \to 123$, with $\sigma_{i-1}^{(k)}$ in the role of 1, as often as necessary to return $\sigma_{i-1}^{(k)}$ to its original location, thus obtaining $\sigma^{(k+1)}$. $\square$

**Proposition 4.2** $\sigma \in C_n(123, 132, 231, 321)$ if and only if 1 occupies an odd position in $\sigma$.

**Proof:** In the identity, 1 occupies an odd position, and since 1 can only participate in a transformation as the smallest element, none of the possible transformations can change the parity of the position occupied by 1. Conversely, let $\sigma$ be a permutation having the element 1 in odd position, and let $\tau$ be the permutation obtained from $\sigma$ by deleting the 1. By Lemma 4.2, we can obtain $1\tau$ from the identity. Then we can use $123 \to 231$ or $132 \to 321$ as necessary to move the element 1 to its correct position. $\square$

**Corollary 4.2** The number of permutations equivalent to the identity under $123 \leftrightarrow 132 \leftrightarrow 231 \leftrightarrow 321$ is $c_n(123, 132, 231, 321) = (n-1)[\lceil \frac{n}{2} \rceil]$.

$$4.3 \quad 123 \leftrightarrow 132 \leftrightarrow 231 \leftrightarrow 312$$

**Proposition 4.3** The only permutations of length $n$ not belonging to $C_n(123, 132, 231, 312)$ are isolated permutations, i.e. belong to classes of size 1.
**Proof:** Suppose $\sigma$ belongs to a class $K$ of size greater than 1, and let $\tau$ be a permutation in $K$ having the smallest number of inversions. We will show that $\tau$ is the identity. First, $\tau$ cannot contain any 132, 231 or 312, because such a string could be replaced by 123, yielding a permutation with a strictly smaller number of inversions. But $K$ contains at least two permutations, therefore some replacement in $\tau$ is possible, and therefore $\tau$ contains a 123.

Now if $\tau$ is not the identity, because $\tau$ has no 231 or 132, $\tau$ must consist of a decreasing sequence followed by an increasing sequence. Consider the string at the junction of these two parts, $x1bc$, where $x > 1 < b < c$ (as $\tau$ is not the identity and contains a 123, $x$, $b$ and $c$ exist). Note that $x < b$ because $\tau$ contains no 312, so we have $1 < x < b < c$. Now we make the transformations $x1bc \rightarrow xc1b \rightarrow 1UNG \rightarrow 1xG$, arriving at a permutation with one fewer inversion than $\tau$. Therefore $\tau$ can only be the identity. $\square$

**Proposition 4.4** *The permutations which are not in $C_n(123, 132, 231, 312)$ are those which are obtained from $D_n = n(n-1)...1$ by taking an element other than 2 and placing it at the end.*

*Proof:* By proposition 4.3, the permutations not in $C_n(123, 132, 231, 312)$ are isolated, i.e. contain no 123, 132, 231 or 312. Because they have no 132 or 231, they must be a descending sequence followed by an increasing sequence. Because they have no 123, the increasing sequence can have length at most 2. Therefore they look like $D_n$ with one element (possibly 1) relocated to the end. But the relocated element cannot be 2 because the permutations contain no 312. $\square$

**Corollary 4.3** *The number of permutations in $C_n(123, 132, 231, 312)$ is $c_n(123, 132, 231, 312) = n! - (n-1)$. Moreover $\#\text{Classes}(n; \{123, 132, 231, 312\}) = n$.*

$$4.4 \quad 123 \leftrightarrow 132 \leftrightarrow 312 \leftrightarrow 321$$

**Proposition 4.5** *The only permutations of length $n$ not belonging to $C_n(123, 132, 312, 321)$ are isolated.*

*Proof:* Suppose $\sigma$ belongs to a class $K$ of size greater than 1, and let $\tau$ be a permutation in $K$ having the smallest number of inversions. We will show that $\tau$ is the identity. First, $\tau$ cannot contain any 132, 312 or 321, because such a string could be replaced by 123, yielding a permutation with a strictly smaller number of inversions. But $K$ contains at least two permutations, therefore some replacement in $\tau$ is possible, and therefore $\tau$ contains a 123. Now if $\tau$ is not the identity, it must either contain a 123 followed by a descent, or a 123 preceded by a descent. In the first case we have $abcx$ with $a < b < c$ and $b > x$ (because $\tau$ avoids 132), and we can make the transformations $abcx \rightarrow acbx \rightarrow axbc$, arriving at a permutation with two fewer inversions. In the second case we have $xabc$ with $a < b < c$ and $a < x < b$ ($\tau$ avoids 312), and we can make the transformations $xabc \rightarrow xcba \rightarrow cbxa \rightarrow caxb \rightarrow axcb \rightarrow axbc$, arriving at a permutation with one fewer inversion. Therefore $\tau$ can only be the identity. $\square$

**Proposition 4.6** *The permutations not belonging to $C_n(123, 132, 312, 321)$ are just the two wedge alterations open on the right as illustrated below.*

*Proof:* By proposition 4.5, the permutations not equivalent to the identity are those which contain no 123, 132, 312 or 321. Because there is no 123 or 321, the permutations must alternate ascents and descents. But because there is no 132 or 312, each descent must set a new left-to-right minimum, and each ascent a new left-to-right maximum. $\square$

<figure><img src="image_1.png" /></figure>
**Corollary 4.4** The number of permutations in $C_n(123, 132, 312, 321)$ is $c_n(123, 132, 312, 321) = n! - 2$.
Moreover $\#\text{Classes}(n; \{123, 132, 312, 321\}) = 3$.

$$4.5 \quad 123 \leftrightarrow 132 \leftrightarrow 213 \leftrightarrow 321$$

**Proposition 4.7** The only permutations not equivalent to the identity under $123 \leftrightarrow 132 \leftrightarrow 213 \leftrightarrow 321$ are the isolated permutations.

*Proof:* Suppose $\sigma$ belongs to a class $K$ of size greater than 1, and let $\tau$ be a permutation in $K$ having the smallest number of inversions. We will show that $\tau$ is the identity. First, $\tau$ cannot contain any 132, 213 or 321, because such a string could be replaced by 123, yielding a permutation with a strictly smaller number of inversions. But $K$ contains at least two permutations, therefore some replacement in $\tau$ is possible, and therefore $\tau$ contains a 123.

Now if $\tau$ is not the identity, it must either contain a 123 followed by a descent, or a 123 preceded by a descent. In the first case we have $abcx$ with $a < b < c$ and $b > x$ ($\tau$ avoids 132), and we can make the transformations $abcx \rightarrow acbx \rightarrow axbc$, arriving at a permutation with two fewer inversions. In the second case we have $xabc$ with $a < b < c$ and $x > b$ ($\tau$ avoids 213), and we can make the transformations $xabc \rightarrow xbac \rightarrow abxc$, arriving at a permutation with two fewer inversions. Therefore $\tau$ can only be the identity. $\square$

**Proposition 4.8** The only permutations not belonging to $C_n(123, 132, 213, 321)$ are the alternating permutations in which the elements in odd positions form a decreasing sequence, and the elements in even positions form also a decreasing sequence.

*Proof:* By Proposition 4.7, the permutations are those with none of the four patterns. Because there is no 123 or 321, these permutations must be alternating; because there is no 123, 132 or 213, two elements which are situated two positions apart must be decreasing. $\square$

**Proposition 4.9** The number of permutations in $C_n(123, 132, 213, 321)$ is $c_n(123, 132, 213, 321) = n! - c(\lfloor \frac{n-1}{2} \rfloor) - c(\lfloor \frac{n}{2} \rfloor)$, where $c(n)$ is the nth Catalan number.

*Proof:* We will denote the number of isolated permutations by $d_n$; as a result of proposition 4.7 we know that $c_n(123, 132, 213, 321) = n! - d_n$. The isolated permutations are the permutations which are alternating, and such that the sequences $(\sigma_{2k})_k$ and $(\sigma_{2k+1})_k$ are decreasing. It follows that $d_n = a_n + b_n$, where $a_n$ is the number of isolated permutations of size $n$ with $n$ in position 1, and $b_n$ is the number of isolated permutations of size $n$ with $n$ in position 2.

Let $\sigma$ be an isolated permutation of size $n$ with $n$ in position 1. We set $\alpha_k = n - \sigma_{2k+1} - k$ for $k \ge 0$. Since $(\sigma_{2k+1})_k$ decreases and $\sigma_1 = n$, $(\alpha_k)_k$ is non decreasing and $\alpha_0 = 0$. Moreover, because $\sigma$ is alternating and $(\sigma_{2k+1})_k$ and $(\sigma_{2k})_k$ are decreasing, $\forall k \ge 1$, $\sigma_{2k} < \sigma_{2k+1}$ and $\sigma_s < \sigma_{2k+1}$ if $2k + 2 \le s \le n$, so $\sigma_{2k+1} > n - 2k$ and $\alpha_k < k$ if $k \ge 1$.

If we represent the points $(k, \alpha_k)$ thus obtained, the result is a non-decreasing sequence of $\lceil n/2 \rceil$ points situated strictly below the diagonal, except for $\alpha_0 = 0$. We can verify that this map is bijective with such sequences of points, and thus with the set of Dyck paths of length $\lceil n/2 \rceil - 1 = \lfloor \frac{n-1}{2} \rfloor$: connect each point to the next with a sequence of rightward steps followed by a sequence of upward steps, and then rotate the resulting diagram accordingly Figure 1. Thus $a_n = c(\lfloor \frac{n-1}{2} \rfloor)$,

<figure><img src="image_2.png" /><figcaption>Fig. 1: $\sigma = 121011695837241$</figcaption></figure>
by the well-known Catalan enumeration of Dyck paths. Now let $\sigma$ be an isolated permutation with $\sigma_2 = n$, and set $\alpha_k = n+1-\sigma_{2k}-k$ for $k \ge 1$. As $(\sigma_{2k})_k$ is decreasing and $\sigma_2 = n$, $(\alpha_k)_k$ is non decreasing and $\alpha_1 = 0$. Furthermore, as $\sigma$ is alternating and $(\sigma_{2k})_k$ and $(\sigma_{2k+1})_k$ are decreasing, $\forall k \ge 1$, $\sigma_{2k-1} < \sigma_{2k}$ and $\sigma_s < \sigma_{2k}$ if $2k+1 \le s \le n$, so $\sigma_{2k} > n+1-2k$ and $\alpha_k < k$ if $k \ge 1$.

If we represent the points $(k, \alpha_k)$ thus obtained, the result is an increasing sequence of $\lfloor n/2 \rfloor$ points situated strictly below the diagonal. Again, this map is bijective, and by adding a point at $(0, 0)$ we have, as above, a bijection with Dyck paths of length $\lfloor \frac{n}{2} \rfloor$. So $b_n = c(\lfloor \frac{n}{2} \rfloor)$. $\square$

**Corollary 4.5** #Classes($n$; $\{123, 132, 213, 321\}$) = $c(\lfloor \frac{n-1}{2} \rfloor) + c(\lfloor \frac{n}{2} \rfloor) + 1$.

## 4.6 $123 \leftrightarrow 231 \leftrightarrow 312 \leftrightarrow 321$

The equivalence class of the identity under $123 \leftrightarrow 231 \leftrightarrow 312 \leftrightarrow 321$ consists of the reversals of the permutations in the equivalence class of $D_n = n, n-1, \dots, 1$ under the transformations $321 \leftrightarrow 132 \leftrightarrow 213 \leftrightarrow 123$, considered in the previous section. But we know that $D_n$ was in the class of the identity under these transformations, because it was not isolated. This observation gives us immediately:

**Proposition 4.10** The only permutations not belonging to $C_n(123, 231, 312, 321)$ are the alternating permutations in which the elements in odd positions form an increasing sequence, and the elements in even positions form an increasing sequence.

The number of permutations in $C_n(123, 231, 312, 321)$ is $c_n(123, 231, 312, 321) = n! - c(\lfloor \frac{n-1}{2} \rfloor) - c(\lfloor \frac{n}{2} \rfloor)$, where $c(n)$ is the nth Catalan number.

Moreover, #Classes($n$; $\{123, 231, 312, 321\}$) = $c(\lfloor \frac{n-1}{2} \rfloor) + c(\lfloor \frac{n}{2} \rfloor) + 1$.

# 5 Replacement sets of size 5

## 5.1 $123 \leftrightarrow 132 \leftrightarrow 213 \leftrightarrow 231 \leftrightarrow 312$

**Proposition 5.1** #Classes($n$; $\{123, 132, 213, 231, 312\}$) = 2, and the two equivalence classes are $C_n(123, 132, 213, 231, 312)$ and $\{D_n\}$ where $D_n = n(n-1)\dots 1$.

*Proof:* Let $\sigma$ be a permutation not in $C_n(123, 132, 213, 231, 312)$: by section 4.3, $\sigma_1 \dots \sigma_{n-1}$ is decreasing and $\sigma_n \ne 2$. And by section 4.1, applying reverse complements, $\sigma_n = 1$, and so $\sigma = D_n$. Conversely, it is clear that $D_n \notin C_n(123, 132, 213, 231, 312)$, because $D_n$ contains only the pattern 321 and so is isolated. $\square$

## 5.2 Remaining cases

**Proposition 5.2** If $n \ge 4$ there is only a single equivalence class for the sets $\{123, 132, 213, 231, 321\}$, $\{123, 132, 213, 312, 321\}$, $\{123, 132, 231, 312, 321\}$ or $\{123, 213, 231, 312, 321\}$.

*Proof:* We will prove the first of the four statements, as the four proofs are straightforward and all very similar. Suppose, conversely, that we can find a permutation $\sigma$ which is not in $C_n(123, 132, 213, 231, 321)$; then by section 4.4, applying reverse complements, $\sigma$ is a wedge alternation >, so by section 4.5 $\sigma$ is alternating and the sequences $(\sigma_{2k})_k$ and $(\sigma_{2k+1})_k$ are both decreasing, which is impossible. $\square$
## 6 Summary table

<table><thead><tr><th>Replacement set</th><th>Enumeration</th><th>Sloane</th><th>Proof</th><th>Characterisation</th></tr></thead><tbody><tr><td>123, 132 or 123, 213</td><td>[n/2]![n/2]!</td><td>A010551</td><td>[LPRW10]</td><td></td></tr><tr><td>123, 231</td><td>[n/2]![n/2]!</td><td>A010551</td><td>2.1</td><td>∀k the rank of σ<sub>k</sub> among σ<sub>1</sub> ... σ<sub>k</sub> is of the same parity as k</td></tr><tr><td>123, 312</td><td>[n/2]![n/2]!</td><td>A010551</td><td>2.1 (RC)</td><td>∀k the rank of σ<sub>k</sub> among σ<sub>k</sub> ... σ<sub>n</sub> is odd</td></tr><tr><td>123, 321</td><td>(<sup>n-1</sup>/<sub>l(n-1)/2</sub>)</td><td>A001405</td><td>[LPRW10]</td><td></td></tr><tr><td>123, 132, 213</td><td>[3, 7, 35, 135, 945]</td><td></td><td>[CEH<sup>+</sup>01]</td><td></td></tr><tr><td>123, 132, 231</td><td>n!(<sup>n-1</sup>/<sub>l(n-1)/2</sub>)/2<sup>n-1</sup></td><td>A000246</td><td>3.2</td><td>left-to-right minima are in odd position</td></tr><tr><td>123, 132, 312</td><td>n!/2</td><td>A001710</td><td>3.1 (RC)</td><td>1 is left of 2</td></tr><tr><td>123, 132, 321</td><td>[3, 9, 54, 285, 2160]</td><td></td><td>[LPRW10]</td><td></td></tr><tr><td>123, 213, 231</td><td>n!/2</td><td>A001710</td><td>3.1</td><td>n - 1 is left of n</td></tr><tr><td>123, 213, 312</td><td>n!(<sup>n-1</sup>/<sub>l(n-1)/2</sub>)/2<sup>n-1</sup></td><td>A000246</td><td>3.2 (RC)</td><td>right-to-left maxima are in positions of same parity as n</td></tr><tr><td>123, 213, 321</td><td>[3, 9, 54, 285, 2160]</td><td></td><td>[LPRW10]</td><td></td></tr><tr><td>123, 231, 312</td><td>[3, 8, 45, 313, 2310]</td><td></td><td>3.3</td><td>Non-isolated even permutations</td></tr><tr><td>123, 231, 321</td><td>[3, 9, 54, 285, 2160]</td><td></td><td>[LPRW10]</td><td></td></tr><tr><td>123, 312, 321</td><td>[3, 9, 54, 285, 2160]</td><td></td><td>[LPRW10]</td><td></td></tr><tr><td>123, 132, 213, 231</td><td>n! - (n - 1)!</td><td>4.1</td><td></td><td>σ<sub>1</sub> ≠ n</td></tr><tr><td>123, 132, 213, 312</td><td>n! - (n - 1)!</td><td>4.1 (RC)</td><td></td><td>σ<sub>n</sub> ≠ 1</td></tr><tr><td>123, 132, 213, 321</td><td>n! - c(<sup>n-1</sup>/<sub>2</sub>) - c(<sup>n</sup>/<sub>2</sub>)</td><td>4.5</td><td></td><td>σ is not alternating or the sequence (σ<sub>2k</sub>)<sub>k</sub> or (σ<sub>2k+1</sub>)<sub>k</sub> is not decreasing</td></tr><tr><td>123, 132, 231, 312</td><td>n! - (n - 1)</td><td>4.3</td><td></td><td>σ<sub>1</sub> ... σ<sub>n-1</sub> is not decreasing or σ<sub>n</sub> = 2</td></tr><tr><td>123, 132, 231, 321</td><td>(n - 1)![<sup>n</sup>/<sub>2</sub>]</td><td>4.2</td><td></td><td>1 is in odd position</td></tr><tr><td>123, 132, 312, 321</td><td>n! - 2</td><td>4.4</td><td></td><td>σ is not a wedge alternation &lt;</td></tr><tr><td>123, 213, 231, 312</td><td>n! - (n - 1)</td><td>4.3 (RC)</td><td></td><td>σ<sub>2</sub> ... σ<sub>n</sub> is not decreasing or σ<sub>1</sub> = n - 1</td></tr><tr><td>123, 213, 231, 321</td><td>n! - 2</td><td>4.4 (RC)</td><td></td><td>σ is not a wedge alternation &gt;</td></tr><tr><td>123, 213, 312, 321</td><td>(n - 1)![<sup>n</sup>/<sub>2</sub>]</td><td>4.2 (RC)</td><td></td><td>n and its position have the same parity</td></tr><tr><td>123, 231, 312, 321</td><td>n! - c(<sup>n-1</sup>/<sub>2</sub>) - c(<sup>n</sup>/<sub>2</sub>)</td><td>4.6</td><td></td><td>σ is not alternating or the sequence (σ<sub>2k</sub>)<sub>k</sub> or (σ<sub>2k+1</sub>)<sub>k</sub> is not increasing</td></tr><tr><td>123, 132, 213, 231, 312</td><td>n! - 1</td><td>5.1</td><td></td><td>All except n(n-1) ... 1</td></tr><tr><td>Other cases</td><td>n!</td><td>5.2</td><td></td><td>All</td></tr></tbody></table>

## References

[CEH<sup>+</sup>01] Julien Cassaigne, Marc Espie, Florent Hivert, Daniel Krob, and Jean-Christophe Novelli. The chinese monoid. *Internat. J. Algebra Comput.*, 11(3):301–334, 2001.

[KM05] Sergey Kitaev and Toufik Mansour. Simultaneous avoidance of generalized patterns. *Ars Combinatoria*, 75:267–288, 2005.

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

[LPRW10] Stephen Linton, James Propp, Tom Roby, and Julian West. Constrained swapping in permutations. In *Proceedings of FPSAC 2010*, 2010.