# Equivalences for pattern avoiding involutions and classification

Mark Dukes<fnref n="1" />, Vít Jelínek<fnref n="2" />†, Toufik Mansour<fnref n="3" /> and Astrid Reifegerste<fnref n="4" />

**Abstract.** We complete the Wilf classification of signed patterns of length 5 for both signed permutations and signed involutions. New general equivalences of patterns are given which prove Jaggard’s conjectures concerning involutions in the symmetric group avoiding certain patterns of length 5 and 6. In this way, we also complete the Wilf classification of $S_5$, $S_6$, and $S_7$ for both permutations and involutions.

**Résumé.** Nous complétons la classification de Wilf des motifs signés de longueur 5 à la fois pour les permutations signées et les involutions signées. Nous donnons de nouvelles équivalences générales de motifs qui prouvent les conjectures de Jaggard concernant les involutions dans le groupe symétrique évitant certains motifs de longueur 5 et 6. De cette manière nous complétons également la classification de Wilf de $S_5$, $S_6$ et $S_7$ à la fois pour les permutations et les involutions.

**Keywords:** forbidden subsequences, pattern avoiding permutations, pattern avoiding involutions, signed permutations, Wilf equivalence

## 1 Introduction

Let $S_n$ and $B_n$ denote the symmetric group and hyperoctahedral group on the set $\{1, 2, \dots, n\}$, respectively. We will represent the elements of $S_n$ as permutation matrices, and the elements of $B_n$ as signed permutation matrices, where a signed permutation matrix is a 0, 1, -1-matrix with exactly one nonzero entry in every row and every column. We may also write the elements of $B_n$ as words $\pi = \pi_1\pi_2\dots\pi_n$ in which each of the letters 1, 2, ..., $n$ appears, possibly barred to signify negative letters; a matrix $p$ corresponds to the word $\pi$ such that $p_{ij} = 1$ if $\pi_i = j$, $p_{ij} = -1$ if $\pi_i = -j$, and $p_{ij} = 0$ otherwise. In our paper, we will make no explicit distinction between these two representations of a signed permutation. Let $I_n$ and $S I_n$ be the set of involutions in $S_n$ and $B_n$, respectively. Note that involutions correspond precisely to symmetric matrices.

<footnote n="1">¹Science Institute, University of Iceland, Reykjavík, Iceland</footnote>

<footnote n="2">²Department of Applied Mathematics, Charles University Prague, Czech Republic</footnote>

<footnote n="3">³Department of Mathematics, University of Haifa, 31905 Haifa, Israel</footnote>

<footnote n="4">⁴Faculty of Mathematics, University of Magdeburg, Germany.</footnote>

<footnote>†Supported by project 201/05/H014 of the Czech Science Foundation and project MSM0021620838 of the Czech Ministry of Education.</footnote>
A signed permutation $\pi \in B_n$ is said to contain the pattern $\tau \in B_k$ if there exists a sequence $1 \le i_1 < i_2 < \dots < i_k \le n$ such that $|\pi_{i_a}| < |\pi_{i_b}|$ if and only if $|\tau_a| < |\tau_b|$ and $\pi_{i_a} > 0$ if and only if $\tau_a > 0$ for all $1 \le a, b \le k$. Otherwise, $\pi$ is called a $\tau$-avoiding permutation. Note that $\pi$ contains $\tau$ if and only if the matrix representing $\pi$ contains the matrix representing $\tau$ as a submatrix. By $M(\tau)$ we denote the set of all elements of $M$ which avoid the pattern $\tau$.

Two signed patterns $\sigma$ and $\tau$ are called Wilf equivalent, in symbols $\sigma \sim \tau$, if they are avoided by the same number of signed $n$-permutations, i.e., if $|B_n(\sigma)| = |B_n(\tau)|$ for each $n \ge 1$. Similarly, $\sigma$ and $\tau$ are called I-Wilf equivalent, denoted by $\sigma \stackrel{I}{\sim} \tau$, if $|SI_n(\sigma)| = |SI_n(\tau)|$ for each $n$. Note that two unsigned permutations $\sigma, \tau \in S_k$ are Wilf-equivalent if and only if they satisfy the identity $|S_n(\sigma)| = |S_n(\tau)|$ for each $n$, and they are I-Wilf equivalent if and only if they satisfy $|I_n(\sigma)| = |I_n(\tau)|$ for each $n$. The classification given by the Wilf equivalence is slightly coarser than that which is based on the symmetries of permutations, that is, the mappings generated by the reversal, transpose, and barring operation. The same is true for the I-Wilf equivalence, where the available symmetries are generated by the two diagonal reflections and the barring operation.

