On $d$-permutations and Pattern Avoidance Classes
Bonichon and Morel first introduced $d$-permutations in their study of multidimensional permutations. Such permutations are represented by their diagrams on $[n]^d$ such that there exists exactly one point per hyperplane $x_i$ that satisfies $x_i= j$ for $i \in [d]$ and $j \in [n]$. Bonichon and Morel previously enumerated $3$-permutations avoiding small patterns, and we extend their results by first proving four conjectures, which exhaustively enumerate $3$-permutations avoiding any two fixed patterns of size $3$. We further provide a enumerative result relating $3$-permutation avoidance classes with their respective recurrence relations. In particular, we show a recurrence relation for $3$-permutations avoiding the patterns $132$ and $213$, which contributes a new sequence to the OEIS database. We then extend our results to completely enumerate $3$-permutations avoiding three patterns of size $3$.
\section{Introduction}
Starting with Knuth's \cite{knuth1973art} work on permutations in 1973, the field of pattern avoidance has been well-studied in enumerative combinatorics. Simion and Schmidt first considered pattern avoidance in their work on enumerating permutation avoidance classes in 1985 \cite{simion1985restricted}. Pattern avoidance can be defined as follows:
\begin{definition}
Let $\sigma \in S_{n}$ and $\pi \in S_{k}$, where $k \leq n$. We say that the permutation $\sigma$ \emph{contains} the pattern $\pi$ if there exists indices $c_1 < \dots < c_k$ such that $\sigma(c_1)  \cdots \sigma(c_k)$ is order-isomorphic to $\pi$. We say a permutation \emph{avoids} a pattern if it does not contain it.
\end{definition}

