# Pattern avoiding alternating involutions

Marilena Barnabei
Dipartimento di Matematica
Università di Bologna, 40126, ITALY
<EMAIL_ADDRESS>Flavio Bonetti
P.A.M.
Università di Bologna, 40126, ITALY
<EMAIL_ADDRESS>Niccolò Castronuovo
Liceo “A. Einstein”, Rimini, 47923, ITALY
<EMAIL_ADDRESS>Matteo Silimbani
Istituto Comprensivo “E. Rosetti”, Forlimpopoli, 47034, ITALY
<EMAIL_ADDRESS>corresponding author

###### Abstract

We enumerate and characterize some classes of alternating and reverse
alternating involutions avoiding a single pattern of length three or four. If
on one hand the case of patterns of length three is trivial, on the other hand
the length four case is more challenging and involves sequences of
combinatorial interest, such as Motzkin and Fibonacci numbers.

2020 msc: 05A05, 05A15 (primary), 05A19 (secondary).

Keywords: permutation pattern, involution, alternating permutation.

##  1 Introduction

A permutation $\pi$ avoids a pattern $\tau$ whenever $\pi$ does not contain
any subsequence order-isomorphic to $\tau.$

The theory of permutation patterns goes back to the work of Knuth [9], who, in
the 1970’s, introduced the definition of pattern avoidance in connection to
the stack sorting problem. The first systematic study of these objects appears
in the paper by Simion and Schmidt ([16]). Nowadays, the theory is very rich
and widely expanded, with hundreds of papers appeared in the last decades (see
e.g. [8] and references therein).

More recently permutation patterns have been studied over particular subset of
the symmetric group. In particular pattern avoidance has been studied over
involutions (see e.g. [1, 4, 7, 8]) and over alternating permutations (see
e.g. [3, 5, 6, 8, 10, 11, 12, 22, 23]), i.e., permutations
$\pi=\pi_{1}\ldots\pi_{n}$ such that $\pi_{i}<\pi_{i+1}$ if and only if $i$ is
odd.

The enumeration of alternating involutions is due to Stanley (see [18] and
also his survey on alternating permutations [19]). However, to the best of our
knowledge, pattern avoiding alternating involutions have not been studied so
far.

In this paper we consider alternating involutions that avoid some patterns of
length three or four. If on one hand the case of patterns of length three is
trivial, on the other hand the length four case is more challenging and
involves sequences of combinatorial interest, such as Motzkin and Fibonacci
numbers.

##  2 Preliminaries

###  2.1 Permutations

Let $S_{n}$ be the symmetric group over the symbols $\\{1,2,\ldots\,n\\}.$ We
will often write permutations in $S_{n}$ in one line notation as
$\pi=\pi_{1}\ldots\pi_{n}.$ An involution is a permutation $\pi$ such that
$\pi=\pi^{-1}.$ The reverse of a permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$
is $\pi^{r}=\pi_{n}\pi_{n-1}\ldots\pi_{1}$ and the complement of $\pi$ is
$\pi^{c}=n+1-\pi_{1}\,n+1-\pi_{2}\ldots n+1-\pi_{n}.$ The reverse-complement
of $\pi$ is $\pi^{rc}=(\pi^{r})^{c}=(\pi^{c})^{r}.$ Notice that
$(\pi^{-1})^{rc}=(\pi^{rc})^{-1}.$ In particular the reverse-complement of an
involution is an involution.

A descent in a permutation $\pi$ is an index $i$ such that
$\pi_{i}>\pi_{i+1}.$ Denote by $\operatorname*{Des}(\pi)$ the set of descents
of $\pi$ and by $\operatorname*{des}(\pi)$ its cardinality.

Recall that a left-to-right minimum (ltr minimum from now on) of a permutation
$\pi$ is a value $\pi(i)$ such that $\pi(j)>\pi(i)$ for every $j<i.$ A left-
to-right maximum (ltr maximum from now on) is a value $\pi(i)$ such that
$\pi(j)<\pi(i)$ for every $j<i.$ The definition of right-to-left (rtl) minimum
and maximum is analogous.

######  Lemma 2.1.

In any involution $\pi$ the ltr minima form an involution themselves, i.e., a
ltr minimum $m$ is at position $i$ if and only if $i$ is a ltr minimum. The
same is true for rtl maxima.

###### Proof.

We will consider only the case of ltr minima, since the other case is
analogous. Denote by $m_{1},m_{2},\ldots,m_{k}$ the left-to-right minima of
$\pi$, and by $i_{1},i_{2}\ldots,i_{k}$ their respective positions. We want to
show that

$\\{m_{1},m_{2},\ldots,m_{k}\\}=\\{i_{1},i_{2}\ldots,i_{k}\\}.$

Suppose on the contrary that there exists an index $j$ such that $i_{j}$ is
not the value of a left-to-right minimum. Then, to the left of $i_{j}$ in
$\pi$ there is a symbol $a$ less than $i_{j}.$ In other terms, there exist two
integers $a,h$ such that $\pi(h)=a,$ $a<i_{j}$ and $h<m_{j}.$ In this
situation, $m_{j}$ is not a left-to-right minimum, since it is preceded by
$h,$ and $h<m_{j},$ contradiction. ∎

######  Example 2.2.

Consider the involution $\pi=7\,9\,4\,3\,5\,6\,1\,10\,2\,8.$ The ltr minima of
$\pi$ are 7,4,3,1 and they form an involution themselves. The same is true for
the rtl maxima 8 and 10.

Given a word $w=w_{1}\ldots w_{j}$ whose letters are distinct numbers, the
standardization of $w$ is the unique permutation $\pi$ in $S_{j}$ order
isomorphic to $w.$ If two words $w$ and $u$ have the same standardization we
write $u\sim w.$

The decomposition into connected components of a permutation $\pi$ is the
finest way to write $\pi$ as $\pi=w_{1}w_{2}\ldots w_{k},$ where each $w_{i}$
is a permutation of the symbols from $|w_{1}|+|w_{2}|+\ldots+|w_{i-1}|+1$ to
$|w_{1}|+|w_{2}|+\ldots+|w_{i-1}|+|w_{i}|.$ Each $w_{i}$ is called a connected
component of $\pi.$ A permutation is said to be connected if it is composed by
only one connected component.

######  Example 2.3.

The decomposition into connected components of the permutation $\pi=34215786$
is $\pi=w_{1}w_{2}w_{3},$ where $w_{1}=3421,$ $w_{2}=5,$ $w_{3}=786.$

###  2.2 Alternating permutations

A permutation $\pi=\pi_{1}\ldots\pi_{n}$ is said to be alternating if
$\pi_{i}<\pi_{i+1}$ if and only if $i$ is odd and reverse alternating if and
only if $\pi_{i}>\pi_{i+1}$ if and only if $i$ is odd. Equivalently, a
permutation $\pi$ is alternating whenever
$\operatorname*{Des}(\pi)=\\{2,4,6,\ldots\\}.$

######  Example 2.4.

The permutation $\pi=4615273$ is alternating, while $\sigma=5372614$ is
reverse alternating.

Denote by $S_{n}$ ($I_{n},$ $A_{n},$ $RA_{n},$ $AI_{n}$ and $RAI_{n},$
respectively) the set of permutations (involutions, alternating permutations,
reverse alternating permutations, alternating involutions, reverse alternating
involutions, respectively) of length $n.$

The following lemma will be useful in the sequel.

######  Lemma 2.5.

  * i)

Let $\pi=\pi_{1}\ldots\pi_{n}\in RAI_{n}.$ Then $1$ is in even position, $n$
is in odd position, hence $\pi_{1}$ is even and $\pi_{n}$ is odd.

  * ii)

Let $\pi=\pi_{1}\ldots\pi_{n}\in AI_{n}.$ Then $1$ is in odd position, $n$ is
in even position, hence $\pi_{1}$ is odd and $\pi_{n}$ is even.

###  2.3 Pattern avoidance

A permutation $\sigma=\sigma_{1}\ldots\sigma_{n}\in S_{n}$ avoids the pattern
$\tau\in S_{k}$ if there are no indices $i_{1},i_{2},\ldots,i_{k}$ such that
the subsequence $\sigma_{i_{1}}\sigma_{i_{2}}\ldots\sigma_{i_{k}}$ is order
isomorphic to $\tau.$

Denote by $S_{n}(\tau)$ the set of permutations of length $n$ avoiding $\tau$
and let $S(\tau):=\bigcup_{n}S_{n}(\tau).$ We will keep this notation also
when $S_{n}$ is replaced by other subsets of permutations, such as $I_{n},$
$A_{n},$ etc.

Notice that an involution avoids $\tau$ if and only if it avoids $\tau^{-1}.$

The next trivial lemma will be useful in the sequel.

######  Lemma 2.6.

The reverse-complement map is a bijection between $AI_{2n+1}(\tau)$ and
$RAI_{2n+1}(\tau^{rc}),$ between $AI_{2n}(\tau)$ and $AI_{2n}(\tau^{rc})$ and
between $RAI_{2n}(\tau)$ and $RAI_{2n}(\tau^{rc}).$

###  2.4 Motzkin paths

A Motzkin path of length $n$ is a lattice path starting at $(0,0),$ ending at
$(n,0),$ consisting of up steps $U$ of the form $(1,1),$ down steps $D$ of the
form $(1,-1),$ and horizontal steps $H$ of the form $(1,0),$ and lying weakly
above the $x$-axis. As usual, a Motzkin path can be identified with a Motzkin
word, namely, a word $w=w_{1}w_{2}\ldots w_{n}$ of length $n$ in the alphabet
$\\{U,D,H\\}$ with the constraint that the number of occurrences of the letter
$U$ is equal to the number of occurrences of the letter $D$ and, for every
$i,$ the number of occurrences of $U$ in the subword $w_{1}w_{2}\ldots w_{i}$
is not smaller than the number of occurrences of $D.$ In the following we will
not distinguish between a Motzkin path and the corresponding word. Denote by
$\mathcal{M}_{n}$ the set of Motzkin path of length $n$ and by $M_{n}$ its
cardinality, the $n$-th Motzkin number (see sequence A001006 in [17]). The
diod decomposition of a Motzkin path $m$ of even length $2n$ is the
decomposition of $m$ as $m=d_{1}d_{2}\ldots d_{n},$ where each $d_{i}$ is a
subword of $m$ of length two. Each $d_{i}$ in the diod decomposition of a
Motzkin path is called a diod of $m.$