The question of whether two patterns are Wilf equivalent or not is difficult to answer in many cases. By the few generic equivalences known so far, it has been possible to completely determine the Wilf classes of $S_n$ up to level $n = 7$. The decomposition of $S_n$ into I-Wilf classes has been completely determined for $n = 4$ and almost solved for $n = 5$ as well. Jaggard (6) conjectured the last case of a possible equivalence for patterns of length 5: 12345 (or equivalently, 54321) and 45312 are equally restrictive for $I_n$ up to $n = 11$.

Continuing the I-Wilf classification of signed patterns that began in (5), we will first prove a general equivalence result which confirms Jaggard's conjecture mentioned above, as well as another conjecture he made about the equivalence of certain patterns of length 6. The correspondence behind this result is based on a bijection between pattern avoiding transversals of Young diagrams given by Backelin, West and Xin (1). In this way, we complete the classification of $S_5$ with respect to $\stackrel{I}{\sim}$, which is fundamental for the analogous classification of $B_5$. The result even covers all missing I-Wilf equivalences in $S_6$ and $S_7$.

Furthermore, we will show that barring some blocks of a signed block diagonal pattern preserves the Wilf class of the pattern, and it also (under some additional assumptions) preserves the I-Wilf class. These results not only allow us to determine the Wilf as well as the I-Wilf classes in $B_5$ but they also have consequences for longer signed patterns. The proofs of the theorems and tables of Wilf equivalence classes may be found in the papers (4; 3).

## 2 Jaggard's conjectures

In 2003, Jaggard (6) proved the equivalences $12\tau \stackrel{I}{\sim} 21\tau$ and $123\tau \stackrel{I}{\sim} 321\tau$, and completed the classification of $S_4$ according to pattern avoidance by involutions in this way. Furthermore, he conjectured that

$$ (1) \quad 12 \dots k\tau \stackrel{I}{\sim} k(k-1) \dots 1\tau \text{ for any } k \ge 1, $$

$$ (2) \quad 12345 \stackrel{I}{\sim} 45312 \text{ (or equivalently, } 54321 \stackrel{I}{\sim} 45312\text{)}, $$

$$ (3) \quad 123456 \stackrel{I}{\sim} 456123 \stackrel{I}{\sim} 564312 \text{ (or equivalently, } 654321 \stackrel{I}{\sim} 456123\text{)}. $$
In (1), Backelin, West and Xin defined a transformation to prove $12...k\tau \sim k(k-1)...1\tau$. (As already mentioned in (5), their proof also works for a signed pattern $\tau$.) This map acts not only on permutation matrices, but more generally, on transversals of Young diagrams. Bousquet-Mélou and Steingrímsson (2) showed that this map commutes with the diagonal reflection of the diagram, which proves the first of the three conjectures above. From this result, it follows that

$$ \begin{pmatrix} \alpha_k & 0 & 0 \\ 0 & \chi & 0 \\ 0 & 0 & \alpha_l \end{pmatrix} \sim I \begin{pmatrix} \beta_k & 0 & 0 \\ 0 & \chi & 0 \\ 0 & 0 & \beta_l \end{pmatrix} $$

for every signed permutation matrix $\chi$ and any $k, l \ge 0$, where $\alpha_n$ and $\beta_n$ denote the $n \times n$ diagonal and antidiagonal permutation matrices corresponding to $12...n$ and $n(n-1)...1$, respectively. In this section, we will show that