It is well-known that permutations avoiding certain patterns are in bijection with other combinatorial objects, such as Dyck paths \cite{krattenthaler2001permutations, reifegerste2003diagram}, maximal chains of lattices \cite{simion1985restricted}, and the Catalan and Schr{\"o}der numbers \cite{west1995generating}. In their work, Simion and Schmidt \cite{simion1985restricted} completely enumerated permutations avoiding any single pattern, two patterns, or three patterns of size $3$, paving the path for more work in the field of pattern avoidance.

More recently, Bonichon and Morel \cite{bonichon2022baxter} defined a multidimensional generalization of a permutation, called a $d$-permutation, which resembles the structure of a $(d-1)$-tuple of permutations. Tuples of permutations have been studied before \cite{gunby2019asymptotics, aldred2005permuting}, but $d$-permutations have not been thoroughly studied yet, mainly appearing in a few papers related to separable permutations \cite{gunby2019asymptotics, asinowski2010separable}. In particular, Asinoski and Mansour \cite{asinowski2010separable} presented a generalization of separable permutations that are similar to $d$-permutations and characterized these generalized permutations with sets of forbidden patterns. The study of pattern-avoidance classes of permutations has received much attention and permutations avoiding sets of small patterns have been exhaustively enumerated \cite{simion1985restricted, mansour2020enumeration, knuth1973art}. However, $d$-permutations introduced by Bonichon and Morel are slightly different than the one introduced by Asinoski and Mansour \cite{asinowski2010separable} and coincide with the classical permutation for $d=2$.

Similar to the enumeration Simion and Schmidt \cite{simion1985restricted} did in 1985, Bonichon and Morel \cite{bonichon2022baxter} started the enumeration of $d$-permutations avoiding small patterns and made many conjectures regarding the enumeration of $3$-permutations avoiding sets of two patterns. We present two main classes of results regarding the enumeration of $3$-permutation avoiding small patterns. We first completely enumerate $3$-permutations avoiding classes of two patterns and prove their respective recurrence relations, solving the conjectures presented by Bonichon and Morel \cite{bonichon2022baxter}. Further, we derive a recurrence relation for $3$-permutations avoiding $132$ and $213$, which does not appear on the OEIS database \cite{oeis} and Bonichon and Morel were unable to make a conjecture about. We then further initiate and completely enumerate $3$-permutations avoiding classes of three patterns, similar to Simion and Schmidt \cite{simion1985restricted}'s results in 1985. 

This paper is organized as follows. In Section 2, we introduce preliminary definitions and notation. In Section 3, we completely enumerate sequences of $3$-permutations avoiding two patterns of size 3 and prove four conjectures of Bonichon and Morel \cite{bonichon2022baxter}. In addition, we prove a recurrence relation for an avoidance class that does not appear on the OEIS database \cite{oeis}, completing our enumeration. In Section 4, we extend our enumeration to $3$-permutations avoiding three patterns of size 3 and prove recurrence relations for their avoidance classes. We conclude with open problems in Section 5.

\section{Preliminaries} \label{sec:preliminaries}

Let $S_n$ denote the set of permutations of $[n] = \{ 1,2, \dots, n \}$. Note that we can represent each permutation $\sigma \in S_n$ as a sequence $\sigma(1) \cdots \sigma(n)$. Further, let $\mathrm{Id}_n$ denote the identity permutation $12 \cdots n$ of size $n$ and given a permutation $\sigma \in S_n$, let $\rev(\sigma)$ denote the reverse permutation $\sigma(n) \sigma(n-1) \cdots \sigma(1)$. We further say that a sequence $w$ is \emph{consecutively increasing} (respectively \emph{decreasing}) if for every index $i$, $w(i+1) = w(i)+1$ (respectively $w(i+1) = w(i)-1$). 

For a sequence $w = w(1) \cdots w(n)$ with distinct real values, the \emph{standardization} of $w$ is the unique permutation with the same relative order. Note that once standardized, a consecutively-increasing sequence is the identity permutation and a consecutively-decreasing sequence is the reverse identity permutation. Moreover, we say that in a permutation $\sigma$, the elements $\sigma(i)$ and $\sigma(i+1)$ are \emph{adjacent} to each other. More specifically, $\sigma(i)$ is \emph{left-adjacent} to $\sigma(i+1)$ and similarly, the element $\sigma(i+1)$ is $\emph{right-adjacent}$ to $\sigma(i)$. The following definitions in this section were introduced in \cite{bonichon2022baxter}.

\begin{definition}
A \emph{$d$-permutation} $\boldsymbol{\sigma} := (\sigma_1 , \dots, \sigma_{d-1})$ of size $n$ is a tuple of permutations, each of size $n$. Let $S_{n}^{d-1}$ denote the set of $d$-permutations of size $n$. We say that $d$ is the \textit{dimension} of $\boldsymbol{\sigma}$. Moreover, the \textit{diagram} of $\sigma$ is the set of points $(i, \sigma_1(i) ,\dots, \sigma_{d-1}(i))$ for all $i \in [n]$.
\end{definition}

Note that the identity permutation is implicitly included in the diagram of a $d$-permutation, which justifies why a $d$-permutation is a $(d-1)$-tuple of permutations. For a $d$-permutation $\boldsymbol{\sigma} = (\sigma_1 ,\dots, \sigma_{d-1}),$ let $\boldsymbol{\Bar{\sigma}} = (\mathrm{Id}_n, \sigma_1, \dots, \sigma_{d-1}).$ Further, with this definition, it is natural to consider the projections of the diagram of a $d$-permutation, which is useful in defining the notion of pattern avoidance for $d$-permutations.

\begin{definition}
Given $d' \in \mathbb N$ and $\boldsymbol{i} = i_1, \dots, i_{d'} \in [d]^{d'}$, the \emph{projection on $\boldsymbol{i}$} of some $d$-permutation $\boldsymbol{\sigma}$ is the $d'$-permutation $\mathrm{proj}_{\boldsymbol{i}}(\boldsymbol{\sigma}) = (\boldsymbol{\Bar{\sigma}}_{i_2} \circ \boldsymbol{\Bar{\sigma}}_{i_1}^{-1}, \dots, \boldsymbol{\Bar{\sigma}}_{i_{d'}} \circ \boldsymbol{\Bar{\sigma}}_{i_1}^{-1} ).$
\end{definition}

We say that a projection is \emph{direct} if $i_1 < \dots < i_{d'}$ and \emph{indirect} otherwise.

\begin{remark}
There are only three direct projections of dimension $2$ of a $3$-permutation $\boldsymbol{\sigma} = (\sigma, \sigma')$. Namely, they are $\sigma$, $\sigma'$, and $\sigma' \circ \sigma^{-1}$.
\end{remark}

In the remainder of the section, we use the projection of a $3$-permutation $\boldsymbol{\sigma} = (\sigma, \sigma')$ to refer to the projection $\sigma' \circ \sigma^{-1}$. Using direct projections, Bonichon and Morel \cite{bonichon2022baxter} introduced the following definition of pattern avoidance, which coincides with the existing concept of pattern avoidance for regular permutations.

\begin{definition}
Let $\boldsymbol{\sigma} = (\sigma_1 ,\dots, \sigma_{d-1}) \in S_{n}^{d-1}$ and $\boldsymbol{\pi} = (\pi_1, \dots, \pi_{d'-1}) \in S_{k}^{d'-1}$, where $k \leq n$. We say that the $d$-permutation $\boldsymbol{\sigma}$ \emph{contains} the pattern $\boldsymbol{\pi}$ if there exists a direct projection $\boldsymbol{\sigma'}$ of dimension $d'$ and indices $c_1 < \dots < c_k$ such that $\boldsymbol{\sigma'}_i(c_1)  \cdots \boldsymbol{\sigma'}_i(c_k)$ is order-isomorphic to $\pi_i$ for all $i$. We say a $d$-permutation \emph{avoids} a pattern if it does not contain it.
\end{definition}

Given $m$ patterns $\boldsymbol{\pi_1}, \dots, \boldsymbol{\pi_m} \in S^{d'-1}_{n'}$, we write $S_{n}^{d-1}(\boldsymbol{\pi_1}, \dots, \boldsymbol{\pi_m})$ to mean the set of $d$-permutations of size $n$ that simultaneously avoid $\boldsymbol{\pi_1}, \dots, \boldsymbol{\pi_m}$.

Bonichon and Morel \cite{bonichon2022baxter} also noted symmetries on $d$-permutations that correspond to symmetries on the $d$-dimensional cube. In particular, these symmetries are counted by signed permutation matrices of dimension $d$. Such a signed permutation matrix is a square matrix with entries consisting of $-1, 0$, or $1$ such that each row and column contain exactly one nonzero element. We call $\textit{d-Sym}$ the set of such signed permutation matrices of size $d$.

This allows us to extend the well-known definitions of Wilf-equivalence and trivial Wilf-equivalence to higher dimensions.

\begin{definition}
We say that two sets of patterns $\boldsymbol{\pi_1}, \dots, \boldsymbol{\pi_k}$ and $\boldsymbol{\tau_1}, \dots, \boldsymbol{\tau_\ell}$ are \emph{d-Wilf-equivalent} if $|S_{n}^{d-1}(\boldsymbol{\pi_1}, \dots, \boldsymbol{\pi_k})| = |S_n^{d-1}(\boldsymbol{\tau_1}, \dots, \boldsymbol{\tau_\ell})|$. Moreover, these patterns are \emph{trivially d-Wilf-equivalent} if there exists a symmetry $s \in \textit{d-Sym}$ that maps $S_{n}^{d-1}(\boldsymbol{\pi_1}, \dots, \boldsymbol{\pi_k})$ to $S_n^{d-1}(\boldsymbol{\tau_1}, \dots, \boldsymbol{\tau_\ell})$ bijectively.
\end{definition}

\section{Enumeration of Pattern Avoidance Classes of at most size 2}
\label{sec:enumeration}

Bonichon and Morel \cite{bonichon2022baxter} proposed the problem of enumerating sequences of $3$-permutations avoiding at most two patterns of size 2 or 3. They provided Table \ref{double avoidance}, conjecturing the recurrences in the last four rows and leaving the remainder as open problems.

\begin{table}[htp]
    \centering
    \begin{tabular}{|c | c | c | c | c|} 
 \hline
 Patterns & \#TWE & Sequence & OEIS Sequence & Comment \\ [0.5ex] 
 \hline\hline
 12 & 1 & $1,0,0,0,0,\dots$ & & \cite{bonichon2022baxter} \\ 
 \hline
 21 & 1 &  $1,1,1,1,1,\dots$ & & \cite{bonichon2022baxter} \\
 \hline
 123 & 1 & $1,4,20,100,410,1224,2232, \dots$ & & Not in OEIS \\
 \hline
 132 & 2 & $1,4,21,116,646,3596,19981, \dots$ & & Not in OEIS \\
 \hline
 231 & 2 & $1,4,21,123,767,4994,35584, \dots$ & & Not in OEIS \\
 \hline
 321 & 1 & $1,4,21,128,850,5956,43235, \dots$ & & Not in OEIS \\
 \hline
 $123, 132$ & 2 & $1,4,8,8,0,0,0, \dots$  & & Terminates after $n=4$ \\
 \hline
 $123, 231$ & 2 & $1,4,9,6,0,0,0, \dots$ & & Terminates after $n=4$ \\
 \hline
 $123, 321$ & 1 & $1,4,8,0,0,0,0, \dots$ & & Terminates after $n=3$ \\
 \hline
 $132, 213$ & 1 & $1,4,12,28,58,114,220, \dots$ & & Theorem \ref{132,213} \\
 \hline
 $132, 231$ & 4 & $1,4,12,32,80,192,448, \dots$ & \href{http://oeis.org/A001787}{A001787} & Theorem \ref{132,231} \\
 \hline
 $132, 321$ & 2 & $1,4,12,27,51,86,134, \dots$ & \href{http://oeis.org/A047732}{A047732} & Theorem \ref{132,321} \\
 \hline
 $231, 312$ & 1 & $1,4,10,28,76,208,568, \dots$ & \href{http://oeis.org/A026150}{A026150} & Theorem \ref{231,312} \\
 \hline
 $231, 321$ & 2 & $1,4,12,36,108,324,972, \dots$ & \href{http://oeis.org/A003946}{A003946} & Theorem \ref{231,321} \\ 
 \hline
\end{tabular}
    \caption{Sequences of $3$-permutations avoiding at most two patterns of size 2 or 3. The second column indicates the number of trivially Wilf-equivalent patterns.}
    \label{double avoidance}
\end{table}

In all of the following theorems, we take constructive approaches to prove recurrence relations. Given an element $\boldsymbol{\sigma}$ in $S_n^2(\pi_1, \pi_2)$, we attempt to construct elements in $S_{n+1}^2(\pi_1, \pi_2)$ via inserting a maximal element $n+1$ into the permutations in $\boldsymbol{\sigma}$. Note that if a permutation $\sigma \in S_n$ contains a pattern $\pi$, then adding a maximal element $n+1$ anywhere into $\sigma$ still contains $\pi$. Similarly, if a permutation $\sigma \in S_n$ avoids a pattern $\pi$, then removing the maximal element $n$ from $\sigma$ will still avoid $\pi$.


\begin{theorem}\label{132,231}
Let $a_n = |S_n^2(132,231)|$. Then $a_n$ satisfies the recurrence relation $a_{n+1} = 2a_n + 2^{n}$ with initial term $a_1 =1$, which corresponds with OEIS sequence \href{http://oeis.org/A001787}{A001787}.
\end{theorem}
\begin{proof}
Given any $\boldsymbol{\sigma} = (\sigma, \sigma') \in S^2_n(132,231)$, we construct an element of $S^2_{n+1}(132,231)$ by inserting a maximal element $n+1$ in both $\sigma$ and $\sigma'$. To avoid both $132$ and $231$, the maximal element $n+1$ must be inserted into either the beginning or end of $\sigma$ and $\sigma'$; otherwise if there are elements on both sides of $n+1$, then there must be either an occurrence of $132$ or $231$.

Appending a maximal element $n+1$ onto the left of both $\sigma$ and $\sigma'$ or onto the right of both $\sigma$ and $\sigma'$ also avoids $132$ and $231$. In other words, $(\sigma (n+1), \sigma'(n+1))$ and $((n+1)\sigma, (n+1)\sigma')$ both still avoid $132$ and $231$. This contributes $2a_{n}$ different $3$-permutations in $S_{n+1}^2(132,231)$.

We now make the following claims:

\begin{claim}
The $3$-permutation $(\sigma(n+1), (n+1)\sigma')$ avoids $132$ and $231$ if and only if $\sigma$ is $\mathrm{Id}_n$ and $\sigma' \in S_n^1(132,231)$.
\end{claim} 
\begin{proof}
For the forwards direction, suppose that $(\sigma(n+1), (n+1)\sigma')$ avoids $132$ and $231$. Now writing the projection $((n+1)\sigma') \circ (\sigma(n+1))^{-1} = (\sigma_L (n+1) \sigma_R)$ for some subpermutations $\sigma_L$ and $\sigma_R$, note that $\sigma_R$ is nonempty, and hence using the reasoning mentioned above, $\sigma_L$ is empty. Otherwise, $(\sigma_L (n+1) \sigma_R)$ contains an occurrence of either $132$ or $231$. And thus $\sigma$ begins with the minimal element $1$. But because $\sigma$ is forced to avoid the $132$ pattern, it is forced to be consecutive and hence is the identity permutation.

For the backwards direction, both $(\sigma(n+1))$ and $((n+1)\sigma')$ still avoid $132$ and $231$. Further, the projection $((n+1)\sigma') \circ (\sigma(n+1))^{-1}$ evaluates to $(n+1)\sigma'$, which also still avoids $132$ and $231$. 
\end{proof}

\begin{claim}
The $3$-permutation $((n+1)\sigma, \sigma'(n+1))$ avoids $132$ and $231$ if and only if $\sigma$ is $\mathrm{rev}(\mathrm{Id}_n)$ and $\sigma' \in S_n^1(132,231)$.
\end{claim} 
\begin{proof}
For the forwards direction, we write the projection $(\sigma'(n+1))\circ((n+1)\sigma)^{-1}$ in the form of $\sigma_L (n+1) \sigma_R$. As above, $\sigma_R$ is nonempty and hence, $\sigma_L$ must be empty to avoid the patterns $132$ and $231$. So we conclude that $\sigma$ must end with a minimal element $1$. And because $\sigma$ must avoid the $231$ permutation, it is forced to be consecutively decreasing and hence is $\mathrm{rev}(\mathrm{Id}_n)$.

For the backwards direction, $((n+1)\sigma)$ and $(\sigma'(n+1))$ both still avoid $132$ and $231$. The projection $(\sigma'(n+1))\circ ((n+1)\sigma)^{-1}$ evaluates to $(n+1)\mathrm{rev}(\sigma')$. Because $132$ and $231$ are reverses of each other, $\mathrm{rev}(\sigma')$ still avoids $132$ and $231$, and thus $(n+1)\mathrm{rev}(\sigma')$ avoids these patterns as well.
\end{proof}

Thus we have shown that given any $3$-permutation $\boldsymbol{\sigma} = (\sigma, \sigma') \in S^2_n(132,231)$, we can construct two elements in $S^2_{n+1}(132,231)$; furthermore, we can construct two additional elements in $S^2_{n+1}(132,231)$ if and only if $\sigma' \in S^1_n(132,231)$ and $\sigma$ is $\Id_n$ or $\rev(\Id_n)$. Simion and Schmidt \cite{simion1985restricted} have shown that $|S^1_n(132,231)| = 2^{n-1}$. In the cases where $\sigma$ is $\Id_n$ or $\rev(\Id_n)$, it follows that $\boldsymbol{\sigma}$ avoids $132$ and $231$ if and only if $\sigma'$ avoids these patterns, and hence it follows that \begin{align*}
    a_{n+1} = 2a_n + 2^n. & \qedhere
\end{align*}

\end{proof}

\begin{theorem}\label{132,321}
Let $a_n = |S^2_n(132,321)|$. Then $a_n$ follows the recurrence relation $a_{n+1} = a_n +n(n+2)$ with initial term $a_1 = 1$, which corresponds with the OEIS sequence \href{http://oeis.org/A047732}{A047732}.
\end{theorem}
\begin{proof}
Let us write $\boldsymbol{\sigma} = (\sigma, \sigma') \in S^2_n(132,321)$ in the form $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$. We construct an element of $S^2_{n+1}(132,321)$ by inserting a maximal element $n+1$ in both $\sigma$ and $\sigma'$.

Inserting $n+1$ onto the end of $\sigma$ and $\sigma'$ always constructs a $132$-avoiding and $321$-avoiding $3$-permutation, and thus contributes $a_n$ different $3$-permutations to $S^2_{n+1}(132,321)$. 

We also have the following three cases:

\begin{enumerate}
    \item $\sigma_R$ and $\sigma_R'$ are both nonempty and $\sigma_L$, $\sigma_L'$, $\sigma_R$, and $\sigma_R'$ are all consecutively increasing. Moreover, every element of $\sigma_L$ and $\sigma_L'$ is greater than every element of $\sigma_R$ and $\sigma_R'$, respectively.
    
    \item Exactly one of $\sigma_R$, $\sigma_R'$ is empty and the other is of the form $\sigma_L n \sigma_R$, where $\sigma_L$ and $\sigma_R$ are consecutively increasing and every element of $\sigma_L$ is greater than every element of $\sigma_R$.
    
    \item Both $\sigma_R$, $\sigma_R'$ are empty.
\end{enumerate}

First we show that when $\boldsymbol{\sigma}$ is none of these cases, inserting a maximal element $n+1$ into  $\boldsymbol{\sigma}$ cannot avoid these patterns. So let $\boldsymbol{\sigma} = (\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$, where without loss of generality, $\sigma_L$ is nonincreasing. 


 Every element of $\sigma_L$ and $\sigma_L'$ still must be greater than every element of $\sigma_R$ and $\sigma_R'$, respectively; otherwise, they would contain an occurrence of $132$. So because $\sigma_L$ is not consecutively increasing, there is an occurrence of $\ell (\ell-c)$ in $\sigma_L$. 
    
    If $\sigma_R$ contains elements in the interval $(\ell-c, n)$, then $\boldsymbol{\sigma}$ would contain an occurrence of $132$. Similarly, if $\sigma_R$ contains elements in the interval $(1, \ell-c)$, then $\boldsymbol{\sigma}$ would contain an occurrence of $321$. So $\sigma_R$ is empty. Inserting $n+1$ to the left of $\ell$ gives an occurrence of $321$. And inserting $n+1$ to the right of $\ell$ gives an occurrence of $132$. So nothing outside these cases avoids $132$ and $321$.

Now we present each case:
\begin{enumerate}
    \item We claim that only $(\sigma_L n (n+1) \sigma_R, \sigma_L' n (n+1) \sigma_R')$ avoids $132$ and $321$.
    
    Because $\sigma_L$ and $\sigma_R$ are consecutive and $\sigma_R$ must start with $1$, then in the projection $(\sigma_L' n (n+1) \sigma_R') \circ (\sigma_L n (n+1) \sigma_R)^{-1}$, either $n+1$ is right-adjacent to $n$, or the composition begins with $n+1$. In the former case, this projection avoids $132$ and $321$, and hence $\boldsymbol{\sigma}$ avoids these patterns too. In the latter case, the projection is of the form $(n+1) \sigma_R' \sigma_L' n$. But  $\sigma_R' \sigma_L' n$ is strictly increasing, so the projection also avoids $132$ and $321$. Therefore the $3$-permutation $(\sigma_L n (n+1) \sigma_R, \sigma_L' n (n+1) \sigma_R')$ avoids these patterns too.
    
    Now we show that inserting $n+1$ into $\boldsymbol{\sigma}$ anywhere else cannot result in an element in $S_{n+1}^2(132,321)$. In particular, we show that we are forced to insert $n+1$ at the end of $\sigma$ and $\sigma'$ or directly after $n$ in these two permutations. Otherwise, because $\sigma_L$, $\sigma_L'$, $\sigma_R$, and $\sigma_R'$ are all consecutively increasing, $\sigma$ or $\sigma'$ would contain $132$. 
    
    Now it is sufficient to show $(\sigma_L n \sigma_R (n+1), \sigma_L' n (n+1) \sigma_R')$ and $(\sigma_L n (n+1) \sigma_R, \sigma_L' n \sigma_R' (n+1))$ do not avoid $132$ and $321$.
    
    To see the former, we take the projection $\rho$ and note that it must take one of the following three forms:
        \begin{enumerate}
            \item $\rev(\Id_{n+1})$.
            
            \item $(\pi_1 c \pi_2 m \pi_3 (c+1))$, where $m >c$ for some $m$ and $c$.
            
            \item $(\pi (n+1)c)$, where $c$ is the maximum element in $\sigma_R'$ and $\pi$ is a subpermutation. 
        \end{enumerate}
        
        In Case (a), $\rho$ contains $321$, in Case (b), $\rho$ contains $132$, and in Case (c), $\rho$ contains $132$.
        
        Similar reasoning shows that $(\sigma_L n (n+1) \sigma_R, \sigma_L' n \sigma_R' (n+1))$ does not avoid $132$ and $321$.
    
    There are $(n-1)$ ways to choose $\sigma_L n \sigma_R$ and $\sigma_L' n \sigma_R'$, so this case contributes $(n-1)^2$ distinct $3$-permutations to $S^2_{n+1}(132,321)$.
    
    \item Without loss of generality, let $\sigma_R$ be empty. Then we claim that only the $3$-permutations $((n+1)\sigma_L n, \sigma_L' n (n+1) \sigma_R')$ and $(\sigma_L n(n+1), \sigma_L' n (n+1) \sigma_R')$ avoid $132$ and $321$. 
    
    Checking that both of these $3$-permutations avoid $132$ and $321$ uses a similar argument to the previous case. Now we show that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot avoid the patterns $132$ and $321$. In particular, we must insert $n+1$ into the beginning or end of $\sigma$ and either right-adjacent to $n$ or at the end in $\sigma'$. So it is sufficient to show that $((n+1)\sigma_L n, \sigma_L' n \sigma_R' (n+1))$ does not avoid $132$ and $321$. 
    
    Now taking the projection gives us a permutation of the form $\pi (n+1) c$, where $c$ is the first element of $\sigma_L'$ and $\pi$ is some subpermutation. Because $\sigma_R'$ is nonempty, $\pi$ contains elements in $\sigma_R'$, and this composition contains an instance of $132$. 
    
    A similar argument holds for when $\sigma_R'$ is empty and $\sigma_R$ is nonempty. This case contributes $4(n-1)$ total $3$-permutations to $S^2_{n+1}(132,321)$.
    
    \item Then $(\sigma_L n (n+1), (n+1) \sigma_L' n)$, $((n+1)\sigma_L n, (n+1) \sigma_L' n)$, and $((n+1)\sigma_L n, \sigma_L' n (n+1))$ all avoid $132$ and $321$.
    
    Checking that these avoid $132$ and $321$ follow a similar reasoning to Case 1. Because we are forced to insert the maximal element $n+1$ to the beginning or end of $\sigma$ and $\sigma'$, any other insertion would not avoid $132$ and $321$.
    
    This case contributes $3$ new elements in $S^2_{n+1}(132,321)$.
\end{enumerate}
    
    And hence we conclude that \begin{align*}
        a_{n+1} &= a_n + (n-1)^2 + 4(n-1) +3 \\
        &= a_n + n(n+2). & \qedhere
    \end{align*}

\end{proof}

\begin{theorem}\label{231,312}
Let $a_n = |S^2_n(231,312)|$. Then $a_n$ follows the recurrence relation $a_{n+1} = 2a_n + 2a_{n-1}$ with initial terms $a_1 = 1$ and $a_2 =4$, which corresponds to the OEIS sequence \href{http://oeis.org/A026150}{A026150}.
\end{theorem}
\begin{proof}

Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(231,312)$ and write $\boldsymbol{\sigma}$ in the form $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$. Note that each element of $\sigma_L$ and $\sigma_L'$ are less than each element of $\sigma_R$ and $\sigma_R'$, respectively. Further, $\sigma_R$ and $\sigma_R'$ have to be consecutively decreasing. If $\sigma_R$ is nonempty, $n-1$ must be right-adjacent to $n$ in $\sigma$ to avoid instances of $231$ and $312$. We then have the following cases, where $\sigma_R$ and $\sigma_R'$ are nonempty: 
\begin{enumerate}
    \item $\boldsymbol{\sigma}$ is of the form $(\sigma_L n, \sigma_L' n)$.
    
    \item $\boldsymbol{\sigma}$ is of the form $(\sigma_L (n-1) n \sigma_R, \sigma_L' (n-1) n \sigma_R')$.
    
    \item $\boldsymbol{\sigma}$ is of the form $(\sigma_L (n-1) n \sigma_R, \sigma_L' n (n-1)  \sigma_R')$.
    
    \item $\boldsymbol{\sigma}$ is of the form $(\sigma_L n (n-1) \sigma_R, \sigma_L' (n-1) n \sigma_R')$.
    
    \item $\boldsymbol{\sigma}$ is of the form $(\sigma_L n (n-1) \sigma_R, \sigma_L' n (n-1) \sigma_R')$.
\end{enumerate}

Now we present each case:

\begin{enumerate}
    \item $(\sigma, \sigma') = (\sigma_L n, \sigma_L' n)$.
    
    The maximal element $n+1$ must be inserted adjacent to $n$ in both $\sigma$ and $\sigma'$. If not, then there would be an occurrence of $312$. Thus the following $3$-permutations all avoid $231$ and $312$: $(\sigma_L n (n+1), \sigma_L' n (n+1)), (\sigma_L n (n+1), \sigma_L' (n+1)n), (\sigma_L (n+1) n, \sigma_L' n (n+1)),$ and $(\sigma_L (n+1)n, \sigma_L' (n+1)n)$. So each instance of $\boldsymbol{\sigma}$ in this case contributes $4$ new $3$-permutations that avoid $231$ and $312$.
    
        \item $(\sigma, \sigma')= (\sigma_L (n-1) n \sigma_R, \sigma_L' (n-1) n \sigma_R')$.
        
        Then both $\sigma_R$ and $\sigma_R'$ are empty (or else there would be an occurrence of $231$). And this is counted in Case 1.
        
        \item $(\sigma, \sigma')= (\sigma_L (n-1) n \sigma_R, \sigma_L' n (n-1)  \sigma_R')$.
        
        Then $\sigma_R$ must be empty and $n (n-1) \sigma_R'$ must be consecutively decreasing. Appending the maximal element $n+1$ onto the end of $\sigma$ and $\sigma'$ also avoids $231$ and $312$. In other words, $(\sigma_L (n-1) n (n+1), \sigma_L' n (n-1)  \sigma_R' (n+1))$ avoids $231$ and $312$. In addition, the $3$-permutation $(\sigma_L (n-1) n (n+1), \sigma_L' (n+1) n (n-1)  \sigma_R')$ also avoids $231$ and $312$. 
        
        To see this, we first evaluate the projection of $(\sigma_L (n-1) n, \sigma_L' n (n-1)  \sigma_R')$. As shown in Figure 1, we can subdivide $\sigma_L$ into $\pi_L$ and $\pi_R$, where $|\pi_L| = |\sigma_L'|$. For the projection to avoid $312$, $\pi_R (n-1) n$ must be strictly increasing because $n (n-1) \sigma_R'$ is consecutively decreasing.

\begin{figure}[htp]
\centering
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.6,0) coordinate (x3)
			--++ (0.8,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (2,0) coordinate (x6)
			--++ (0.8,0) coordinate (x7)
			--++ (0.8,0) coordinate (x8);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L2-|x1) -- (L2-|x6) node[above,pos=0.5] {$\sigma_L$};
	\node at (L2-|x7) {$n-1$};
	\node at (L2-|x8) {$n$};
		 
	\draw[|-|] (L3-|x1) -- (L3-|x2) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L3-|x3) {$n$};
	\node at (L3-|x4) {$n-1$};
	\draw[|-|] (L3-|x5) -- (L3-|x8) node[above,pos=0.5] {$\sigma_R'$}; 
	
	\draw[|-|,dashed] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L1-|x6) -- (L1-|x2) node[above,pos=0.5] {$\pi_R$};
		

\end{tikzpicture}
\caption{The two-line notation used to evaluate $(\sigma_L' n (n-1) \sigma_R') \circ (\sigma_L (n-1)n)^{-1}$. The second line represents the first permutation in the $3$-permutation and the last line represents the second permutation in the $3$-permutation.}
\end{figure}
        This projection is of the form $(\sigma_L' \circ \pi_L^{-1}) n (n-1) \sigma_R'$, which still avoids $231$ and $312$. A similar argument shows that $(\sigma_L (n-1) n (n+1), \sigma_L' (n+1) n (n-1)  \sigma_R')$ also avoids $231$ and $312$ by noting that its projection is of the form $(\sigma_L' \circ \pi_L^{-1})(n+1)n (n-1) \sigma_R'$, which still avoids these patterns.
        
        Now we show that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot produce a $3$-permutation that avoids $231$ and $312$. We must insert $n+1$ adjacent to $n$ in $\sigma$. If not, then inserting $n+1$ anywhere to the left of $n-1$ contains an occurrence of $312$. Similarly, we must insert $n+1$ left-adjacent to $n$ or at the end in $\sigma'$. Inserting $n+1$ anywhere to the right of $n-1$ contains an occurrence of $231$. 
        
        We first show that $(\sigma_L (n-1) (n+1) n, \sigma_L' (n+1) n (n-1)  \sigma_R')$ cannot avoid these patterns. 
        As discussed above, we can subdivide $\sigma_L$ into $\pi_L$ and $\pi_R$, where $\pi_L$ is the same size as $\sigma_L'$ and $\pi_R(n-1)$ is consecutively increasing.
        
\begin{center}
\begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.8,0) coordinate (x3)
			--++ (0.8,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (0.8,0) coordinate (x6)
			--++ (0.8,0) coordinate (x7)
			--++ (0.8,0) coordinate (x8)
			--++ (1.2,0) coordinate (x9)
			--++ (0.8,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L2-|x1) -- (L2-|x7) node[above,pos=0.5] {$\sigma_L$};
	\node at (L2-|x8) {$n-1$};
	\node at (L2-|x9) {$n+1$};
	\node at (L2-|xx) {$n$};
		 
	\draw[|-|] (L3-|x1) -- (L3-|x2) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L3-|x5) {$n-1$};
	\node at (L3-|x4) {$n$};
	\node at (L3-|x3) {$n+1$};
	\draw[|-|] (L3-|x6) -- (L3-|xx) node[above,pos=0.5] {$\sigma_R'$}; 
	
	\draw[|-|,dashed] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L1-|x7) -- (L1-|x2) node[above,pos=0.5] {$\pi_R$};
		

\end{tikzpicture}
\end{center}
        
        Then the projection is of the form $(\sigma_L' \circ \pi_L^{-1}) \pi (r+2) r (r+1)$, where $r$ is the minimal element of $\sigma_R'$ and $\pi$ is a subpermutation. This contains an occurrence of $312$.
        
        A similar calculation shows that $(\sigma_L (n-1) (n+1) n, \sigma_L' n (n-1)  \sigma_R' (n+1))$ cannot avoid $231$ and $312$ either, because the projection is of the form $\pi (r+1) (n+1) r$ for a subpermutation $\pi$, which contains an occurrence of $231$. Hence each instance of $\boldsymbol{\sigma}$ in this case contributes $2$ new elements in $S_{n+1}^2(231,312)$.
    
        \item $(\sigma, \sigma')= (\sigma_L n (n-1) \sigma_R, \sigma_L' (n-1) n \sigma_R')$.
        
        Similar to the previous case, $n(n-1)\sigma_R$ must be consecutively decreasing and $\sigma_R'$ must be empty. As in the previous cases, $(\sigma_L n (n-1) \sigma_R (n+1), \sigma_L' (n-1) n (n+1))$ avoids $231$ and $312$. Moreover, $(\sigma_L (n+1) n (n-1) \sigma_R, \sigma_L' (n-1) n (n+1))$ also avoids these patterns. To see this, we first evaluate the projection of $(\sigma_L n (n-1) \sigma_R, \sigma_L' (n-1) n)$.
        
        \begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.6,0) coordinate (x3)
			--++ (1.0,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (2,0) coordinate (x6)
			--++ (0.8,0) coordinate (x7)
			--++ (0.8,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
	\draw[|-|] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x3) {$n$};
	\node at (L1-|x4) {$n-1$};
	\draw[|-|] (L1-|x5) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x6) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x7) {$n-1$};
	\node at (L2-|xx) {$n$};
	
	\draw[|-|,dashed] (L3-|x1) -- (L3-|x2) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L3-|x6) -- (L3-|x2) node[above,pos=0.5] {$\pi_R$};
	\node at (L3-|x4) { };

\end{tikzpicture}
\end{center}
        
        Because the projection of $(\sigma_L n (n-1) \sigma_R, \sigma_L' (n-1) n)$ is of the form $(\pi_L \circ \sigma_L^{-1}) n (n-1) \mathrm{rev}(\pi_R)$, we conclude that $n(n-1)\mathrm{rev}(\pi_R)$ must be consecutively decreasing, since this projection must avoid $231$ and $312$. We evaluate the projection of $(\sigma_L (n+1) n (n-1) \sigma_R, \sigma_L' (n-1) n (n+1))$.
        
        \begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.8,0) coordinate (x3)
			--++ (1.0,0) coordinate (x4)
			--++ (1.0,0) coordinate (x5)
			--++ (0.8,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (0.8,0) coordinate (x8)
			--++ (1.0,0) coordinate (x9)
			--++ (1.0,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x3) {$n+1$};
	\node at (L1-|x4) {$n$};
	\node at (L1-|x5) {$n-1$};
	\draw[|-|] (L1-|x6) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x7) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x8) {$n-1$};
	\node at (L2-|x9) {$n$};
	\node at (L2-|xx) {$n+1$};
	
	\draw[|-|,dashed] (L3-|x1) -- (L3-|x2) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L3-|x7) -- (L3-|x2) node[above,pos=0.5] {$\pi_R$};
	\node at (L3-|x8) { };

\end{tikzpicture}
\end{center}
        
        Then the projection of the $3$-permutation $(\sigma_L (n+1) n (n-1) \sigma_R, \sigma_L' (n-1) n (n+1))$ is of the form $(\pi_L \circ \sigma_L^{-1}) (n+1) n (n-1) \mathrm{rev}(\pi_R)$, which also avoids $231$ and $312$.
        
        Now we show that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot produce a $3$-permutation that avoids $231$ and $312$. Using similar logic to the previous case, it is sufficient to show that $(\sigma_L (n+1) n (n-1) \sigma_R, \sigma_L' (n-1) (n+1) n)$ and $(\sigma_L n (n-1) \sigma_R (n+1), \sigma_L' (n-1) (n+1) n)$ do not avoid $231$ and $312$.
        
        For the former $3$-permutation, we take the projection:
        
    \begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.8,0) coordinate (x3)
			--++ (1.0,0) coordinate (x4)
			--++ (1.0,0) coordinate (x5)
			--++ (0.8,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (0.8,0) coordinate (x8)
			--++ (1.2,0) coordinate (x9)
			--++ (1.0,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x3) {$n+1$};
	\node at (L1-|x4) {$n$};
	\node at (L1-|x5) {$n-1$};
	\draw[|-|] (L1-|x6) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x7) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x8) {$n-1$};
	\node at (L2-|x9) {$n+1$};
	\node at (L2-|xx) {$n$};
	
	\draw[|-|,dashed] (L3-|x1) -- (L3-|x2) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L3-|x7) -- (L3-|x2) node[above,pos=0.5] {$\pi_R$};
	\node at (L3-|x8) { };

\end{tikzpicture}
\end{center}
        
        The projection is of the form $(\pi_L \circ \sigma_L^{-1}) n (n+1) (n-1) \mathrm{rev}(\pi_R)$, which contains an occurrence of $231$.
        
        For the latter $3$-permutation, a similar argument shows that this projection contains an occurrence of $312$. Hence each instance of $\boldsymbol{\sigma}$ in this case contributes $2$ new elements in $S_{n+1}^2(231,312)$.
    
        \item $(\sigma, \sigma')= (\sigma_L n (n-1) \sigma_R, \sigma_L' n (n-1) \sigma_R')$.
        
        Then $n(n-1)\sigma_R$ and $n(n-1)\sigma_R'$ must be consecutively decreasing. We claim $|\sigma_R| = |\sigma_R'|$. For the sake of contradiction, suppose that $|\sigma_R'|>|\sigma_R|$. Then the $3$-permutations are:
        
    \begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.6,0) coordinate (x3)
			--++ (1,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (2,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (1,0) coordinate (x8)
			--++ (0.8,0) coordinate (x9)
			--++ (2.5,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x6) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x7) {$n$};
	\node at (L1-|x8) {$n-1$};
	\draw[|-|] (L1-|x9) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x2) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x3) {$n$};
	\node at (L2-|x4) {$n-1$};
	\draw[|-|] (L2-|x5) -- (L2-|xx) node[above,pos=0.5] {$\sigma_R'$}; 
		

\end{tikzpicture}
\end{center}
        
        The projection is of the form $\pi_1 n \pi_2 r \pi_3 (r+c)$, where $r$ is the minimal element of $\sigma_R'$, $c$ is some positive integer, and $\pi_1$, $\pi_2$, $\pi_3$ are subpermutations. And hence the projection contains $312$, a contradiction. 
        
        A similar argument holds for $|\sigma_R'|<|\sigma_R|$, so the two permutations must be the same size. Moreover, because both $n(n-1)\sigma_R$ and $n(n-1)\sigma_R'$ are consecutively decreasing, then $\sigma_R = \sigma_R'$.
        
        We immediately see that $(\sigma_L n (n-1) \sigma_R (n+1), \sigma_L' n (n-1) \sigma_R' (n+1))$ is in $S_{n+1}^2 (231,312)$.
        
        Moreover, $(\sigma_L (n+1) n (n-1) \sigma_R, \sigma_L' (n+1) n (n-1) \sigma_R')$ also avoids $231$ and $312$, because the projection is of the form $(\sigma_L' \circ \sigma_L^{-1}) (\sigma_R' \circ \sigma_R^{-1}) (n-1) n (n+1)$.
        
        Now we show that inserting the maximal element $n+1$ anywhere else cannot avoid $231$ and $312$. In fact, $n+1$ can only be inserted either at the end of $\sigma$ and $\sigma'$ or left-adjacent to $n$. If $n+1$ is inserted anywhere in $\sigma_L$ or $\sigma_L'$, then there would be an occurrence of $312$. If $n+1$ is inserted anywhere to the right of $n$ and not at the end of the permutation, then there would be an occurrence of $231$. 
        
        So we show that the $3$-permutations $(\sigma_L (n+1) n (n-1) \sigma_R, \sigma_L' n (n-1) \sigma_R' (n+1))$ and $(\sigma_L n (n-1) \sigma_R (n+1), \sigma_L' (n+1) n (n-1) \sigma_R')$ cannot avoid $231$ and $312$.
        
        For the first $3$-permutation, the projection looks like
        
            \begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.8,0) coordinate (x3)
			--++ (0.8,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (0.8,0) coordinate (x6)
			--++ (0.8,0) coordinate (x7)
			--++ (0.8,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x5) {$n-1$};
	\node at (L1-|x4) {$n$};
	\node at (L1-|x3) {$n+1$};
	\draw[|-|] (L1-|x6) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$}; 
		 
	\draw[|-|] (L2-|x1) -- (L2-|x2) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x4) {$n-1$};
	\node at (L2-|x3) {$n$};
	\node at (L2-|xx) {$n+1$};
	\draw[|-|] (L2-|x5) -- (L2-|x7) node[above,pos=0.5] {$\sigma_R'$}; 
		

\end{tikzpicture}
\end{center}
        
        Evaluating the projection gives the form $(\sigma_L' \circ \sigma_L^{-1})(n+1) \pi (n-1)(n)$ for a subpermutation $\pi$, which contains $312$.
        
        A similar argument shows that for the second $3$-permutation, the projection is of the form $(\sigma_L' \circ \sigma_L^{-1}) \pi (n-1)n(n+1)r$, where $r$ is the minimal element of $\sigma_R'$ and $\pi$ is a subpermutation. This contains $231$.
        
        So each instance of $\boldsymbol{\sigma}$ in this case contributes $2$ new elements in $S_{n+1}^2(231,312)$. 
    \end{enumerate}
    

Now we show that $3$-permutations avoiding $231$ and $312$ must be one of the forms above. We have only one form to consider, where exactly one of $\sigma$, $\sigma'$ is empty. Let $\sigma_R$ be empty and $\sigma_R'$ be nonempty. In particular, $(\sigma, \sigma')= (\sigma_L n, \sigma_L' n \sigma_R')$. 
    
    Now $n-1$ must be adjacent to $n$ in $\sigma'$. If $\sigma' = \sigma_L' (n-1) n \sigma_R'$, then $\sigma_R'$ must be empty to avoid an occurrence of $231$. Then Case 1 covers this. If $\sigma' = \sigma_L' n (n-1) \sigma_R'$, then we show that $n-1$ is adjacent to $n$ in $\sigma$. So suppose, for the sake of contradiction, that this is not the case. First, $n(n-1)\sigma_R'$ must be consecutively decreasing. Taking the projection $\sigma' \circ \sigma^{-1}$, we conclude that it is of the form $\pi_L n \pi_R k r$, where $k \neq r+1$ and $r$ is the minimal element in $\sigma_R'$. Now we consider where the element $r+1$ is in the permutation. If $r+1$ is in $\pi_L$, then there is an occurrence of $231$. If $r+1$ is in $\pi_R$, then if $k>r+1$, then there is an occurrence of $231$, and if $k<r+1$, then there is an occurrence of $312$. Hence $n-1$ must be adjacent to $n$ in $\sigma$, and a similar argument from Case 3 covers this case.
    
A similar argument also holds for when the case when $\sigma_R$ is nonempty and $\sigma_R'$ is empty. So we see that for every $3$-permutation $\boldsymbol{\sigma} = (\sigma, \sigma')$ in $S_n^2(231,312)$, inserting a maximal element $n+1$ onto the end of both $\sigma$ and $\sigma'$ always yields a $3$-permutation in $S_{n+1}^2(231,312)$; moreover, inserting a maximal element such that the parities of the two largest elements in $\sigma$ and $\sigma'$ are preserved also always yields another $3$-permutation. 

This contributes $2a_n$ different $3$-permutations to $S_{n+1}^2(231,312)$. In the case that $\boldsymbol{\sigma}$ is in the form in Case 1 (where $\sigma$, $\sigma'$ each end with the maximal element $n$), each $\boldsymbol{\sigma}$ can construct two elements in $S_{n+1}^2(231,312)$ in addition to the elements generated above, so this case constructs an additional $2a_{n-1}$ elements in $S_{n+1}^2(231,312)$. Hence \begin{align*}
    a_{n+1} = 2a_n + 2a_{n-1}. & \qedhere
\end{align*}
\end{proof}

\begin{theorem}\label{231,321}
Let $a_n = |S^2_n(231,321)|$. Then $a_n$ follows the formula $a_{n+1} = 4 \cdot 3^{n-1}$ (where $a_1 = 1$), which corresponds to the OEIS sequence \href{http://oeis.org/A003946}{A003946}.
\end{theorem}
\begin{proof}

Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(231,321)$ and let $\boldsymbol{\sigma}$ be of the form $(\sigma_L 1 \sigma_R, \sigma_L' 1 \sigma_R')$. Note that $\sigma_L$ and $\sigma_L'$ either contain one element or are empty.

We insert a minimal element $0$ to the permutation and standardize the new permutation. The element $0$ must be inserted adjacent to $1$ or in the front of both $\sigma$ and $\sigma'$. We then have the following cases:

\begin{enumerate}
    \item $(\sigma, \sigma') = (1 \sigma_R, 1 \sigma_R')$.
    
    We can see that $(0 \ 1 \ \sigma_R, 0 \ 1 \ \sigma_R')$, $(0 \ 1 \ \sigma_R, 1 \ 0 \ \sigma_R')$, $(1 \ 0 \ \sigma_R, 0 \ 1 \ \sigma_R')$, and $(1 \ 0 \ \sigma_R, 1 \ 0 \ \sigma_R')$ all avoid $231$ and $321$.
    
    So a $3$-permutation $\boldsymbol{\sigma}$ in this case constructs $4$ distinct $3$-permutations in $S_{n+1}^2 (231,321)$.
    
    \item $(\sigma, \sigma') = (1 \sigma_R, \ell 1 \sigma_R')$ for some integer $\ell$.
    
    Similar to the previous case, we see that $(0 \ 1 \ \sigma_R, 0 \ell 1 \sigma_R')$, $(0 \ 1 \ \sigma_R, \ell 0 \ 1 \ \sigma_R')$, $(1 \ 0 \ \sigma_R, 0 \ell 1 \sigma_R')$, and $(1 \ 0 \ \sigma_R, \ell 0 \ 1 \ \sigma_R')$ all avoid $231$ and $321$.
    
    A $3$-permutation $\boldsymbol{\sigma}$ in this case also constructs $4$ distinct $3$-permutations in $S_{n+1}^2 (231,321)$.

    \item $(\sigma, \sigma') = (\ell 1 \sigma_R, 1 \sigma_R')$ for some integer $\ell$.
    
    Appending a minimal element $0$ onto the front of $\sigma$ and $\sigma'$ still avoids $231$ and $321$. In particular, $(0 \ell 1 \sigma_R, 0 \ 1 \ \sigma_R')$, as well as $(\ell 0 \ 1 \ \sigma_R, 1 \ 0 \ \sigma_R')$, avoids these patterns.
    
    Now we show that inserting $0$ anywhere else cannot avoid these patterns. In particular, note that $(0 \ell 1 \sigma_R, 1 \ 0 \ \sigma_R')$ and $(\ell 0 \ 1 \ \sigma_R, 0 \ 1 \ \sigma_R')$ cannot avoid $231$ and $321$. For both $3$-permutations, the projection is of the form $1 \pi_L 0 \pi_R$ for subpermutations $\pi_L$ and $\pi_R$ (where $\pi_L$ is nonempty). This contains an instance of $231$.
    
    Hence $3$-permutations $\boldsymbol{\sigma}$ in this case constructs $2$ different elements in $S_{n+1}^2 (231,321)$.
    
    \item $(\sigma, \sigma') = (\ell_L 1 \sigma_R, \ell_R' 1 \sigma_R')$ for integers $\ell_L$, $\ell_R'$.
    
    As in the previous cases, note that $(0 \ell_L 1 \sigma_R, 0 \ell_R' 1 \sigma_R')$, as well as $(\ell_L 0 \ 1 \ \sigma_R, \ell_R' 0 \ 1 \ \sigma_R')$, avoids $231$ and $321$. 
    
    Now we show that inserting $0$ anywhere else in $\boldsymbol{\sigma}$ cannot avoid $231$ and $321$. In particular, we show that $(0 \ell_L 1 \sigma_R, \ell_R' 0 \ 1 \ \sigma_R')$ and $(\ell_L 0 \ 1 \ \sigma_R, 0 \ell_R' 1 \sigma_R')$ cannot avoid $231$ and $321$.
    
    For both $3$-permutations, the projection is $\ell_R' 1 \pi_R$ for some subpermutation $\pi_R$, which contains an instance of $321$ since $\pi_R$ must contain the element $0$. And hence $3$-permutations $\boldsymbol{\sigma}$ in this case constructs $2$ distinct elements in $S_{n+1}^2 (231,321)$.
    
\end{enumerate}

We claim that in $S_n^2(231,321)$, exactly half of the elements $\boldsymbol{\sigma} = (\sigma, \sigma')$ satisfy $\sigma(1) = 1$ after standardization. The base case can be seen in $S_2^2(231,321)$. Then for our inductive step let us assume that this is the case for $S_n^2(231,321)$. We wish to show that this is true for $S_{n+1}^2(231,321)$. In each case above, exactly half of the $3$-permutations constructed have the property $\sigma(1)= 1$ and the other half satisfy $\sigma(1) \neq 1$ after standardization, so via induction, exactly half of the elements in $S_n^2(231,321)$ satisfy $\sigma(1) = 2$.

Then when $\sigma(1) = 1$, we are in Case 1 or Case 2, which contribute $4$ elements in $S_{n+1}^2(231,321)$. When $\sigma(1) \neq 1$, we are in Case 3 or Case 4, which contribute $2$ elements in $S_{n+1}^2(231,321)$.

Thus we conclude that $$a_{n+1} = \frac{a_n}{2}\cdot 4 + \frac{a_n}{2} \cdot 2 = 3a_n.$$

We can see that $a_2 = 4$, so we conclude that \begin{align*}
    a_{n+1} = 4 \cdot 3^{n-1}. & \qedhere
\end{align*}
\end{proof}

This allows us to prove all the conjectures Bonichon and Morel \cite{bonichon2022baxter} have made in regard to $3$-permutations avoiding two patterns of size $3$. However, there is one class of $3$-permutations that have yet to be classified, which we now enumerate. We begin with a well-known lemma.

\begin{lemma}\label{inverselemma}
Let $\sigma$ be a permutation and $\pi$ be an involution. Then $\sigma$ avoids $\pi$ if and only if $\sigma^{-1}$ avoids $\pi$. 
\end{lemma}

Because $132$ and $213$ are both involutions, $\sigma$ avoids $132$ if and only if $\sigma^{-1}$ avoids $132$. The same reasoning holds for the pattern $213$.

\begin{theorem}\label{132,213}
Let $a_n = |S_n^2(132,213)|$. Then $a_n$ follows the recurrence relation $$a_{n+1} = a_n + 3 \cdot 2^{n-1} +2(n-1)$$ with the initial term $a_1 = 1$.
\end{theorem}
\begin{proof}

Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(132,213)$ and let $\boldsymbol{\sigma}$ be of the form $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$.

Note that $\sigma_L n$ and $\sigma_L' n$ are increasing; otherwise we would contain an occurrence of $213$. Moreover, they must be consecutively increasing; if not we would have an occurrence of $132$.

Adding a maximal element $n+1$ right-adjacent to $n$ in both $\sigma$ and $\sigma'$ always produces a $3$-permutation in $S_{n+1}^2(132,213)$. To see this, suppose that $|\sigma_L| > |\sigma_L'|$. Then the projection $\sigma' \circ \sigma^{-1}$ would look like

\begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.6,0) coordinate (x3)
			--++ (0.6,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (2,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (0.6,0) coordinate (x8)
			--++ (0.8,0) coordinate (x9)
			--++ (2.5,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x6) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x7) {$n$};
	\draw[|-|] (L1-|x8) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x2) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x3) {$n$};
	\draw[|-|] (L2-|x4) -- (L2-|xx) node[above,pos=0.5] {$\sigma_R'$}; 
	
	\draw[|-|,dashed] (L3-|x1) -- (L3-|x4) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L3-|xx) -- (L3-|x8) node[above,pos=0.5] {$\pi_R$};
	\draw[|-|,dashed] (L3-|x4) -- (L3-|x8) node[above,pos=0.5] {$\pi_M$};

\end{tikzpicture}
\end{center}

This has the form $(\pi_R \circ \sigma_R^{-1}) \pi_L \pi_M$, where $\pi_L$ is consecutively increasing and ends with $n$. This must avoid $132$ and $213$.

Now consider $(\sigma_1, \sigma_2) = (\sigma_L n (n+1) \sigma_R, \sigma_L' n (n+1) \sigma_R')$. The projection would look like

\begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.6,0) coordinate (x3)
			--++ (1,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (2,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (1,0) coordinate (x8)
			--++ (0.8,0) coordinate (x9)
			--++ (2.5,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x6) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x7) {$n$};
	\node at (L1-|x8) {$n+1$};
	\draw[|-|] (L1-|x9) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x2) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x3) {$n$};
	\node at (L2-|x4) {$n+1$};
	\draw[|-|] (L2-|x5) -- (L2-|xx) node[above,pos=0.5] {$\sigma_R'$}; 
	
	\draw[|-|,dashed] (L3-|x1) -- (L3-|x4) node[above,pos=0.5] {$\pi_L$};
	\draw[|-|,dashed] (L3-|xx) -- (L3-|x9) node[above,pos=0.5] {$\pi_R$};
	\draw[|-|,dashed] (L3-|x4) -- (L3-|x9) node[above,pos=0.5] {$\pi_M$};
		

\end{tikzpicture}
\end{center}

This has the form $(\pi_R \circ \sigma_R^{-1}) \pi_L (n+1) \pi_M$, which still avoids $132$ and $213$. The case where $|\sigma_L| = |\sigma_L'|$ follows as well. To see when $|\sigma_L| < |\sigma_L'|$, we utilize Lemma 3.5. We've showed that if $\sigma$, $\sigma'$, and $\sigma' \circ \sigma^{-1}$ avoid $132$ and $213$ and $|\sigma_L| > |\sigma_L'|$, then $\sigma_2 \circ \sigma_1^{-1}$ also avoids $132$ and $213$. So it follows that if $\sigma'$, $\sigma$, and $\sigma \circ \sigma'^{-1}$ avoid $132$ and $213$ and $|\sigma_L'| > |\sigma_L|$, then $\sigma_1 \circ \sigma_2^{-1}$ also avoids $132$ and $213$. But Lemma 3.5 shows that $\sigma_1 \circ \sigma_2^{-1}$ avoiding $132$ and $213$ implies that $\sigma_2 \circ \sigma_1^{-1}$ also avoids $132$ and $213$.

Hence appending a maximal element $n+1$ right-adjacent to $n$ in both $\sigma$ and $\sigma'$ contributes $a_{n}$ elements in $S^2_{n+1}(132,213).$


In addition, we have the following cases:

\begin{enumerate}
    \item $\sigma = \sigma'$.
    
    Then $((n+1) \sigma, (n+1) \sigma')$ also avoids $132$ and $213$. 
    
    Now we show that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ does not avoid $132$ and $213$. Note that $n+1$ must be inserted either at the beginning or right-adjacent to $n$ in $\sigma$ and $\sigma'$. If we insert $n+1$ to the left of $n$ (but not at the beginning), then we contain an instance of $132$. Similarly, if we insert $n+1$ to the right of $n$ (but not adjacent to $n$), then we contain an instance of $213$.
    
    Then we show that $((n+1)\sigma, \sigma_L' n (n+1) \sigma_R')$ and $(\sigma_L n (n+1) \sigma_R, (n+1) \sigma')$ cannot avoid $132$ or $213$. To see that the first $3$-permutation cannot avoid $132$ or $213$, its projection is of the form $1\pi(n+1)\ell$, where $\ell$ is the first element in $\sigma_L'$ and $\pi$ is a subpermutation. This contains an occurrence of $132$. A similar argument shows that the projection of the latter $3$-permutation also contains $213$.  The exception is when $\sigma = \sigma' = \Id_n$, in which case $((n+1)\Id_n, \Id_n (n+1))$ and $(\Id_n (n+1), (n+1) \Id_n)$ both avoid $132$ and $213$.
    
    Since Simion and Schmidt \cite{simion1985restricted} showed there are $2^{n-1}$ possible permutations that avoid $132$ and $213$ with size $n$, this contributes an additional $2^{n-1} + 2$ elements in $S_{n+1}^2(132,213)$.
    
    \item $\sigma = \Id_n$ and $\sigma' \neq \Id_n$.
    
    We note that $(\sigma (n+1), (n+1) \sigma')$ avoids $132$ and $213$. In the special case where $\sigma_R'$ is consecutively increasing, then $((n+1) \sigma, \sigma_L' n (n+1) \sigma_R')$ is also an element in $S_{n+1}^2(132,213)$.
    
    Now we show that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot avoid $132$ and $213$. We first show that $(\sigma (n+1), \sigma' (n+1))$ and $((n+1)\sigma, (n+1) \sigma')$ cannot avoid $132$ and $213$. Taking the projection of these $3$-permutations evaluates to $\sigma' (n+1)$, which contains an occurrence of $213$ because $\sigma'$ is not the identity and hence must contain an occurrence of $21$.
    
    Now we show that $((n+1) \sigma, \sigma' (n+1))$ cannot avoid $132$ and $213$. Let us write $\sigma' = \ell \pi_2$. Note that $\ell>1$, because if $\sigma'$ started with $1$, then it would become the identity.
    
    Taking the projection gives us the form $\pi_2 (n+1) \ell$, which contains an occurrence of $132$.
    
    Now let $\sigma_R'$ be nonincreasing. We wish to show that $((n+1) \sigma, \sigma_L' n (n+1) \sigma_R')$ cannot avoid $132$ and $213$. Because $\sigma_R'$ contains an instance of $21$ and every element in $\sigma_R'$ is smaller than every element in $\sigma_L'$, taking the projection gives an occurrence of $213$.
    
    Simion and Schmidt \cite{simion1985restricted} has shown that there are $2^{n-1}$ different $\sigma'$ that avoid $132$ and $213$, so $(\sigma (n+1), (n+1) \sigma')$ contributes $2^{n-1}-1$ different elements to $S_{n+1}^2(132,213)$. Moreover, the special case $((n+1) \sigma, \sigma_L' n (n+1) \sigma_R')$ contributes $n-1$ elements to $S_{n+1}^2(132,213)$.
    
    \item $\sigma \neq \Id_n$ and $\sigma' = \Id_n$.
    
    This case also contributes $2^{n-1}+n-2$ elements in $S_{n+1}^2(132,213)$. This is a consequence of Lemma 3.5 and the reasoning discussed above. 
    
\end{enumerate}

Now we show that nothing else can contribute to $S_{n+1}^2(132,213)$. Let $\boldsymbol{\sigma} = (\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$ and assume that $\sigma_R$ and $\sigma_R'$ are nonempty and that $\sigma \neq \sigma'$. This implies that $\sigma$ and $\sigma'$ cannot be the identity permutation.

Inserting $n+1$ at the beginning of $\sigma$ and $\sigma'$ gives the projection $(\sigma' \circ \sigma^{-1}) (n+1)$. And because $\sigma \neq \sigma'$, then $\sigma' \circ \sigma^{-1}$ cannot be the identity and hence contains an occurrence of $21$. So the projection contains an occurrence of $213$.

We show that $((n+1) \sigma, \sigma_L' n (n+1) \sigma_R')$ cannot avoid $132$ and $213$ either. To see this, let $|\sigma_L| \geq |\sigma_L'|$. Then we evaluate the projection.

\begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (1.1,0) coordinate (x2)
			--++ (2,0) coordinate (x3)
			--++ (0.6,0) coordinate (x4)
			--++ (0.8,0) coordinate (x5)
			--++ (0.8,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (0.6,0) coordinate (x8)
			--++ (0.6,0) coordinate (x9)
			--++ (2.5,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x2) -- (L1-|x7) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x8) {$n$};
	\node at (L1-|x1) { \ \ \ \ \ $n+1$};
	\draw[|-|] (L1-|x9) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x1) -- (L2-|x3) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x4) {$n$};
	\node at (L2-|x5) {$n+1$};
	\draw[|-|] (L2-|x6) -- (L2-|xx) node[above,pos=0.5] {$\sigma_R'$}; 
		

\end{tikzpicture}
\end{center}

This is of the form $r \pi_L (n+1) \pi_R \ell$, where $\ell$ is an element in $\sigma_L'$ (or $n$ if $\sigma_L'$ is empty), $r$ is an element in $\sigma_R'$, and $\pi_L$ and $\pi_R$ are subpermutations. Because elements in $\sigma_L'$ are greater than elements in $\sigma_R'$, then the projection contains an occurrence of $132$. Lemma 3.5 concludes that when $|\sigma_L| \leq |\sigma_L'|$, the projection cannot avoid $132$ either.

Finally we show that $( \sigma_L n (n+1) \sigma_R, (n+1) \sigma')$ cannot avoid $132$ and $213$. Let $|\sigma_L| \geq |\sigma_L'|$. Then we evaluate the projection.

\begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (1.1,0) coordinate (x2)
			--++ (2,0) coordinate (x3)
			--++ (0.6,0) coordinate (x4)
			--++ (0.6,0) coordinate (x5)
			--++ (2,0) coordinate (x6)
			--++ (0.6,0) coordinate (x7)
			--++ (1,0) coordinate (x8)
			--++ (0.8,0) coordinate (x9)
			--++ (2.5,0) coordinate (xx);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x6) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x7) {$n$};
	\node at (L1-|x8) {$n+1$};
	\draw[|-|] (L1-|x9) -- (L1-|xx) node[above,pos=0.5] {$\sigma_R$};	
		 
	\draw[|-|] (L2-|x2) -- (L2-|x3) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x4) {$n$};
	\node at (L2-|x1) {\ \ \ \ \ $n+1$};
	\draw[|-|] (L2-|x5) -- (L2-|xx) node[above,pos=0.5] {$\sigma_R'$}; 
		

\end{tikzpicture}
\end{center}

This is of the form $(\sigma_R' \circ \sigma_R^{-1}) (n+1) \pi_L n \pi_R$, where $\pi_L$ and $\pi_R$ are subpermutations. Because $\sigma_R' \circ \sigma_R^{-1}$ must contain the minimal element $1$, the projection contains an occurrence of $132$, and Lemma 3.5 concludes that when $|\sigma_L| \leq |\sigma_L'|$, this result holds as well.

And because nothing else can contribute elements in $S_{n+1}^2(132,213)$, we conclude that \begin{align*}
    a_{n+1} = a_n + 3 \cdot 2^{n-1} + 2(n-1). & \qedhere
\end{align*}

\end{proof}

These theorems allow us to enumerate all $3$-permutations avoiding two patterns of size $3$ that correspond to existing OEIS sequences. Moreover, since the sequence in Theorem \ref{132,213} does not yet correspond to a sequence on the OEIS database \cite{oeis}, it allows the complete classification and enumeration of all $3$-permutations avoiding two patterns of size $3$.

\section{Enumeration of Pattern Avoidance Classes of size 3}

Having enumerated all $3$-permutations avoiding two patterns, we now turn our attention to enumerating $3$-permutations avoiding three patterns, as Simion and Schmidt \cite{simion1985restricted} have done with classic permutations. In Table \ref{triple avoidance}, we extend Bonichon and Morel's \cite{bonichon2022baxter} conjectures to $3$-permutations avoiding three patterns of size $3$.

\begin{table}[h]
    \centering
    \begin{tabular}{|c | c | c | c | c|} 
 \hline
 Patterns & \#TWE & Sequence & OEIS Sequence & Comment \\ [0.5ex] 
 \hline\hline
 $123,132,213$ & 3 &  $1,4,2,0,0, \dots$ & & Terminates after $n=3$ \\ 
 \hline
 $123,132,231$ & 4 &  $1,4,3,0,0,\dots$ & & Terminates after $n=3$ \\
 \hline
 $123,231,312$ & 1 & $1,4,0,0,0, \dots$ & & Terminates after $n=2$ \\
 \hline
 $123,231,321$ & 2 & $1,4,3,0,0, \dots$ & & Terminates after $n=3$ \\
 \hline
 $132,213,312$ & 2 & $1,4,6,8,10, \dots$ & \href{http://oeis.org/A005843}{A005843} & Theorem \ref{132,213,312} \\
 \hline
 $132,213,321$ & 1 & $1,4,9,16,25, \dots$ & \href{http://oeis.org/A000290}{A000290} & Theorem \ref{132,213,321} \\
 \hline
 $132,231,312$ & 2 & $1,4,7,10,13, \dots$  & \href{http://oeis.org/A016777}{A016777} & Theorem \ref{132,231,312} \\
 \hline
 $213, 231, 321$ & 4 & $1,4,6,8,10, \dots$ & \href{http://oeis.org/A005843}{A005843} & Theorem \ref{213,231,321} \\
 \hline
 $231,312,321$ & 1 & $1,4,7,19,40, \dots$ & \href{http://oeis.org/A006130}{A006130} & Theorem \ref{231,312,321} \\
 \hline
\end{tabular}
    \caption{Sequences of $3$-permutations avoiding three permutations of size $3$. The second column indicates the number of trivially Wilf-equivalent patterns.}
    \label{triple avoidance}
\end{table}

\begin{theorem}\label{132,213,312}
Let $a_n = |S_n^2(132,213,312)|$. Then $a_{n+1}$ follows the formula $a_{n+1} = 2(n+1)$ for $n>0$ (with initial term $a_1=1$).
\end{theorem}
\begin{proof}
Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(132,213,312)$. Let $\boldsymbol{\sigma}$ be of the form $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R').$ 

Note that $\sigma_R$ and $\sigma_R'$ have to be either empty or consecutively decreasing, and similarly, $\sigma_L$ and $\sigma_L'$ have to be either empty or consecutively increasing. Moreover, every element in $\sigma_L$ and $\sigma_L'$ must be larger than every element in $\sigma_R$ and $\sigma_R'$, respectively. If not, there would be an occurrence of $132$. 

We have the following cases:
\begin{enumerate}
    \item $\sigma_L$, $\sigma_R$ are nonempty.
    
    If $\sigma_L'$ and $\sigma_R'$ are nonempty, consider $\boldsymbol{\sigma} = (\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$ in $S_{n}^2 (132,213,312)$. Note that inserting $n+1$ right-adjacent to $n$ in both $\sigma$ and $\sigma'$ will avoid $132$, $231$, and $312$. In particular, $(\sigma_L n (n+1) \sigma_R, \sigma_L' n (n+1) \sigma_R')$ avoids $132$, $213$, and $312$. 
    
    Now we show that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ does not yield an element of $S_{n+1}^2 (132,213,312)$. Consider $\sigma_L n \sigma_R$. We cannot insert $n+1$ in the beginning of this permutation, or else there would be an instance of $312$. Further, we cannot insert $n+1$ anywhere to the left of $n$, or else there would be an instance of $132$. There would also be an occurrence of $213$ if $n+1$ is inserted anywhere to the right of $n$ that is not adjacent to $n$. 
    
    Hence $n+1$ is forced to be right-adjacent to $n$ in $\sigma$. The same conclusion follows for $\sigma'$.
    
    If $\sigma_L'$ is empty, then $\sigma' = \rev(\Id_n)$. The projection $\sigma' \circ \sigma^{-1}$ contains an occurrence of $132$, and hence this case is impossible. Similarly, if $\sigma_R'$ is empty, the projection $\sigma' \circ \sigma^{-1}$ contains an occurrence of $312$, and this case is also impossible.
    
    Therefore every element in this case contributes $1$ element in $S_{n}^2 (132,213,312)$.
    
    \item $\sigma_L$ is empty.
    
    If both $\sigma_L'$ and $\sigma_R'$ are nonempty, then $\boldsymbol{\sigma} = (\rev(\Id_n), \sigma_L' n \sigma_R')$. Taking the projection gives an instance of $132$ because every element in $\sigma_L'$ is larger than every element in $\sigma_R'$. And hence this is not a valid element in $S_{n}^2 (132,213,312)$, so this case is impossible.
    
    If $\sigma_L'$ is empty, then we conclude that $(\sigma, \sigma') = (\rev(\Id_n), \rev(\Id_n))$. Following similar logic to the previous case, $n+1$ must be inserted adjacent to $n$ in both $\sigma$ and $\sigma'$ to avoid $312$ and $213$. Note that $((n+1)\rev(\Id_n), (n+1)\rev(\Id_n))$ avoids $132$, $213$, and $312$. However, the projections of the $3$-permutations $((n+1)\rev(\Id_n), (n (n+1) \rev(\Id_{n-1}))$, $(n(n+1)\rev(\Id_{n-1}), (n+1)\rev(\Id_n))$, and $(n(n+1)\rev(\Id_{n-1}), n(n+1)\rev(\Id_{n-1}))$ all cannot avoid $132$, $213$, and $312$, so $(\rev(\Id_n), \rev(\Id_n))$ contributes one additional element to $S_{n+1}^2 (132,213,312)$, in addition to inserting $n+1$ right-adjacent to $n$ in both $\sigma$ and $\sigma'$ as discussed in the previous case.
    
    If $\sigma_R'$ is empty, then $(\sigma, \sigma') = (\rev(\Id_n), \Id_n)$. The element $n+1$ must be inserted adjacent to $n$ in $\sigma$, while $n+1$ must be inserted at the end of $\sigma'$. We can see that $((n+1)\rev(\Id_n), \Id_n (n+1))$ is an element of $S_{n+1}^2 (132,213,312)$ and furthermore, $(n (n+1) \rev(\Id_{n-1}), \Id_n (n+1))$ is not an element, because the projection $\sigma' \circ \sigma^{-1}$ contains an instance of $312$. 
    
    Hence each element in this case contributes $1$ element towards $S_{n+1}^2 (132,213,312)$, with the exception of $(\rev(\Id_n), \rev(\Id_n))$, which contributes $2$ elements towards $S_{n+1}^2 (132,213,312)$.
    
    \item $\sigma_R$ is empty. 
    
    If $\sigma_L'$ is nonempty, then $\boldsymbol{\sigma} = (\Id_n, \sigma_L' n \sigma_R')$. Then $n+1$ is forced to be right-adjacent to $n$ for both $\sigma$ and $\sigma'$, which contributes $1$ element to $S_{n+1}^2 (132,213,312)$.
    
    If $\sigma_L'$ is empty, then $(\sigma, \sigma') = (\Id_n, \rev(\Id_n))$. Note that $(\Id_n(n+1), (n+1)\rev(\Id_n))$ avoids $132$, $213$, and $312$, so $(\Id_n, \rev(\Id_n))$ contributes one additional element to $S_{n+1}^2 (132,213,312)$ in addition to inserting $n+1$ right-adjacent to $n$ in both $\sigma$ and $\sigma'$.
    
    Hence each element in this case contributes $1$ element towards $S_{n+1}^2 (132,213,312)$, with the exception of $(\Id_n, \rev(\Id_n))$, which contributes $2$ elements towards $S_{n+1}^2 (132,213,312)$.

\end{enumerate}

Inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot provide an element in $S_{n+1}^2 (132,213,312)$, and hence $a_{n+1} = a_n +2$. We have the base case $a_2 = 4$, thus \begin{align*}
    a_{n+1} = 2(n+1). & \qedhere
\end{align*}
\end{proof}

\begin{theorem}\label{132,213,321}
Let $a_n = |S_n^2(132,213,321)|$. Then $a_{n+1}$ follows the formula $a_{n+1} = (n+1)^2$.
\end{theorem}
\begin{proof}
Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(132,213,321)$. Write $(\sigma, \sigma')$ as $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$. 

Using a similar reasoning discussed in Theorem \ref{132,213,312}, note that $\sigma_L$, $\sigma_L'$, $\sigma_R$, and $\sigma_R'$ are consecutively increasing. Moreover, every element in $\sigma_L$ and $\sigma_L'$ is larger than every element in $\sigma_R$ and $\sigma_R'$, respectively.

Similar to the reasoning in Theorem \ref{132,213,312}, $(\sigma_L n (n+1) \sigma_R, \sigma_L' n (n+1) \sigma_R')$ is in $S_{n+1}^2(132,213,321)$. This contributes $a_n$ different $3$-permutations to $S_{n+1}^2(132,213,321)$. We also have the following cases:

\begin{enumerate}
    \item $\sigma_R$ is empty and $\sigma_R'$ is nonempty.
    
    Note that this implies that $\sigma = \Id_n$ and $\sigma' \neq \Id_n$. Then $((n+1) \Id_n, \sigma_L' n (n+1) \sigma_R')$ avoids $132$, $213$, and $312$.
    
    Inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot avoid $132$, $213$, and $312$. In $\sigma$, we must insert $n+1$ at the beginning of the permutation, or else we contain an instance of $132$. Similarly, we must insert $n+1$ right-adjacent to $n$ in $\sigma'$. If $n+1$ is left of $n$, then $\sigma'$ contains an instance of $321$. If $n+1$ is right of $n$ but not adjacent, then $\sigma'$ contains an instance of $213$.
    
    And hence $((n+1) \Id_n, \sigma_L' n (n+1) \sigma_R')$ is the only $3$-permutation we can construct in $S_{n+1}^2(132,213,321)$. Hence this case contributes $n-1$ elements to $S_{n+1}^2(132,213,321)$.
    
    \item $\sigma_R$ is nonempty and $\sigma_R'$ is empty.
    
    This implies that $\sigma' = \Id_n$ and $\sigma \neq \Id_n$. Note that $(\sigma_L n (n+1) \sigma_R, (n+1) \Id_n)$ belongs to $S_{n+1}^2(132,213,321)$. Using a similar argument as in Case 1, inserting $n+1$ in $\boldsymbol{\sigma}$ anywhere else does not avoid $132$, $213$, and $312$. Hence this case contributes $n-1$ different $3$-permutations to $S_{n+1}^2(132,213,321)$.
    
    \item Both $\sigma_R$, $\sigma_R'$ are empty.
    
    This implies that $\sigma = \sigma' = \Id_n$. We see that $((n+1)\Id_n,\Id_n (n+1))$, $((n+1)\Id_n, (n+1)\Id_n)$, and $(\Id_n (n+1), (n+1) \Id_n)$ all avoid $132$, $213$, and $312$. And using the same reasoning as in Case 1 shows that inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot avoid these patterns, and hence this case contributes $3$ elements to $S_{n+1}^2(132,213,321)$.
\end{enumerate}

Lastly when $\sigma$ and $\sigma'$ are not the identity permutation, then $\sigma_R$ and $\sigma_R'$ are both nonempty, and the same argument in Case 1 shows that inserting $n+1$ anywhere not right-adjacent to $n$ in $\sigma$ and $\sigma'$ cannot avoid $132$, $213$, and $312$. Hence no other insertions of $n+1$ in $\boldsymbol{\sigma}$ produce an element in $S_{n+1}^2(132,213,321)$, and so $$a_{n+1} = a_n + 2n + 1.$$

The base case is $a_1 = 1$, so we conclude that \begin{align*}
    a_{n+1} = (n+1)^2. & \qedhere
\end{align*}
\end{proof}

\begin{theorem}\label{132,231,312}
Let $a_n = |S_n^2(132,231,312)|$. Then $a_n$ follows the recurrence relation $a_{n+1} = a_n+3$ with initial term $a_1 = 1$.
\end{theorem}
\begin{proof}
Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(132,231,312)$. Write $(\sigma, \sigma')$ as $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$. Note that $n \sigma_R$ and $n \sigma_R'$ must be consecutively decreasing to avoid $312$ and $132$. 

We insert a maximal element $n+1$ into $\sigma$ and $\sigma'$ to count how many elements in $S_{n+1}^2(132,231,312)$ there are. Note that $(\sigma (n+1), \sigma' (n+1))$ avoids $132$, $231$, and $312$. So this contributes $a_n$ different $3$-permutations to $S_{n+1}^2(132,231,312)$. We have the following additional cases:

\begin{enumerate}
    \item $\sigma = \rev(\Id_n)$ and $\sigma' \neq \rev(\Id_n)$.
    
    This forces $\sigma'$ to be the identity. Then $((n+1)\rev(\Id_n), \sigma' (n+1))$ avoids $132$, $231$, and $312$. Now inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot avoid these patterns. Namely, if $n+1$ is inserted anywhere not in the beginning or end of $\sigma$, there is an occurrence of $231$. Moreover, inserting $n+1$ into the beginning of $\sigma'$ contains $312$. If $n+1$ is inserted anywhere not in the beginning or end of $\sigma'$, there is an occurrence of either $231$ or $132$. Hence $((n+1)\rev(\Id_n), \sigma' (n+1))$ is the only element we can construct in $S_{n+1}^2(132,231,312)$ in this case. And this case contributes one element towards $S_{n+1}^2(132,231,312)$.
    
    \item $\sigma' = \rev(\Id_n)$ and $\sigma \neq \rev(\Id_n)$.
    
    Then similar to Case 1, $(\sigma (n+1), (n+1) \rev(\Id_n))$ avoids $132$, $231$, and $312$, and inserting $n+1$ anywhere else into this $3$-permutation cannot construct a $3$-permutation in $S_{n+1}^2(132,231,312)$. Hence this case contributes one element towards $S_{n+1}^2(132,231,312)$.
    
    \item $\sigma = \sigma' =\rev(\Id_n)$.
    
    Note that $((n+1) \rev(\Id_n), (n+1) \rev(\Id_n))$ works. Now we show that no other insertions of $n+1$ into this $3$-permutation avoids the patterns $132$, $231$, and $312$. The projection of $( \rev(\Id_n) (n+1), (n+1) \rev(\Id_n))$ contains an occurrence of $231$ and the projection of $((n+1) \rev(\Id_n), \rev(\Id_n) (n+1))$ contains an occurrence of $312$, and hence this case contributes one element towards $S_{n+1}^2(132,231,312)$.
\end{enumerate}

Inserting $n+1$ into $(\sigma, \sigma') = (\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$ anywhere else cannot avoid $132$, $231$, and $312$, where $\sigma, \sigma' \neq \rev(\Id_n)$. This implies that $\sigma_L$ and $\sigma_L'$ are nonempty.

Inserting $n+1$ left-adjacent to $n$ contains $132$ and inserting $n+1$ anywhere to the left of this contains $312$. Further, inserting $n+1$ anywhere to the right of $n$ (but not at the end of the permutation) contains $231$. Hence we must insert $n+1$ at the end of the permutation, and no other insertions of $n+1$ in $\boldsymbol{\sigma}$ avoid $132$, $231$, and $312$.

Thus $$a_{n+1} = a_n+3.$$

Because our base case is $a_1 = 1$, this is equivalent to $a_{n+1} = 3n+1$.
\end{proof}

\begin{theorem}\label{213,231,321}
Let $a_n = |S_n^2(213, 231, 321)|$. Then $a_{n+1}$ follows the formula $a_{n+1} = 2(n+1)$ for $n>0$ (with initial term $a_1 = 1$).
\end{theorem}
\begin{proof}
Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(213,231,321)$. Writing $(\sigma, \sigma')$ as $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$, note that $\sigma_L$, $\sigma_L'$, $\sigma_R$, and $\sigma_R'$ are all consecutively increasing or empty.

We insert a maximal element $n+1$ to $\sigma$ and $\sigma'$ in an attempt to construct an element in $S_{n+1}^2(213,231,321)$. If $\sigma_R$ and $\sigma_R'$ are nonempty, we cannot construct an element of $S_{n+1}^2(213,231,321)$ via insertion because inserting $n+1$ to the left of $n$ contains $321$, inserting $n+1$ right-adjacent to $n$ contains $231$, and inserting $n+1$ anywhere else contains $213$. Then it is enough to consider $(\sigma, \sigma') = (\Id_n, \Id_n)$. We have two cases:

\begin{enumerate}
    \item We insert $n+1$ to the end of $\sigma$. 
    
    Then we can insert $n+1$ anywhere in $\sigma'$ and the resulting $3$-permutation is an element of $S_{n+1}^2(213,231,321)$. So this case contributes $n+1$ different elements to $S_{n+1}^2(213,231,321)$.
    
    \item We do not insert $n+1$ to the end of $\sigma$. 
    
    Note that inserting $n+1$ into the same position in $\sigma$ and $\sigma'$ avoids $213$, $231$, and $321$. Further, $(\Id_{n-1} (n+1)n, \Id_{n} (n+1))$ also avoids these patterns. 
    
    Inserting $n+1$ anywhere else contains one of these patterns because the resulting projection contains either $321$ or $231$, and hence this case contributes $n+1$ different $3$-permutations to $S_{n+1}^2(213,231,321)$.
\end{enumerate}

And hence \begin{align*}
    a_{n+1} = 2(n+1). & \qedhere
\end{align*}
\end{proof}

\begin{theorem}\label{231,312,321}
Let $a_n = |S_n^2(231,312,321)|$. Then $a_n$ follows the recurrence relation $$a_{n+1} = a_n + 3a_{n-1}$$ with initial terms $a_1 = 1$ and $a_2 = 4$.
\end{theorem}
\begin{proof}
Let $\boldsymbol{\sigma} = (\sigma, \sigma') \in S_n^2(231,312,321)$. Write $(\sigma, \sigma')$ as $(\sigma_L n \sigma_R, \sigma_L' n \sigma_R')$.

Note that $(\sigma (n+1), \sigma' (n+1))$ is an element of $S_{n+1}^2(231,312,321)$. This contributes $a_n$ different $3$-permutations towards $S_{n+1}^2(231,312,321)$. We consider the following additional case: when $\sigma_R$ and $\sigma_R'$ are empty.

Then $(\sigma, \sigma') = (\sigma_L n, \sigma_L' n)$, and thus $(\sigma_L (n+1)n, \sigma_L' n(n+1))$, $(\sigma_L (n+1)n, \sigma_L' (n+1)n)$, and $(\sigma_L n(n+1), \sigma_L' (n+1)n)$ are all elements in $S_{n+1}^2(231,312,321)$. Inserting $n+1$ anywhere else cannot avoid these patterns, because inserting $n+1$ anywhere non-adjacent to $n$ contains $312$. And hence this case contributes $3a_{n-1}$ distinct $3$-permutations to $S_{n+1}^2(231,312,321)$.

Now when either $\sigma_R$ and $\sigma_R'$ are nonempty, we show that inserting $n+1$ anywhere but the end of the $3$-permutation cannot avoid $231$, $312$, and $321$. Let $\sigma_R$ be nonempty. Then we must insert $n+1$ at the end of $\sigma$; otherwise, inserting $n+1$ to the right of $n$ contains $231$, inserting left-adjacent to $n$ contains $321$, and inserting to the left of $n$ contains $312$. And we evaluate the projection $(\sigma_L n \sigma_R (n+1), \sigma_L' (n+1) n)$:

\begin{center}
    \begin{tikzpicture}[coo/.style={coordinate}]
	\path (0,0) coordinate (x1) --++ (2,0) coordinate (x2)
			--++ (0.6,0) coordinate (x3)
			--++ (0.6,0) coordinate (x4)
			--++ (0.6,0) coordinate (x5)
			--++ (0.8,0) coordinate (x6)
			--++ (0.8,0) coordinate (x7);
	\foreach \i in {1,2,3}
		\coordinate[] (L\i) at (0,-\i);
		
		
	\draw[|-|] (L1-|x1) -- (L1-|x2) node[above,pos=0.5] {$\sigma_L$};
	\node at (L1-|x3) {$n$};
	\node at (L1-|x7) {$n+1$};
	\draw[|-|] (L1-|x4) -- (L1-|x6) node[above,pos=0.5] {$\sigma_R$}; 
	
	\draw[|-|] (L2-|x1) -- (L2-|x5) node[above,pos=0.5] {$\sigma_L'$};
	\node at (L2-|x7) {$n$};
	\node at (L2-|x6) {$n+1$};
		
\end{tikzpicture}
\end{center}

Since $\sigma_R$ is nonempty, this contains an instance of $312$. The case where $\sigma_R'$ is nonempty is similar. Inserting $n+1$ anywhere else in $\boldsymbol{\sigma}$ cannot produce an element in $S_{n+1}^2(231,312,321)$, and hence \begin{align*}
    a_{n+1} = a_n + 3a_{n-1}. & \qedhere
\end{align*}
\end{proof}

\section{Final Remarks and Open Problems}

In this paper, we completely enumerated $3$-permutations avoiding two patterns of size $3$ and three patterns of size $3$. The theorems in this paper prove all the conjectures by Bonichon and Morel \cite{bonichon2022baxter} regarding $3$-permutations avoiding two patterns of size $3$ and extend their conjectures to classify  $3$-permutations avoiding all classes of three patterns of size $3$. We conclude with the following open problems.

\begin{problem}
Enumerate $3$-permutations avoiding one pattern of size $3$ or one pattern of size $4$.
\end{problem}

Although this paper has shown connections between $3$-permutations avoiding two patterns of size $3$ and their recurrence relations, there are no existing OEIS sequences \cite{oeis} that correspond with the number of $3$-permutations avoiding one pattern of size $3$ or $3$ permutations avoiding one pattern of size $4$. In a similar vein, enumeration of $d$-permutations with dimension greater than $3$ remains an open problem.

Bonichon and Morel \cite{bonichon2022baxter} also introduced other tables enumerating $3$-permutations avoiding other combinations of patterns, such as avoiding patterns with dimension $3$ or avoiding exactly one permutation of size 2 and dimension 3 and exactly one permutation of size 3 and dimension 2. We present a few of these as future directions to continue.

\begin{conjecture}[Bonichon and Morel \cite{bonichon2022baxter}]
The $3$-permutations avoiding the $3$-patterns $(12,12)$ and $(231,312)$ are enumerated by the OEIS sequence \href{http://oeis.org/A295928}{A295928}.
\end{conjecture}

In addition, Table \ref{future problems} by Bonichon and Morel \cite{bonichon2022baxter} presents $3$-permutations avoiding a permutation of size 2 and dimension 3 as well as a pattern of size 3 and dimension 2. Many of these sequences also correspond to existing sequences on the OEIS database \cite{oeis}, but little research has been done to enumerate such sequences of $3$-permutations. It would be interesting to prove these recurrences that result from $3$-permutations avoiding patterns with different dimensions.

\begin{table}[htp]
    \centering
    \begin{tabular}{|c | c | c | c | c|} 
 \hline
 Patterns & \#TWE & Sequence & OEIS Sequence & Comment \\ [0.5ex] 
 \hline\hline
 $123, (12,12)$ & 1 & $1,3,14,70,288,822,1260, \dots$ & & Not in OEIS \\
 \hline
 $123, (12,21)$ & 3 & $1,3,6,6,0,0,0, \dots$ & & Terminates after $n=4$ \\
 \hline
 $132, (12,12)$ & 2 & $1,3,11,41,153,573,2157, \dots$ & \href{http://oeis.org/A281593}{A281593?} & \\
 \hline
 $132, (12,21)$ & 6 & $1,3,11,43,173,707,2917, \dots$ & \href{http://oeis.org/A026671}{A026671?} &  \\
 \hline
 $231, (12,12)$ & 2 & $1,3,9,26,72,192,496, \dots$  & \href{http://oeis.org/A072863}{A072863?} &  \\
 \hline
 $231, (12,21)$ & 4 & $1,3,11,44,186,818,3706, \dots$ & & Not in OEIS \\
 \hline
 $231, (21,12)$ & 2 & $1,3,12,55,273,1428,7752, \dots$ & \href{http://oeis.org/A001764}{A001764?} &  \\
 \hline
 $321, (12,12)$ & 1 & $1,3,2,0,0,0,0, \dots$ & & Terminates after $n=3$ \\
 \hline
 $321, (12,21)$ & 3 & $1,3,11,47,221,1113,5903, \dots$ & \href{http://oeis.org/A217216}{A217216?} &  \\
 \hline
\end{tabular}
    \caption{Sequences of $3$-permutations avoiding one pattern of size 3 and dimension 2 and one pattern of size 2 and dimension 3. The ``?" after the OEIS sequences mean that the sequences match on the first few terms and Bonichon and Morel \cite{bonichon2022baxter} conjectured that they are the same. The second column indicates the number of trivially Wilf-equivalent patterns.}
    \label{future problems}
\end{table}

We notice that the sequence \href{http://oeis.org/A001787}{A001787} in Theorem \ref{132,231} counts the number of $132$-avoiding permutations of length $n+2$ with exactly one occurrence of a $123$-pattern and the number of Dyck $(n+2)$-paths with exactly one valley at height $1$ and no higher valley \cite{oeis}. In this spirit, we propose the following problem:
\begin{problem}
Find combinatorial bijections to explain the relationships between the $3$-permutation avoidance classes found in this paper and their recurrence relations.
\end{problem}
In general, the problem of enumerating $d$-permutations avoiding sets of small patterns is widely open. Since several of these enumeration sequences correspond to sequences on the OEIS database \cite{oeis}, there are certainly interesting combinatorial properties of these $3$-permutation avoidance classes, and there are several bijections to find that explain these sequences.


\section*{Acknowledgements}

This research was conducted at the 2022 University of Minnesota Duluth REU and is supported by Jane Street Capital, the NSA (grant number H98230-22-1-0015), the NSF (grant number DMS-2052036), and the Harvard College Research Program. The author is indebted to Joe Gallian for his dedication and organizing the University of Minnesota Duluth REU. Lastly, a special thanks to Joe Gallian, Amanda Burcroff, Maya Sankar, and Andrew Kwon for their invaluable feedback and advice on this paper.

\newpage

2022-08-26T02:03:14.000
2208
2208.08506
en
https://arxiv.org/abs/2208.08506
Bonichon and Morel first introduced $d$-permutations in their study of multidimensional permutations. Such permutations are represented by their diagrams on $[n]^d$ such that there exists exactly one point per hyperplane $x_i$ that satisfies $x_i= j$ for $i \in [d]$ and $j \in [n]$. Bonichon and Morel previously enumerated $3$-permutations avoiding small patterns, and we extend their results by first proving four conjectures, which exhaustively enumerate $3$-permutations avoiding any two fixed patterns of size $3$. We further provide a enumerative result relating $3$-permutation avoidance classes with their respective recurrence relations. In particular, we show a recurrence relation for $3$-permutations avoiding the patterns $132$ and $213$, which contributes a new sequence to the OEIS database. We then extend our results to completely enumerate $3$-permutations avoiding three patterns of size $3$.
Combinatorics (math.CO)
On $d$-permutations and Pattern Avoidance Classes
Qwen/Qwen-72B
1. YES
2. YES