\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{caption}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
%\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\input{preambule.tex}
\usepackage{authblk}
\usepackage[switch]{lineno}
\begin{document}
\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Baxter $d$-Permutations and \\
\vskip .1in
Other Pattern-Avoiding Classes
}
\vskip 1cm
\large
Nicolas Bonichon and Pierre-Jean Morel \\
Univ. Bordeaux \\
CNRS, Bordeaux INP\\
LaBRI \\
UMR 5800\\
F-33400 Talence\\
France\\
\href{mailto:nicolas.bonichon@u-bordeaux.fr}{\tt nicolas.bonichon@u-bordeaux.fr} \\
\href{mailto:Pierre-Jean.Morel@bordeaux-inp.fr}{\tt Pierre-Jean.Morel@bordeaux-inp.fr}
\end{center}
\vskip .2 in
\begin{abstract}
A permutation of size $n$ can be identified with its diagram in which there
is exactly one point in each row and column in the grid $[n]^2$.
In this paper we consider multidimensional permutations (or
$d$-permutations), which are identified with their diagrams on the grid
$[n]^d$ in which there is exactly one point per hyperplane
$x_i=j$ for $i\in[d]$ and $j\in[n]$. We first exhaustively investigate all
small pattern-avoiding
classes for $d=3$. We provide several bijections to enumerate some of these classes and
we propose conjectures for others. We then give a
generalization of the well-studied Baxter permutations to higher dimensions.
In addition, we provide a vincular pattern-avoidance
characterization
of Baxter $d$-permutations.
\end{abstract}
\section{Introduction}\label{sec:intro}
A permutation $\sigma=\sigma(1), \ldots,\sigma(n) \in S_n$ is a bijection from
$[n]:=\{1,2, \ldots,n\}$ to itself. The (2-dimensional) \emph{diagram} of
$\sigma$ is simply the set of points $P_\sigma:=\{(i,\sigma(i)), 1\leq i \leq
n\}$. The diagrams of permutations of size $n$ are exactly the point sets
such that
every row and column of $[n]^2$ contains exactly one point.
\begin{figure}[!htb]
\center{\includegraphics[width=0.4\textwidth]{example1.pdf}}
\caption{The diagram of the 3-permutation \permfirst~together with its
3 projections
of dimension 2: the blue, red permutations that define the
$3$-permutation and green permutation {\color{axeX} $51$} that is
deduced from the two
first
permutations.}\label{fig:example1}
\end{figure}
In this paper we are interested in $d$-dimensional diagrams: sets of points
$P_\bsig$ of $[n]^d$ such that every hyperplane $x_i=j$ with $i \in [d]$ and $j \in [n]$
contains exactly one point of $P_\bsig$. Such a diagram is equivalently
described
by a sequence of $d-1$ permutations $\bsig:=(\sigma_1, \ldots,\sigma_{d-1})$
such
that
$$P_\sigma=\{(i,\sigma_1(i), \sigma_2(i), \ldots, \sigma_{d-1}(i)), i \in
[n]\}.$$ Figure~\ref{fig:example1} gives an example of a 3-permutation of
size 6. We remark that different generalizations of permutations to higher
dimensions have also been proposed, such as Latin
squares~\cite{earnest2014permutation, earnest2014permutation} or other
``semi-dense'' multidimensional permutations~\cite{eriksson2000combinatorial}.
Permutation-tuples have already been studied (see, for
instance,~\cite{gunby2019asymptotics,aldred2005permuting}), but as
far as we know, the $d$-permutations have been explicitly considered
only in a few papers: \cite{asinowski2010separable,gunby2019asymptotics}. From
our
point of view, the paper of Asinoski and Mansour~\cite{asinowski2010separable}
is the most significant in our context: they present a generalization of
\emph{separable
permutations} (permutations that can be recursively decomposed with two
elementary composition operations: add the second diagram after the first one
and shift it above or below the first diagram). The formal definition is
provided in
Section~\ref{sec:baxter}. In addition, they characterize those
$d$-permutations with a set of forbidden patterns.
The study of permutations defined by forbidden patterns has received a lot of
attention and sets of small patterns have been exhaustively
studied~\cite{knuth1973art,simion1985restricted,mansour2020enumeration}.
The first main contribution of this paper is to initiate the exhaustive study
of small patterns for 3-permutations. For this purpose, we propose a
definition of pattern avoidance for $d$-permutations. We say that the
3-permutation $\bsig$ contains the $3$-permutation $\bpi:=\perm{\pi_1}{\pi_2}$
if there is a subset of $P_\bsig$
that is order isomorphic to $P_\bpi$. Also, we say that $\bsig$ contains a
2-permutation $\pi$ if one of its (direct) projections contains $\pi$. We let
$S_n^{d-1}(\bpi_1, \ldots,\bpi_k)$ denote the set of $d$-permutations of size
$n$
that avoid all patterns $\bpi_1, \ldots,\bpi_k$. The
formal definition is provided in Section~\ref{sec:prelim}. This definition is slightly different from the one
introduced in~\cite{asinowski2010separable}. The present definition has the
advantage of being more expressive than the previous one and it matches the
classical one for $d=2$.
With this definition in mind, we first investigate exhaustively the enumeration
of 3-permutations defined by small sets of patterns to avoid.
Since $3$-permutations are defined by a couple of permutations, it is not
surprising that we fall back on existing combinatorial objects from different
fields: $S_n^2(\perm{12}{12})$ are in bijection with intervals in
the weak-Bruhat order (see Prop.~\ref{prop:bruhat}), $S_n^2(\perm{12}{21},
\perm{312}{132})$ are the
allowable pairs sorted by a priority queue~\cite{atkinson1995priority}. Also,
several ``OEIS coincidences'' lead us to conjecture other bijections. This is
the
case for four different pairs of size 3 permutations (see Table~\ref{tab:pat2}).
In
addition, even very simple patterns lead to sequences not listed in the
\textit{On-Line Encyclopedia of Integer Sequences} (OEIS)~\cite{oeis}. This is in
particular the case for all non-trivially equivalent patterns of size 3 ($S_n^2(\perm{123}{123}), S_n^2(\perm{123}{132}), S_n^2(\perm{132}{213}),
S_n^2(123), S_n^2(312)$ and $S_n^2(321)$) and some 2- and 3-dimensional
pairs of patterns ($S_n^2(132, \perm{12}{21})$,
$S_n^2(213, \perm{12}{12})$, $S_n^2(231, \perm{12}{12})$,
$S_n^2(231, \perm{21}{12})$, $S_n^2(321, \perm{21}{12})$) (see
Section~\ref{sec:prelim} for the notation).
The second main contribution of this paper is a generalization of Baxter
permutations to higher dimensions. Baxter permutations are a central family of
permutations that have received a lot of attention, in particular because they are
in bijection with a large variety of combinatorial objects:
\begin{itemize}
\item twin binary
trees~\cite{dulucq1998baxter},
\item plane bipolar
orientations~\cite{bonichon2010baxter},
\item triples of non-intersecting lattice
paths~\cite{dulucq1998baxter},
\item monotone 2-line meanders~\cite{fusy_meanders},
open diagrams~\cite{burrill2016tableau},
\item Baxter tree-like
tableaux~\cite{aval2021baxter},
\item boxed arrangements of axis-parallel
segments in $\mathbb{R}^2$~\cite{felsner2011bijections},
\end{itemize}
and many others.
With the bijection with boxed arrangements in mind, the following
question~\cite{cardinal_open,asinowski2010separable,silveira2018note} was
raised: What are the 3-dimensional analog of Baxter
permutations? In this paper we propose an analog of Baxter permutations of
any dimension $d\geq 3$. The
proposed extension seems natural to us, but we did not investigate the
potential links with boxed arrangements. The generalization of the
bijection with boxed arrangements in higher dimensions remains open.
In addition, we propose a generalization of vincular
patterns for $d$-permutations and we characterize Baxter $d$-permutations
by a set of forbidden vincular patterns (Theorem~\ref{thm:cara-sep}).
The rest of this paper is organized as follows. In Section~\ref{sec:prelim} we
give some definitions and examples of $d$-permutations. We also formalize the
notion of patterns for $d$-permutations and we give a few simple properties. Then
in Section~\ref{sec:small-pat} we provide an exhaustive study of the
enumeration of 3-permutations that avoid different sets of small patterns. For
some known sequences, we provide (simple)
explanations. Then in Section~\ref{sec:baxter} we propose a definition of
Baxter $d$-permutations that generalizes the classic Baxter permutations. We
also generalize vincular patterns and we characterize Baxter
$d$-permutations in terms of vincular pattern-avoidance. Finally, in
Section~\ref{sec:conclusion} we conclude with a list of open problems.
\section{Preliminaries}\label{sec:prelim}
Let $S_n$ be the symmetric group on $[n] :=\{1,2, \ldots,n\}$.
Given a permutation
$$\sigma=\sigma(1), \ldots,\sigma(n) \in S_n,$$
the \emph{diagram} of $\sigma$,
denoted by $P_\sigma$, is the point set $\{(1,\sigma(1)), (2,\sigma(2)), \ldots,
(n,\sigma(n))\}$. A permutation $\sigma$ \emph{contains} a permutation (or a
\emph{pattern}) $\pi=\pi(1), \ldots,\pi(k) \in S_k$ if there exist indices $c_1
< \cdots < c_k$ such that $\sigma(c_1) \cdots \sigma(c_k)$ is
order isomorphic to
$\pi$. We say that the set of indices $c_1, \ldots, c_k$, and by extension the
point
set $\{(c_1,
\sigma(c_1)), \ldots, (c_k, \sigma(c_k))\}$, is an \emph{occurrence}
of the $\pi$.
We let $\Id_n$ denote the identity permutation of size $n$. Given a set of
patterns $\pi_1, \ldots, \pi_k$, we let $S_n(\pi_1, \ldots, \pi_k)$ denote the
set
of permutations of $S_n$ that avoid each pattern $\pi_i$.
\begin{definition}
A \emph{$d$-permutation} of size $n$, $\bsig:=(\sigma_1,
\ldots,\sigma_{d-1})$
is a sequence of $d-1$ permutations of size $n$. We let $S_n^{d-1}$ denote
the set of $d$-permutations of size $n$. Let
$\bbasig=(\Id_n,\sigma_1, \ldots,\sigma_{d-1})$. Then $d$ is called the
\emph{dimension} of the permutation.
The \emph{diagram} of a $d$-permutation $\bsig$ is the set of points in
$P_\bsig:=\{ (\basig_1(i)$,
$\basig_2(i), \ldots,\basig_{d}(i)), i \in [n] \}$.
\end{definition}
A $2$-permutation is in fact a (classical) permutation. A $d$-permutation can
be seen as a sequence of $d$ permutations such that the
first one is the identity (as defined with the notation $\bbasig$). This first
trivial permutation can be forgotten, leading to a sequence of $d-1$
permutations. The choice to have this offset of 1 is motivated by the fact the
value $d$ matches the dimension of the diagram of the $d$-permutation.
The \emph{$d$-diagrams} of size $n$ are exactly the point sets of $[n]^d$ such
that every
hyperplane $x_i=j$ with $i \in [d]$ and $j \in [n]$ contains exactly one point.
One can observe that $|S_n^{d-1}| = n!^{d-1}$.
Figure~\ref{fig:example1} gives an example of a $3$-permutation of size 6.
Suppose given $P:=\{p_1, \ldots, p_n\}$ a set of points in $\mathbb{R}^d$ such
that every
hyperplane $x_j=\alpha$ with $\alpha\in \mathbb{R}$ contains at most one point
of $P$. The \emph{standardization} of $P$ is the point set
$P'=\{p'_1, \ldots, p'_n\}$ in $[n]^{d-1}$ such that the relative order with
respect
to each axis is the same. Hence the standardization of a subset of points of a
diagram is the diagram of a (smaller) $d$-permutation (with the same dimension).
In what follows we identify a $d$-permutation and its
diagram, so that a transformation on one can be directly translated into the
other. For instance, removing a point of a permutation means removing one
point of its diagram and considering the permutation of the standardization of
the sub-diagram.
At this point we are tempted to define a pattern in the following way: a
$d$-permutation $\bsig \in S_n^{d-1}$ contains a pattern $\bpi\in S_k^{d-1}$ if
there exists a subset of points of the diagram of $\bsig$ such that its
standardization is equal to the diagram of $\bpi$ (see
Figure~\ref{fig:pattern-ex}).
\begin{figure}[htb]
\center{\includegraphics[width=0.4\textwidth]{example1.pdf}}
\caption{On the left, the 3-permutation \perm{1432}{3124}. The red dots are
an instance of the pattern \perm{132}{213} that
is represented in the
middle. The red dots are also an instance of the pattern 231 that is
represented on the right.}\label{fig:pattern-ex}
\end{figure}
This definition has been considered in~\cite{gunby2019asymptotics}, for
instance, in the context of permutation tuples. For $d=2$, this definition is
consistent with the classical definition over permutations. In higher
dimensions, it is convenient to deal also with patterns of smaller dimensions
(which is not possible when $d=2$). Hence we provide a more general
definition of pattern that matches the previous one when the dimension of
the pattern is equal to the dimension of the permutation.
Given a sequence of indices $\boldsymbol{i}:=i_1, \ldots, i_{d'} \in
[d]^{d'}$, the \emph{projection} on $\boldsymbol{i}$ of the $d$-permutation $\bsig$
is the $d'$-permutation
$\proj_{\boldsymbol{i}}(\bsig):=\basig_{i_2}\basig_{i_1}^{-1},
\basig_{i_3}\basig_{i_1}^{-1}, \ldots,\basig_{i_{d'}}\basig_{i_1}^{-1}$.
Then $d'$ is
the \emph{dimension} of the projection.
When dealing with permutations of dimension 2 or 3, we often use $x,y,z$ instead of $1,2,3$.
\begin{remark} We have $\proj_{1,i}(\bsig)=\sigma_{i-1}=\basig_i$ and
$\proj_{i,1}(\bsig)=\basig_i^{-1}$. In particular, when $d=3$, we have
$\proj_{xy}(\bsig)={\color{axeZ}\sigma_1}$ and
$\proj_{xz}(\bsig)={\color{axeY}\sigma_2}$, and so
$\proj_{yz}(\bsig)={\color{axeY}\sigma_2}{\color{axeZ}\sigma_1}^{-1}$.
For instance, $\proj_{yz}(\permfirst)=\permfirstproj$ (see
Figure~\ref{fig:example1}).
\end{remark}
A projection $\proj_{\boldsymbol{i}}$ is \emph{direct} if $i_1 < i_2 < \cdots <
i_{d'}$ and \emph{indirect} otherwise.
\begin{definition}
Let $\bsig=(\sigma_1, \ldots, \sigma_{d-1}) \in S^{d-1}_n$ and
$\bpi=(\pi_1, \ldots, \pi_{d'-1}) \in S^{d'-1}_k$ with $k\leq n$.
Then $\bsig$ \emph{contains the pattern} $\bpi$
if there exist a direct projection $\bsig'=\proj_{\boldsymbol{i}}(\bsig)$
of
dimension $d'$ and indices $c_1 < \cdots < c_k$ such that
$\sigma'_i(c_1) \cdots \sigma'_i(c_k)$
is order isomorphic to $\pi_i$ for all $i\in [d']$.
A permutation \emph{avoids} a pattern if it does not contain it.
\end{definition}
Given a set of patterns $\bpi_1, \ldots, \bpi_k$, we let
$S_n^{d-1}(\bpi_1, \ldots, \bpi_k)$ denote
the set of $d$-permutations that avoid each pattern $\bpi_i$.
This definition of pattern differs slightly from the one proposed
in~\cite{asinowski2010separable}: here we consider only \emph{direct}
projections, whereas they consider every projection. The advantage of our
convention is that for $d=2$ our definition matches the classical definition of
pattern avoidance: $S_n^2(\bpi) = S_n(\bpi)$, where, for instance, the set of
$2$-permutations that avoid $2413$ with the other definition is $S_n(2413,
3142)$, since $3142=\proj_{yx}(2413)$.
We observe that a $d$-permutation $\bsig$ contains a $d$-permutation $\bpi$
if there exists a subset of points of its diagram that have the same relative
positions as those of the diagram of the pattern $\bpi$. This implies that
$\sigma_i \in S(\pi_i) \forall i \in [d-1]$.
Hence
$$S_n(\pi_1)\times S_n(\pi_2) \cdots \times S_n(\pi_{d-1}) \subseteq
S_n^{d-1}(\bpi).$$
In general this inclusion is strict. For instance, the \perm{132}{312} does not
contain the pattern \perm{12}{12} but {\color{axeZ} 132} and {\color{axeY} 312}
both contain the pattern 12 (but in different positions).
Avoiding a pattern $\pi$ of dimension 2 means that each projection of dimension $2$ avoids $\pi$, in particular the $d-1$ permutations defining the $d$-permutation, hence
$$S_n^{d-1}(\pi) \subseteq \underbrace{S_n(\pi)\times \cdots \times
S_n(\pi)}_\text{$d-1$ times}.$$
Once again, in general this inclusion is strict. For instance,
$\perm{132}{132} \in S_n(123)\times S_n(123)$ but not in $S_n^2(123)$ since
$\proj_{yz}(\perm{132}{132})={\color{axeX}123}$.
We conclude this section with the bijections of $S_n^{d-1}$ that correspond to
symmetries of the $d$-dimensional cube. These operations are defined by
signed permutation matrices of dimension $d$. Let us formalize this. A
\emph{signed permutation matrix} is a square matrix with entries in
$\{-1,0,1\}$ such
that each row and column contains exactly one non-zero entry. The set of such
matrices of size $d$ will be
denoted by \emph{$d-\Sym$} (or simply \emph{$\Sym$} when the dimension
$d$ is
understood).
Given $s \in d-\Sym$ and $\bsig \in S_n^{d-1}$, we define $s(\bsig)$ as
the $d$-permutation whose diagram is the
standardization of the point set $$P':=\{(s.(p_1, \ldots, p_d)^T)^T,
(p_1, \ldots, p_d) \in P_\bsig \}.$$
For instance, in two dimensions, $\matSym{-1}{0}{0}{1}(\sigma)$ is the
\emph{reverse}
permutation of $\sigma$, denoted by $\rev(\sigma)$:
$\rev(\sigma)(i)=\sigma(n-i+1)$. $\matSym{0}{1}{1}{0}(\sigma)$ is the
\emph{inverse}
permutation of $\sigma$, denoted by $\sigma^{-1}$. In dimension 2, there are 8
symmetries and in dimension
3,
there are 48 ($|3$-$\Sym|=48$).
\section{Pattern avoidance}\label{sec:small-pat}
In this section, we give some exhaustive enumerations of small pattern-avoiding
$d$-permutations. We first recall known results for $d=2$ and then we
investigate the case $d=3$.
We start with combinations of basic patterns.
Two sets of patterns $\bpi_1,\bpi_2, \ldots,\bpi_k$ and
$\btau_1,\btau_2, \ldots,\btau_{k'}$ are \emph{$d$-Wilf-equivalent} if
$$|S_n^{d-1}(\bpi_1,\bpi_2, \ldots,\bpi_k)|=
|S_n^{d-1}(\btau_1,\btau_2, \ldots,\btau_{k'})|.$$
We say that two sets of
patterns $\bpi_1,\bpi_2, \ldots,\bpi_k$ and
$\btau_1,\btau_2, \ldots,\btau_{k'}$ are \emph{trivially $d$-Wilf-equivalent} if
there
exists a
symmetry $s\in d-\Sym$ that is a bijection from
$S_n(\bpi_1,\bpi_2, \ldots,\bpi_k)$ to $S_n(\btau_1,\btau_2,
\ldots,\btau_{k'})$.
In
particular, if each pattern $\bpi_1,\bpi_2, \ldots,\bpi_k,
\btau_1,\btau_2, \ldots,\btau_{k'}$ is of dimension $d$, the two pattern
sets are
equivalent if $s$ sends the the first one to the second one.
\subsection{Some known results on permutations}
In dimension 2, there are only two patterns of size 2 ($12$ and
$21$) that are trivially Wilf-equivalent. For patterns of size $3$, there are
2 classes of patterns that are trivially Wilf-equivalent: $123$ and $321$
on the one hand and $312$, $213$, $231$, $132$ on the other hand. In fact, these
six patterns are Wilf-equivalent and enumerated by Catalan
numbers~\cite{simion1985restricted}: $|S_n(\tau)|=C_n$ for any $\tau$ of
size $3$ where $C_n=\frac{1}{n+1}\binom{2n}{n}$.
All combinations of patterns of size 3 have been treated
in~\cite{simion1985restricted}. Table~\ref{tab:pat2d}
summarizes these results. Recently, all combinations of size 4
patterns have been studied~\cite{mansour2020enumeration}.
\begin{table}[!htb]
\resizebox{\textwidth}{!}{$\displaystyle
\begin{array}{|c|c|c|c|}
\hline
\text{Patterns} & \text{\#TWE} &
\text{Sequence} &
\text{Comment} \\
\hline
\hline
12 & 2 & 1, 1, 1, 1, 1, 1, 1, \ensuremath{\cdots} &
\\
\hline
12, 21 & 1 & 1, 0, 0, 0, 0, 0, 0, \ensuremath{\cdots} &
\\
\hline
312 & 4 & \frac{1}{n+1}\binom{2n}{n}= 1, 2, 5, 14, 42, 132, 429,
\ensuremath{\cdots} & \text{stack-sortable~\cite{knuth1973art}} \\
\hline
123 & 2 & \frac{1}{n+1}\binom{2n}{n}= 1, 2, 5, 14, 42, 132, 429,
\ensuremath{\cdots} &
\text{\cite{knuth1973art}, \cite[Prop.~19]{simion1985restricted}}
\\
\hline
123, 321 & 1 & 1, 2, 4, 4, 0, 0, 0, \ensuremath{\cdots} &
\text{\cite[Prop.~14]{simion1985restricted}}
\\
\hline
213, 321 & 4 & 1+\frac{n(n-1)}{2} = 1, 2, 4, 7, 11, 16, 22,
\ensuremath{\cdots} & \text{\cite[Prop.~11]{simion1985restricted}}
\\
\hline
312, 231 & 2 & 2^{n-1} = 1, 2, 4, 8, 16, 32, 64, \ensuremath{\cdots} &
\text{\cite[Thm.~9]{rotem1981stack}, \cite[Prop.~8]{simion1985restricted}}
\\
\hline
231, 132 & 4 & 2^{n-1} = 1, 2, 4, 8, 16, 32, 64, \ensuremath{\cdots} &
\text{\cite[Prop.~9]{simion1985restricted}}
\\
\hline
312, 321 & 4 & 2^{n-1} = 1, 2, 4, 8, 16, 32, 64, \ensuremath{\cdots} &
\text{\cite[Prop.~7]{simion1985restricted}}
\\
\hline
213, 132, 123 & 2 & \text{Fibonacci:}~ 1, 2, 3, 5, 8, 13, 21,
\ensuremath{\cdots} &
\text{\cite[Prop.~15]{simion1985restricted}}
\\
\hline
231, 213, 321 & 8 & n = 1, 2, 3, 4, 5, 6, 7, \ensuremath{\cdots} &
\text{\cite[Prop.~16*]{simion1985restricted}}
\\
\hline
312, 132, 213 & 4 & n = 1, 2, 3, 4, 5, 6, 7, \ensuremath{\cdots} &
\text{\cite[Prop.~16*]{simion1985restricted}}
\\
\hline
312, 321, 123 & 4 & 1, 2, 3, 1, 0, 0, 0, \ensuremath{\cdots} &
\\
\hline
321, 213, 123 & 4 & 1, 2, 3, 1, 0, 0, 0, \ensuremath{\cdots} &
\\
\hline
321, 213, 132 & 2 & n = 1, 2, 3, 4, 5, 6, 7, \ensuremath{\cdots} &
\text{\cite[Prop.~16*]{simion1985restricted}}
\\
\hline
\end{array}$
}
\caption{Sequences of (2-)permutations avoiding small
patterns. The second column (\#TWE) indicates the number of trivially
Wilf-equivalent patterns.}\label{tab:pat2d}
\end{table}
\subsection{Exhaustive enumeration of small pattern-avoiding 3-permutations}
Here we investigate the different small pattern sets for 3-permutations. We
start with combinations of small patterns of dimension 3. The results are
presented
in Table~\ref{tab:pat1}.
In dimension $3$, there are four patterns of size 2 that are trivially
Wilf-equivalent to the pattern \perm{12}{12}. The class $S_n^2(\perm{21}{12})$
corresponds intervals in the weak-Bruhat poset (see
Prop.~\ref{prop:bruhat}). An
\emph{inversion} in a
permutation $\pi$ is a pair $(i,j)$
such that $i \pi(j)$. We say that that a permutation
$\pi_1$ is smaller than a permutation $\pi_2$, $\pi_1 \leq_b \pi_2$ in the
\emph{weak Bruhat order} if the set of inversions of $\pi_1$ is included in
the
set of inversions of $\pi_2$. An \emph{interval} is a pair of comparable
permutations.
No explicit formula is known for the enumeration of intervals in the
weak-Bruhat poset. This is in
contrast with the 2-dimensional case, where almost everything is known for the
set
of patterns of size at most 4.
\begin{table}[!htb]
\resizebox{\textwidth}{!}{$\displaystyle
\begin{array}{|c|c|c|c|}
\hline
\text{Patterns} & \text{\#TWE} &
\text{Sequence} &
\text{Comment}
\\
\hline
\hline
\perm{12}{12} &
4
&
1, 3, 17, 151, 1899, 31711, \cdots &
\text{Prop.~\ref{prop:bruhat}},
\seqnum{A007767} \\
\hline
\perm{12}{12}, \perm{12}{21} &
6
&
n! = 1, 2, 6, 24, 120 \cdots &
\text{Prop.~\ref{prop:factor}}
\\
\hline
\begin{tabular}{@{}c@{}}\perm{12}{12}, \perm{12}{21}, \\
\perm{21}{12}\end{tabular} &
4
&
1, 1, 1, 1, 1, 1,
\cdots &
\text{Prop.~\ref{prop:factor}}
\\
\hline
\begin{tabular}{@{}c@{}}\perm{12}{12}, \perm{12}{21}, \\
\perm{21}{12}, \perm{21}{21}\end{tabular} &
1
&
1, 0, 0, 0, 0, 0,\cdots
&
\\
\hline
\input patterns_3_1.tex
\perm{12}{12}, \perm{132}{312} &
48
&
(n+1)^{n-1} = 1, 3, 16, 125, 1296 \cdots &
\seqnum{A000272}\
\text{\cite{atkinson1995priority,atkinson1993permutational}} \\
\hline
\perm{12}{12}, \perm{123}{321} &
12
&
1, 3, 16, 124, 1262, 15898, \cdots &
\text{Prop.~\ref{prop:bruhat}}, \seqnum{A190291}
\\
\hline
\perm{12}{12}, \perm{231}{312} &
8
&
1, 3, 16, 122, 1188, 13844, \cdots &
\text{\seqnum{A295928}}?\ \cite{salo2020cutting}
\\
\hline
\end{array}$
}
\caption{Sequences of 3-permutations avoiding patterns of dimension 3: one,
two,
or
three patterns of size 2 or one pattern of size 3. The ``?'' after
a sequence ID means that the sequence matches the first terms and that
we conjecture that the sequences are the same.}\label{tab:pat1}
\end{table}
Avoiding two patterns of size 2 also leads to a unique Wilf equivalence class
that has cardinality $n!$:
\begin{proposition}\label{prop:factor}
\begin{samepage}
For $n\geq 1$, we have
$$|S^2_n(\perm{12}{12}, \perm{12}{12})|=n!,$$
$$|S^2_n(\perm{12}{12}, \perm{12}{21}, \perm{21}{12})|=1.$$
\end{samepage}
\end{proposition}
\begin{proof}
Let us consider the pattern set $\{\perm{12}{21}, \perm{21}{12}\}$, which is
trivially Wilf equivalent to $\{\perm{12}{12}, \perm{12}{12}\}$.
Let $\perm{\sigma_1}{\sigma_2}\in S_n^2\{\perm{12}{21}, \perm{21}{12}\}$.
For all $i,j, \sigma_1(i) < \sigma_1(j)$ if and only if
$\sigma_1(i) < \sigma_1(j)$. This implies that $\sigma_1=\sigma_2$.
Hence $S^2_n(\perm{12}{21}, \perm{21}{12})=\{\perm{\sigma}{\sigma}, \sigma
\in S_n\}$, and $|S^2_n(\perm{12}{21}, \perm{21}{12})| = n!$.
In this set, if we avoid a third pattern \perm{21}{21}, the only
permutation that remains is \perm{\Id_n}{\Id_n}, hence
$|S^2_n(\perm{12}{21}, \perm{21}{12},\perm{21}{21})|=1$. Since every set
of three patterns of size 2 is trivially Wilf equivalent to every other, we
get the second
equality.
\end{proof}
As opposed to classical permutations avoiding one pattern of size 3, which are
all
enumerated by Catalan numbers, the patterns of size 3 are not all
Wilf-equivalent in dimension 3. Surprisingly, the three different classes of
Wilf-equivalent patterns of size 3 lead to new integer sequences.
In contrast, the combination of patterns of size 2 and 3 already give known
sequences (the link with the last one being only conjectural).
Let us start with the pattern set $\{\perm{12}{12}, \perm{132}{312}\}$. This
pattern set is sent to the pattern set $\{\perm{12}{21}, \perm{321}{132}\}$ by
the
symmetry \matSymT{0}{0}{-1}{0}{-1}{0}{1}{0}{0}.
The set $S_n^2(\perm{12}{21}, \perm{321}{132})$ is exactly the set of allowable
pairs sorted by a priority queue, as shown in~\cite{atkinson1995priority}.
Moreover Atkinson and Thiyagarajah~\cite{atkinson1993permutational} proved that
this set is of size
$(n+1)^{n+1}$. A bijection between these permutations and labeled trees has
been described in~\cite{atkinson1995priority}.
\begin{proposition}\label{prop:bruhat}
For $n\geq 1$, we have
\begin{enumerate}
\item $S_n^2(\perm{12}{12})$ is in bijection with the intervals in
the weak-Bruhat poset on $S_n$.
\item $S_n^2(\perm{12}{12}, \perm{123}{321})$ is in bijection with
the intervals in the weak-Bruhat on $S_n$ that are distributive
lattices.
\end{enumerate}
\end{proposition}
\begin{proof}
\begin{enumerate}
\item Observe that $i_1,i_2$ is an inversion in
$\pi_1$
but not in $\pi_2$. Hence, $i_1,i_2$ is an instance of the pattern
$\perm{12}{12}$ in \perm{\pi_1}{\pi_2}. Hence the class
$S_n^2(\perm{21}{12})$
corresponds to the intervals in the weak-Bruhat poset. We
conclude by
observing that the symmetry
$\matSymT{-1}{0}{0}{0}{1}{0}{0}{0}{-1}$
maps bijectively
$S_n^2(\perm{21}{12})$ to $S_n^2(\perm{12}{12})$.
\item As shown in~\cite[Proposition 2.3]{stembridge1996fully}, the
sub-poset
defined by the interval $\sigma_1,\sigma_2$ is isomorphic to the
sub-poset of permutations smaller than $\sigma_1^{-1} \sigma_2$.
Moreover, as shown in~\cite[Theorem
3.2]{stembridge1996fully}, this sub-poset is a distributive
lattice if and only if
$\sigma_1^{-1} \sigma_2 \in S_n(321)$. Let $G_n$ be the set of
3-permutations $\bsig \in
S_n^2(\perm{21}{12})$
such that $\sigma_1^{-1} \sigma_2 \in S_n(321)$. We will now show that
$S_n^2(\perm{21}{12}, \perm{123}{321})= G_n$. If $i_1 < i_2 < i_3$ is
an occurrence of $\perm{123}{321}$ in a permutation $\bsig$, then it is
also an occurrence of 321 in $\sigma_1^{-1} \sigma_2$. Hence $G_n
\subseteq
S_n^2(\perm{21}{12}, \perm{123}{321})$, so let us
focus on the second inclusion.
Consider $\perm{\sigma_1}{\sigma_2} \in S_n^2(\perm{21}{12})$ such
that $i_1 < i_2
\sigma_1(i_2)$. Applying the same argument to $i_2$ and $i_3$, we get
that $i_1,i_2,i_3$ is an occurrence of 123 in $\sigma_1$.
Now, $\sigma_1^{-1} \sigma_2$ and $\sigma_1$ fully determine $\sigma_2$ and
we have $\pi_2(i_1) > \pi_2(i_2) > \pi_2(i_3)$. Hence $i_1, i_2, i_3$
is an occurrence of $\perm{123}{321}$ in
$\bsig$, which yields the second inclusion.
We conclude by observing that the symmetry
$\matSymT{-1}{0}{0}{0}{1}{0}{0}{0}{-1}$
sends $S_n^2(\perm{21}{12}, \perm{123}{321})$ bijectively to
$S_n^2(\perm{12}{12}, \perm{123}{321})$.
\end{enumerate}
\end{proof}
Now, let us focus on 3-permutations that avoid patterns of dimension 2.
Table~\ref{tab:pat2} synthesizes the results. We start by some considerations on
the trivially $d$-Wilf-equivalence of patterns (and pattern sets) of smaller
dimension.
\begin{remark}\label{rem:triv} Let $\bsig \in S_n^2$ with $n\geq 2$. One can
observe that if $\proj_{x,y}(\bsig) \in S_n(21)$ and $\proj_{x,z}(\bsig)
\in
S_n(21)$, then $\proj_{y,z}(\bsig)$ contains the pattern $21$. Hence
$|S_n^2(21)|=0$ for $n\geq 2$. On the other hand, one can check that
$S_n^2(21)=\{\perm{\Id_n}{\Id_n}\}$. More generally, two patterns of dimension
$d$
can be trivially $d$-Wilf-equivalent but not $d'$-Wilf-equivalent for
$d'>d$.
For instance, $12$ and $21$ are trivially 2-Wilf-equivalent but not
3-Wilf-equivalent. In fact, any symmetry of the 3-cube other than the
identity
sends the pattern $12$ into the pattern set $\{12,21\}$.
\end{remark}
Given a symmetry $s\in d-\Sym$ and an increasing sequence of indices $i_1 <
i_2\cdots i_{d'}$, we define $s_\bi$ as an
element of $d'-\Sym$ obtained from $s$ by keeping the rows whose index is in
$\bi$,
and the columns containing a non-zero value in one of these rows. For instance, if $s
= \matSymT{0}{0}{-1}{0}{-1}{0}{1}{0}{0}$ and $\bi = 1,3$, then $s_\bi =
\matSym{0}{-1}{1}{0}$.
Given $s \in d-\Sym$ and $\bpi \in S_n^{d'-1}$, we make the following
definition, if
$\bpi$
is a $d'$-multipermutation:
$\widetilde{s}(\{\bpi\}):=\{s_\bi(\bpi), \bi =i_1, \ldots, i_{d'}\}$ and if
$\bpi_1, \ldots, \bpi_k$ is a set, $\widetilde{s}(\{\bpi_1, \ldots,
\bpi_k\}):=\cup_{i=1}^k \widetilde{s}(\{\bpi_i\})$.
In general $\widetilde{s}(\widetilde{s^{-1}}(\bpi)) \neq \bpi$. For instance, as
we saw above, for
$d=3$ and $s$ the identity matrix of size 3,
$\widetilde{s^{-1}}(\widetilde{s}(\{12\}))= \{12,21\}$.
\begin{proposition}\label{prop:TWE}
Two pattern sets $\bpi_1, \ldots, \bpi_k$ and $\btau_1, \ldots,
\btau_k'$ are trivially $d$-Wilf-equivalent if there exists $s\in
d-\Sym$ such that
$\widetilde{s}(\bpi_1, \ldots, \bpi_k) = \btau_1, \ldots, \btau_k'$ and
$\bpi_1,
\ldots, \bpi_k = \widetilde{s^{-1}}(\btau_1, \ldots, \btau_k')$.
\end{proposition}
\begin{proof}
Let $\bpi_1, \ldots, \bpi_k$, $\btau_1, \ldots, \btau_k'$ and $s$ be as in
the
proposition. Let us first show that $|S_n(\bpi_1, \ldots, \bpi_k)| \geq
|S_n(\btau_1, \ldots, \btau_k)|$ and then we will show the other
inequality.
Let $\bsig \not \in S_n^d(\bpi_1, \ldots, \bpi_k)$ and let $\bi,k$ be such
that
$\proj_\bi(\bsig)$ contains $\bpi_k$. Then $s_\bi(\proj_\bi(\bsig)))$
contains $s_\bi(\bpi_k)$.
Let $\bj$ be the set of indices of the rows of $s$ that contain a
non-zero entry in the
columns of index in $\bi$. Since
$\proj_\bj(s(\bsig)) = s_\bi(\proj_\bi(\bsig))$ and $s_\bi(\bpi_k) \in
\widetilde{s}(\bpi_k) \subset
\{\btau_1, \ldots, \btau_k'\}$, we
have $s(\bsig) \not \in
S_n^d(\btau_1, \ldots, \btau_k)$. Hence $|S_n(\bpi_1, \ldots, \bpi_k)|
\geq
|S_n(\btau_1, \ldots, \btau_k)|$.
We proceed similarly for the other inequality. Let $\bsig \not \in
S_n^d(\btau_1, \ldots, \btau_k)$ and let $\bi,k$ be such
that
$\proj_\bi(\bsig)$ contains $\btau_k$. Then $s^{-1}_\bi(\proj_\bi(\bsig))$
contains $s^{-1}_\bi(\btau_k)$.
Let $\bj$ be the indices of the rows that contain a non-zero entry in the
columns of $s^{-1}$ of index in $\bi$. Since
$\proj_\bj(s^{-1}(\bsig)) = s^{-1}_\bi(\proj_\bi(\bsig))$ and
$s^{-1}_\bi(\btau_k) \in
\widetilde{s^{-1}}(\btau_k) \subset
\{\bpi_1, \ldots, \bpi_k'\}$, we
have $s(\bsig) \not \in
S_n^d(\bpi_1, \ldots, \bpi_k)$. Hence $|S_n(\bpi_1, \ldots, \bpi_k)|
\leq
|S_n(\btau_1, \ldots, \btau_k)|$.
\end{proof}
What is very surprising is that all the classes composed of a single pattern of size
3 lead to new sequences and that four of the five classes composed of pairs of
patterns of size 3 seem to match with known sequences. For the known sequences,
we
did not find any simple interpretations. If we now consider combinations of
patterns of dimension 2 and 3 (see Table~\ref{tab:pat3}),
we find several finite sets, two new sequences, and five sequences that seem to
match with known sequences. Three of the four couples of patterns of size 2
are in fact equivalent to a single pattern (12 or 21), since any instance
of the pattern of dimension 3 is also an instance of the pattern of
dimension 2.
\begin{table}[!htb]
\begin{centermath}
\begin{array}{|c|c|c|c|}
\hline
\text{Patterns} & \text{\#TWE} &
\text{Sequence} &
\text{Comment} \\
\hline
\hline
12 & 1 & 1, 0, 0, 0, 0, \ensuremath{\cdots}
& \text{Remark~\ref{rem:triv}} \\
\hline
21 & 1 & 1, 1, 1, 1, 1, \ensuremath{\cdots}
& \text{Remark~\ref{rem:triv}} \\
\hline
\input patterns_3_1_d2.tex
\input patterns_3_2_d2.tex
\end{array}
\end{centermath}
\caption{Sequences of 3-permutations avoiding at most two patterns of size 2
or
three of dimension 2. The ``?'' after
a sequence ID means that the first terms of the sequences match and that
we conjecture that the sequences are the same.}\label{tab:pat2}
\end{table}
\begin{table}[!htb]
\begin{centermath}
\begin{array}{|c|c|c|c|}
\hline
\text{Patterns} & \text{\#TWE} &
\text{Sequence} &
\text{Comment} \\
\hline
\hline
12, \perm{12}{12} &
1 & 1, 0, 0,
0, 0, \ensuremath{\cdots} & 12 \\
\hline
12, \perm{21}{12} &
3 & 1, 0, 0,
0, 0, \ensuremath{\cdots} & 12 \\
\hline
21, \perm{12}{12} &
1 & 1, 0, 0,
0, 0, \ensuremath{\cdots} & \\
\hline
21, \perm{21}{12} &
3 & 1, 1, 1,
1, 1, \ensuremath{\cdots} & 21 \\
\hline
\input patterns_2_1_3_1_mix.tex
\end{array}
\end{centermath}
\caption{Sequences of 3-permutations avoiding a permutation of size 2 and
dimension 3 with a pattern of dimension 2 of size 2 or 3. The ``?''
after
a sequence ID means that the first terms of the sequences match and that
we conjecture that the sequences are the same.}\label{tab:pat3}
\end{table}
We conclude this section with sets of patterns that are invariant under all
symmetries.
Given a $d$-permutation $\bsig$, we write $\Sym(\bsig):=\{s(\bsig)) | s \in
d$-$\Sym\}$.
Figure~\ref{fig:patt3} describes all the symmetric $2$-permutations obtained
from $\perm{132}{213}$. This symmetric pattern plays an important role in
separable $d$-permutations and Baxter $d$-permutations, as we will see in
Section~\ref{sec:baxter}.
\begin{remark}\label{rem:patt}
A convenient way to describe this pattern is the following: a permutation
$\bsig$ contains the pattern $\patt$ if its diagram contains three points
$p_1, p_2, p_3$ and three axes such that $p_1$ and $p_2$ are in the same
quadrant of $p_3$ in the plane generated by the first two axes and $p_3$ is
between $p_1$ and $p_2$ on the third axis.
\end{remark}
\begin{figure}[htb]
\center{\includegraphics{patt3.pdf}}
\caption{The eight 3-permutations of \patt.}\label{fig:patt3}
\end{figure}
\begin{table}[!htb]
\begin{centermath}
\begin{array}{|c|c|c|c|}
\hline
\text{Patterns} & |\Sym(\bpi)| &
\text{Sequence} & \text{Comment} \\
\hline
\hline
\Sym(\perm{123}{123}) & 4 & 1, 4,
32, 368, 4952, 68256, \cdots & {\rm new} \\
\hline
\Sym(\perm{123}{132}) & 24 & 1, 4,
12, 4, 4, 4, \cdots &
\text{Prop.~\ref{prop:const}}
\\
\hline
\Sym(\perm{132}{213}) & 8 & 1, 4,
28, 256, 2704, 31192, \cdots & {\rm new} \\
\hline
\end{array}
\end{centermath}
\caption{Sequences of 3-permutations avoiding a pattern of size 3 with all
its symmetries. The second column indicates the number of forbidden
patterns.}\label{tab:pat3b}
\end{table}
The number of permutations avoiding $\Sym(\perm{123}{132})$ becomes a constant
(equal to 4) for sizes greater than 4.
In fact, it can be shown that these permutations are four diagonals of the cube.
\begin{proposition}\label{prop:const}
For $n\geq 1$, we have
\[
S^2_n(\Sym(\perm{123}{132})) =
\begin{cases}
S_n^2, & \text{if } n \leq 2; \\
S_3^2 \setminus \Sym(\perm{123}{132}), & \text{if } n = 3; \\
{\Sym(\perm{\Id_n}{\Id_n})}, &
\text{otherwise}. \\
\end{cases}
\]
\end{proposition}
\begin{proof} For $n\leq 4$ the proposition can be easily checked manually.
For $n \geq 4$, we will show that $S^2_n(\Sym(\perm{123}{132}))=
\Sym(\perm{\Id_n}{\Id_n})$ =
$\{\perm{\Id_n}{\Id_n}$, $\perm{\Id_n}{\rev(\Id_n)}$,
$\perm{\rev(\Id_n)}{\Id_n}$,
$\perm{\rev(\Id_n)}{\rev(\Id_n)}\}$.
Clearly, $\Sym(\perm{\Id_n}{\Id_n}) \subseteq S^2_n(\Sym(\perm{123}{132}))$,
so we only have to show the other inclusion.
Suppose that the proposition is true until some $n \geq 4$ and let us
show that it is still true for $n+1$. Let $\bsig \in
S^2_{n+1}(\Sym(\perm{123}{132}))$. Let $\bsig'$ be the permutation
obtained by removing the point $(x,y,z)$ such that $z=n+1$. If $\bsig$
avoids a pattern $\bpi$, $\bsig'$ also avoids $\bpi$. Hence $\bsig' \in
S^2_{n}(\Sym(\perm{123}{132}))$. By our inductive hypothesis, $\bsig'
\in \Sym(\perm{\Id_n}{\Id_n})$. Now we only have to show that if $\bsig' =
\perm{\Id_n}{\Id_n}$, then $\bsig=\perm{\Id_{n+1}}{\Id_{n+1}}$, the
three
other
cases being equivalent.
Let us consider all the different possible positions for the point $(x,y,n+1)$. Here we only consider cases where $x \leq y$, the other cases being deduced from the first ones by symmetry:
\begin{itemize}
\item $x=y=n+1$. In this case $\bsig=\perm{\Id_{n+1}}{\Id_{n+1}}$.
\item $x = y = 1$: the permutation will be
$\bsig=\perm{\Id_{n+1}}{(n+1) \ 1 \cdots n}$ which contains the pattern
$\perm{123}{312} \in \Sym(\perm{123}{132})$, which is a contradiction.
\item $x = 1, y > 1$: $\perm{y \ 1 \cdots y-1 \ y+2 \ \cdots n+1}{n+1 \ 1 \cdots n}$ which contains $\perm{123}{312} \in \Sym(\perm{123}{132})$, which is a contradiction.
\item $1 < x < n+1, \ y=x$.
$\bsig=\perm{\Id_{n+1}}{1 \cdots (x-1) \ (n+1) \ x \cdots n}$
which contains the pattern $\perm{123}{132} \in
\Sym(\perm{123}{132})$, which is a contradiction.
\item $1 < x < n+1, \ y > x$.
$\bsig=\perm{1 \cdots (x-1) \ y \ x \cdots (n+1)}{1 \cdots (y-1) \ (n+1) \ y \cdots n}$ contains $\perm{132}{132} \in \Sym(\perm{123}{132})$, which is a contradiction.
\item $x = n+1, \ y < n+1$.
$\bsig=\perm{1 \cdots (y-1) (y+1) \cdots (n+1) \ y}{\Id_{n+1}}$
which contains $\perm{231}{123} \in \Sym(\perm{123}{132})$.
Contradiction.
\end{itemize}
So if $\bsig'=\perm{\Id_n}{\Id_n}$, then
$\bsig=\perm{\Id_{n+1}}{\Id_{n+1}}$. By symmetry, we conclude that
$$\Sym(\perm{\Id_{n+1}}{\Id_{n+1}}) = S^2_{n+1}(\Sym(\perm{123}{132})).$$
Hence the property is true for all $n\geq 4$.
\end{proof}
In the Appendix, we give sequences corresponding to larger patterns. At the date of writing,
none of these sequences appear in OEIS~\cite{oeis}.
\section{Baxter $d$-permutations}\label{sec:baxter}
In this section we consider separable $d$-permutations and Baxter
$d$-permutations. We
first recall the definitions and properties in the classical case ($d=2$). Then we recall the definition and characterization of separable
$d$-permutations given in~\cite{asinowski2010separable}, and after that we
propose a
definition of Baxter $d$-permutation and show how some of the properties of
Baxter permutations are generalized to higher dimensions. Finally, we show that
we can also extend the notion of \emph{complete Baxter permutation} and
\emph{anti-Baxter permutation}.
\subsection{Separable permutations and Baxter permutations}
Let $\sigma$ and $\pi$ be two permutations respectively of size $n$ and $k$.
Their
\emph{direct sum} and \emph{skew sum} are the permutations of size $n+k$
defined by
$$\sigma \oplus \pi := \sigma(1), \ldots,\sigma(n),\pi(1)+n, \ldots,\pi(k)+n
\text { and}$$
$$\sigma \ominus \pi := \sigma(1)+k, \ldots,\sigma(n)+k,\pi(1), \ldots,\pi(k).$$
A permutation is \emph{separable} if it is of size $1$ or it is the direct
sum or the skew sum of two separable permutations. Let
$\Sep_n$ denote the set of separable permutations of size $n$. These permutations
are enumerated by large Schr{\"o}der numbers as shown
in~\cite{shapiro1991bootstrap}:
$$|\Sep_n| =
\frac1{n-1}\sum_{k=0}^{n-2}\binom{n-1}k\binom{n-1}{k+1}2^{n-k-1}.$$
The characterization of separable permutations with patterns has been
given in~\cite{bose1998pattern}:
$$\Sep_n=S_n(2413, 3142).$$
\begin{figure}[htb]
\center{\includegraphics[width=0.8\textwidth]{2dsep.pdf}}
\caption{On the left the separable permutation $643512 = 1
\ominus((1\ominus1)\oplus1)\ominus(1\oplus1)$. In the middle a Baxter
permutation that is not a separable permutation. On the right a permutation
that is not a Baxter permutation.}\label{fig:2dsep}
\end{figure}
A related class of permutations are the \emph{Baxter permutations}. Baxter
permutations have been widely studied because they are related to numerous other
combinatorial
objects~\cite{bonichon2010baxter,felsner2011bijections,fusy_meanders}.
To
introduce them, we first need to define a more general type of pattern.
A vincular pattern is a pattern where some entries must be consecutive in the
permutation. More formally, a \emph{vincular pattern} $\vinpat{\pi}{X}$ is
composed of $\pi \in S_k$, a permutation, and ${\color{axeX}X} \subseteq [k-1]$,
a set of (horizontal) \emph {adjacencies}. A permutation $\sigma \in S_n$
\emph{contains} the vincular pattern $\vinpat{\pi}{X}$ if there exist indices
$i_1 < \cdots < i_k$ such that $\sigma_{i_1},\sigma_{i_2}\cdots\sigma_{i_k}$ is
an
occurrence of $\pi$ in $\sigma$ and $i_{j+1}=i_{j}+1$ for each $j\in
{\color{axeX}X}$. A vincular pattern $\vinpat{\pi}{X}$ is classically
represented as a permutation with dashes between the entries without adjacency
constraints. For instance, the vincular pattern $\vinpat{2413}{2}$ is
represented by 2-41-3. We stick to our notation so that it can be generalized
to $d$-permutations.
\begin{figure}[htb]
\center{\includegraphics[width=0.5\textwidth]{baxter-patterns.pdf}}
\caption{Baxter permutation forbidden vincular patterns: $\vinpat{2413}{2}$
and $\vinpat{3142}{2}$. The adjacency is indicated by a vertical (green)
strip.}\label{fig:baxter-patterns}
\end{figure}
Baxter permutations (introduced by Baxter~\cite{Bax:65}) are exactly
the permutations that avoid $\vinpat{2413}{2}$ and $\vinpat{3142}{2}$ (see
Figure~\ref{fig:baxter-patterns}):
\begin{align*}
B_n &:=S_n(\vinpat{2413}{2},\vinpat{3142}{2}). \\
|B_n| &= \sum_{k=1}^{n}\frac{\binom{n+1}{k-1}\binom{n+1}{k}\binom{n+1}{k+1}}{\binom{n+1}{1}\binom{n+1}{2}}.
\end{align*}
The first few terms of $(B_n)$ are 1, 2, 6, 22, 92, 422, 2074 (sequence
\seqnum{A001181}).
Figure~\ref{fig:baxter2d} and the first two permutations of
Figure~\ref{fig:2dsep} give examples of Baxter permutations.
\begin{figure}[htb]
\center{\includegraphics[width=0.5\textwidth]{baxter2d.pdf}}
\caption{An example of a Baxter permutation. At each ascent (resp., descent)
we
associate a blue (resp., red) vertical rectangle, called \emph{slice},
and
we associate a blue (resp., red) horizontal rectangle to each ascent
(resp.,
descent) of the inverse permutation.}\label{fig:baxter2d}
\end{figure}
\subsection{Separable $d$-permutations}
A \emph{$d$-direction} (or simply a \emph{direction}) $\bdir$ is a word on the
alphabet $\{+,-\}$ of length $d$ such that its first
entry is positive.
Let $\bsig$ and $\bpi$ be two $d$-permutations and $\bdir$ a direction.
The \emph{$d$-sum} with respect to $\bdir$ is the $d$-permutation
$$\bsig \oplus^\bdir \bpi := \basig_2 \oplus^\bdir_2 \bapi_2, \ldots, \basig_{d}
\oplus^\bdir_d \bapi_{d},$$
where $\oplus^\bdir_i$ is $\oplus$ if $\bdir_i=+$ and $\ominus$ if $\bdir_i=-$.
A \emph{separable $d$-permutation} is a $d$ permutation of size 1 or the $d$-sum of two separable $d$-permutations.
These definitions are illustrated in Figure~\ref{fig:3d-sep-sum}.
\begin{figure}[htb]
\center{\includegraphics[width=0.9\textwidth]{3d-sep-sum.pdf}}
\caption{A permutation $p_1 = \perm{132}{132}$ (on the left) and a
permutation $p_2 = \perm{12}{21}$ (in the middle).
$p_1$ and $p_2$ are separable $3$-permutations because $p_1 = \perm{1}{1} \oplus^{(+++)} (\perm{1}{1} \oplus^{(+--)} \perm{1}{1})$ and $p_2 = \perm{1}{1} \oplus^{(+-+)} \perm{1}{1}$.
On the right, their $d$-sum with respect to $(+++)$ is $\perm{132}{132} \oplus^{(+++)} \perm{21}{21} = \perm{13254}{13254}$ which is still separable.}
\label{fig:3d-sep-sum}
\end{figure}
As we have seen previously, for $d=2$, every permutation of size at most $3$ is
separable and these permutations are characterized by the avoidance of 2
patterns of size 4. For $d=3$, it is no longer true that all 3-permutations of
size 3 are separable. The eight 3-permutations of size 3 that are not separable
are
$\patt$ (see Figure~\ref{fig:patt3}). In fact, these eight permutations together
with the two patterns of length 4 exactly characterize the separable
$d$-permutations
for any $d\geq 3$, as shown in~\cite{asinowski2010separable}. We restate their
result with our formalism:
\begin{theorem}~\cite{asinowski2010separable}
Let $\Sep_n^{d-1}$ be set of separable $d$-permutations of size $n$.
$$\Sep_n^{d-1}=S_n^{d-1}(\patt, 2413, 3142).$$
\end{theorem}
The following explicit formulas were established in~\cite{asinowski2010separable}:
$$|\Sep_n^{d-1}| = \frac{1}{n-1}
\sum_{k=0}^{n-2}\binom{n-1}{k}\binom{n-1}{k+1}(2^{d-1}-1)^k(2^{d-1})^{n-k-1}.$$
\begin{table}[!htb]
\center{\begin{tabular}{|c||c|c|c|c|}
\hline
$n \backslash d$ & 2 & 3 & 4 & 5 \\
\hline
\hline
1 & 1 & 1 & 1 & 1 \\
\hline
2 & 2 & 4 & 8 & 16 \\
\hline
3 & 6 & 28 & 120 & 496 \\
\hline
4 & 22 & 244 & 2248 & 19216 \\
\hline
5 & 90 & 2380 & 47160 & 833776 \\
\hline
6 & 394 & 24868 & 1059976 & 38760976 \\
\hline
7 & 1806 & 272188 & 24958200 & 1887736816 \\
\hline
\end{tabular}}
\caption{Values of $|\Sep_n^{d-1}|$ for the first few values of $n$ and
$d$.}
\end{table}
Now we give a new characterization of separable $d$-permutations (Theorem~\ref{thm:cara-sep}).
This makes it simpler to check whether a $d$-permutation is separable:
we only need to check whether it avoids the dimension 3 patterns and then whether it
avoids the dimension 2 patterns only on $d-1$ projections instead of
on $(d-1)\times(d-2)/2$ projections.
\begin{theorem}\label{thm:cara-sep}
For $n \geq 1$, we have
$$\Sep_n^{d-1} = S_n(2413, 3142)^{d-1} \cap S_n^{d-1}(\patt).$$
\end{theorem}
\begin{proof}
To prove this result, we only need to prove that for any $\bsig \in S_n^{d-1}(\patt)$ and any $1* y(p_6)$ and $y(p_2),y(p_4) <
y(p_1)$. Hence $p_1, p_3, p_4, p_6$ is an occurrence of
\vinpatb{3142}{.}{2} in $\proj_{xy}(\bsig)$. Hence $\bsig$
contains a pattern of $\sbaxpa$.
\item {\it (iii) there is a slice that intersects no slice of a given
type.}
Without loss of generality, let us consider the direction $(+++)$.
Assume there is an $x$-slice $(p_2, p_3)$ that does not intersect
any $y$-slice. Let us consider $\proj_{xy}(\bsig)$. If $\bsig$
is not Baxter, $\proj_{xy}(\bsig)$ contains a forbidden pattern
$\sbaxpa$. Otherwise, in $\proj_{xy}(\bsig)$, the slice
$(p_2, p_3)$ intersects exactly one slice. Let $p_2, p_3$ be such
that
the slice $(p_1, p_4)$ intersects the slice $(p_2, p_3)$ in
$\proj_{xy}(\bsig)$. Note that the $p_1$ may be equal to
$p_2$. Since these two slices do not intersect in $\bsig$, there
must be a third coordinate, say $z$, such
that either $z(p_1),z(p_4) \leq z(p_2)$ or $z(p_1),z(p_4) > z(p_3)$.
If $p_1=p_3$, then the three points form an occurrence of a forbidden pattern in $\sbaxpb$. Otherwise, the four points form an occurrence of a forbidden pattern in $\sbaxpc$.
\end{itemize}
\end{proof}
As all the patterns involved in the previous theorem are of dimension 2 or 3, we get the following corollary:
\begin{corollary}
A $d$-permutation is Baxter if and only if all its projections of dimensions 2 or 3 are well-sliced.
\end{corollary}
\subsection{Anti- and complete Baxter $d$-permutations}
In a Baxter permutation $\sigma$, each vertical slice intersects exactly one horizontal
slice. These intersections are cells (squares of width 1). (See, for instance,
Figure~\ref{fig:anti2dV}). Let $P'_\sigma$ be the set of centers of these cells.
If
we combine $P_\sigma$ and $P'_\sigma$, we obtain the diagram of a permutation of
size
$2n+1$ (on a finer grid). These permutations are often called \emph{complete}
Baxter permutations, and were introduced by Baxter and
Joichi~\cite{baxterjoichi} under the name \emph{$w$-admissible}
permutations. What we call here Baxter permutations are sometimes called
\emph{reduced} Baxter permutations.
\begin{figure}
\center{\includegraphics[width=0.4\textwidth]{baxter2dVer.pdf}}
\caption{The Baxter permutation $5\, 3\, 4\, 9\, 7\, 8\, 10\, 6\, 1\, 2$
(square points) together with its associate anti-Baxter permutation
(circle
points) $4\, 3\, 5\, 8\, 7\, 9\, 6\, 2\, 1$. The corresponding
complete
Baxter permutation (all points together) is
$9\, 8\, 5\, 6\, 7\, 10\, 17\, 16\, 13\, 14\, 15\, 18\, 19\, 12\, 11\,
4\, 1\,
2\, 3$.}\label{fig:anti2dV}
\end{figure}
The permutations corresponding to $P'_\sigma$ are called \emph{anti-Baxter}
permutations. These permutations are exactly the ones avoiding
$\vinpatb{2143}{2}{.}$ and $\vinpatb{3412}{2}{.}$, as shown
in~\cite{asinowski2013orders}. As with Baxter patterns,
$S_n(\vinpatb{2143}{2}{.},\vinpatb{3412}{2}{.}) =
S_n(\vinpatb{2143}{2}{2},\vinpatb{3412}{2}{2})$ (see \cite[Lemma
3.5]{asinowski2013orders} and Figure~\ref{fig:anti-baxter-patterns-bis}). The
enumeration of this class of permutation was
given in~\cite{asinowski2013orders}.
\begin{figure}[htb]
\center{\includegraphics[width=0.5\textwidth]{anti-baxter-patterns-bis.pdf}}
\caption{Forbidden patterns in anti-Baxter permutations:
$\vinpatb{2143}{2}{2}$ and
$\vinpatb{3412}{2}{2}$.}\label{fig:anti-baxter-patterns-bis}
\end{figure}
We will now generalize these definitions of anti-Baxter and complete Baxter to
higher dimensions. For this purpose, we will start with the following property.
\begin{proposition}\label{pro:intersect}
Let $\bsig$ be a well-sliced $d$-permutation. Given a slice $p_1, p'_1$ of
type
$1$, let
$(p_i, p'_i)$ be the slices of type $i \in [d]$ that intersect $p_1, p'_1$.
The
intersection of all these slices is the cell $q,q'$, where
$x_i(q):=x_i(p_i)$ and $x_i(q'):=x_i(p'_i)$.
\end{proposition}
\begin{proof}
First observe that the cell $q,q'$ is included in each slice $p_i, p'_i$.
Hence the cell $q, q'$ is included in the intersection of all slices $p_i,
p'_i$.
Since every slice $p_j, p'_j$ intersects the slice $p_i, p'i$, we have
\begin{align*}
\max(\min(x_i(p_i),x_i(p'_i)),\min(x_i(p_j),x_i(p'_j))) <
\min( & \max(x_i(p_i),x_i(p'_i)),\\
& \max(x_i(p_j),x_i(p'_j))).
\end{align*}
Moreover, since
$p_i, p'_i$ is of width 1 with respect to axis $i$ and all the others
have
a width greater than or equal to one, we have
$$
\min(x_i(p_j),x_i(p'_j)) \leq \min(x_i(p_i),x_i(p'_i)) \quad
\text{and} \quad
\max(x_i(p_j),x_i(p'_j)) \geq \max(x_i(p_i),x_i(p'_i)).$$
Hence the intersection of the projections of the slices on the axis $i$ is the
interval
$$[\min(x_i(p_i),x_i(p'_i)), \max(x_i(p_i),x_i(p'_i))].$$
Hence the
intersection of the considered slices is included in the slice $q,q'$.
\end{proof}
With a Baxter $d$-permutation $\bsig$, for every slice of type $1$, we
associate the \emph{intersecting cell} defined by
Property~\ref{pro:intersect} (see Figure~\ref{fig:bax3dV}).
Let $P'_\bsig$ be the set of centers of intersecting cells. Since every slice
of any type contains exactly one intersecting cell, $P'_\bsig$ defines a
$d$-permutation, and we call the $d$-permutations obtained this way
\emph{anti-Baxter} $d$-permutations (see Figure~\ref{fig:bax3dV}). Again, this
definition coincides with the classical one. If we combine $P_\sigma$ and
$P'_\sigma$, we obtain the diagram of a $d$-permutation of size $2n+1$ (on a finer
grid). We naturally call these $d$-permutations \emph{complete Baxter
$d$-permutations}.
\begin{figure}[htb]
\center{\includegraphics[width=1\textwidth]{baxter3dVer.pdf}}
\caption{On the left, the complete Baxter 3-permutation
$\perm{14386527}{47513268}$
with its cell
(circle) points. Each cell point corresponds to the triple intersection
of slices of the same type (see
Figure~\ref{fig:paral1}). On the right, the
anti-Baxter 3-permutation $\perm{1347526}{4631257}$ associated
with the Baxter permutation of Figure~\ref{fig:bax3dV}.}\label{fig:bax3dV}
\end{figure}
As with Baxter
$d$-permutations, a projection of an anti-Baxter (resp., a complete
Baxter)
$d$-permutation is also an anti-Baxter (resp., a complete Baxter)
$d'$-permutation. We let
$A_n^{d-1}$ denote the set of anti-Baxter $d$-permutations of size $n$.
The first few values of $A_n^{d-1}$ are given in Table~\ref{tab:seqAnti}.
\begin{table}[!htb]
\center{\begin{tabular}{|c||c|c|c|c|}
\hline
$n \backslash d$ & 2 & 3 & 4 & 5 \\
\hline
\hline
1 & 1 & 1 & 1 & 1 \\
\hline
2 & 2 & 4 & 8 & 16 \\
\hline
3 & 6 & 36 & 216 & 1296 \\
\hline
4 & 22 & 444 & 7096 & \\
\hline
5 & 88 & 5344 & & \\
\hline
6 & 374 & 64460 & & \\
\hline
7 & 1668 & & & \\
\hline
\end{tabular}}
\caption{Values of $|A_n^{d-1}|$ for the first few values of $n$ and
$d$.}\label{tab:seqAnti}
\end{table}
\section{Conclusion and perspectives}\label{sec:conclusion}
In this paper we have started to consider pattern-avoidance in $d$-permutations
and we have generalized the notion of a Baxter permutation to this context. These first steps
give rise to a large number of open problems, some probably hard, but some probably
very tractable.
The enumeration of $d$-permutations avoiding the smallest patterns is quite
open, starting from the smallest one: $\perm{12}{12}$. Moreover, as has been presented,
many known enumeration sequences seem to match several permutation
families. Clearly, there are several bijections to find.
Considering Baxter $d$-permutations, a large field of research is opening up.
Let us mention several examples of questions related to Baxter
permutations. Clearly, the first expected result would be the enumeration of
the Baxter $d$-permutations. As mentioned in the Introduction, Baxter permutations
are in bijection with several interesting combinatorial objects. A very natural
question would be: which of these bijections can be extended to $d$-Baxter
permutations.
For instance, Baxter permutations are in bijection with boxed arrangements of
axis-parallel segments in $\mathbb{R}^2$~\cite{felsner2011bijections}.
In~\cite{felsner2020plattenbauten}, the authors studied boxed arrangements of
axis-parallel segments in $\mathbb{R}^3$. Are there some links between Baxter
$d$-permutations boxed arrangements in $\mathbb{R}^{2^{d-1}}$?
We were able to characterize Baxter $d$-permutations with forbidden vincular patterns. This question remains open for anti-Baxter $d$-permutations.
In addition, several classes related to Baxter permutations have
received some attention: \emph{doubly alternating} Baxter
permutations~\cite{guibert2000doubly}, Baxter
\emph{involutions}~\cite{fusy2012bijective}, \emph{semi} and \emph{strong} Baxter
permutations~\cite{bouvel2018semi}, as well as \emph{twisted} Baxter permutations~\cite{west2006enumeration}. Once again, can some of these classes
be extended and enumerated in higher dimensions?
We have developed a module based on Sage to work with
$d$-permutations:\\
\centerline{\url{https://plmlab.math.cnrs.fr/bonichon/multipermutation} \ .}\\
We hope that
this tool will help the community to investigate the problems above.
\section{Acknowledgments} The authors would like to thank \'Eric Fusy, Valentin
Feray, Mathilde Bouvel, Olivier Guibert and Jean Cardinal for fruitful
discussions. The
authors are very grateful to the anonymous referee for his detailed corrections.
This work
was partially supported by ANR grant 3DMaps ANR-20-CE48-0018.
\bigskip
\hrule
\appendix
\section{All symmetries of Baxter patterns}\label{sec:sym_bx}
$\Sym(\vinpatb{2413}{2}{2}) =$
$\vinpatb{2413}{2}{2},$
$\vinpatb{3142}{2}{2}.$
\bigskip\noindent$\sbaxpb=\vinpatd{312}{213}{1}{.2}{.}$,
$\vinpatd{312}{231}{1}{.2}{.}$,
$\vinpatd{132}{213}{1}{.1}{.}$,
$\vinpatd{132}{231}{1}{.1}{.}$, \\
$\vinpatd{213}{312}{2}{.2}{.}$,
$\vinpatd{213}{132}{2}{.2}{.}$,
$\vinpatd{231}{312}{2}{.1}{.}$,
$\vinpatd{231}{132}{2}{.1}{.}$, \\
$\vinpatd{213}{312}{1}{.}{2}$,
$\vinpatd{213}{132}{1}{.}{1}$,
$\vinpatd{231}{312}{1}{.}{2}$,
$\vinpatd{231}{132}{1}{.}{1}$, \\
$\vinpatd{312}{213}{2}{.}{2}$,
$\vinpatd{312}{231}{2}{.}{1}$,
$\vinpatd{132}{213}{2}{.}{2}$,
$\vinpatd{132}{231}{2}{.}{1}$, \\
$\vinpatd{213}{132}{.}{1}{2}$,
$\vinpatd{213}{312}{.}{1}{1}$,
$\vinpatd{231}{132}{.}{2}{2}$,
$\vinpatd{231}{312}{.}{2}{1}$, \\
$\vinpatd{312}{231}{.}{1}{2}$,
$\vinpatd{312}{213}{.}{1}{1}$,
$\vinpatd{132}{231}{.}{2}{2}$,
$\vinpatd{132}{213}{.}{2}{1}$.
\bigskip\noindent$\Sym(\vinpatd{3412}{1432}{2}{2}{.}) =$
$\vinpatd{2341}{4123}{.}{2}{2},$
$\vinpatd{2143}{3214}{2}{2}{.},$
$\vinpatd{4123}{3214}{.}{2}{2},$ \\
$\vinpatd{3412}{3214}{2}{2}{.},$
$\vinpatd{3214}{4123}{.}{2}{2},$
$\vinpatd{2341}{1432}{.}{2}{2},$
$\vinpatd{1432}{3214}{.}{2}{2},$ \\
$\vinpatd{2143}{1432}{2}{2}{.},$
$\vinpatd{3412}{1432}{2}{2}{.},$
$\vinpatd{2143}{4123}{2}{2}{.},$
$\vinpatd{1432}{2143}{2}{.}{2},$ \\
$\vinpatd{4123}{2341}{.}{2}{2},$
$\vinpatd{3214}{1432}{.}{2}{2},$
$\vinpatd{3412}{4123}{2}{2}{.},$
$\vinpatd{3412}{2341}{2}{2}{.},$\\
$\vinpatd{1432}{3412}{2}{.}{2},$
$\vinpatd{2143}{2341}{2}{2}{.},$
$\vinpatd{2341}{3412}{2}{.}{2},$
$\vinpatd{4123}{2143}{2}{.}{2},$\\
$\vinpatd{4123}{3412}{2}{.}{2},$
$\vinpatd{3214}{3412}{2}{.}{2},$
$\vinpatd{1432}{2341}{.}{2}{2},$
$\vinpatd{3214}{2143}{2}{.}{2},$\\
$\vinpatd{2341}{2143}{2}{.}{2}.$
\bigskip\noindent$\Sym(\vinpatd{2143}{1423}{2}{2}{.}) =$
$\vinpatd{3241}{2143}{2}{.}{2}, $
$\vinpatd{3412}{2314}{2}{2}{.}, $
$\vinpatd{1423}{3412}{2}{.}{2}, $\\
$\vinpatd{2314}{2143}{2}{.}{2}, $
$\vinpatd{1342}{3124}{.}{2}{2}, $
$\vinpatd{3124}{1342}{.}{2}{2}, $
$\vinpatd{1342}{2431}{.}{2}{2}, $\\
$\vinpatd{3241}{3412}{2}{.}{2}, $
$\vinpatd{4132}{3412}{2}{.}{2}, $
$\vinpatd{2431}{4213}{.}{2}{2}, $
$\vinpatd{2143}{3241}{2}{2}{.}, $\\
$\vinpatd{4213}{2431}{.}{2}{2}, $
$\vinpatd{3412}{3241}{2}{2}{.}, $
$\vinpatd{3412}{1423}{2}{2}{.}, $
$\vinpatd{4213}{3124}{.}{2}{2}, $\\
$\vinpatd{2143}{4132}{2}{2}{.}, $
$\vinpatd{3124}{4213}{.}{2}{2}, $
$\vinpatd{2431}{1342}{.}{2}{2}, $
$\vinpatd{2314}{3412}{2}{.}{2}, $\\
$\vinpatd{2143}{1423}{2}{2}{.}, $
$\vinpatd{1423}{2143}{2}{.}{2}, $
$\vinpatd{4132}{2143}{2}{.}{2}, $
$\vinpatd{2143}{2314}{2}{2}{.}, $\\
$\vinpatd{3412}{4132}{2}{2}{.}.$
\section{Other patterns}
\captionsetup[table]{skip=10pt}
Here we give the beginning of sequences of permutations avoiding some larger
patterns or combination of patterns.
\begin{longtable}{|c|c|c|c|}
\hline
Patterns & \#TWE & Sequence & Comment \\
\hline
\hline
\input patterns_4_1_d2.tex
\caption{Patterns of size 4 and dimension 2.} \\
\end{longtable}
\begin{longtable}{|c|c|c|c|}
\hline
Patterns & \#TWE & Sequence & Comment \\
\hline
\hline
\input patterns_4_2_d2.tex
\caption{Pairs of patterns of size 4 and dimension 2.} \\
\end{longtable}
\begin{longtable}{|c|c|c|c|}
\hline
Patterns & \#TWE & Sequence & Comment \\
\hline
\hline
\input patterns_3_1_3_1_mix.tex
\caption{Pairs of patterns of size 3 respectively of dimension 2 and 3. } \\
\end{longtable}
{\small\tabcolsep=3pt % hold it local
\begin{longtable}{|c|c|c|c|}
\hline
Patterns & \#TWE & Sequence & Comment \\
\hline
\hline
\input patterns_3_2.tex
\caption{Pairs of patterns of size 3 and of dimension 3.} \\
\end{longtable}
}
\begin{longtable}{|c|c|c|c|}
\hline
Patterns & \#TWE & Sequence & Comment \\
\hline
\hline
\input patterns_4_1.tex
\caption{Patterns of size 4 and dimension 3.} \\
\end{longtable}
\begin{thebibliography}{10}
\bibitem{aldred2005permuting}
Robert E.~L. Aldred, Mike~D. Atkinson, Hans~P. van Ditmarsch, Chris~C. Handley,
Derek~A. Holton, and D.~J. McCaughan, Permuting machines and priority queues,
{\em Theoret. Comput. Sci.} {\bf 349} (2005), 309--317.
\bibitem{asinowski2013orders}
Andrei Asinowski, Gill Barequet, Mireille Bousquet-M{\'e}lou, Toufik Mansour,
and Ron~Y Pinter, Orders induced by segments in floorplans and (2-14-3,
3-41-2)-avoiding permutations, {\em Electron. J. Combin.} {\bf 20} (2013),
Paper P35.
\bibitem{asinowski2010separable}
Andrei Asinowski and Toufik Mansour, Separable $d$-permutations and guillotine
partitions, {\em Ann. Comb.} {\bf 14} (2010), 17--43.
\bibitem{atkinson1995priority}
Mike~D. Atkinson, Stephen~A. Linton, and Louise~A. Walker, Priority queues and
multisets, {\em Electron. J. Combin.} {\bf 2} (1995), R24.
\bibitem{atkinson1993permutational}
Mike~D. Atkinson and Murali Thiyagarajah, The permutational power of a priority
queue, {\em BIT} {\bf 33} (1993), 1--6.
\bibitem{aval2021baxter}
Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Olivier Guibert, and
Matteo Silimbani, Baxter tree-like tableaux, (2021),
\url{https://arxiv.org/abs/2108.06212}.
\bibitem{Bax:65}
Glen Baxter, On fixed points of the composite of commuting functions, {\em
Proc. Amer. Math. Soc.} {\bf 15} (1964), 851--855.
\bibitem{baxterjoichi}
Glen Baxter and J.~T. Joichi, On permutations induced by commuting functions,
and an embedding question, {\em Math. Scand.} {\bf 13} (1963), 140--150.
\bibitem{bonichon2010baxter}
Nicolas Bonichon, Mireille Bousquet-M{\'e}lou, and {\'E}ric Fusy, Baxter
permutations and plane bipolar orientations, {\em S{\'e}m. Lothar. Combin.}
{\bf 61} (2010), B61Ah.
\bibitem{bose1998pattern}
Prosenjit Bose, Jonathan~F. Buss, and Anna Lubiw, Pattern matching for
permutations, {\em Inform. Process. Lett.} {\bf 65} (1998), 277--283.
\bibitem{bouvel2018semi}
Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, and Simone Rinaldi,
Semi-{B}axter and strong-{B}axter: two relatives of the {B}axter sequence,
{\em SIAM J. Discrete Math.} {\bf 32} (2018), 2795--2819.
\bibitem{burrill2016tableau}
Sophie Burrill, Julien Courtiel, {\'E}ric Fusy, Stephen Melczer, and Marni
Mishna, Tableau sequences, open diagrams, and {B}axter families, {\em
European J. Combin.} {\bf 58} (2016), 144--165.
\bibitem{cardinal_open}
Jean Cardinal, Order and geometry workshop 2016 --- problem booklet,
\url{http://orderandgeometry2016.tcs.uj.edu.pl/docs/OG2016-Problem-Booklet.pdf},
2016.
\bibitem{silveira2018note}
Jean Cardinal, Vera SacristÃ¡n, and Rodrigo~I. Silveira, A note on flips in
diagonal rectangulations, {\em Discrete Math. Theor. Comput. Sci.} {\bf 20}
(2) (2018), 1--22.
\bibitem{dulucq1998baxter}
Serge Dulucq and Olivier Guibert, Baxter permutations, {\em Discrete Math.}
{\bf 180} (1998), 143--156.
\bibitem{earnest2014permutation}
Michael~J. Earnest and Samuel~C. Gutekunst, Permutation patterns in {L}atin
squares, {\em Aust. J. Combin.} {\bf 59} (2014), 218--228.
\bibitem{eriksson2000combinatorial}
Kimmo Eriksson and Svante Linusson, A combinatorial theory of
higher-dimensional permutation arrays, {\em Adv. in Appl. Math.} {\bf 25}
(2000), 194--211.
\bibitem{felsner2011bijections}
Stefan Felsner, {\'E}ric Fusy, Marc Noy, and David Orden, Bijections for
{B}axter families and related objects, {\em J. Combin. Theory Ser. A} {\bf
118} (2011), 993--1020.
\bibitem{felsner2020plattenbauten}
Stefan Felsner, Kolja Knauer, and Torsten Ueckerdt, Plattenbauten: touching
rectangles in space, In Isolde Adler and Haiko M{\"u}ller, editors, {\em
International Workshop on Graph-Theoretic Concepts in Computer Science}, Vol.
12301 of {\em Lect. Notes in Comp. Sci.}, pp. 161--173. Springer, 2020.
\bibitem{fusy_meanders}
{\'E}ric Fusy, Baxter permutations and meanders,
\url{https://igm.univ-mlv.fr/~fusy/Talks/baxter_meanders.pdf}, 2012.
\bibitem{fusy2012bijective}
{\'E}ric Fusy, Bijective counting of involutive {B}axter permutations, {\em
Fund. Inform.} {\bf 117} (2012), 179--188.
\bibitem{guibert2000doubly}
Olivier Guibert and Svante Linusson, Doubly alternating {B}axter permutations
are {C}atalan, {\em Discrete Math.} {\bf 217} (2000), 157--166.
\bibitem{gunby2019asymptotics}
Benjamin Gunby and D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi, Asymptotics of
pattern avoidance in the {K}lazar set partition and permutation-tuple
settings, {\em European J. Combin.} {\bf 82} (2019), 102992.
\bibitem{knuth1973art}
Donald~E. Knuth, {\em The Art of Computer Programming, volume 3: Searching and
sorting}, Addison-Wesley Publishing Company, 1973.
\bibitem{mansour2020enumeration}
Toufik Mansour, Enumeration and {W}ilf-classification of permutations avoiding
four patterns of length 4, {\em Discrete Math. Lett} (2020), 67--94.
\bibitem{oeis}
OEIS~Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2022.
Available at \url{https://oeis.org/}.
\bibitem{rotem1981stack}
Doron Rotem, Stack sortable permutations, {\em Discrete Math.} {\bf 33} (1981),
185--196.
\bibitem{salo2020cutting}
Ville Salo, Cutting corners, Arxiv preprint \url{https://arxiv.org/abs/2002.08730}, 2020.
\bibitem{shapiro1991bootstrap}
Louis Shapiro and A.~Brooke Stephens, Bootstrap percolation, the {S}chr{\"o}der
numbers, and the $n$-kings problem, {\em SIAM J. Discrete Math.} {\bf 4}
(1991), 275--280.
\bibitem{simion1985restricted}
Rodica Simion and Frank~W. Schmidt, Restricted permutations, {\em European J.
Combin.} {\bf 6} (1985), 383--406.
\bibitem{stembridge1996fully}
John~R. Stembridge, On the fully commutative elements of {C}oxeter groups, {\em
J. Algebraic Combin.} {\bf 5} (1996), 353--385.
\bibitem{west2006enumeration}
Julian West and Olivier Guibert, Enumeration of {R}eading's twisted {B}axter
permutations, In {\em The Fourth Annual International Conference on
Permutation Patterns}, Reykjavik University, Reykjavik, 2006.
Available at \url{http://www.cs.otago.ac.nz/staffpriv/mike/PP2006/abs/West.pdf}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent
2020 \emph{Mathematics Subject Classification}:~Primary 05A05;
Secondary 05A19, 05A10, 15A69.
\medskip
\noindent
\emph{Keywords}:~Baxter permutation, multipermutation, Schr\"oder number,
separable permutation.
\bigskip
\hrule
\bigskip
\noindent
(Concerned with sequences
\seqnum{A000108},
\seqnum{A000272},
\seqnum{A001003},
\seqnum{A001181},
\seqnum{A001764},
\seqnum{A001787},
\seqnum{A003946},
\seqnum{A006318},
\seqnum{A007767},
\seqnum{A026150},
\seqnum{A026671},
\seqnum{A047732},
\seqnum{A071684},
\seqnum{A071688},
\seqnum{A072863},
\seqnum{A086810},
\seqnum{A090181},
\seqnum{A103211},
\seqnum{A107841},
\seqnum{A131763},
\seqnum{A131765},
\seqnum{A133308},
\seqnum{A190291},
\seqnum{A217216},
\seqnum{A281593},
\seqnum{A295928} and
\seqnum{A356197}
.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received February 25 2022;
revised versions received March 3 2022; July 29 2022; October 11 2022.
Published in {\it Journal of Integer Sequences},
October 11 2022.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
*