$$ \begin{pmatrix} 0 & 0 & 0 & \alpha_k \\ 0 & 0 & \chi & 0 \\ 0 & \chi^t & 0 & 0 \\ \alpha_k & 0 & 0 & 0 \end{pmatrix} \sim I \begin{pmatrix} 0 & 0 & 0 & \beta_k \\ 0 & 0 & \chi & 0 \\ 0 & \chi^t & 0 & 0 \\ \beta_k & 0 & 0 & 0 \end{pmatrix} \quad \text{and} \quad \begin{pmatrix} 0 & 0 & 0 & 0 & \alpha_k \\ 0 & 0 & 0 & \chi & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & \chi^t & 0 & 0 & 0 \\ \alpha_k & 0 & 0 & 0 & 0 \end{pmatrix} \sim I \begin{pmatrix} 0 & 0 & 0 & 0 & \beta_k \\ 0 & 0 & 0 & \chi & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & \chi^t & 0 & 0 & 0 \\ \beta_k & 0 & 0 & 0 & 0 \end{pmatrix}, $$

where $\chi^t$ denotes the transpose of $\chi$. Note that, different to the general case, the reverse operation is not a symmetry for involutions, so these equivalences are really new.

Our proof also uses the BWX bijection. Therefore, let us first recall the extended notion of pattern avoidance they have used. A *Young diagram* (or *Young shape*) is a top-justified and left-justified array of cells, i.e., an array whose rows have non-increasing lengths from top to bottom, and its columns have non-increasing lengths from left to right. A cell of a Young shape is called a *corner* if the array obtained by removing the cell is still a Young shape. Occasionally, it will be convenient to use top-right justified diagrams instead of the top-left justified diagrams defined above. We will refer to the top-right justified shapes as *NE-shapes* to avoid confusion with the ordinary Young shapes.

A *(signed) transversal* of a Young diagram $\lambda$ is an assignment of 0's and 1's (of 0's, 1's and -1's) to the cells of $\lambda$, such that each row and column contains exactly one nonzero entry. A *sparse filling* of $\lambda$ is an arrangement of 0's, 1's and -1's which has at most one nonzero entry in every row and column.

For a $k \times k$ permutation matrix $\tau$, we say that a filling $L$ of a shape $\lambda$ contains $\tau$ if there exists a $k \times k$ subshape within $\lambda$ whose induced filling is equal to $\tau$. The set of all transversals (or signed transversals) of a shape $\lambda$ which do not contain $\tau$ is denoted by $S_{\lambda}(\tau)$ (or $B_{\lambda}(\tau)$, respectively). Two signed permutation matrices $\sigma$ and $\tau$ are called *shape Wilf equivalent* if $|B_{\lambda}(\sigma)| = |B_{\lambda}(\tau)|$ for all Young shapes $\lambda$. Shape Wilf equivalence clearly implies Wilf equivalence. We will also say that $\sigma$ and $\tau$ are NE-shape Wilf equivalent if $|B_{\lambda}(\sigma)| = |B_{\lambda}(\tau)|$ for each NE-shape $\lambda$. Observe that if $\sigma$ and $\tau$ are permutation matrices, then they are shape Wilf equivalent if and only if $|S_{\lambda}(\sigma)| = |S_{\lambda}(\tau)|$ for each Young diagram $\lambda$.

By (1, Proposition 2.2), $\alpha_k$ and $\beta_k$ are shape Wilf equivalent for all $k$. The following proposition, which is also largely based on (1, Proposition 2.3), will allow us to extend this equivalence to more general patterns.

**Proposition 2.1** Let $\lambda$ be a Young shape, and let $\chi, \chi_1, \chi_2$ be signed permutations, such that $\chi_1$ and $\chi_2$ are shape Wilf equivalent. We set

$$ \theta = \begin{pmatrix} \chi_1 & 0 \\ 0 & \chi \end{pmatrix} \quad \text{and} \quad \omega = \begin{pmatrix} \chi_2 & 0 \\ 0 & \chi \end{pmatrix}. $$
There is a bijection between $\theta$-avoiding and $\omega$-avoiding sparse fillings of $\lambda$. This bijection preserves the number of nonzero entries in each row and column; in particular, $\theta$ and $\omega$ are shape Wilf equivalent. Furthermore, if $\chi$ is nonempty, the bijection preserves the filling in the corners of $\lambda$.

Note that Proposition 2.1 yields some information even when $\chi$ is the empty matrix. In such situation, the proposition shows that a bijection between pattern avoiding signed transversals can be extended to a bijection between pattern-avoiding sparse fillings, by simply ignoring the rows and columns with no nonzero entries.

We will now show how the results on shape Wilf equivalence may be applied to obtain new classes of I-Wilf equivalent patterns. Let us first give the necessary definitions. For an $n \times n$ matrix $\pi$ let $\pi^+$ denote the subfilling of $\pi$ formed by the cells of $\pi$ which are strictly above the main diagonal, and let $\pi_0^+$ denote the subfilling formed by the cells on the main diagonal and above it. For example, for $\pi = 2431$ we have

$$ \pi^+ = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}] 
  \node[inner sep=1pt] at (0,0) {1};
  \node[inner sep=1pt] at (1,0) {-1};
  \node[inner sep=1pt] at (0,1) {1};
  \node[inner sep=1pt] at (1,1) {1};