##  3 General results

In this section we prove two general results which will be used in the paper.

######  Lemma 3.1.

Let $\tau$ be any permutation of $\\{3,\ldots,m\\},$ $m\geq 3,$ Then

$|AI_{n}(12\tau)|=|AI_{n}(21\tau)|.$

###### Proof.

We closely follow [15], where a similar result is proved for doubly
alternating permutations, i.e., alternating permutations whose inverse is also
alternating.

Our goal is to find a bijection between
$AI_{n}(12\tau)=AI_{n}(12\tau,12\tau^{-1})$ and
$AI_{n}(21\tau)=AI_{n}(21\tau,21\tau^{-1}).$

We will use the diagrammatic representation of a permutation, i.e., we will
identify a permutation $\pi$ in $S_{n}$ with a $n\times n$ diagram with a dot
at position $(i,\pi_{i}),$ for every $i$ (notice that Ouchterlony [15] uses a
slightly different definition for the diagram of a permutation).

A dot, $d,$ in the diagram of a permutation $\pi$ is called active if $d$ is
the 1 or 2 in any $12\tau,$ $12\tau^{-1},$ $21\tau$ or $21\tau^{-1}$ pattern
in $\pi,$ or inactive otherwise. Also the pair of dots $(d_{1},d_{2})$ is
called an active pair if $d_{1}d_{2}$ is the $12$ in a $12\tau$ or
$12\tau^{-1}$ pattern or the $21$ in a $21\tau$ or $21\tau^{-1}$ pattern.

We now define a Young diagram, $\lambda_{\pi},$ consisting of the part of the
diagram of $\pi$ which contains the active dots. For any two dots
$d_{1},d_{2},$ let $R_{d_{1},d_{2}}$ be the smallest rectangle with bottom
left coordinates (1, 1), such that $d_{1},d_{2}\in R_{d_{1},d_{2}}.$ Define

$\lambda_{\pi}=\bigcup R_{d_{1},d_{2}},$

where the union is over all active pairs $(d_{1},d_{2})$ of $\pi.$ It is clear
from the definition that $\lambda_{\pi}$ is indeed a Young diagram. Since
$\pi$ is an involution, its diagram is symmetric with respect to the main
diagonal, and for every active dot in position $(i,j)$ there is also an active
dot in position $(j,i),$ hence $\lambda_{\pi}$ is a Young diagram symmetric
with respect to the main diagonal.

A rook placement of a Young diagram $\lambda$ is a placement of dots in its
boxes, such that all rows and columns contain exactly one dot. If some of the
rows or columns are empty we call it a partial rook placement. Furthermore, we
say that a rook placement on $\lambda$ avoids the pattern $\tau$ if no
rectangle, $R\subseteq\lambda,$ contains $\tau.$ Notice that the rook
placement on $\lambda_{\pi}$ induced by an involution $\pi$ is symmetric.

Now, it has been proved by Jaggard [7, Theorem 4.2], that the number of
symmetric rook placements on the self-conjugate shape $\mu$ avoiding the
patterns $12\tau$ and $12\tau^{-1}$ is equal to the number of symmetric rook
placements on the self-conjugate shape $\mu$ avoiding the patterns $21\tau$
and $21\tau^{-1}.$

We call two permutations $\pi$ and $\sigma$ of the same size a-equivalent if
they have the same inactive dots, and write $\pi\sim_{a}\sigma.$

In the sequel we will need the following three facts that are immediate
consequences of Lemma 6.4, Lemma 6.3 and Lemma 6.2 in [15], respectively.

  * (I)

$\pi\sim_{a}\sigma\Rightarrow\lambda_{\pi}=\lambda_{\sigma}.$

  * (II)

If $\pi\in AI_{n}(12\tau,12\tau^{-1})\cup AI_{n}(21\tau,21\tau^{-1})$ and
$\pi\sim_{a}\sigma$ then $\sigma$ is doubly alternating.

  * (III)

If $\pi\in AI_{n}$ and $rp(\lambda_{\pi})$ is the partial rook placement on
$\lambda_{\pi}$ induced by $\pi,$ then

$\pi\in AI_{n}(12\tau,12\tau^{-1})\Leftrightarrow rp(\lambda_{\pi})\mbox{ is
}12\mbox{-avoiding}$

and

$\pi\in AI_{n}(21\tau,21\tau^{-1})\Leftrightarrow rp(\lambda_{\pi})\mbox{ is
}21\mbox{-avoiding}.$

Now we are ready to construct a bijection

$\phi:AI_{n}(12\tau,12\tau^{-1})\to AI_{n}(21\tau,21\tau^{-1}).$

Let $\pi\in AI_{n}(12\tau,12\tau^{-1}),$ so that the restriction of $\pi$ to
$\lambda_{\pi}$ is a partial $12$-avoiding symmetric rook placement. By
Jaggard’s theorem (ignoring the empty rows and columns) and by point (I) there
exists a unique $21$-avoiding (partial) symmetric rook placement on
$\lambda_{\pi}$ with the same rows and columns empty, which we combine with
the inactive dots of $\pi$ to get $\phi(\pi).$ By point (II), $\phi(\pi)$ is
doubly alternating and, since its diagram is symmetric, it is an involution.
By point (III) it avoids $21\tau$ (and hence also $21\tau^{-1}$). It is also
clear from Jaggard’s theorem that $\phi$ is indeed a bijection.

∎

######  Example 3.2.

Consider the permutation $\pi=593716482\in AI_{9}(12435).$ Notice that $\pi$
contains the pattern $21435.$ Here $\tau=435.$ The diagram of $\pi$ is the
following

The blue dots are the active dots of $\pi$ and the red Young diagram is
$\lambda_{\pi}.$ Now applying to $\lambda_{\pi}$ the procedure described in
the above proof we get $\phi(\pi)=195736482\in AI_{9}(21435).$

It follows from the previous lemma and Lemma 2.6 that if $\tau$ is any
permutation of $\\{1,\ldots,k-2\\}$ then

$|AI_{2n}(\tau\,k-1\,k)|=|AI_{2n}(\tau\,k\,k-1)|$

and

$|RAI_{2n+1}(\tau\,k-1\,k)|=|RAI_{2n+1}(\tau\,k\,k-1)|.$

Notice that similar relations do not hold for $RAI_{2n},$ in fact, numerical
computations show that, for general $n,$
$|RAI_{2n}(1234)|\neq|RAI_{2n}(1243)|$ and
$|RAI_{2n}(1234)|\neq|RAI_{2n}(2134)|.$

When $\tau$ is an increasing sequence it is possible to provide a more
explicit bijection $f$ between $|AI_{2n}(\tau\,k-1\,k)|$ and
$|AI_{2n}(\tau\,k\,k-1)|.$ Such a bijection has been defined for the first
time by J. West [21] for permutations and has been used by M. Bóna [3] to
prove a conjecture by J. B. Lewis about alternating permutations. To this aim
Bóna proved that $f$ preserves the alternating property when the length of the
permutation is even. Here we recall the definition of the map
$f:S_{t}(12\ldots\,k-1\,k)\to S_{t}(12\ldots\,k\,k-1).$ Consider a permutation
$\pi\in S_{t}(12\ldots\,k-1\,k)$ and define the rank of the element $\pi_{i}$
to be the maximum length of an increasing subsequence ending at $\pi_{i}.$
Since $\pi$ avoids $12\ldots\,k-1\,k,$ the maximal rank of an element is
$k-1.$ Let $R$ be the set of elements of $\pi$ whose rank is $k-1,$ and $P$
the set of their positions. The permutation $\rho=f(\pi)$ is obtained as
follows.

  * •

if $j\notin P,$ $\rho_{j}=\pi_{j},$

  * •

if $j\in P,$ $\rho_{j}$ is the smallest unused element of $R$ that is larger
than the closest entry of rank $k-2$ to the left of $\pi_{j}.$

Notice that, if $k=3,$ the map $f$ reduces to the classic Simion-Schmidt
bijection ([16], [21]).

In the following lemma we prove that $f$ preserves also the property of being
an involution and we describe what happens in the odd case.

######  Lemma 3.3.

The map $f$ is a bijection between $AI_{2n}(12\ldots\,k-1\,k)$ and
$AI_{2n}(12\ldots\,k\,k-1).$ Moreover, $f$ maps bijectively the subset of
$AI_{2n+1}(1234)$ of those permutations having $2n+1$ at position 2 to the set
$AI_{2n+1}(1243).$

###### Proof.

First of all we notice that, in an involution $\pi,$ all the elements of a
given rank form an involution. To prove this fact it is sufficient to observe
that elements of $\pi$ of rank 1 are the ltr minima of the permutation, which
form an involution (see Lemma 2.1). We can consider the involution obtained
removing from $\pi$ the elements of rank 1 and proceed inductively.

Now we want to prove that $f$ sends involutions of lenght $n$ to involutions
of length $n$ (for every length $n$). Also in this case we can obtain the
result by induction on $k.$ When $k=3,$ we noticed above that $f$ coincides
with the Simion-Schmidt map ([16]), and it is well-known that this map sends
involutions to involutions. If $k>3,$ we can delete from $\pi$ the elements of
rank 1 and standardize, obtaining an involution $\pi^{\prime}$ which avoids
$12\ldots\,k-2\;\,k-1.$ If we apply the map $f,$ we obtain an involution
avoiding $12\ldots\,k-1\;\,k-2$ which can be obtained from $f(\pi)$ by
removing the elements of rank 1 and standardizing. Hence also $f(\pi)$ is an
involution. The fact that $f$ preserves the alternating property (when the
length is even) has been proved by Bóna [3, Theorem 1].

Now we turn our attention to the second assertion. We want to prove that
$f^{-1}$ maps bijectively the set $AI_{2n+1}(1243)$ onto the set
$Y_{2n+1}=AI_{2n+1}(1234)\cap\\{\pi\in S_{2n+1}\,|\,\pi(2)=2n+1\\}.$

The fact that the injective map $f^{-1}$ preserves the alternating property
has been already observed by Bóna [3, Corollary 1]. Moreover $f^{-1}$
preserves the involutory property, as proved above.