\end{tikzpicture} \quad \text{and} \quad \pi_0^+ = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}] 
  \node[inner sep=1pt] at (0,0) {1};
  \node[inner sep=1pt] at (1,0) {-1};
  \node[inner sep=1pt] at (0,1) {1};
  \node[inner sep=1pt] at (1,1) {1};
\end{tikzpicture}. $$

The coordinates of the entries in $\pi$ are used for the cells of $\pi^+$ as well. Thus, for instance, the cell (1, 2) is the top-left corner of $\pi^+$. Analogously, we define $\pi^-$ to be the filled shape corresponding to the entries strictly below the main diagonal of $\pi$. Clearly, a symmetric matrix $\pi$ is completely determined by $\pi_0^+$. Observe that a symmetric 0, 1, -1-matrix $\pi$ is a signed involution if and only if, for every $i = 1, \dots, n$, the filling $\pi_0^+$ has exactly one nonzero entry in the union of all cells of the $i$-th row and $i$-th column.

Note that $i$ is a fixed point of a signed involution $\pi$, that is $|\pi_i| = i$, if and only if the $i$-th row and the $i$-th column of $\pi^+$ have all entries equal to zero. In general, a signed involution $\pi$ need not be completely determined by the filling $\pi^+$; however, if we have two signed involutions $\pi, \rho$ with $\pi^+ = \rho^+$, then $\pi$ and $\rho$ only differ by the signs of their fixed points. If $\pi$ is a signed involution, then, for each $i = 1, \dots, n$, the filling $\pi^+$ has at most one nonzero entry in the union of the $i$-th row and $i$-th column; conversely, any filling $\pi^+$ of appropriate shape with these properties can be extended into a signed involution $\pi$, which is determined uniquely up to the sign of its fixed points.

For a signed permutation $\sigma$, let $\sigma'$ denote the involution $(\sigma'_{\sigma^t \sigma^t})$, where $\sigma^t$ is the transpose of $\sigma$. We are now ready to state our first result on I-Wilf equivalence.

**Theorem 2.2** If $\sigma$ and $\tau$ are two NE-shape Wilf equivalent signed permutation matrices, then $\sigma' \stackrel{I}{\sim} \tau'$. Moreover, the bijection between $SI_n(\sigma')$ and $SI_n(\tau')$ preserves fixed points.

**Proof:** Let $\pi \in SI_n$ be an involution. We claim that $\pi$ avoids $\sigma'$ if and only if $\pi^+$ avoids $\sigma$. To see this, notice that any occurrence of $\sigma'$ in $\pi$ can be restricted either to an occurrence of $\sigma$ in $\pi^+$ or an occurrence of $\sigma^t$ in $\pi^-$; however, since $\pi^+$ is the transpose of $\pi^-$, we know that $\pi^-$ contains $\sigma^t$ if and only if $\pi^+$ contains $\sigma$. The converse is even easier to see.