Now consider $\pi\in AI_{2n+1}(1243).$ The symbol $2n+1$ appears at even
position $a.$ Suppose that $a\geq 4.$ Then $\pi_{2}=2n,$ otherwise
$\pi_{1}\;\,\pi_{2}\;\,2n+1\;\,2n\sim 1243.$ As a consequence,
$\pi_{2n+1}=a>2=\pi_{2n}$ which is impossible since $\pi$ is alternating.
Hence $a=2$ and $\pi_{2}=2n+1.$

Since for every $\pi\in AI_{2n+1}(1243),$ $\pi(2)=2n+1,$ the symbols $2n+1$
and $2$ have rank $2.$ The map $f^{-1}$ fixes the elements of rank $k-2$ or
less, hence it fixes the positions of $2n+1$ and $2.$

With similar arguments one can show that $f(Y_{2n+1})\subseteq
AI_{2n+1}(1243)$ and conclude that $f(Y_{2n+1})=AI_{2n+1}(1243).$

∎

######  Example 3.4.

Consider the permutation $\pi=5\,9\,7\,10\,1\,8\,3\,6\,2\,4\in AI_{10}(1234).$
The elements of rank 1 are 5 and 1, the elements of rank 2 are 9,7,3 and 2,
the elements of rank 3 are 10, 8, 6 and 4. Then
$f(\pi)=5\,9\,7\,8\,1\,10\,3\,4\,2\,6\in AI_{10}(1243).$

##  4 Patterns of length three

The following proposition is an easy consequence of Proposition 3.1 in [15].
See also [14].

######  Proposition 4.1.

$|AI_{n}(123)|=|AI_{n}(213)|=|AI_{n}(231)|=|AI_{n}(231)|=$
$|RAI_{n}(132)|=|RAI_{n}(231)|=|RAI_{n}(312)|=|RAI_{n}(321)|=1$
$|AI_{n}(132)|=|RAI_{n}(213)|=\begin{cases}1&\mbox{ if }n\mbox{ is even or
}n=1\\\ 0&\mbox{ otherwise}.\end{cases}$
$|AI_{n}(321)|=|RAI_{n}(123)|=\begin{cases}2&\mbox{ if }n\mbox{ is even and
}n\geq 4\\\ 1&\mbox{ otherwise}.\end{cases}$

##  5 Patterns 4321 and 1234

We recall the definition of a bijection $\Phi$ between the set $I_{n}(4321)$
of $4321$-avoiding involutions of the symmetric group $S_{n}$ and the set
$\mathcal{M}_{n}$ of Motzkin paths of length $n$ (see [1]), that is
essentially a restriction to the set $I_{n}(4321)$ of the bijection appearing
in [2].

Consider an involution $\tau$ avoiding $4321$ and determine the set
$exc(\tau)=\\{i|\tau(i)>i\\}$ of its excedances. Start from the empty path and
create the Motzkin path $\Phi(\tau)$ by adding a step for every integer $1\leq
i\leq n$ as follows:

  * •

if $\tau(i)=i,$ add a horizontal step at the $i$-th position;

  * •

if $\tau(i)>i,$ add an up step at the $i$-th position;

  * •

if $\tau(i)<i,$ add a down step at the $i$-th position.

The map $\Phi$ is a bijection whose inverse can be described as follows.

Given a Motzkin path $M,$ let $A=(a_{1},\ldots,a_{k})$ be the list of
positions of up steps in $M,$ written in increasing order, and let
$B=(b_{1},\ldots,b_{k})$ the analogous list of positions of down steps. Then
$\Phi^{-1}(M)$ is the involution $\tau$ given by the product of the cycles
$(a_{i},b_{i})$ for $1\leq i\leq k.$

######  Lemma 5.1.

$\Phi$ maps the set $RAI_{2n}(4321)$ onto the set $\widehat{\mathcal{M}}_{2n}$
of Motzkin paths of length $2n$ whose diods are either of the form $UH,$ $HD$
or $UD.$

###### Proof.

Let $\tau\in RAI_{2n}(4321).$ For every integer $k=1,2,\ldots,2n-1,$ if $k$ is
odd, and hence a descent of $\tau$ , $\tau_{k}\tau_{k+1}$ is mapped by $\Phi$
to one of the following pairs: $UH,$ $UD,$ $HD.$ ∎

######  Theorem 5.2.

$|RAI_{2n}(4321)|=M_{n}.$

###### Proof.

The previous lemma allows us to define a bijection
$\hat{\Phi}:RAI_{2n}(4321)\to\mathcal{M}_{n}.$ Let $m=d_{1}d_{2}\ldots d_{n}$
be a Motzkin path (of even length) whose diods $d_{i}$ are either of the form
$UH,$ $UD$ or $HD.$ Define $\Delta(m):=s_{1}\ldots s_{n}\in\mathcal{M}_{n}$
where

$s_{i}=\begin{cases}U&\mbox{ if }d_{i}=UH\\\ D&\mbox{ if }d_{i}=HD\\\ H&\mbox{
if }d_{i}=UD.\end{cases}$

Set now $\hat{\Phi}=\Delta\circ\Phi.$ ∎

######  Example 5.3.

Consider $\pi=6\,2\,8\,4\,5\,1\,10\,3\,9\,7\in RAI_{10}(4321).$

Then