Let us choose $\pi \in SI_n(\sigma')$. Since $\pi^+$ is a sparse $\sigma$-avoiding filling, we may apply the bijection from Proposition 2.1 (adapted for NE-shapes) to $\pi^+$, to obtain a $\tau$-avoiding sparse filling of the same shape, which has a nonzero entry in a row $i$ (or column $i$) whenever $\pi^+$ has a nonzero entry in the same row (or column, respectively). Hence this filling also corresponds to an involution, more exactly, to $\rho^+$ for an involution $\rho \in SI_n$, and furthermore, the fixed points of $\rho$ are in the same position as the fixed points of $\pi$, because the position of the fixed points is determined by the zero rows and columns, which are preserved
by the bijection from Proposition 2.1. By defining the signs of the fixed points of $\rho$ to be the same as the signs of the fixed points of $\pi$, the involution $\rho$ is determined uniquely. Clearly, since $\rho^+$ avoids $\tau$, we know that $\rho$ avoids $\tau'$. Each step of this construction can be inverted which proves the bijectivity. Furthermore, the bijection preserves fixed points by construction. $\square$

By a similar reasoning, we obtain an analogous result for patterns of odd size. For a signed permutation $\sigma$, let $\sigma''$ denote the involution matrix

$$ \begin{pmatrix} 0 & 0 & \sigma \\ 0 & 1 & 0 \\ \sigma^t & 0 & 0 \end{pmatrix}, $$

and let $\sigma^*$ denote the signed permutation $(\begin{smallmatrix} 0 & \sigma \\ 1 & 0 \end{smallmatrix})$.

**Theorem 2.3** If $\sigma$ and $\tau$ are NE-shape Wilf equivalent, then $\sigma'' \stackrel{I}{\sim} \tau''$. Moreover, the bijection between $SI_n(\sigma'')$ and $SI_n(\tau'')$ preserves fixed points.

Let us apply these two theorems to some special cases of shape Wilf equivalent patterns. For an integer $k \ge 0$ and a signed permutation $\chi$, let us define

$$ \theta = \begin{pmatrix} 0 & \alpha_k \\ \chi & 0 \end{pmatrix} \quad \text{and} \quad \omega = \begin{pmatrix} 0 & \beta_k \\ \chi & 0 \end{pmatrix}. $$

As we know, the two patterns $\theta$ and $\omega$ are NE-shape Wilf equivalent. From our results, we then obtain the following classes of I-Wilf equivalent patterns.

**Corollary 2.4** We have

$$ \begin{pmatrix} 0 & 0 & 0 & \alpha_k \\ 0 & 0 & \chi & 0 \\ 0 & \chi^t & 0 & 0 \\ \alpha_k & 0 & 0 & 0 \end{pmatrix} \stackrel{I}{\sim} \begin{pmatrix} 0 & 0 & 0 & \beta_k \\ 0 & 0 & \chi & 0 \\ 0 & \chi^t & 0 & 0 \\ \beta_k & 0 & 0 & 0 \end{pmatrix} \quad \text{and} \quad \begin{pmatrix} 0 & 0 & 0 & 0 & \alpha_k \\ 0 & 0 & 0 & \chi & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & \chi^t & 0 & 0 & 0 \\ \alpha_k & 0 & 0 & 0 & 0 \end{pmatrix} \stackrel{I}{\sim} \begin{pmatrix} 0 & 0 & 0 & 0 & \beta_k \\ 0 & 0 & 0 & \chi & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & \chi^t & 0 & 0 & 0 \\ \beta_k & 0 & 0 & 0 & 0 \end{pmatrix}. $$

The special cases $\chi = \emptyset$ and $\chi = (1)$ show both of Jaggard's conjectures to be correct.

**Corollary 2.5** We have 54321 $\stackrel{I}{\sim}$ 45312 and 654321 $\stackrel{I}{\sim}$ 456123 $\stackrel{I}{\sim}$ 564312.

## 3 Barring of blocks

In (5) it was shown that the barring of $\tau$ in $12...k\tau$ and $k(k-1)...1\tau$ preserves both the Wilf class and the I-Wilf class. Furthermore it was proved that

$$ \begin{pmatrix} \alpha_k & 0 & 0 \\ 0 & \chi & 0 \\ 0 & 0 & \alpha_k \end{pmatrix} \stackrel{I}{\sim} \begin{pmatrix} \alpha_k & 0 & 0 \\ 0 & -\chi & 0 \\ 0 & 0 & \alpha_k \end{pmatrix} $$

for every signed permutation matrix $\chi$ and $k \ge 0$. Basically, the assertion follows from $123 \stackrel{I}{\sim} 123$. By a similar reasoning, we can show the I-Wilf equivalence of the reversed patterns because $321 \stackrel{I}{\sim} 321$ as well. Now we turn our attention to the general block pattern

$$ \begin{pmatrix} \chi_1 & 0 & 0 \\ 0 & \chi_2 & 0 \\ 0 & 0 & \chi_3 \end{pmatrix} $$

where the $\chi_i$ are signed permutation matrices. First we prove the following crucial statement.
**Theorem 3.1** Let $\chi_1$ and $\chi_2$ be signed permutation matrices and set

$$ \theta = \begin{pmatrix} \chi_1 & 0 \\ 0 & \chi_2 \end{pmatrix} \quad \text{and} \quad \omega = \begin{pmatrix} \chi_1 & 0 \\ 0 & -\chi_2 \end{pmatrix}. $$

For any Young shape $\lambda$, there is a bijection between $\theta$-avoiding and $\omega$-avoiding sparse fillings of $\lambda$. The bijection preserves the position of all nonzero entries, i.e., it transforms the filling only by changing the signs of some of the entries. In particular, the patterns $\theta$ and $\omega$ are shape Wilf equivalent. Moreover, if $\lambda$ is self-conjugate and at least one of the matrices $\chi_1$ and $\chi_2$ is symmetric, then the bijection maps symmetric fillings to symmetric fillings.

An immediate consequence of the previous theorem is the following:

**Corollary 3.2** For any signed permutation matrices $\chi_1, \chi_2, \chi_3$, we have

$$ \begin{pmatrix} \chi_1 & 0 & 0 \\ 0 & \chi_2 & 0 \\ 0 & 0 & \chi_3 \end{pmatrix} \sim \begin{pmatrix} \chi_1 & 0 & 0 \\ 0 & -\chi_2 & 0 \\ 0 & 0 & \chi_3 \end{pmatrix}. $$

Because of the symmetry property of the bijection we can prove an analogous result for pattern avoiding involutions.

**Corollary 3.3** Let $\chi_1, \chi_2, \chi_3$ be signed permutation matrices, at least two of which are symmetric. Then we have

$$ \begin{pmatrix} \chi_1 & 0 & 0 \\ 0 & \chi_2 & 0 \\ 0 & 0 & \chi_3 \end{pmatrix} \sim I \begin{pmatrix} \chi_1 & 0 & 0 \\ 0 & -\chi_2 & 0 \\ 0 & 0 & \chi_3 \end{pmatrix}. $$

**Proof:** By Theorem 3.1, the signed pattern $\text{diag}(\chi_1, \chi_2, \chi_3)$ is I-Wilf equivalent with the signed pattern $\text{diag}(\chi_1, \chi_2, -\chi_3)$ (note that at least one of the two matrices $\text{diag}(\chi_1, \chi_2)$ and $\chi_3$ is symmetric). By the same argument, the pattern $\text{diag}(\chi_1, \chi_2, \chi_3)$ is I-Wilf equivalent with $\text{diag}(\chi_1, -\chi_2, -\chi_3)$. Combining these facts with the observation that changing the signs of all the three blocks clearly preserves the I-Wilf class, we may even conclude that any matrix obtained by changing the signs of any of the three blocks is I-Wilf equivalent with the original matrix. $\square$

Combining Theorem 3.1 with Theorems 2.2 and 2.3, we obtain more classes of I-Wilf equivalent patterns. The following corollary gives an example.

**Corollary 3.4** Let $\chi_1$ and $\chi_2$ be signed permutation matrices. Then we have

$$ \begin{pmatrix} 0 & 0 & 0 & 0 & \chi_1 \\ 0 & 0 & 0 & \chi_2 & 0 \\ 0 & 0 & \varepsilon & 0 & 0 \\ 0 & \chi_2^t & 0 & 0 & 0 \\ \chi_1^t & 0 & 0 & 0 & 0 \end{pmatrix} \sim I \begin{pmatrix} 0 & 0 & 0 & 0 & \chi_1 \\ 0 & 0 & 0 & -\chi_2 & 0 \\ 0 & 0 & \varepsilon & 0 & 0 \\ 0 & -\chi_2^t & 0 & 0 & 0 \\ \chi_1^t & 0 & 0 & 0 & 0 \end{pmatrix}. $$

where $\varepsilon$ is empty or $\varepsilon = (1)$.

# 4 Classification

The proof of Jaggard's conjecture provides the complete classification of the I-Wilf equivalences among the patterns from $S_5$. It turns out that there are 36 different classes (in comparison with 45 symmetry classes). In (5) it was shown that $B_5$ has at most 405 I-Wilf equivalence classes. Applying the new
equivalences in this paper, we obtain 402 classes which are definitively different. (By the symmetries of an involutive permutation, the patterns are divided into 566 classes.) A list of these can be found in (8). There are 36 such I-Wilf equivalence when we restrict out attention to $S_5$.

The classification of the patterns of $B_5$ by Wilf equivalence becomes complete by Corollary 3.2. The relations given in (5) did not cover seven pairs of patterns whose Wilf equivalence was indicated by numerical results. All these cases are proved now by the corollary. Consequently, $B_5$ falls into 130 Wilf classes (in comparison with 284 symmetry classes). See (5, Table 7) for the complete list.

The bijections of Theorem 2.2 and Theorem 2.3 also provide the complete classification of $S_6$ and $S_7$ with respect to the I-Wilf equivalence. There are 203 such classes of $S_6$ obtained by all equivalences, already known or proven here. As the enumeration of involutions in $I_{12}$ avoiding the patterns shows, they are different. In a similar way, we obtain 1291 Wilf classes for $S_7$. (See (8) for a table of these.)

It is very possible that the results given here and in (5) suffice to solve the I-Wilf classification of signed patterns up to length 7. However, the numerical proof that two classes are really different for a rapidly increasing number of classes is the challenge we (and computers) have to master.

**Remark 4.1** After finishing this paper, Aaron Jaggard mentioned that he and Joseph Marincel have shown that the patterns $(k-1)k(k-2)\dots312$ and $k(k-1)\dots21$ are I-Wilf equivalent for any $k \ge 5$ by using generating tree techniques (7).

## References

[1] J. Backelin, J. West, and G. Xin, Wilf-equivalence for singleton classes, in *Proceedings of the 13th Conference on Formal Power Series and Algebraic Combinatorics*, Arizona State University, 2001, 29-38.

[2] M. Bousquet-Mélou and E. Steingrímsson, Decreasing subsequences in permutations and Wilf equivalence for involutions, *J. Algebraic Combin.* **22** (2005), 383-409.

[3] Mark Dukes, Vít Jelínek, Toufik Mansour, Astrid Reifegerste, New equivalences for pattern avoiding involutions, *arXiv:0708.1357*.

[4] W. M. B. Dukes, Vít Jelínek, Toufik Mansour and Astrid Reifegerste, New equivalences for pattern avoiding involutions, to appear in *Proc. Amer. Math. Soc.* (2008).

[5] W. M. B. Dukes, T. Mansour, and A. Reifegerste, Wilf classification of three and four letter signed patterns, to appear in *Discrete Math.* (2008).

[6] A. D. Jaggard, Prefix exchanging and pattern avoidance by involutions, *Electron. J. Combin.* **9** (2003), R16.

[7] A. D. Jaggard and Joseph J. Marincel, Generating tree isomorphisms for pattern-avoiding involutions, http://www.ams.org/amsmtgs/2098_abstracts/1023-05-1618.pdf, 2007.

[8] T. Mansour, http://www.math.haifa.ac.il/toufik/enum2005.html, 2007.