$\Phi(\pi)=\leavevmode\hbox to145.51pt{\vbox
to31.7pt{\pgfpicture\makeatletter\hbox{\hskip 1.62263pt\lower-1.62263pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{143.68643pt}{0.0pt}\pgfsys@curveto{143.68643pt}{0.7857pt}{143.0495pt}{1.42264pt}{142.2638pt}{1.42264pt}\pgfsys@curveto{141.47809pt}{1.42264pt}{140.84116pt}{0.7857pt}{140.84116pt}{0.0pt}\pgfsys@curveto{140.84116pt}{-0.7857pt}{141.47809pt}{-1.42264pt}{142.2638pt}{-1.42264pt}\pgfsys@curveto{143.0495pt}{-1.42264pt}{143.68643pt}{-0.7857pt}{143.68643pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{142.2638pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{142.2638pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{129.46005pt}{14.22638pt}\pgfsys@curveto{129.46005pt}{15.01208pt}{128.82312pt}{15.64902pt}{128.03741pt}{15.64902pt}\pgfsys@curveto{127.25171pt}{15.64902pt}{126.61478pt}{15.01208pt}{126.61478pt}{14.22638pt}\pgfsys@curveto{126.61478pt}{13.44067pt}{127.25171pt}{12.80374pt}{128.03741pt}{12.80374pt}\pgfsys@curveto{128.82312pt}{12.80374pt}{129.46005pt}{13.44067pt}{129.46005pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{128.03741pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{128.03741pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{115.23367pt}{14.22638pt}\pgfsys@curveto{115.23367pt}{15.01208pt}{114.59674pt}{15.64902pt}{113.81104pt}{15.64902pt}\pgfsys@curveto{113.02533pt}{15.64902pt}{112.3884pt}{15.01208pt}{112.3884pt}{14.22638pt}\pgfsys@curveto{112.3884pt}{13.44067pt}{113.02533pt}{12.80374pt}{113.81104pt}{12.80374pt}\pgfsys@curveto{114.59674pt}{12.80374pt}{115.23367pt}{13.44067pt}{115.23367pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{113.81104pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{113.81104pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{101.0073pt}{28.45276pt}\pgfsys@curveto{101.0073pt}{29.23846pt}{100.37036pt}{29.8754pt}{99.58466pt}{29.8754pt}\pgfsys@curveto{98.79895pt}{29.8754pt}{98.16202pt}{29.23846pt}{98.16202pt}{28.45276pt}\pgfsys@curveto{98.16202pt}{27.66705pt}{98.79895pt}{27.03012pt}{99.58466pt}{27.03012pt}\pgfsys@curveto{100.37036pt}{27.03012pt}{101.0073pt}{27.66705pt}{101.0073pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{99.58466pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{99.58466pt}{28.45276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{86.78091pt}{14.22638pt}\pgfsys@curveto{86.78091pt}{15.01208pt}{86.14398pt}{15.64902pt}{85.35828pt}{15.64902pt}\pgfsys@curveto{84.57257pt}{15.64902pt}{83.93564pt}{15.01208pt}{83.93564pt}{14.22638pt}\pgfsys@curveto{83.93564pt}{13.44067pt}{84.57257pt}{12.80374pt}{85.35828pt}{12.80374pt}\pgfsys@curveto{86.14398pt}{12.80374pt}{86.78091pt}{13.44067pt}{86.78091pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{85.35828pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{72.55453pt}{28.45276pt}\pgfsys@curveto{72.55453pt}{29.23846pt}{71.9176pt}{29.8754pt}{71.1319pt}{29.8754pt}\pgfsys@curveto{70.34619pt}{29.8754pt}{69.70926pt}{29.23846pt}{69.70926pt}{28.45276pt}\pgfsys@curveto{69.70926pt}{27.66705pt}{70.34619pt}{27.03012pt}{71.1319pt}{27.03012pt}\pgfsys@curveto{71.9176pt}{27.03012pt}{72.55453pt}{27.66705pt}{72.55453pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{71.1319pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{71.1319pt}{28.45276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{58.32816pt}{28.45276pt}\pgfsys@curveto{58.32816pt}{29.23846pt}{57.69122pt}{29.8754pt}{56.90552pt}{29.8754pt}\pgfsys@curveto{56.11981pt}{29.8754pt}{55.48288pt}{29.23846pt}{55.48288pt}{28.45276pt}\pgfsys@curveto{55.48288pt}{27.66705pt}{56.11981pt}{27.03012pt}{56.90552pt}{27.03012pt}\pgfsys@curveto{57.69122pt}{27.03012pt}{58.32816pt}{27.66705pt}{58.32816pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{56.90552pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{56.90552pt}{28.45276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{44.10178pt}{28.45276pt}\pgfsys@curveto{44.10178pt}{29.23846pt}{43.46484pt}{29.8754pt}{42.67914pt}{29.8754pt}\pgfsys@curveto{41.89343pt}{29.8754pt}{41.2565pt}{29.23846pt}{41.2565pt}{28.45276pt}\pgfsys@curveto{41.2565pt}{27.66705pt}{41.89343pt}{27.03012pt}{42.67914pt}{27.03012pt}\pgfsys@curveto{43.46484pt}{27.03012pt}{44.10178pt}{27.66705pt}{44.10178pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{42.67914pt}{28.45276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{29.8754pt}{14.22638pt}\pgfsys@curveto{29.8754pt}{15.01208pt}{29.23846pt}{15.64902pt}{28.45276pt}{15.64902pt}\pgfsys@curveto{27.66705pt}{15.64902pt}{27.03012pt}{15.01208pt}{27.03012pt}{14.22638pt}\pgfsys@curveto{27.03012pt}{13.44067pt}{27.66705pt}{12.80374pt}{28.45276pt}{12.80374pt}\pgfsys@curveto{29.23846pt}{12.80374pt}{29.8754pt}{13.44067pt}{29.8754pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{28.45276pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{15.64902pt}{14.22638pt}\pgfsys@curveto{15.64902pt}{15.01208pt}{15.01208pt}{15.64902pt}{14.22638pt}{15.64902pt}\pgfsys@curveto{13.44067pt}{15.64902pt}{12.80374pt}{15.01208pt}{12.80374pt}{14.22638pt}\pgfsys@curveto{12.80374pt}{13.44067pt}{13.44067pt}{12.80374pt}{14.22638pt}{12.80374pt}\pgfsys@curveto{15.01208pt}{12.80374pt}{15.64902pt}{13.44067pt}{15.64902pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{14.22638pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{1.42264pt}{0.0pt}\pgfsys@curveto{1.42264pt}{0.7857pt}{0.7857pt}{1.42264pt}{0.0pt}{1.42264pt}\pgfsys@curveto{-0.7857pt}{1.42264pt}{-1.42264pt}{0.7857pt}{-1.42264pt}{0.0pt}\pgfsys@curveto{-1.42264pt}{-0.7857pt}{-0.7857pt}{-1.42264pt}{0.0pt}{-1.42264pt}\pgfsys@curveto{0.7857pt}{-1.42264pt}{1.42264pt}{-0.7857pt}{1.42264pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{1.14737pt}{1.14737pt}\pgfsys@lineto{13.07901pt}{13.07901pt}\pgfsys@moveto{15.84901pt}{14.22638pt}\pgfsys@lineto{26.83012pt}{14.22638pt}\pgfsys@moveto{29.60013pt}{15.37375pt}\pgfsys@lineto{41.53177pt}{27.30539pt}\pgfsys@moveto{44.30177pt}{28.45276pt}\pgfsys@lineto{55.28288pt}{28.45276pt}\pgfsys@moveto{58.52815pt}{28.45276pt}\pgfsys@lineto{69.50926pt}{28.45276pt}\pgfsys@moveto{72.27927pt}{27.30539pt}\pgfsys@lineto{84.2109pt}{15.37375pt}\pgfsys@moveto{86.50565pt}{15.37375pt}\pgfsys@lineto{98.43729pt}{27.30539pt}\pgfsys@moveto{100.73203pt}{27.30539pt}\pgfsys@lineto{112.66367pt}{15.37375pt}\pgfsys@moveto{115.43367pt}{14.22638pt}\pgfsys@lineto{126.41478pt}{14.22638pt}\pgfsys@moveto{129.18478pt}{13.07901pt}\pgfsys@lineto{141.11642pt}{1.14737pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$

and

$\widehat{\Phi}(\pi)=\leavevmode\hbox to74.38pt{\vbox
to31.7pt{\pgfpicture\makeatletter\hbox{\hskip 1.62263pt\lower-1.62263pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{72.55453pt}{0.0pt}\pgfsys@curveto{72.55453pt}{0.7857pt}{71.9176pt}{1.42264pt}{71.1319pt}{1.42264pt}\pgfsys@curveto{70.34619pt}{1.42264pt}{69.70926pt}{0.7857pt}{69.70926pt}{0.0pt}\pgfsys@curveto{69.70926pt}{-0.7857pt}{70.34619pt}{-1.42264pt}{71.1319pt}{-1.42264pt}\pgfsys@curveto{71.9176pt}{-1.42264pt}{72.55453pt}{-0.7857pt}{72.55453pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{71.1319pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{71.1319pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{58.32816pt}{14.22638pt}\pgfsys@curveto{58.32816pt}{15.01208pt}{57.69122pt}{15.64902pt}{56.90552pt}{15.64902pt}\pgfsys@curveto{56.11981pt}{15.64902pt}{55.48288pt}{15.01208pt}{55.48288pt}{14.22638pt}\pgfsys@curveto{55.48288pt}{13.44067pt}{56.11981pt}{12.80374pt}{56.90552pt}{12.80374pt}\pgfsys@curveto{57.69122pt}{12.80374pt}{58.32816pt}{13.44067pt}{58.32816pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{56.90552pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{56.90552pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{44.10178pt}{14.22638pt}\pgfsys@curveto{44.10178pt}{15.01208pt}{43.46484pt}{15.64902pt}{42.67914pt}{15.64902pt}\pgfsys@curveto{41.89343pt}{15.64902pt}{41.2565pt}{15.01208pt}{41.2565pt}{14.22638pt}\pgfsys@curveto{41.2565pt}{13.44067pt}{41.89343pt}{12.80374pt}{42.67914pt}{12.80374pt}\pgfsys@curveto{43.46484pt}{12.80374pt}{44.10178pt}{13.44067pt}{44.10178pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{42.67914pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{29.8754pt}{28.45276pt}\pgfsys@curveto{29.8754pt}{29.23846pt}{29.23846pt}{29.8754pt}{28.45276pt}{29.8754pt}\pgfsys@curveto{27.66705pt}{29.8754pt}{27.03012pt}{29.23846pt}{27.03012pt}{28.45276pt}\pgfsys@curveto{27.03012pt}{27.66705pt}{27.66705pt}{27.03012pt}{28.45276pt}{27.03012pt}\pgfsys@curveto{29.23846pt}{27.03012pt}{29.8754pt}{27.66705pt}{29.8754pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{28.45276pt}{28.45276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{15.64902pt}{14.22638pt}\pgfsys@curveto{15.64902pt}{15.01208pt}{15.01208pt}{15.64902pt}{14.22638pt}{15.64902pt}\pgfsys@curveto{13.44067pt}{15.64902pt}{12.80374pt}{15.01208pt}{12.80374pt}{14.22638pt}\pgfsys@curveto{12.80374pt}{13.44067pt}{13.44067pt}{12.80374pt}{14.22638pt}{12.80374pt}\pgfsys@curveto{15.01208pt}{12.80374pt}{15.64902pt}{13.44067pt}{15.64902pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{14.22638pt}{14.22638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{1.42264pt}{0.0pt}\pgfsys@curveto{1.42264pt}{0.7857pt}{0.7857pt}{1.42264pt}{0.0pt}{1.42264pt}\pgfsys@curveto{-0.7857pt}{1.42264pt}{-1.42264pt}{0.7857pt}{-1.42264pt}{0.0pt}\pgfsys@curveto{-1.42264pt}{-0.7857pt}{-0.7857pt}{-1.42264pt}{0.0pt}{-1.42264pt}\pgfsys@curveto{0.7857pt}{-1.42264pt}{1.42264pt}{-0.7857pt}{1.42264pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{1.14737pt}{1.14737pt}\pgfsys@lineto{13.07901pt}{13.07901pt}\pgfsys@moveto{15.37375pt}{15.37375pt}\pgfsys@lineto{27.30539pt}{27.30539pt}\pgfsys@moveto{29.60013pt}{27.30539pt}\pgfsys@lineto{41.53177pt}{15.37375pt}\pgfsys@moveto{44.30177pt}{14.22638pt}\pgfsys@lineto{55.28288pt}{14.22638pt}\pgfsys@moveto{58.05289pt}{13.07901pt}\pgfsys@lineto{69.98453pt}{1.14737pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$

######  Theorem 5.4.

$|RAI_{2n-1}(4321)|=M_{n}-M_{n-2}.$

###### Proof.

Consider a permutation $\pi\in RAI_{2n}(4321).$ By Lemma 2.5, $\pi_{2n}$ is
odd. Now consider the element $2n-1$ in $\pi.$ Notice that this element is at
position $2n$ or $2n-1,$ otherwise $\pi$ would contain the pattern
$2n\;\,2n-1\;\,\pi(2n-1)\;\,\pi(2n)\sim 4321$ (notice that $2n$ appears before
$2n-1$ because $\pi$ is an involution and $\pi_{2n-1}>\pi_{2n}$).

If $\pi_{2n}=2n-1,$ the permutation $\pi^{\prime}$ obtained from $\pi$ by
removing the element $2n-1$ and standardizing is an arbitrary element of
$RAI_{2n-1}(4321)$ which ends with its maximum element.

If $\pi_{2n-1}=2n-1,$ write $\pi$ as
$\pi=\left(\begin{smallmatrix}\cdots&k&\cdots&2n-2&2n-1&2n\\\
\cdots&2n&\cdots&j&2n-1&k\end{smallmatrix}\right)$.

If $k>j,$ consider the permutation $\pi^{\prime}$ obtained from $\pi$ by
removing the element $2n-1$ and standardizing. $\pi^{\prime}$ is an arbitrary
element of $RAI_{2n-1}(4321)$ which does not end with its maximum element.

If $k<j,$ we must have $k=2n-3$ and $j=2n-2,$ otherwise $\pi$ would contain
$4321.$ Hence we can write $\pi=\pi^{\prime}\;\,2n\;\,2n-2\;\,2n-1\;\,2n-3,$
where $\pi^{\prime}$ is an arbitrary permutation in $RAI_{2n-4}(4321).$

As a consequence, $|RAI_{2n}(4321)|=|RAI_{2n-1}(4321)|+|RAI_{2n-4}(4321)|.$

∎

The preceding lemma implies that the sequence $(|AI_{2n-1}(4321)|)_{n\geq 1}$
coincides with sequence A102071 in [17].

######  Theorem 5.5.

$|AI_{n}(1234)|=|RAI_{n}(4321)|$

and

$|RAI_{n}(1234)|=|AI_{n}(4321)|.$

###### Proof.

The Robinson-Schensted map $RS$ (see e.g. [20]) associates an involution $\pi$
with a standard Young Tableau whose descent set $D$ is equal to the descent
set of $\pi.$ If we apply the inverse of the map $RS$ to the transposed
Tableau we get another involution $\pi^{\prime}$ whose descent set is
$[n-1]\setminus D.$ In particular, $\pi$ is alternating if and only if
$\pi^{\prime}$ is reverse alternating. Moreover, by the properties of the map
$RS,$ $\pi$ avoids $1234$ if and only if the corresponding tableau has at most
three columns, hence the transposed tableau has at most three rows and
$\pi^{\prime}$ avoids $4321.$ ∎

Theorems 5.2, 5.4 and 5.5 and Lemma 2.6 imply the following result.

######  Corollary 5.6.

$|RAI_{2n}(4321)|=|AI_{2n}(1234)|=M_{n}$

and

$|RAI_{2n-1}(1234)|=|AI_{2n-1}(4321)|=|RAI_{2n-1}(4321)|=$
$|AI_{2n-1}(1234)|=M_{n}-M_{n-2}.$

We now give an explicit formula for the cardinalities of the sets
$RAI_{2n}(1234)$ and $AI_{2n}(4321).$

######  Theorem 5.7.

$|RAI_{2n}(1234)|=|AI_{2n}(4321)|=M_{n+1}-2M_{n-1}+M_{n-3}.$

###### Proof.

We proceed as in the proof of Theorem 5.4. Consider a permutation $\pi\in
AI_{2n+1}(4321).$ The symbol $2n$ is either at position $2n$ or $2n+1,$
otherwise $\pi$ would contain $4321.$

If $\pi_{2n+1}=2n,$ the permutation $\pi^{\prime}$ obtained from $\pi$ by
removing the element $2n+1$ and standardizing is an arbitrary element of
$AI_{2n}(4321)$ which ends with its maximum element.

If $\pi_{2n}=2n,$ set
$\pi=\left(\begin{smallmatrix}\cdots&k&\cdots&2n-1&2n&2n+1\\\
\cdots&2n+1&\cdots&j&2n&k\end{smallmatrix}\right)$.

If $j<k,$ the permutation $\pi^{\prime}$ obtained from $\pi$ by removing the
element $2n$ and standardizing is an arbitrary element of $AI_{2n}(4321)$
which does not end with its maximum element.

If $j>k,$ the element $j=2n-1$ must be fixed and $k=2n-2,$ otherwise $\pi$
would contain an occurrence of $4321.$ Removing from $\pi$ the last four
elements we get an arbitrary permutations in $AI_{2n-3}(4321).$

Hence $|AI_{2n+1}(4321)|=|AI_{2n}(4321)|+|AI_{2n-3}(4321)|$ and the assertion
now follows from Corollary 5.6. ∎

##  6 Pattern 3412

######  Theorem 6.1.

$|RAI_{2n}(3412)|=|AI_{2n+2}(3412)|=|AI_{2n+1}(3412)|=|RAI_{2n+1}(3412)|=M_{n}.$

###### Proof.

We recall that also the set $I_{n}(3412)$ corresponds bijectively to the set
$\mathcal{M}_{n}$ via a map $\Psi$ whose definition coincides with the
definition of the map $\Phi$ of Section 5 (see [1]). It is easily seen that
$\Psi$ maps the set $RAI_{2n}(3412)$ to the set of Motzkin paths in
$\mathcal{M}_{2n}$ whose diods are either of the form $UH,$ $HD,$ or $UD.$
Hence the map $\widehat{\Psi}=\Delta\circ\Psi$ is a bijection between
$RAI_{2n}(3412)$ and $\mathcal{M}_{n},$ where $\Delta$ is the map defined in
the proof of Theorem 5.2.

We observe that any permutation in $AI_{t}(3412)$ begins with 1, hence, a
permutation $\pi\in AI_{2n+1}(3412)$ can be written as $\pi=1\,\pi^{\prime},$
where $\pi^{\prime}$ is an arbitrary permutation in $RAI_{2n}(3412).$
Moreover, any permutation $\pi$ in $AI_{2n+2}(3412)$ ends with its maximum
element, hence it can be can be written as $\pi=1\,\pi^{\prime}\,2n+2$ where
$\pi^{\prime}$ is an arbitrary permutation in $RAI_{2n}(3412).$

The last equality follows from Lemma 2.6. ∎

##  7 Patterns 2143, 2134 and 1243

######  Theorem 7.1.

$|AI_{2n}(1243)|=|AI_{2n}(2143)|=|AI_{2n}(2134)|=M_{n}$

and

$|AI_{2n-1}(2134)|=|RAI_{2n-1}(1243)|=M_{n}-M_{n-2}.$

###### Proof.

It is an immediate consequence of Lemma 2.6, Lemma 3.1 and Corollary 5.6. ∎

######  Theorem 7.2.

$|AI_{2n+1}(1243)|=|AI_{2n+1}(2143)|=|RAI_{2n+1}(2143)|=|RAI_{2n+1}(2134)|=M_{n}.$

###### Proof.

By Lemmas 2.6, 3.1 and 3.3, it suffices to show that
$|AI_{2n+1}(1234)\cap\\{\sigma\in S_{2n+1}\,|\,\sigma(2)=2n+1\\}|=M_{n}.$

If $\pi$ is a permutation in this last set, removing $2n+1$ and $2$ from $\pi$
and standardizing we get an arbitrary permutation $\widehat{\pi}$ in
$I_{2n-1}(1234)$ with either
$\operatorname*{Des}(\widehat{\pi})=\\{3,5,7,\ldots 2n-3\\}$ or
$\operatorname*{Des}(\widehat{\pi})=\\{1,3,5,7,\ldots 2n-3\\}.$ In other
words, this permutation is reverse alternating or it is reverse alternating
only to the right of the second position. Hence we have

$|AI_{2n+1}(1234)\cap\\{\sigma\in S_{2n+1}\,|\,\sigma(2)=2n+1\\}|=$
$|I_{2n-1}(1234)\cap\\{\sigma\in
S_{2n-1}\,|\,\operatorname*{Des}(\sigma)=\\{3,5,7,\ldots
2n-3\\}\\}|+|RAI_{2n-1}(1234)|.$

We want to show that the sum on the right hand side of the previous equality
is equal to $M_{n}.$ We proceed by induction on $n$. The assertion is trivial
when $n=2$ or $n=3.$ Assume that the assertion is true for every $m<n.$ We
know by Corollary 5.6 that $|RAI_{2n-1}(1234)|=M_{n}-M_{n-2}.$ Consider a
permutation $\rho$ in $I_{2n-1}(1234)\cap\\{\sigma\in
S_{2n-1}\,|\,\operatorname*{Des}(\sigma)=\\{3,5,7,\ldots 2n-3\\}\\}.$ Notice
that $\rho(2)=2n-2$ and $\rho(3)=2n-1,$ otherwise the permutation would
contain the subsequence $\rho(1)\;\,\rho(2)\;\,2n-2\;\,2n-1\sim 1234.$
Removing $2,3,2n-2$ and $2n-1$ and standardizing we get an arbitrary
permutation in $I_{2n-5}(1234)\cap\\{\sigma\in
S_{2n-5}\,|\,\operatorname*{Des}(\sigma)=\\{3,5,7,\ldots 2n-7\\}\\}$ or in
$RAI_{2n-5}(1234).$ By the inductive hypothesis we have

$|I_{2n-5}(1234)\cup\\{\sigma\in
S_{2n-5}\,|\,\operatorname*{Des}(\sigma)=\\{3,5,7,\ldots 2n-7\\}\\}|+$
$|RAI_{2n-5}(1234)|=M_{n-2}.$

This completes the proof.

∎

######  Example 7.3.

Consider $\pi=5\,11\,9\,10\,1\,7\,6\,8\,3\,4\,2\in AI_{11}(1234).$ If we
remove 11 and 2 from $\pi$ and standardize we get the involution

$\widehat{\pi}=4\,8\,9\,1\,6\,5\,7\,2\,3$

with $\operatorname*{Des}(\widehat{\pi})=\\{3,5,7\\}.$ Removing from
$\widehat{\pi}$ the symbols 8,9,2 and 3 we get the involution
$2\,1\,4\,3\,5\in RAI_{5}(1234).$

Consider now the permutation $\pi=9\,11\,7\,8\,5\,10\,3\,4\,1\,6\,2.$ If we
remove 11 and 2 from $\pi$ and standardize we get the involution

$\widehat{\pi}=8\,6\,7\,4\,9\,2\,3\,1\,5\in RAI_{9}(1234).$

######  Theorem 7.4.

$|RAI_{2n}(2143)|=M_{n-1}.$

###### Proof.

Let $\pi$ be a permutation in $RAI_{2n}(2143).$ The maximum of $\pi$ is in
position $1,$ otherwise $2\,1\,\pi_{2n-1}\,\pi_{2n}$ would be an occurrence of
$2143$ in $\pi.$ Write $\pi$ as $2n\,\widehat{\pi}\,1.$ Then the
standardization of $\widehat{\pi}$ is an arbitrary permutation in
$AI_{2n-2}(2143).$ The assertion now follows from Theorem 7.1. ∎

##  8 Patterns 3421 and 4312

Notice that the these two patterns are inverse of each other. Hence
$AI_{n}(3421)=AI_{n}(4312)=AI_{n}(3421,4312)$ and the same is true for reverse
alternating involutions. The following theorem shows that all these classes
are enumerated by the Fibonacci numbers $F_{n}$ (sequence A000045 in [17]).

######  Theorem 8.1.

$|AI_{n}(3421,4312)|=|RAI_{n}(3421,4312)|=F_{n-1},$

where $F_{k}$ is the $k$-th Fibonacci number.

###### Proof.

Let $\pi\in RAI_{2n}(3421,4312).$ The last element of $\pi$ is odd and the
position of $2n$ is odd by Lemma 2.5.

Notice that the symbol $2n-1$ can be either at position $2n$ or $2n-1,$
otherwise $\pi$ would contain the subsequence
$2n\;\,2n-1\;\,\pi(2n-2)\;\,\pi(2n-1)$ whose standardization is $4312.$

If $\pi_{2n}=2n-1,$ then $\pi=\pi^{\prime}\;\,2n\;\,2n-1,$ where
$\pi^{\prime}$ is an arbitrary permutation in $RAI_{2n-2}(3421,4312).$

If $\pi_{2n-1}=2n-1,$ let $y=\pi_{2n-2}$ and $x=\pi_{2n}.$ If $x>y,$ removing
from $\pi$ the symbol $2n-1$ and standardizing we obtain an arbitrary
permutation in $RAI_{2n-1}(3421,4312)$ which does not end with its maximum.

If $x<y,$ notice that either $\pi(2n-2)=2n-2$ or $\pi(2n-3)=2n-2$ (otherwise
$\pi$ would contain the patterns). If $\pi(2n-2)=2n-2,$ then $\pi(2n-3)$ is
forced to be $2n$ (because $\pi$ is alternating), so we can write
$\pi=\tau\;\,2n\;\,2n-2\;\,2n-1\;\,2n-3,$ where $\tau\in
RAI_{2n-4}(3421,4312).$ We associate to $\pi$ the permutation
$\pi^{\prime}=\tau\;\,2n-2\;\,2n-3\;\,2n-1.$ Such $\pi^{\prime}$ is an
arbitrary permutation in $RAI_{2n-1}(3421,4312)$ which ends with its maximum
and in which $2n-3$ precedes the maximum.

If $\pi(2n-3)=2n-2,$ we write
$\pi=\sigma^{\prime}\;\,2n\;\,\sigma^{\prime\prime}\;\,2n-2\;\,2n-3\;\,2n-1\;\,x$
and we associate to $\pi$ the permutation
$\pi^{\prime}=\sigma^{\prime}\;\,2n-2\;\,\sigma^{\prime\prime}\;\,2n-3\;\,x\;\,2n-1$
which is an arbitrary permutation in $RAI_{2n-1}(3421,4312)$ which ends with
its maximum and in which $2n-3$ follows the maximum.

As a consequence

$|RAI_{2n}(3421,4312)|=|RAI_{2n-1}(3421,4312)|+|RAI_{2n-2}(3421,4312)|.$

Let $\pi\in RAI_{2n+1}(3421,4312).$ The last element of $\pi$ is odd and the
position of $2n+1$ is odd by Lemma 2.5. Notice that the symbol $2n+1$ is
either at position $2n+1$ or $2n-1,$ otherwise $\pi$ would contain the
subsequence $2n\;\,2n+1\;\,\pi(2n-1)\;\,\pi(2n)\sim 3421.$

If $\pi_{2n+1}=2n+1,$ then $\pi=\pi^{\prime}\,2n+1,$ where $\pi^{\prime}$ is
an arbitrary permutation in $RAI_{2n}(3421,4312).$

If $\pi_{2n-1}=2n+1,$ write $\pi=\tau\;\,2n+1\;\,x\;\,2n-1.$ Then
$\pi^{\prime}=\tau\;\,2n-1\;\,x$ is an arbitrary permutation in
$RAI_{2n}(3421,4312)$ with $2n-1$ as a fixed point. We observed above that
such permutations are in bijection with $RAI_{2n-1}(3421,4312).$

As a consequence

$|RAI_{2n+1}(3421,4312)|=|RAI_{2n}(3421,4312)|+|RAI_{2n-1}(3421,4312)|.$ (1)

Hence we can conclude that

$|RAI_{m}(3421,4312)|=F_{m-1}.$

By Lemma 2.6, we have also $|AI_{2n+1}(3421,4312)|=|RAI_{2n+1}(3421,4312)|.$

Consider now $\pi\in AI_{2n}(3421,4312).$ By Lemma 2.5, $\pi_{1}$ is odd and
the symbol 1 is in odd position. Notice that either $\pi(1)=1$ or $\pi(3)=1$
otherwise $\pi$ would contain the subsequence $\pi_{1}\,\pi_{2}\,2\,1,$ whose
standardization is 3421.

If $\pi_{1}=1,$ the standardization of $\pi_{2}\ldots\pi_{2n}$ is an arbitrary
permutation in $RAI_{2n-1}(3421,4312).$ If $\pi(3)=1,$ write
$\pi=3\,\pi_{2}\,1\,\tau.$ The standardization of the word $\pi_{2}\,3\,\tau$
is an arbitrary permutation $\pi^{\prime}$ in $RAI_{2n-1}(3421,4312)$ which
fixes the symbol $2.$

Observe that, if $\pi\in RAI_{2n-1}(3421,4312),$ then $\pi(1)=2$ or
$\pi(2)=2,$ namely $RAI_{2n-1}(3421,4312)=A\cup B$ where
$A=RAI_{2n-1}(3421,4312)\cap\\{\pi\in S_{2n-1}\,|\,\pi(2)=1\\}$ and
$B=RAI_{2n-1}(3421,4312)\cap\\{\pi\in S_{2n-1}\,|\,\pi(2)=2\\}.$

The set $A$ corresponds bijectively to the set $RAI_{2n-3}(3421,4312)$ by
removing the firs two elements, hence the set $B$ corresponds bijectively to
the set $RAI_{2n-2}(3421,4312)$ by equation (1).

Hence,

$|AI_{2n}(3421,4312)|=|RAI_{2n-1}(3421,4312)|+|RAI_{2n-2}(3421,4312)|$

and

$|AI_{m}(3421,4312)|=F_{m-1}.$

∎

######  Example 8.2.

Consider the set $RAI_{6}(3421,4312),$ whose elements are

$\alpha=2\,1\,6\,4\,5\,3\quad\quad\beta=2\,1\,4\,3\,6\,5\quad\quad\gamma=4\,2\,6\,1\,5\,3$
$\delta=4\,2\,3\,1\,6\,5\quad\quad\epsilon=6\,2\,4\,3\,5\,1.$

The permutations $\beta$ and $\delta$ correspond to $2\,1\,4\,3$ and
$4\,2\,3\,1,$ namely, the elements of the set $RAI_{4}(3421,4312),$ whereas
the permutations $\alpha,\gamma$ and $\epsilon$ correspond to $2\,1\,4\,3\,5,$
$4\,2\,5\,1\,3$ and $5\,2\,3\,4\,1,$ respectively, namely, the elements of
$RAI_{5}(3421,4312).$

##  9 Patterns 2431, 4132, 3241 and 4213.

Notice that the two patterns $2431$ and $4132$ are inverse of each other.
Hence $AI_{n}(2431)=AI_{n}(4132)=AI_{n}(2431,4132)$ and the same is true for
reverse alternating involutions and for the pair of patterns $(3241,4213).$

######  Theorem 9.1.

$|RAI_{2n}(2431,4132)|=|RAI_{2n}(3241,4213)|=|RAI_{2n+1}(3241,4213)|=$
$|AI_{2n+1}(2431,4132)|=2^{n-1}.$

###### Proof.

Consider a permutation $\pi\in RAI_{2n}(2431,4132).$ We want to show that
$\pi=\tau^{\prime}\,2n\,\tau^{\prime\prime},$ where $\tau^{\prime}$ is a
permutation of the symbols $1,2,\ldots,i-1$ and $\tau^{\prime\prime}$ is a
permutation of the symbols $i,\ldots,2n-1.$

Suppose on the contrary that there exists an element $b$ in $\tau^{\prime}$
such that $b>i,$ so that $\pi=\ldots b\ldots 2n\ldots i.$ Let $a=\pi_{2n-1}.$
Since $\pi$ is alternating, we have $a>i,$ hence $2n-1$ follows $2n$ in $\pi$
and the subsequence $b\,2n\,2n-1\,i$ is order-isomorphic to 2431.

As a consequence, the word $2n\,\tau^{\prime\prime}$ is itself a reverse
alternating involution avoiding 132, and there exists only one of such
permutations, as observed in Section 4, while the word $\tau^{\prime}$ is an
arbitrary permutation in $RAI_{j}(2431,4132),$ $j$ even.

We can conclude that

$|RAI_{2n}(2431,4132)|=\sum_{j\mbox{ even,
}j<2n}|RAI_{j}(2431,4132)|=2^{n-1},$

where the last equality follows from the previous one by induction.

The facts that

$|RAI_{2n}(2431,4132)|=|RAI_{2n}(3241,4213)|$

and

$|RAI_{2n+1}(3241,4213)|=|AI_{2n+1}(2431,4132)|$

follow by Lemma 2.6.

Consider now a permutation $\pi$ in $RAI_{2n+1}(4213,3241).$

Write $\pi=m_{1}\,w_{1}\,m_{2}\,w_{2}\ldots m_{k}\,w_{k},$ where the
$m_{i}^{\prime}s$ are the ltr maxima of $\pi$ and the $w_{i}^{\prime}s$ are
words. Since $\pi$ is alternating and avoids the patterns 4213 and 3241, it
follows that for every $i=1,2\ldots,k-1$ the word $w_{i}$ with is non empty
and that $w_{i}<w_{i+1},$ namely, every symbol in $w_{i}$ is smaller than any
symbol in $w_{i+1}.$

As a consequence $m_{i}w_{i}$ is an interval for every $i.$ Obviously
$m_{k}=2n+1$ and its position is $\pi_{2n+1}$ since $\pi$ is an involution.
Suppose that $\pi_{2n+1}\neq 2n+1.$ Since $\pi_{2n}<\pi_{2n+1},$ the symbol
$2n$ should appear to the left of $2n+1$ in $\pi,$ but this contradicts the
fact that $m_{k}w_{k}$ is an interval. Hence $2n+1$ is the last element of
$\pi$ and removing it from $\pi$ we get an arbitrary permutation in
$RAI_{2n}(4213,3241),$ so we have

$|RAI_{2n}(4213,3241)|=|RAI_{2n+1}(4213,3241)|.$

∎

######  Theorem 9.2.

$|RAI_{2n+1}(2431,4132)|=|AI_{2n+1}(3241,4213)|=\left\lfloor\dfrac{2^{n-1}\cdot
5}{3}\right\rfloor.$

To prove this theorem we need the following lemma.

######  Lemma 9.3.

The number of connected permutations in $RAI_{2l+1}(4132,2431)$ is

$\left\lfloor\frac{2l+1}{4}\right\rfloor.$

###### Proof.

Let $\tau\in RAI_{2l+1}(4132,2431)$ be a connected permutations. Consider the
position $i$ of $2l+1$ in $\tau.$ This position is odd by lemma 2.5 and $i\neq
2l+1$ since $\tau$ is connected.

If $i=2l-1,$ we can remove from $\tau$ the symbols $2l+1$ and $2l-1$ obtaining
an arbitrary connected permutation $\tau$ in $RAI_{2l-1}(2431,4132).$

If $i<2l-1,$ let $a=\tau_{2l},$ $b=\tau_{2l-1}$ and $c=\tau_{2l-2}.$

We can write
$\tau=\left(\setcounter{MaxMatrixCols}{11}\begin{smallmatrix}\cdots&a&\cdots&i&\cdots&b&\cdots&2l-2&2l-1&2l&2l+1\\\
w_{1}&2l&w_{2}&2l+1&w_{3}&2l-1&w_{4}&c&b&a&i\end{smallmatrix}\right)$ where,
since $\tau$ is alternating, $c<b>a<i.$

If $bai\sim 312,$ since $\tau$ avoids 2431, the elements of $w_{1}$ and
$w_{2}$ are smaller than the elements of $w_{4}\,c\,b\,a\,i$ that, in turn,
are smaller than the elements of $w_{3}.$ But now, if $a\neq i-1,$ we would
have an occurence of 4132. Hence $a=i-1,$ and this is impossible since $\tau$
is connected ($w_{1}$ would be a connected component of $\tau$).

Hence $bai\sim 213.$ Notice that we must have $cba\sim 231$ and we can write
$\tau=\left(\setcounter{MaxMatrixCols}{13}\begin{smallmatrix}\cdots&a&\cdots&c&\cdots&b&\cdots&i&\cdots&2l-2&2l-1&2l&2l+1\\\
w_{1}&2l&w_{2_{1}}&2l-2&w_{2_{2}}&2l-1&w_{3}&2l+1&w_{4}&c&b&a&i\end{smallmatrix}\right)$

where, as above, $w_{1}<w_{4}<w_{3}<w_{2_{2}}<w_{2_{1}}.$

The word $w_{1}$ is empty, since $\tau$ is connected. If $i\neq 2l-3,$ we have
$\tau_{2l-3}>\tau_{2l-2},$ since $\tau$ is alternating. Hence $2l-3$ must
follow $2l-2.$ So we can conclude that also $w_{2_{1}}$ is empty and $c=2.$
Since $\tau_{2}<\tau_{3},$ 3 must follows 2 in $\tau$ so $b=3$ and $w_{2_{2}}$
is also empty.

Iterating these arguments one can show that

$\tau=2l\;2l-2\;2l-1\;2l-4\;2l-3\;\ldots l-1\;2l+1\;l-3\;l-2\;\ldots
2\;3\;1\;l+1.$

In particular $i=l+1.$ Since $i$ is odd, this implies that $2l+1\equiv
1\,\mbox{ mod }4.$

As a consequence, the number of connected permutations in
$RAI_{2l+1}(4132,2431)$ is the same as the number of connected permutations in
$RAI_{2l-1}(4132,2431)$ if $2l+1\equiv 3\mbox{ mod }4$ and increases by one if
$2l+1\equiv 1\mbox{ mod }4.$

As an example, when $2l+1=21$ such permutations are

$4\;2\;6\;1\;8\;3\;10\;5\;12\;7\;14\;9\;16\;11\;18\;13\;20\;15\;21\;17\;19$
$8\;6\;7\;4\;10\;2\;3\;1\;12\;5\;14\;9\;16\;11\;18\;13\;20\;15\;21\;17\;19$
$12\;10\;11\;8\;9\;6\;14\;4\;5\;2\;3\;1\;16\;7\;18\;13\;20\;15\;21\;17\;19$
$16\;14\;15\;12\;13\;10\;11\;8\;18\;6\;7\;4\;5\;2\;3\;1\;20\;9\;21\;17\;19$
$20\;18\;19\;16\;17\;14\;15\;12\;13\;10\;21\;8\;9\;6\;7\;4\;5\;2\;3\;1\;11$

(notice that all of them but the last one have 21 at position 19 and the last
one has 21 in position 11). When $2l+1=23$ such permutations are

$4\;2\;6\;1\;8\;3\;10\;5\;12\;7\;14\;9\;16\;11\;18\;13\;20\;15\;22\;17\;23\;19\;21$
$8\;6\;7\;4\;10\;2\;3\;1\;12\;5\;14\;9\;16\;11\;18\;13\;20\;15\;22\;17\;23\;19\;21$
$12\;10\;11\;8\;9\;6\;14\;4\;5\;2\;3\;1\;16\;7\;18\;13\;20\;15\;22\;17\;23\;19\;21$
$16\;14\;15\;12\;13\;10\;11\;8\;18\;6\;7\;4\;5\;2\;3\;1\;20\;9\;22\;17\;23\;19\;21$
$20\;18\;19\;16\;17\;14\;15\;12\;13\;10\;22\;8\;9\;6\;7\;4\;5\;2\;3\;1\;23\;11\;21$

(all of them have the symbol 23 in position 21).

Since when $2l+1=5$ there is only one of such permutations, the number of
connected permutations in $RAI_{2l+1}(4132,2431)$ is
$\left\lfloor\frac{2l+1}{4}\right\rfloor.$ ∎

Now we turn to the proof of Theorem 9.2.

Proof of Theorem 9.2. Let $\pi\in RAI_{2n+1}(2431,4132).$ Consider the last
connected component $\tau$ of $\pi$ and write $\pi=\sigma\tau.$

Now, $\sigma$ is an arbitrary permutation in $RAI_{2k}(2431,4132),$ with
$k\geq 0$ (notice that $\sigma$ has even length, since $\tau$ is connected and
$\pi$ is alternating) and $\tau^{\prime},$ the standardization of $\tau,$ is
an arbitrary connected permutation in $RAI_{2n+1-2k}(2431,4132),$ with $l\geq
0.$

Hence, by Lemma 9.3 and by Theorem 9.1, we have

$|RAI_{2n+1}(2431,4132)|=2^{n-1}+\sum_{k\geq
1}^{n-1}2^{k-1}\left\lfloor\frac{2n+1-2k}{4}\right\rfloor+\left\lfloor\frac{2n+1}{4}\right\rfloor,$

where the first summand of the right hand side corresponds to the case
$\tau=2n+1$ and the third summand corresponds to the case $|\tau|=2n+1.$

Now it can be shown by induction that

$|RAI_{2n+1}(2431,4132)|=\left\lfloor\frac{2^{n-1}\cdot 5}{3}\right\rfloor.$

The fact that $|AI_{2n+1}(3241,4213)|=|RAI_{2n+1}(2431,4132)|$ follows by
Lemma 2.6.

Notice that $\\{|RAI_{2n+1}(2431,4132)|\\}_{n}$ is sequence A081254 in [17].

On the contrary, the sequence enumerating $AI_{2n}(3241,4213)$ and
$AI_{2n}(2431,4132),$ whose first terms are $1,2,5,9,17,31,59,\ldots,$ is not
present in [17].

##  10 Patterns 2413 and 3142

The set $AI_{n}(2413,3142)$ coincides with the set of alternating Baxter
involutions of length $n.$

We recall that a Baxter permutation of length $n$ is a permutation $\pi\in
S_{n}$ such that, for every $1\leq i\leq j\leq k\leq l\leq n,$

$\mbox{if }\pi_{i}+1=\pi_{l}\mbox{ and }\pi_{j}>\pi_{l}\mbox{ then
}\pi_{k}>\pi_{l}\mbox{ and}$ $\mbox{if }\pi_{l}+1=\pi_{i}\mbox{ and
}\pi_{k}>\pi_{i}\mbox{ then }\pi_{j}>\pi_{i}.$

In [15] the author shows that the set of doubly alternating Baxter
permutations coincides with the set of doubly alternating permutations
avoiding 2413 and $3142=2413^{-1}.$

An involution is clearly doubly alternating. As a consequence, the set
$AI_{n}(2413,3142)$ coincides with the set of alternating Baxter involutions
of length $n.$ A recurrence relation for this sequence has been found in [13]
and the corresponding sequence in [17] is A347546.

Moreover we have

$|AI_{2n+1}(2413,3142)|=|RAI_{2n+1}(2413,3142)|=|RAI_{2n}(2413,3142)|,$

where the first equality follows from Lemma 2.6 and the second one is a
consequence of the fact that each permutation in $RAI_{2n+1}(2413,3142)$ ends
with its maximum (see [13]) and this maximum can be removed, hence obtaining
any permutation in $RAI_{2n}(2413,3142).$

##  11 Patterns 4123, 2341

Since $4123=2341^{-1}$ we have $AI_{n}(4123)=AI_{n}(2341)=AI_{n}(4123,2341)$
and the same is true for reverse alternating involutions.

To enumerate these classes we need the following lemma.

######  Lemma 11.1.

The number of connected permutations in $RAI_{n}(4123,2341)$ is
$\begin{cases}1&\mbox{ if }n\mbox{ is odd and }n\neq 3\\\ 2&\mbox{ if }n\mbox{
is even and }n\geq 6\\\ 0&\mbox{ if }n=3\\\ 1&\mbox{ if }n=2,4.\end{cases}.$
The number of connected permutations in $AI_{n}(4123,2341)$ is
$\begin{cases}1&\mbox{ if }n\geq 4\mbox{ or }n=1\\\ 0&\mbox{ if }n=2\mbox{ or
}3\\\ \end{cases}.$

###### Proof.

The small cases are trivial, so we can assume $n\geq 5.$

Let $\pi\in RAI_{2n}(4123,2341)$ be connected. Write
$\pi=w_{k}\,m_{k}\,w_{k-1}m_{k-1}\ldots m_{2}\,w_{1}\,m_{1}$ where the
$m_{i}^{\prime}s$ are the rtl maxima of $\pi.$

Since $\pi$ is reverse alternating and avoids 4123, every $w_{i}$ with $2\leq
i\leq k-1$ must have length 1. For the same reason, $w_{1}$ must be empty
($\pi$ ends with a descent) and the length of $w_{k}$ is 0 or 2.

If $|w_{k}|=0,$

$\pi=2n\,2n-2\,2n-1\,2n-4\,2n-3\ldots 4\,5\,2\,3\,1,$

if $|w_{k}|=2,$

$\pi=2n-2\,2n-4\,2n\,2n-6\,2n-1\,2n-8\,2n-3\ldots 2\,7\,1\,5\,3.$

In a similar way it is possible to prove that the only connected permutation
in $RAI_{2n+1}(4123,2341)$ is

$\pi=2n\,2n-2\,2n+1\,2n-4\,2n-1\,2n-6\,2n-3\ldots 9\,4\,7\,2\,5\,1\,3.$

The classification of the connected permutations in $AI_{n}(4123,2341)$ is
fully analogous. ∎

######  Example 11.2.

There are two connected permutations in $RAI_{10}(4123,2341),$ namely,

$8\,6\,10\,4\,9\,2\,7\,1\,5\,3\mbox{ and }10\,8\,9\,6\,7\,4\,5\,2\,3\,1,$

while the only connected permutation in $RAI_{11}(4123,2341)$ is

$10\,8\,11\,6\,9\,4\,7\,2\,5\,1\,3.$

The only connected permutation in $AI_{10}(4123,2341)$ is

$9\,10\,7\,8\,5\,6\,3\,4\,1\,2$

and the only connected permutation in $AI_{11}(4123,2341)$ is

$9\,11\,7\,10\,5\,8\,3\,6\,1\,4\,2.$

In the following theorem we find the ordinary generating functions that
enumerate reverse alternating involutions avoiding 4123 and 2341 of even and
odd length (sequences A052980 and A193641 in [17], respectively). We also find
the same generating function for the alternating even case. This last sequence
does not appear in [17].

######  Theorem 11.3.

We have

$\sum_{n\geq 0}|AI_{2n+1}(4123,2341)|x^{2n+1}=\sum_{n\geq
0}|RAI_{2n+1}(4123,2341)|x^{2n+1}=$ $\frac{x^{5}-x^{3}+x}{1-2x^{2}-x^{6}},$
$\sum_{n\geq 0}|RAI_{2n}(4123,2341)|x^{2n}=\frac{1-x^{2}}{1-2x^{2}-x^{6}},$

and

$\sum_{n\geq
0}|AI_{2n}(4123,2341)|x^{2n}=1+\frac{x^{4}}{1-x^{2}}+\frac{(x^{5}-x^{3}+x)^{2}}{(1-2x^{2}-x^{6})\cdot(1-x^{2})}.$

###### Proof.

The fact that $|RAI_{2n+1}(4123,2341)|=|AI_{2n+1}(4123,2341)|$ follows from
Lemma 2.6.

Let $\pi\in RAI_{2n+1}(4123,2341).$ Decompose $\pi$ in connected components as
$\pi=\tau_{1}\tau_{2}\ldots\tau_{k}.$ Denote by $\widehat{\tau}_{i}$ the
standardization of $\tau_{i}.$ The $\widehat{\tau}_{i}^{\prime}s$ are
arbitrary connected permutations with $\widehat{\tau}_{i}\in\cup_{j\geq
1}RAI_{2j}(4123,2341)$ for $1\leq i\leq k-1$ (because $\pi$ is reverse
alternating) and $\tau_{k}\in\cup_{j\geq 0}RAI_{2j+1}(4123,2341).$ By the
previous lemma it follows that the ordinary generating function that counts
connected permutations in $\cup_{j\geq 1}RAI_{2j}(4123,2341)$ (by length) is
$F(x)=x^{2}+x^{4}+\frac{2x^{6}}{1-x^{2}}$ and the ordinary generating function
that counts connected permutations in $RAI_{2j+1}(4123,2341)$ is
$G(x)=x+\frac{x^{5}}{1-x^{2}}.$

As a consequence

$\sum_{n\geq 0}|RAI_{2n+1}(4123,2341)|x^{2n+1}=\frac{G(x)}{1-F(x)}.$

Trivial algebraic manipulations lead to the desired generating function.

Similarly, given $\pi\in RAI_{2n}(4123,2341)$ we can decompose $\pi$ in
connected components as $\pi=\tau_{1}\tau_{2}\ldots\tau_{k}$ where
$\widehat{\tau}_{i}\in\cup_{j\geq 1}RAI_{2j}(4123,2341)$ for $1\leq i\leq k.$

As a consequence

$\sum_{n\geq 0}|RAI_{2n+1}(4123,2341)|x^{2n+1}=\frac{1}{1-F(x)}.$

The decomposition in connected components of a permutation $\pi\in
AI_{2n}(4123,2341)$ is more subtle than the above ones because these
components are not necessarily only of even or odd length. However such a
permutation $\pi$ can only be

  * •

the empty one,

  * •

connected itself,

  * •

of the form $\sigma\tau,$ where $\sigma$ is an arbitrary permutation in
$\cup_{j\geq 0}AI_{2j+1}(4123,2341)$ and $\tau$ is a connected permutation in
$\cup_{j\geq 0}RAI_{2j+1}(4123,2341).$

By the above results and by the previous lemma we get

$\sum_{n\geq
0}|AI_{2n}(4123,2341)|x^{2n}=1+\frac{x^{4}}{1-x^{2}}+\frac{x^{5}-x^{3}+x}{1-2x^{2}-x^{6}}\cdot\frac{x^{5}-x^{3}+x}{1-x^{2}}$

where the three summand on the left hand side correspond to the three dotted
cases.

∎

##  12 Other patterns

The following three conjectures are based on numerical evidences. The first
one covers the last open case about the patterns 1243 and 2134 and the second
covers the patterns 1432 and 3214.

######  Conjecture 12.1.

$|RAI_{2n}(1243)|=|RAI_{2n}(2134)|=M_{n}.$

######  Conjecture 12.2.

$|AI_{2n}(1432)|=|AI_{2n}(3214)|=|RAI_{2n}(1432)|=|RAI_{2n}(3214)|=M_{n},$
$|AI_{2n+1}(1432)|=|RAI_{2n+1}(3214)|=M_{n},$
$|AI_{2n-1}(3214)|=|RAI_{2n-1}(1432)|=M_{n}-M_{n-2}.$

######  Conjecture 12.3.

Let $\tau$ be any permutation of $\\{4,\ldots,m\\},m\geq 4.$ Then

$|AI_{n}(123\tau)|=|AI_{n}(321\tau)|.$

A classical subject in pattern avoidance is the study of Wilf-equivalent
patterns. Let $\sigma$ and $\tau$ two patterns and $P_{n}$ a given subset of
$S_{n}.$ Then $\sigma$ and $\tau$ are said to be Wilf-equivalent on $P_{n}$ if
$|P_{n}(\sigma)|=|P_{n}(\tau)|.$

A proof of Conjectures 12.1 and 12.2 would conclude the Wilf-classification of
alternating and reverse alternating involutions avoiding a pattern of length
4. In fact, trivial numerical experiments show that the only Wilf-equivalences
among all the other patterns not mentioned in the paper are the trivial ones
given by the reverse complement map and the inverse map.

## Acknowledgments

We thank the anonymous referee for his very detailed revision and his valuable
suggestions.

## References

  * [1] M. Barnabei, F. Bonetti, and M. Silimbani.  Restricted involutions and Motzkin paths.  Adv. in Appl. Math., 47(1):102–115, 2011.
  * [2] P. Biane.  Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine.  European J. Combin., 14(4):277–284, 1993.
  * [3] M. Bóna.  On a family of conjectures of Joel Lewis on alternating permutations.  Graphs Combin., 30(3):521–526, 2014.
  * [4] M. Bóna, C. Homberger, J. Pantone, and V. Vatter.  Pattern-avoiding involutions: exact and asymptotic enumeration.  Australas. J. Combin., 64:88–119, 2016.
  * [5] J. N. Chen, W. Y. C. Chen, and R. D. P. Zhou.  On pattern avoiding alternating permutations.  European J. Combin., 40:11–25, 2014.
  * [6] N. Gowravaram and R. Jagadeesan.  Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux.  Electron. J. Combin., 20(4):Paper 17, 28, 2013.
  * [7] A. D. Jaggard.  Prefix exchanging and pattern avoidance by involutions.  Electron. J. Combin., 9:Paper 16, 24, 2002/03.  Permutation patterns (Otago, 2003).
  * [8] S. Kitaev.  Patterns in Permutations and Words.  Monographs in Theoretical Computer Science. Springer, 2011.
  * [9] D. E. Knuth.  The Art of Computer Programming, volume 3.  Addison-Wesley, 1973.
  * [10] J. B. Lewis.  Alternating, pattern-avoiding permutations.  Electron. J. Combin., 16(1):Note 7, 8, 2009.
  * [11] J. B. Lewis.  Pattern avoidance for alternating permutations and Young tableaux.  J. Combin. Theory Ser. A, 118(4):1436–1450, 2011.
  * [12] J. B. Lewis.  Generating trees and pattern avoidance in alternating permutations.  Electron. J. Combin., 19(1):Paper 21, 21, 2012.
  * [13] S. Min.  The enumeration of involutions of doubly alternating Baxter permutations.  J. Chungcheong Math. Soc., 34(3):253–257, 2021.
  * [14] E. Ouchterlony.  On Young tableau involutions and patterns in permutations.  PhD thesis, Linköpings Universitet, 2005.
  * [15] E. Ouchterlony.  Pattern avoiding doubly alternating permutations.  Proceedings FPSAC (San Diego 2006), 2006.
  * [16] R. Simion and F. Schmidt.  Restricted permutations.  European J. Combin., 6:383–406, 1985.
  * [17] N. J. A. Sloane.  The On-Line Encyclopedia of Integer Sequences.  https://oeis.org/.
  * [18] R. P. Stanley.  Alternating permutations and symmetric functions.  J. Combin. Theory Ser. A, 114(3):436–460, 2007.
  * [19] R. P. Stanley.  A survey of alternating permutations.  In Combinatorics and graphs, volume 531 of Contemporary Mathematics, pages 165–196. Amer. Math. Soc., Providence, RI, 2010.
  * [20] M. A. A. van Leeuwen.  The Robinson-Schensted and Schützenberger algorithms, an elementary approach.  Electron. J. Combin., Foata Festschrift, 3, 1996.
  * [21] J. West.  Permutations with restricted subsequences and stack-sortable permutations.  PhD thesis, M.I.T., 1990.
  * [22] Y. Xu and S. H. F. Yan.  Alternating permutations with restrictions and standard Young tableaux.  Electron. J. Combin., 19(2):Paper 49, 16, 2012.
  * [23] S. H. F. Yan.  On Wilf equivalence for alternating permutations.  Electron. J. Combin., 20(3):Paper 58, 19, 2013.