Baxter d-Permutations and Other Pattern-Avoiding Classes

Nicolas Bonichon and Pierre-Jean Morel Univ. Bordeaux CNRS, Bordeaux INP LaBRI UMR 5800 F-33400 Talence France

            nicolas.bonichon@u-bordeaux.fr

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 ∈ [d] and j ∈ [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 patternavoidance characterization of Baxter d-permutations.

1 Introduction

A permutation σ = σ(1), …, σ(n) ∈ S_{n} is a bijection from [n] := {1, 2, …, n} to itself. The (2-dimensional) diagram of σ is simply the set of points P_{σ} := {(i, σ(i)), 1 ≤ i ≤ 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.

In this paper we are interested in d-dimensional diagrams: sets of points P_{σ} of [n]^{d} such that every hyperplane x_{i} = j with i ∈ [d] and j ∈ [n] contains exactly one point of P_{σ}. Such

x 1 2 3 4 5 6 y 1 2 3 4 5 6 z 1 2 3 4 5 6

Figure 1: The diagram of the 3-permutation (253146, 654321) together with its 3 projections of dimension 2: the blue, red permutations that define the 3-permutation and green permutation 51 that is deduced from the two first permutations.

a diagram is equivalently described by a sequence of d − 1 permutations σ := (σ_{1}, …, σ_{d−1}) such that

P_{σ} = {(i, σ_{1}(i), σ_{2}(i), …, σ_{d−1}(i)), i ∈ [n]}.

Figure 1 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 [16, 16] or other “semi-dense” multidimensional permutations [17].

Permutation-tuples have already been studied (see, for instance, [23, 1]), but as far as we know, the d-permutations have been explicitly considered only in a few papers: [3, 23]. From our point of view, the paper of Asinoski and Mansour [3] is the most significant in our context: they present a generalization of 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 4. 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 [24, 30, 25]. 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 σ contains the 3-permutation π := (π_{1}, π_{2}) if there is a subset of P_{σ} that is order isomorphic to P_{π}. Also, we say that σ contains a 2-permutation π if one of its (direct) projections contains π. We let S_{n}^{d−1}(π_{1}, …, π_{k}) denote the set of d-permutations of size n that avoid all patterns π_{1}, …, π_{k}. The formal definition is provided in Section 2. This definition is slightly different from the one introduced in [3]. 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 3permutations 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}((12, 12)) are in bijection with intervals in the weak-Bruhat order (see Prop. 5), S_{n}^{2}((12, 21), (312, 132)) are the allowable pairs sorted by a priority queue [4]. Also, several “OEIS coincidences” lead us to conjecture other bijections. This is the case for four different pairs of size 3 permutations (see Table 3). In addition, even very simple patterns lead to sequences not listed in the On-Line Encyclopedia of Integer Sequences (OEIS) [26]. This is in particular the case for all non-trivially equivalent patterns of size 3 (S_{n}^{2}((123, 123)), S_{n}^{2}((123, 132)), S_{n}^{2}((132, 213)), S_{n}^{2}(123), S_{n}^{2}(312) and S_{n}^{2}(321)) and some 2and 3-dimensional pairs of patterns (S_{n}^{2}(132, (12, 21)), S_{n}^{2}(213, (12, 12)), S_{n}^{2}(231, (12, 12)), S_{n}^{2}(231, (21, 12)), S_{n}^{2}(321, (21, 12))) (see Section 2 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:

• twin binary trees [15],

• plane bipolar orientations [9],

• triples of non-intersecting lattice paths [15],

• monotone 2-line meanders [20], open diagrams [12],

• Baxter tree-like tableaux [6],

• boxed arrangements of axis-parallel segments in ℝ^{2} [18],

and many others.

With the bijection with boxed arrangements in mind, the following question [13, 3, 14] 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 ≥ 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 11).

The rest of this paper is organized as follows. In Section 2 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 3 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 4 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 patternavoidance. Finally, in Section 5 we conclude with a list of open problems.

2 Preliminaries

Let S_{n} be the symmetric group on [n] := {1, 2, …, n}. Given a permutation

σ = σ(1), …, σ(n) ∈ S_{n},

the diagram of σ, denoted by P_{σ}, is the point set {(1, σ(1)), (2, σ(2)), …, (n, σ(n))}. A permutation σ contains a permutation (or a pattern) π = π(1), …, π(k) ∈ S_{k} if there exist indices c_{1} < ⋯ < c_{k} such that σ(c_{1}) ⋯ σ(c_{k}) is order isomorphic to π. We say that the set of indices c_{1}, …, c_{k}, and by extension the point set {(c_{1}, σ(c_{1})), …, (c_{k}, σ(c_{k}))}, is an occurrence of the π.

We let Id_{n} denote the identity permutation of size n. Given a set of patterns π_{1}, …, π_{k}, we let S_{n}(π_{1}, …, π_{k}) denote the set of permutations of S_{n} that avoid each pattern π_{i}.

Definition 1. A d-permutation of size n, σ := (σ_{1}, …, σ_{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 \overline{σ} = (Id_{n}, σ_{1}, …, σ_{d−1}). Then d is called the dimension of the permutation. The diagram of a d-permutation σ is the set of points in P_{σ} := \{(\overline{σ}_{1}(i), \overline{σ}_{2}(i), …, \overline{σ}_{d}(i)), i ∈ [n]\}.

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 \overline{σ}). 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 d-diagrams of size n are exactly the point sets of [n]^{d} such that every hyperplane x_{i} = j with i ∈ [d] and j ∈ [n] contains exactly one point. One can observe that |S_{n}^{d−1}| = n!^{d−1}. Figure 1 gives an example of a 3-permutation of size 6.

Suppose given P := {p_{1}, …, p_{n}} a set of points in ℝ^{d} such that every hyperplane x_{j} = α with α ∈ ℝ contains at most one point of P. The standardization of P is the point set P′ = {p′_{1}, …, 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 σ ∈ S_{n}^{d−1} contains a pattern π ∈ S_{k}^{d−1} if there exists a subset of points of the diagram of σ such that its standardization is equal to the diagram of π (see Figure 2).

x 1 2 3 4 y 1 2 3 4 z 1 2 3 4 x 1 2 3 y 1 2 3 z 1 2 3 1 2 3 x 1 2 3 y

Figure 2: On the left, the 3-permutation (1432, 3124). The red dots are an instance of the pattern (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.

This definition has been considered in [23], 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 i := i_{1}, …, i_{d′} ∈ [d]^{d′}, the projection on i of the d-permutation σ is the d′-permutation proj_{i}(σ) := \overline{σ}_{i_{2}} \overline{σ}_{i_{1}}^{−1}, \overline{σ}_{i_{3}} \overline{σ}_{i_{1}}^{−1}, …, \overline{σ}_{i_{d′}} \overline{σ}_{i_{1}}^{−1}. Then d′ is the dimension of the projection.

When dealing with permutations of dimension 2 or 3, we often use x, y, z instead of 1, 2, 3.

Remark 2. We have proj_{1,i}(σ) = σ_{i−1} = \overline{σ}_{i} and proj_{i,1}(σ) = \overline{σ}_{i}^{−1}. In particular, when d = 3, we have proj_{xy}(σ) = σ_{1} and proj_{xz}(σ) = σ_{2}, and so proj_{yz}(σ) = σ_{2}σ_{1}^{−1}. For instance, proj_{yz}((253146, 654321)) = 364251 (see Figure 1).

A projection proj_{i} is direct if i_{1} < i_{2} < ⋯ < i_{d′} and indirect otherwise.

Definition 3. Let σ = (σ_{1}, …, σ_{d−1}) ∈ S_{n}^{d−1} and π = (π_{1}, …, π_{d′−1}) ∈ S_{k}^{d′−1} with k ≤ n. Then σ contains the pattern π if there exist a direct projection σ′ = proj_{i}(σ) of dimension d′ and indices c_{1} < ⋯ < c_{k} such that σ′_{i}(c_{1}) ⋯ σ′_{i}(c_{k}) is order isomorphic to π_{i} for all i ∈ [d′]. A permutation avoids a pattern if it does not contain it.

Given a set of patterns π_{1}, …, π_{k}, we let S_{n}^{d−1}(π_{1}, …, π_{k}) denote the set of d-permutations that avoid each pattern π_{i}.

This definition of pattern differs slightly from the one proposed in [3]: here we consider only 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}(π) = S_{n}(π), 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 σ contains a d-permutation π if there exists a subset of points of its diagram that have the same relative positions as those of the diagram of the pattern π. This implies that σ_{i} ∈ S(π_{i})∀i ∈ [d − 1].

Hence

S_{n}(π_{1}) × S_{n}(π_{2}) ⋯ × S_{n}(π_{d−1}) ⊆ S_{n}^{d−1}(π).

In general this inclusion is strict. For instance, the (132, 312) does not contain the pattern (12, 12) but 132 and 312 both contain the pattern 12 (but in different positions).

Avoiding a pattern π of dimension 2 means that each projection of dimension 2 avoids π, in particular the d − 1 permutations defining the d-permutation, hence

S_{n}^{d−1}(π) ⊆ \underbrace{S_{n}(π) × ⋯ × S_{n}(π)}_{d − 1 times} .

Once again, in general this inclusion is strict. For instance, (132, 132) ∈ S_{n}(123)×S_{n}(123) but not in S_{n}^{2}(123) since proj_{yz}((132, 132)) = 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 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 d−Sym (or simply Sym when the dimension d is understood).

Given s ∈ d − Sym and σ ∈ S_{n}^{d−1}, we define s(σ) as the d-permutation whose diagram is the standardization of the point set

P′ := {(s.(p_{1}, …, p_{d})^{T})^{T} , (p_{1}, …, p_{d}) ∈ P_{σ}}.

For instance, in two dimensions, ( \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} )(σ) is the reverse permutation of σ, denoted by rev(σ): rev(σ)(i) = σ(n − i + 1). ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )(σ) is the inverse permutation of σ, denoted by σ^{−1}. In dimension 2, there are 8 symmetries and in dimension 3, there are 48 (|3-Sym | = 48).

3 Pattern avoidance

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 π_{1}, π_{2}, …, π_{k} and τ_{1}, τ_{2}, …, τ_{k′} are d-Wilf-equivalent if

|S_{n}^{d−1}(π_{1}, π_{2}, …, π_{k})| = |S_{n}^{d−1}(τ_{1}, τ_{2}, …, τ_{k′})|.

We say that two sets of patterns π_{1}, π_{2}, …, π_{k} and τ_{1}, τ_{2}, …, τ_{k′} are trivially d-Wilf-equivalent if there exists a symmetry s ∈ d − Sym that is a bijection from S_{n}(π_{1}, π_{2}, …, π_{k}) to S_{n}(τ_{1}, τ_{2}, …, τ_{k′}). In particular, if each pattern π_{1}, π_{2}, …, π_{k}, τ_{1}, τ_{2}, …, τ_{k′} is of dimension d, the two pattern sets are equivalent if s sends the the first one to the second one.

3.1 Some known results on permutations

In dimension 2, there are only two patterns of size 2 (12 and 21) that are trivially Wilfequivalent. For patterns of size 3, there are 2 classes of patterns that are trivially Wilfequivalent: 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 [30]: |S_{n}(τ)| = C_{n} for any τ of size 3 where C_{n} = \frac{1}{n+1} \binom{2n}{n}. All combinations of patterns of size 3 have been treated in [30]. Table 1 summarizes these results. Recently, all combinations of size 4 patterns have been studied [25].

Patterns #TWE  Sequence  Comment
12  2  1, 1, 1, 1, 1, 1, 1, ⋯
12, 21  1  1, 0, 0, 0, 0, 0, 0, ⋯
312  4  \frac{1}{n+1} \binom{2n}{n} = 1, 2, 5, 14, 42, 132, 429, ⋯  stack-sortable [24]
123  2  \frac{1}{n+1} \binom{2n}{n} = 1, 2, 5, 14, 42, 132, 429, ⋯  [24], [30, Prop. 19]
123, 321  1  1, 2, 4, 4, 0, 0, 0, ⋯  [30, Prop. 14]
213, 321  4  1 + \frac{n(n−1)}{2} = 1, 2, 4, 7, 11, 16, 22, ⋯  [30, Prop. 11]
312, 231  2  2^{n−1} = 1, 2, 4, 8, 16, 32, 64, ⋯  [27, Thm. 9], [30, Prop. 8]
231, 132  4  2^{n−1} = 1, 2, 4, 8, 16, 32, 64, ⋯  [30, Prop. 9]
312, 321  4  2^{n−1} = 1, 2, 4, 8, 16, 32, 64, ⋯  [30, Prop. 7]
213, 132, 123  2  Fibonacci: 1, 2, 3, 5, 8, 13, 21, ⋯  [30, Prop. 15]
231, 213, 321  8  n = 1, 2, 3, 4, 5, 6, 7, ⋯  [30, Prop. 16*]
312, 132, 213  4  n = 1, 2, 3, 4, 5, 6, 7, ⋯  [30, Prop. 16*]
312, 321, 123  4  1, 2, 3, 1, 0, 0, 0, ⋯
321, 213, 123  4  1, 2, 3, 1, 0, 0, 0, ⋯
321, 213, 132  2  n = 1, 2, 3, 4, 5, 6, 7, ⋯  [30, Prop. 16*]

Table 1: Sequences of (2-)permutations avoiding small patterns. The second column (#TWE) indicates the number of trivially Wilf-equivalent patterns.

3.2 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 2.

In dimension 3, there are four patterns of size 2 that are trivially Wilf-equivalent to the pattern (12, 12). The class S_{n}^{2}((21, 12)) corresponds intervals in the weak-Bruhat poset (see Prop. 5). An inversion in a permutation π is a pair (i, j) such that i < j and π(i) > π(j). We say that that a permutation π_{1} is smaller than a permutation π_{2}, π_{1} ≤_{b} π_{2} in the weak Bruhat order if the set of inversions of π_{1} is included in the set of inversions of π_{2}. An 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.

Patterns  #TWE  Sequence  Comment
(12, 12)  4  1, 3, 17, 151, 1899, 31711, ⋯  Prop. 5, \underline{A007767}
(12, 12), (12, 21)  6  n! = 1, 2, 6, 24, 120 ⋯  Prop. 4
\begin{matrix}(12, 12), (12, 21), \\ (21, 12) \end{matrix}  4  1, 1, 1, 1, 1, 1, ⋯  Prop. 4
\begin{matrix}(12, 12), (12, 21), \\ (21, 12), (21, 21) \end{matrix}  1  1, 0, 0, 0, 0, 0, ⋯
(123, 123)  4  1, 4, 35, 524, 11774, 366352, 14953983, ⋯  new
(123, 132)  24 1, 4, 35, 524, 11768, 365558, 14871439, ⋯  new
(132, 213)  8  1, 4, 35, 524, 11759, 364372, 14748525, ⋯  new
(12, 12), (132, 312) 48  (n + 1)^{n−1} = 1, 3, 16, 125, 1296 ⋯  \underline{A000272} [4, 5]
(12, 12), (123, 321) 12  1, 3, 16, 124, 1262, 15898, ⋯  Prop. 5, \underline{A190291}
(12, 12), (231, 312)  8  1, 3, 16, 122, 1188, 13844, ⋯  \underline{A295928}? [28]

Table 2: 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.

Avoiding two patterns of size 2 also leads to a unique Wilf equivalence class that has cardinality n!:

Proposition 4. For n ≥ 1, we have

|S_{n}^{2}((12, 12), (12, 12))| = n!,
|S_{n}^{2}((12, 12), (12, 21), (21, 12))| = 1.

Proof. Let us consider the pattern set {(12, 21), (21, 12)}, which is trivially Wilf equivalent to {(12, 12), (12, 12)}. Let (σ_{1}, σ_{2}) ∈ S_{n}^{2}{(12, 21), (21, 12)}. For all i, j, σ_{1}(i) < σ_{1}(j) if and only if σ_{1}(i) < σ_{1}(j). This implies that σ_{1} = σ_{2}. Hence S_{n}^{2}((12, 21), (21, 12)) = {(σ, σ), σ ∈ S_{n}}, and |S_{n}^{2}((12, 21), (21, 12))| = n!. In this set, if we avoid a third pattern (21, 21), the only permutation that remains is (Id_{n}, Id_{n}), hence |S_{n}^{2}((12, 21), (21, 12), (21, 21))| = 1. Since every set of three patterns of size 2 is trivially Wilf equivalent to every other, we get the second equality.

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 {(12, 12), (132, 312)}. This pattern set is sent to the pattern set \{(12, 21), (321, 132)\} by the symmetry ( \begin{matrix}0 & 0 & −1 \\ 0 & −1 & 0 \\ 1 & 0 & 0 \end{matrix} ).

The set S_{n}^{2}((12, 21), (321, 132)) is exactly the set of allowable pairs sorted by a priority queue, as shown in [4]. Moreover Atkinson and Thiyagarajah [5] proved that this set is of size (n+1)^{n+1}. A bijection between these permutations and labeled trees has been described in [4].

Proposition 5. For n ≥ 1, we have

1. S_{n}^{2}((12, 12)) is in bijection with the intervals in the weak-Bruhat poset on S_{n}.

2. S_{n}^{2}((12, 12), (123, 321)) is in bijection with the intervals in the weak-Bruhat on S_{n} that are distributive lattices.

Proof. 1. Observe that i_{1}, i_{2} is an inversion in π_{1} but not in π_{2}. Hence, i_{1}, i_{2} is an instance of the pattern (12, 12) in (π_{1}, π_{2}). Hence the class S_{n}^{2}((21, 12)) corresponds to the intervals in the weak-Bruhat poset. We conclude by observing that the symmetry ( \begin{matrix}−1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & −1 \end{matrix} ) maps bijectively S_{n}^{2}((21, 12)) to S_{n}^{2}((12, 12)).

2. As shown in [31, Proposition 2.3], the sub-poset defined by the interval σ_{1}, σ_{2} is isomorphic to the sub-poset of permutations smaller than σ_{1}^{−1}σ_{2}. Moreover, as shown in [31, Theorem 3.2], this sub-poset is a distributive lattice if and only if σ_{1}^{−1}σ_{2} ∈ S_{n}(321). Let G_{n} be the set of 3-permutations σ ∈ S_{n}^{2}((21, 12)) such that σ_{1}^{−1}σ_{2} ∈ S_{n}(321). We will now show that S_{n}^{2}((21, 12), (123, 321)) = G_{n}. If i_{1} < i_{2} < i_{3} is an occurrence of (123, 321) in a permutation σ, then it is also an occurrence of 321 in σ_{1}^{−1}σ_{2}. Hence G_{n} ⊆ S_{n}^{2}((21, 12), (123, 321)), so let us focus on the second inclusion. Consider (σ_{1}, σ_{2}) ∈ S_{n}^{2}((21, 12)) such that i_{1} < i_{2} < i_{3} is an occurrence of 321 in σ_{1}^{−1}σ_{2}. If σ_{1}(i_{1}) < σ_{1}(i_{2}), then i_{1}, i_{2} is an occurrence of (21, 12) in σ, which is impossible. Hence σ_{1}(i_{1}) > σ_{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 σ_{1}. Now, σ_{1}^{−1}σ_{2} and σ_{1} fully determine σ_{2} and we have π_{2}(i_{1}) > π_{2}(i_{2}) > π_{2}(i_{3}). Hence i_{1}, i_{2}, i_{3} is an occurrence of (123, 321) in σ, which yields the second inclusion.

We conclude by observing that the symmetry ( \begin{matrix}−1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & −1 \end{matrix} ) sends S_{n}^{2}((21, 12), (123, 321)) bijectively to S_{n}^{2}((12, 12), (123, 321)).

Now, let us focus on 3-permutations that avoid patterns of dimension 2. Table 3 synthesizes the results. We start by some considerations on the trivially d-Wilf-equivalence of patterns (and pattern sets) of smaller dimension.

Remark 6. Let σ ∈ S_{n}^{2} with n ≥ 2. One can observe that if proj_{x,y}(σ) ∈ S_{n}(21) and proj_{x,z}(σ) ∈ S_{n}(21), then proj_{y,z}(σ) contains the pattern 21. Hence |S_{n}^{2}(21)| = 0 for n ≥ 2. On the other hand, one can check that S_{n}^{2}(21) = {(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}.

Given a symmetry s ∈ d − Sym and an increasing sequence of indices i_{1} < i_{2} ⋯ i_{d′}, we define s_{i} as an element of d′ − Sym obtained from s by keeping the rows whose index is in i, and the columns containing a non-zero value in one of these rows. For instance, if

s = ( \begin{matrix}0 & 0 & −1 \\ 0 & −1 & 0 \\ 1 & 0 & 0 \end{matrix} ) and i = 1, 3, then s_{i} = ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} ). Given s ∈ d − Sym and π ∈ S_{n}^{d′−1}, we make

the following definition, if π is a d′-multipermutation: s̃({π}) := {s_{i}(π), i = i_{1}, …, i_{d′}} and if π_{1}, …, π_{k} is a set, s̃({π_{1}, …, π_{k}}) := ∪_{i=1}^{k}s̃({π_{i}}).

In general s̃(s̃^{−1}(π)) ≠ π. For instance, as we saw above, for d = 3 and s the identity matrix of size 3, s̃^{−1}(s̃({12})) = {12, 21}.

Proposition 7. Two pattern sets π_{1}, …, π_{k} and τ_{1}, …, τ ′_{k} are trivially d-Wilf-equivalent if there exists s ∈ d−Sym such that s̃(π_{1}, …, π_{k}) = τ_{1}, …, τ ′_{k} and π_{1}, …, π_{k} = s̃^{−1}(τ_{1}, …, τ ′_{k}).

Proof. Let π_{1}, …, π_{k}, τ_{1}, …, τ ′_{k} and s be as in the proposition. Let us first show that |S_{n}(π_{1}, …, π_{k})| ≥ |S_{n}(τ_{1}, …, τ_{k})| and then we will show the other inequality.

Let σ ∉ S_{n}^{d}(π_{1}, …, π_{k}) and let i, k be such that proj_{i}(σ) contains π_{k}. Then s_{i}(proj_{i}(σ))) contains s_{i}(π_{k}). Let j be the set of indices of the rows of s that contain a non-zero entry in the columns of index in i. Since proj_{j}(s(σ)) = s_{i}(proj_{i}(σ)) and s_{i}(π_{k}) ∈ s̃(π_{k}) ⊂ {τ_{1}, …, τ ′_{k}}, we have s(σ) ∉ S_{n}^{d}(τ_{1}, …, τ_{k}). Hence |S_{n}(π_{1}, …, π_{k})| ≥ |S_{n}(τ_{1}, …, τ_{k})|.

We proceed similarly for the other inequality. Let σ ∉ S_{n}^{d}(τ_{1}, …, τ_{k}) and let i, k be such that proj_{i}(σ) contains τ_{k}. Then s_{i}^{−1}(proj_{i}(σ)) contains s_{i}^{−1}(τ_{k}). Let j be the indices of the rows that contain a non-zero entry in the columns of s^{−1} of index in i. Since proj_{j}(s^{−1}(σ)) = s_{i}^{−1}(proj_{i}(σ)) and s_{i}^{−1}(τ_{k}) ∈ s̃^{−1}(τ_{k}) ⊂ {π_{1}, …, π′_{k}}, we have s(σ) ∉ S_{n}^{d}(π_{1}, …, π_{k}). Hence |S_{n}(π_{1}, …, π_{k})| ≤ |S_{n}(τ_{1}, …, τ_{k})|.

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 4), 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.

We conclude this section with sets of patterns that are invariant under all symmetries. Given a d-permutation σ, we write Sym(σ) := {s(σ))|s ∈ d-Sym}.

Figure 3 describes all the symmetric 2-permutations obtained from (132, 213). This symmetric pattern plays an important role in separable d-permutations and Baxter d-permutations, as we will see in Section 4.

Patterns #TWE  Sequence  Comment
12  1  1, 0, 0, 0, 0, ⋯  Remark 6
21  1  1, 1, 1, 1, 1, ⋯  Remark 6
123  1  1, 4, 20, 100, 410, 1224, 2232, ⋯  new
132  2  1, 4, 21, 116, 646, 3596, 19981, ⋯  new
231  2  1, 4, 21, 123, 767, 4994, 33584, ⋯  new
321  1  1, 4, 21, 128, 850, 5956, 43235, ⋯  new
123, 132  2  1, 4, 8, 8, 0, 0, 0, ⋯
123, 231  2  1, 4, 9, 6, 0, 0, 0, ⋯
123, 321  1  1, 4, 8, 0, 0, 0, 0, ⋯
132, 213  1  1, 4, 12, 28, 58, 114, 220, ⋯  new
132, 231  4  1, 4, 12, 32, 80, 192, 448, ⋯  \underline{A001787}?
132, 321  2  1, 4, 12, 27, 51, 86, 134, ⋯  \underline{A047732}?
231, 312  1  1, 4, 10, 28, 76, 208, 568, ⋯  \underline{A026150}?
231, 321  2  1, 4, 12, 36, 108, 324, 972, ⋯ \underline{A003946}?

Table 3: 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.

Patterns #TWE  Sequence  Comment
12, (12, 12)  1  1, 0, 0, 0, 0, ⋯  12
12, (21, 12)  3  1, 0, 0, 0, 0, ⋯  12
21, (12, 12)  1  1, 0, 0, 0, 0, ⋯
21, (21, 12)  3  1, 1, 1, 1, 1, ⋯  21
123, (12, 12)  1  1, 3, 14, 70, 288, 822, 1260, ⋯  new
123, (12, 21)  3  1, 3, 6, 6, 0, 0, 0, ⋯
132, (12, 12)  2  1, 3, 11, 41, 153, 573, 2157, ⋯ \underline{A281593}?
132, (12, 21)  6  1, 3, 11, 43, 173, 707, 2917, ⋯ \underline{A026671}?
231, (12, 12)  2  1, 3, 9, 26, 72, 192, 496, ⋯ \underline{A072863}?
231, (12, 21)  4  1, 3, 11, 44, 186, 818, 3706, ⋯  new
231, (21, 12)  2  1, 3, 12, 55, 273, 1428, 7752, ⋯ \underline{A001764}?
321, (12, 12)  1  1, 3, 2, 0, 0, 0, 0, ⋯
321, (12, 21)  3  1, 3, 11, 47, 221, 1113, 5903, ⋯ \underline{A217216}?

Table 4: 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.

Remark 8. A convenient way to describe this pattern is the following: a permutation σ contains the pattern Sym((132, 213)) 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.

1 2 3 1 2 3 1 2 3

[[2, 1, 3], [1, 3, 2]]

1 2 3 1 2 3 1 2 3

[[3, 1, 2], [2, 1, 3]]

1 2 3 1 2 3 1 2 3

[[2, 1, 3], [3, 1, 2]]

1 2 3 1 2 3 1 2 3

[[3, 1, 2], [2, 3, 1]]

1 2 3 1 2 3 1 2 3

[[2, 3, 1], [1, 3, 2]]

1 2 3 1 2 3 1 2 3

[[1, 3, 2], [2, 1, 3]]

1 2 3 1 2 3 1 2 3

[[1, 3, 2], [2, 3, 1]]

1 2 3 1 2 3 1 2 3

[[2, 3, 1], [3, 1, 2]]

Figure 3: The eight 3-permutations of Sym((132, 213)).

Patterns  | Sym(π)|  Sequence  Comment
Sym((123, 123))  4  1, 4, 32, 368, 4952, 68256, ⋯  new
Sym((123, 132))  24  1, 4, 12, 4, 4, 4, ⋯  Prop. 9
Sym((132, 213))  8  1, 4, 28, 256, 2704, 31192, ⋯  new

Table 5: Sequences of 3-permutations avoiding a pattern of size 3 with all its symmetries. The second column indicates the number of forbidden patterns.

The number of permutations avoiding Sym((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.

Proposition 9. For n ≥ 1, we have

S_{n}^{2}(Sym((123, 132))) = \begin{cases}S_{n}^{2}, & if n ≤ 2; \\ S_{3}^{2} \ Sym((123, 132)), & if n = 3; \\ Sym((Id_{n}, Id_{n})), & otherwise. \end{cases}

Proof. For n ≤ 4 the proposition can be easily checked manually. For n ≥ 4, we will show that S_{n}^{2}(Sym((123, 132))) = Sym((Id_{n}, Id_{n})) = {(Id_{n}, Id_{n}), (Id_{n}, rev(Id_{n})), (rev(Id_{n}), Id_{n}), (rev(Id_{n}), rev(Id_{n}))}. Clearly, Sym((Id_{n}, Id_{n})) ⊆ S_{n}^{2}(Sym((123, 132))), so we only have to show the other inclusion.

Suppose that the proposition is true until some n ≥ 4 and let us show that it is still true for n + 1. Let σ ∈ S_{n+1}^{2}(Sym((123, 132))). Let σ′ be the permutation obtained by removing the point (x, y, z) such that z = n + 1. If σ avoids a pattern π, σ′ also avoids π. Hence σ′ ∈ S_{n}^{2}(Sym((123, 132))). By our inductive hypothesis, σ′ ∈ Sym((Id_{n}, Id_{n})). Now we only have to show that if σ′ = (Id_{n}, Id_{n}), then σ = (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 ≤ y, the other cases being deduced from the first ones by symmetry:

• x = y = n + 1. In this case σ = (Id_{n+1}, Id_{n+1}).

• x = y = 1: the permutation will be σ = (Id_{n+1}, (n + 1) 1 ⋯ n) which contains the pattern (123, 312) ∈ Sym((123, 132)), which is a contradiction.

• x = 1, y > 1: (y 1 ⋯ y − 1 y + 2 ⋯ n + 1, n + 1 1 ⋯ n) which contains (123, 312) ∈ Sym((123, 132)), which is a contradiction.

• 1 < x < n + 1, y = x. σ = (Id_{n+1}, 1 ⋯ (x − 1) (n + 1) x ⋯ n) which contains the pattern (123, 132) ∈ Sym((123, 132)), which is a contradiction.

• 1 < x < n + 1, y > x. σ = (1 ⋯ (x − 1) y x ⋯ (n + 1), 1 ⋯ (y − 1) (n + 1) y ⋯ n) contains (132, 132) ∈ Sym((123, 132)), which is a contradiction.

• x = n + 1, y < n + 1. σ = (1 ⋯ (y − 1)(y + 1) ⋯ (n + 1) y, Id_{n+1}) which contains (231, 123) ∈ Sym((123, 132)). Contradiction.

So if σ′ = (Id_{n}, Id_{n}), then σ = (Id_{n+1}, Id_{n+1}). By symmetry, we conclude that

Sym((Id_{n+1}, Id_{n+1})) = S_{n+1}^{2}(Sym((123, 132))).

Hence the property is true for all n ≥ 4.

In the Appendix, we give sequences corresponding to larger patterns. At the date of writing, none of these sequences appear in OEIS [26].

4 Baxter d-permutations

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 [3], 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 complete Baxter permutation and anti-Baxter permutation.

4.1 Separable permutations and Baxter permutations

Let σ and π be two permutations respectively of size n and k. Their direct sum and skew sum are the permutations of size n + k defined by

σ ⊕ π := σ(1), …, σ(n), π(1) + n, …, π(k) + n and
σ ⊖ π := σ(1) + k, …, σ(n) + k, π(1), …, π(k).

A permutation is 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öder numbers as shown in [29]:

| Sep_{n} | = \frac{1}{n − 1} ∑_{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 [10]:

Sep_{n} = S_{n}(2413, 3142).

A related class of permutations are the Baxter permutations. Baxter permutations have been widely studied because they are related to numerous other combinatorial objects [9, 18, 20]. 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 vincular pattern π|_{X} is composed of π ∈ S_{k}, a permutation, and X ⊆ [k − 1], a set of (horizontal) adjacencies. A permutation σ ∈ S_{n} contains the vincular pattern π|_{X} if there exist indices i_{1} < ⋯ < i_{k} such that σ_{i_{1}}, σ_{i_{2}} ⋯ σ_{i_{k}} is an occurrence of π in σ and i_{j+1} = i_{j} + 1 for each j ∈ X. A vincular pattern π|_{X} is classically represented as a permutation with dashes between the entries without adjacency constraints. For instance, the vincular pattern 2413|_{2} is represented by 2-41-3. We stick to our notation so that it can be generalized to d-permutations.

Baxter permutations (introduced by Baxter [7]) are exactly the permutations that avoid 2413|_{2} and 3142|_{2} (see Figure 5):

B_{n} := S_{n}(2413|_{2}, 3142|_{2}).
|B_{n}| = ∑_{k=1}^{n} \begin{matrix}\binom{n+1}{k−1} & \binom{n+1}{k} & \binom{n+1}{k+1} \\ \binom{n+1}{1} & \binom{n+1}{2} \end{matrix}.

1 2 3 4 5 6 x 1 2 3 4 5 6 y

[[6, 4, 3, 5, 1, 2]]

1 2 3 4 5 6 x 1 2 3 4 5 6 y

[[4, 1, 3, 5, 2, 6]]

1 2 3 4 5 6 x 1 2 3 4 5 6 y

[[2, 4, 1, 5, 3, 6]]

Figure 4: On the left the separable permutation 643512 = 1 ⊖ ((1 ⊖ 1) ⊕ 1) ⊖ (1 ⊕ 1). In the middle a Baxter permutation that is not a separable permutation. On the right a permutation that is not a Baxter permutation.

1 2 3 4 x 1 2 3 4 y 1 2 3 4 x 1 2 3 4 y

Figure 5: Baxter permutation forbidden vincular patterns: 2413|_{2} and 3142|_{2}. The adjacency is indicated by a vertical (green) strip.

The first few terms of (B_{n}) are 1, 2, 6, 22, 92, 422, 2074 (sequence \underline{A001181}).

Figure 6 and the first two permutations of Figure 4 give examples of Baxter permutations.

4.2 Separable d-permutations

A d-direction (or simply a direction) dir is a word on the alphabet {+, −} of length d such that its first entry is positive.

Let σ and π be two d-permutations and dir a direction. The d-sum with respect to dir is the d-permutation

σ ⊕^{dir} π := \overline{σ}_{2} ⊕_{2}^{dir} \overline{π}_{2}, …, \overline{σ}_{d} ⊕_{d}^{dir} \overline{π}_{d},

where ⊕_{i}^{dir} is ⊕ if dir_{i} = + and ⊖ if dir_{i} = −.

A 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 7.

1 2 3 4 5 6 7 8 9 10 x 2 4 6 8 10 y

Figure 6: An example of a Baxter permutation. At each ascent (resp., descent) we associate a blue (resp., red) vertical rectangle, called slice, and we associate a blue (resp., red) horizontal rectangle to each ascent (resp., descent) of the inverse permutation.

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 Sym((132, 213)) (see Figure 3). In fact, these eight permutations together with the two patterns of length 4 exactly characterize the separable d-permutations for any d ≥ 3, as shown in [3]. We restate their result with our formalism:

Theorem 10. [3] Let Sep_{n}^{d−1} be set of separable d-permutations of size n.

Sep_{n}^{d−1} = S_{n}^{d−1}(Sym((132, 213)), 2413, 3142).

The following explicit formulas were established in [3]:

| Sep_{n}^{d−1} | = \frac{1}{n − 1} ∑_{k=0}^{n−2} \binom{n − 1}{k}\binom{n − 1}{k + 1}(2^{d−1} − 1)^{k}(2^{d−1})^{n−k−1}.

Now we give a new characterization of separable d-permutations (Theorem 11). 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) × (d − 2)/2 projections.

Theorem 11. For n ≥ 1, we have

Sep_{n}^{d−1} = S_{n}(2413, 3142)^{d−1} ∩ S_{n}^{d−1}(Sym((132, 213))).

1 2 3 1 2 3 1 2 3 1 2 1 2 1 2 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

Figure 7: A permutation p_{1} = (132, 132) (on the left) and a permutation p_{2} = (12, 21) (in the middle). p_{1} and p_{2} are separable 3-permutations because p_{1} = (1, 1)⊕^{(+++)} ((1, 1)⊕^{(+−−)} (1, 1)) and p_{2} = (1, 1) ⊕^{(+−+)} (1, 1). On the right, their d-sum with respect to (+ + +) is (132, 132) ⊕^{(+++)} (21, 21) = (13254, 13254) which is still separable.

\begin{matrix}n\d & 2 & 3 & 4 & 5 \\ 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 4 & 8 & 16 \\ 3 & 6 & 28 & 120 & 496 \\ 4 & 22 & 244 & 2248 & 19216 \\ 5 & 90 & 2380 & 47160 & 833776 \\ 6 & 394 & 24868 & 1059976 & 38760976 \\ 7 & 1806 & 272188 & 24958200 & 1887736816 \end{matrix}

Table 6: Values of | Sep_{n}^{d−1} | for the first few values of n and d.

Proof. To prove this result, we only need to prove that for any σ ∈ S_{n}^{d−1}(Sym((132, 213))) and any 1 < i < j ≤ n, if proj_{i,j}(σ) contains one of the patterns 2413, 3142, then σ_{j} does also.

So let σ ∈ S_{n}^{d−1}(Sym((132, 213))) and 1 < i, j ≤ n be such that proj_{i,j}(σ) contains the pattern 2413 (the other case being identical). Let p_{1}, p_{2}, p_{3}, p_{4} ∈ P_{σ} be an occurrence of this pattern such that x(p_{1}) < x(p_{2}) < x(p_{3}) < x(p_{4}). The projection of p_{1} and p_{2} in the plane (x_{i}, x_{j}) are in the same quadrant as the projection of p_{3} since σ avoids Sym((132, 213)) and by Remark 8, x(p_{3}) is not between x(p_{1}) and x(p_{2}).

Applying the same argument to the three other triplets of points, we get that x(p_{1}) is not between x(p_{2}) and x(p_{4}), x(p_{3}) is not between x(p_{1}) and x(p_{2}), and x(p_{4}) is not between x(p_{1}) and x(p_{3}).

There are only two orders that satisfy these four constraints: x(p_{1}) < x(p_{2}) < x(p_{3}) < x(p_{4}) and x(p_{4}) < x(p_{3}) < x(p_{2}) < x(p_{1}). In the first case, the four points induce the pattern 2413 on proj_{1,j}. In the second case, they induce 3142.

Hence, if proj_{i,j}(σ) contains a forbidden pattern, so does proj_{1,j}(σ) = σ_{j}.

4.3 Baxter d-permutations

We now generalize the notion of a Baxter permutation to higher dimensions. To do so, we introduce a formalism that will facilitate the definition of Baxter d-permutations.

Given P_{σ} the diagram of a d-permutation σ, two points p_{i}, p_{j} of P_{σ} are k-adjacent if they differ by one in their kth coordinate, and k is said to be the type of the adjacency. The direction of p_{i}, p_{j} is the sequence of the signs of x_{k}(p_{j})−x_{k}(p_{i}) (for k ∈ [d]) if x_{1}(p_{i}) < x_{1}(p_{j}), otherwise it is the direction of p_{j}, p_{i}. Given two adjacent points p_{i} and p_{j}, the slice of p_{i}, p_{j} is the d-dimensional box with p_{i} and p_{j} as corners. A slice p_{i}, p_{j} is of type k is p_{i}, p_{j} are k-adjacent. The direction of a slice p_{i}, p_{j} is the direction of p_{i}, p_{j}. A cell is a unit cube whose corners are in [n]^{d}. A single slice can have multiple types. For instance, if a slice is a cell, it is of all possible types.

For d = 2, an ascent in a permutation corresponds to an adjacency of type 1 (which corresponds to the x-axis) with direction (++); a descent is an adjacency of type 1 with direction (+−). An adjacency of type 2 (which corresponds to the y-axis) with direction (+−) corresponds to an ascent in the inverse permutation.

In Figure 6, slices of direction (++) are represented in blue and those of type (+−) in blue.

Definition 12. A d-permutation is well-sliced if each slice intersects exactly one slice of each type and two intersecting slices have the same direction.

One can observe that the Baxter permutation in Figure 6 is well-sliced.

Definition 13. A Baxter d-permutation is a d-permutation such that each of its d′ ≤ d projections is well-sliced.

By definition, if a d-permutation is Baxter, this is also the case for all its projections of smaller dimensions. On the other hand, a d-permutation can be well-sliced and have projections that are not well-sliced. Take, for instance, the 3-permutation (342651, 156243). Its projection on the plane (y, z) is 361542, which is not well-sliced since it is not a Baxter permutation (see Figure 8).

Table 7 gives the first few values of |B_{n}^{d−1}|.

In order to characterize the Baxter d-permutations, let us introduce the notion of generalized vincular patterns.

Definition 14. A generalized vincular pattern π|_{X_{1},...,X_{d}} is a permutation π together with a list of subsets of [k − 1] X_{1}, …, X_{d} called adjacencies. Given σ a d-permutation, we say that p_{1}, …, p_{k} ∈ P_{σ} is an occurrence of the pattern π|_{X_{1},...,X_{d}} if p_{1}, …, p_{k} is an occurrence of π and if it satisfies the adjacency constraints: for each k and each i ∈ X_{k}: the ith and (i + 1)th points with respect to the order along the axis k are k-adjacent. We say that σ, a d-permutation, contains the pattern π|_{X_{1},...,X′_{d}} (of dimension d′) if at least one direct projection of dimension d′ of σ contains an occurrence of the pattern π|_{X_{1},...,X′_{d}}.

n\d 2  3  4  5
1  1  1  1  1
2  2  4  8  16
3  6  28  120  496
4  22  260 2440 20816
5  92 2872 59312 1035616
6 422 35620
7 2074 479508

Table 7: Values of |B_{n}^{d−1}| for the first few values of n and d.

x 1 2 3 4 5 6 y 1 2 3 4 5 6 z 1 2 3 4 5 6 1 2 3 4 5 6 x 1 2 3 4 5 6 y

Figure 8: On the left, (342651, 156243), an example of a 3-permutation that is well-sliced but not Baxter since its projection on the plane (y, z) (361542) on the right is not well-sliced.

It is well known that S_{n}(2413|_{2}) = S_{n}(2413|_{2,2}) and S_{n}(3142|_{2}) = S_{n}(3142|_{2,2}) (see Figure 10). Every occurrence of 2413|_{2,2} is clearly an occurrence of 2413|_{2}. The converse is obtained due to the following observation: if i_{1}, i_{2}, i_{3}, i_{4} is an occurrence of 2413|_{2} in σ, let i′_{1} be such that i′_{1} < i_{2} and σ(i_{1}) ≤ σ(i′_{1}) < σ(i_{4}), such that σ(i′_{1}) is maximal. Let i′_{4} = σ^{−1}(σ(i′_{1}) + 1). We have that i′_{1}, i_{2}, i_{3}, i′_{4} is an occurrence of 2413|_{2,2}.

It follows that

B_{n} = S_{n}(2413|_{2,2}, 3142|_{2,2}).

As a warm-up for the rest of this section, let us reprove that our definition of Baxter d-permutations coincides with the classical one.

Proposition 15. A permutation is a Baxter permutation if and only if it is well-sliced.

Proof. As shown above, B_{n} = S_{n}(2413|_{2,2}, 3142|_{2,2}). If a permutation contains one of the above patterns, then it contains 2 intersecting slices of different directions, hence it is not

x 1 2 3 4 5 6 7 8 y 1 2 3 4 5 6 7 8 z 1 2 3 4 5 6 7 8 x 1 2 3 4 5 6 7 8 y 1 2 3 4 5 6 7 8 z 1 2 3 4 5 6 7 8 x 1 2 3 4 5 6 7 8 y 1 2 3 4 5 6 7 8 z 1 2 3 4 5 6 7 8 x 1 2 3 4 5 6 7 8 y 1 2 3 4 5 6 7 8 z 1 2 3 4 5 6 7 8

Figure 9: (14386527, 47513268): an example of a Baxter 3-permutation, together with its slices of different types.

well-sliced. Now let consider a permutation σ that is not well-sliced and let us show that it contains a forbidden pattern. As it is not well-sliced, it contains (i) a pair of intersecting slices of different directions, (ii) it contains a slice that intersects two other slices or (iii) it contains a slice that does not intersect any other slices.

(i): Any occurrence of two slices of different directions is an occurrence of one of the two forbidden patterns.

(ii): Let p_{1}, p′_{1}, p_{2}, p_{3}, p_{4}, p′_{4} be such that p_{2}, p_{3} is a vertical slice, and p_{1}, p_{4} and p′_{1}, p′_{4} are two horizontal slices intersecting the slice p_{2}, p_{3}. Since we have treated the case (i) we can assume that the 3 slices are of the same type and, without loss of generality, we can assume that this type is (++). Observe that p_{1}, p′_{1}, p_{4}, p′_{4} are four different points but this set of points may intersect the point set {p_{2}, p_{3}}. Nevertheless we can assume that p_{1} and p′_{1} are on the left of p_{3} and p_{4} and p′_{4} are on the right of p_{2}. We can also assume, without loss of generality, that p′_{1} and p′_{4} are below p_{1} and p_{4}. Hence p_{1}, p_{2}, p_{3}, p′_{4} are four different points and we can then observe that this point set is an occurrence of 3142|_{2}, hence σ contains 3142|_{2,2}.

1 2 3 4 x 1 2 3 4 y 1 2 3 4 x 1 2 3 4 y

Figure 10: Baxter permutations can also be characterized by these two generalized vincular forbidden patterns: 2413|_{2,2} and 3142|_{2,2}.

(iii): Let us show this case cannot occur. In other words, let us show that every vertical slice intersects at least one horizontal slice. Without loss of generality, we may restrict ourselves to the case of an ascent. Let i_{1} be such that σ(i_{1}) < σ(i_{1} + 1). Let i_{2} be such that i_{2} ≤ i_{1} such that σ(i_{1}) ≤ σ(i_{2}) < σ(i_{1} + 1) and such that σ(i_{2}) is maximal. Let i_{3} = σ^{−1}(σ(i_{2}) + 1). By construction, i_{3} ≥ i_{2}. Hence, the vertical slice p_{i_{1}}, p_{i_{1}+1} intersects the horizontal slice p_{i_{2}}, p_{i_{3}}, which is a contradiction.

The action of the symmetries of the hypercube extends naturally to the generalized vincular patterns. We can remark that Sym(2413|_{2,2}) = {2413|_{2,2}, 3142|_{2,2}}, and hence B_{n} = S_{n}(Sym(2413|_{2,2})).

Theorem 16. For n ≥ 1, we have

B_{n}^{d−1} = S_{n}^{d−1}( Sym(2413|_{2,2}), Sym((312, 213)|_{1,2,.}),
Sym((3412, 1432)|_{2,2,.}), Sym((2143, 1423)|_{2,2,.})).

Figure 11 depicts an occurrence of each class of forbidden patterns of dimension 3. The list of all symmetries of these patterns is given in Appendix A.

Proof. Let us start with the easy inclusion:

⊆: Let σ be a d-permutation that contains one of the forbidden patterns. If a dpermutation contains one of the forbidden patterns

Sym(2413|_{2,2}) (resp., Sym((2143, 1423)|_{2,2,.})),

then at least one of its 2-dimensional (resp., 3-dimensional) projection is not well sliced since these patterns are witnesses of the intersections of two slices of different directions. Hence σ is not Baxter.

If p_{1}, p_{2}, p_{3} (resp., p_{1}, p_{2}, p_{3}, p_{4}) is an occurrence of the pattern (312, 213)|_{1,2,.} (resp., (3412, 1432)|_{2,2,.}) in one of the 3-dimensional projection of σ := σ_{3}, then the slices p_{1}, p_{2} and p_{1}, p_{3} (resp., p_{1}, p_{4} and p_{2}, p_{3}) do not intersect. We remark that in proj_{x,y}(σ_{3}), the corresponding slices intersect. Hence, either there is no other intersection of the slices p_{1}, p_{2} (resp., p_{1}, p_{4}) in σ_{3} and σ_{3} is not well sliced, or the slice intersects another slice in σ_{3} and in this case the slice p_{1}, p_{2} (resp., p_{1}, p_{4}) intersects two slices in proj_{x,y}(σ_{3}). In either case, σ is not Baxter. We can apply the same reasoning to all symmetries of (312, 213)|_{1,2,.}and (3412, 1432)|_{2,2,.}. Now let us consider the other inclusion.

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Figure 11: On the left, the three 3-dimensional vincular pattern forbidden in Baxter dpermutations: (312, 213)|_{1,2,.},(3412, 1432)|_{2,2,.},(2143, 1423)|_{2,2,.}. The adjacency constraints are materialized by boxes orthogonal to the concerned axes. On the right the corresponding 3-permutations with all its slices. One can observe that it is not well-sliced because the first two have a lack of slice intersections and the last one a bad intersection.

⊇: Let σ be a d-permutation that is not Baxter. We will now prove that it contains one of the forbidden patterns. Consider the three following sub-cases:

• (i) there are two intersecting slices of different directions. We may assume, without loss of generality, that the slice p_{2}, p_{3} of type x intersects the slice p_{1}, p_{4} of type y. If the signs of the direction of the slices are different for x or y, then p_{1}, p_{2}, p_{3}, p_{4} is an occurrence of a forbidden pattern in Sym(2413|_{2,2}) in proj_{xy}(σ). So now let us assume that the directions of these two slices share the same signs on the coordinates x and y but differ on a third coordinate. Without loss of generality, we may assume that the third coordinate is z and in proj_{xyz}(σ) the direction for the first one is (+ + +) and (+ + −) for the second. First observe that since these two slices intersect each other and are of different types, p_{1}, p_{2}, p_{3}, p_{4} are four different points and we have x(p_{1}) < x(p_{2}) < x(p_{3}) < x(p_{4}) and y(p_{2}) < y(p_{1}) < y(p_{4}) < y(p_{3}). Moreover we have z(p_{2}) < z(p_{3}) and z(p_{4}) < z(p_{1}). If z(p_{1}) and z(p_{4}) are between z(p_{2}) and z(p_{3}), then proj_{xz}(σ) contains a forbidden pattern in Sym(2413|_{2,2}). If z(p_{2}) and z(p_{3}) are between z(p_{4}) and z(p_{1}), then proj_{yz}(σ) contains a forbidden pattern in Sym(2413|_{2,2}). If this is not the case, then either z(p_{2}) < z(p_{4}) < z(p_{3}) < z(p_{1}) or z(p_{4}) < z(p_{2}) < z(p_{1}) < z(p_{3}). In these last two cases, p_{1}, p_{2}, p_{3}, p_{4} is an occurrence of a forbidden pattern of Sym((2143, 1423)|_{2,2,.}) in proj_{xyz}(σ).

• (ii) there is a slice that intersects two slices of the same type. Assume that there is a slice p_{1}, p_{6} of type y that intersect two slices of type x, p_{2}, p_{3} and p_{4}, p_{5}, such that x(p_{1}) < x(p_{2}) < ⋯ < x(p_{6}). Since we have already treated the case of intersections of different directions, we can assume that these three slices share the same direction and, without loss of generality, we can assume that this is the direction (+ + +). This implies that y(p_{3}), y(p_{5}) > 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 3142|_{.,2} in proj_{xy}(σ). Hence σ contains a pattern of Sym(2413|_{2,2}).

• (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}(σ). If σ is not Baxter, proj_{xy}(σ) contains a forbidden pattern Sym(2413|_{2,2}). Otherwise, in proj_{xy}(σ), 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}(σ). Note that the p_{1} may be equal to p_{2}. Since these two slices do not intersect in σ, there must be a third coordinate, say z, such that either z(p_{1}), z(p_{4}) ≤ 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 Sym((312, 213)|_{1,2,.}). Otherwise, the four points form an occurrence of a forbidden pattern in Sym((3412, 1432)|_{2,2,.}).

As all the patterns involved in the previous theorem are of dimension 2 or 3, we get the following corollary:

Corollary 17. A d-permutation is Baxter if and only if all its projections of dimensions 2 or 3 are well-sliced.

4.4 Anti- and complete Baxter d-permutations

In a Baxter permutation σ, each vertical slice intersects exactly one horizontal slice. These intersections are cells (squares of width 1). (See, for instance, Figure 12). Let P′_{σ} be the set of

1 2 3 4 5 6 7 8 9 10 x 2 4 6 8 10 y

Figure 12: 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.

centers of these cells. If we combine P_{σ} and P′_{σ}, we obtain the diagram of a permutation of size 2n + 1 (on a finer grid). These permutations are often called complete Baxter permutations, and were introduced by Baxter and Joichi [8] under the name w-admissible permutations. What we call here Baxter permutations are sometimes called reduced Baxter permutations.

The permutations corresponding to P′_{σ} are called anti-Baxter permutations. These permutations are exactly the ones avoiding 2143|_{2,.} and 3412|_{2,.}, as shown in [2]. As with Baxter patterns, S_{n}(2143|_{2,.}, 3412|_{2,.}) = S_{n}(2143|_{2,2}, 3412|_{2,2}) (see [2, Lemma 3.5] and Figure 13). The enumeration of this class of permutation was given in [2].

1 2 3 4 x 1 2 3 4 y 1 2 3 4 x 1 2 3 4 y

Figure 13: Forbidden patterns in anti-Baxter permutations: 2143|_{2,2} and 3412|_{2,2}.

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.

Proposition 18. Let σ 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 ∈ [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}).

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

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}))).

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})) ≤ min(x_{i}(p_{i}), x_{i}(p′_{i})) and max(x_{i}(p_{j}), x_{i}(p′_{j})) ≥ 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′.

With a Baxter d-permutation σ, for every slice of type 1, we associate the intersecting cell defined by Property 18 (see Figure 14). Let P′_{σ} be the set of centers of intersecting cells. Since every slice of any type contains exactly one intersecting cell, P′_{σ} defines a dpermutation, and we call the d-permutations obtained this way anti-Baxter d-permutations (see Figure 14). Again, this definition coincides with the classical one. If we combine P_{σ} and P′_{σ}, we obtain the diagram of a d-permutation of size 2n + 1 (on a finer grid). We naturally call these d-permutations complete Baxter d-permutations.

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 8.

n\d 2  3  4  5
1  1  1  1  1
2  2  4  8  16
3  6  36 216 1296
4  22 444 7096
5  88 5344
6 374 64460
7 1668

Table 8: Values of |A_{n}^{d−1}| for the first few values of n and d.

x 1 2 3 4 5 6 7 8 y 1 2 3 4 5 6 7 8 z 1 2 3 4 5 6 7 8 x 1 2 3 4 5 6 7 y 1 2 3 4 5 6 7 z 1 2 3 4 5 6 7

Figure 14: On the left, the complete Baxter 3-permutation (14386527, 47513268) with its cell (circle) points. Each cell point corresponds to the triple intersection of slices of the same type (see Figure 9). On the right, the anti-Baxter 3-permutation (1347526, 4631257) associated with the Baxter permutation of Figure 14.

5 Conclusion and perspectives

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: (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 ℝ^{2} [18]. In [19], the authors studied boxed arrangements of axis-parallel segments in ℝ^{3}. Are there some links between Baxter d-permutations boxed arrangements in ℝ^{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: doubly alternating Baxter permutations [22], Baxter involutions [21], semi and strong Baxter permutations [11], as well as twisted Baxter permutations [32]. 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:

          https://plmlab.math.cnrs.fr/bonichon/multipermutation .

We hope that this tool will help the community to investigate the problems above.

6 Acknowledgments

The authors would like to thank Éric 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.

A All symmetries of Baxter patterns

Sym(2413|_{2,2}) = 2413|_{2,2}, 3142|_{2,2}.

Sym((312, 213)|_{1,2,.}) = (312, 213)|_{1,.2,.}, (312, 231)|_{1,.2,.}, (132, 213)|_{1,.1,.}, (132, 231)|_{1,.1,.}, (213, 312)|_{2,.2,.}, (213, 132)|_{2,.2,.}, (231, 312)|_{2,.1,.}, (231, 132)|_{2,.1,.}, (213, 312)|_{1,.,2}, (213, 132)|_{1,.,1}, (231, 312)|_{1,.,2}, (231, 132)|_{1,.,1}, (312, 213)|_{2,.,2}, (312, 231)|_{2,.,1}, (132, 213)|_{2,.,2}, (132, 231)|_{2,.,1}, (213, 132)|_{.,1,2}, (213, 312)|_{.,1,1}, (231, 132)|_{.,2,2}, (231, 312)|_{.,2,1}, (312, 231)|_{.,1,2}, (312, 213)|_{.,1,1}, (132, 231)|_{.,2,2}, (132, 213)|_{.,2,1}.

Sym((3412, 1432)|_{2,2,.}) = (2341, 4123)|_{.,2,2}, (2143, 3214)|_{2,2,.}, (4123, 3214)|_{.,2,2}, (3412, 3214)|_{2,2,.}, (3214, 4123)|_{.,2,2}, (2341, 1432)|_{.,2,2}, (1432, 3214)|_{.,2,2}, (2143, 1432)|_{2,2,.}, (3412, 1432)|_{2,2,.}, (2143, 4123)|_{2,2,.}, (1432, 2143)|_{2,.,2}, (4123, 2341)|_{.,2,2}, (3214, 1432)|_{.,2,2}, (3412, 4123)|_{2,2,.}, (3412, 2341)|_{2,2,.}, (1432, 3412)|_{2,.,2}, (2143, 2341)|_{2,2,.}, (2341, 3412)|_{2,.,2}, (4123, 2143)|_{2,.,2}, (4123, 3412)|_{2,.,2}, (3214, 3412)|_{2,.,2}, (1432, 2341)|_{.,2,2}, (3214, 2143)|_{2,.,2}, (2341, 2143)|_{2,.,2}.

Sym((2143, 1423)|_{2,2,.}) = (3241, 2143)|_{2,.,2}, (3412, 2314)|_{2,2,.}, (1423, 3412)|_{2,.,2}, (2314, 2143)|_{2,.,2}, (1342, 3124)|_{.,2,2}, (3124, 1342)|_{.,2,2}, (1342, 2431)|_{.,2,2}, (3241, 3412)|_{2,.,2}, (4132, 3412)|_{2,.,2}, (2431, 4213)|_{.,2,2}, (2143, 3241)|_{2,2,.}, (4213, 2431)|_{.,2,2}, (3412, 3241)|_{2,2,.}, (3412, 1423)|_{2,2,.}, (4213, 3124)|_{.,2,2}, (2143, 4132)|_{2,2,.}, (3124, 4213)|_{.,2,2}, (2431, 1342)|_{.,2,2}, (2314, 3412)|_{2,.,2}, (2143, 1423)|_{2,2,.}, (1423, 2143)|_{2,.,2}, (4132, 2143)|_{2,.,2}, (2143, 2314)|_{2,2,.}, (3412, 4132)|_{2,2,.}.

B Other patterns

Here we give the beginning of sequences of permutations avoiding some larger patterns or combination of patterns.

Patterns #TWE  Sequence  Comment
1234  1  1, 4, 36, 506, 9032, 181582, 3836372, ⋯  new
1243  2  1, 4, 36, 507, 9089, 185253, 4017231, ⋯  new
1324  1  1, 4, 36, 507, 9087, 185455, 4053668, ⋯  new
1342  4  1, 4, 36, 507, 9102, 185920, 4059355, ⋯  new
1432  2  1, 4, 36, 507, 9119, 188501, 4230523, ⋯  new
2143  1  1, 4, 36, 507, 9121, 187799, 4163067, ⋯  new
2341  2  1, 4, 36, 507, 9105, 187502, 4191192, ⋯  new
2413  2  1, 4, 36, 507, 9141, 189810, 4291658, ⋯  new
2431  4  1, 4, 36, 507, 9124, 188197, 4197349, ⋯  new
3412  1  1, 4, 36, 507, 9135, 190457, 4368455, ⋯  new
3421  2  1, 4, 36, 507, 9133, 190307, 4355801, ⋯  new
4231  1  1, 4, 36, 507, 9119, 189363, 4318292, ⋯  new
4321  1  1, 4, 36, 507, 9147, 192181, 4482267, ⋯  new

Table 9: Patterns of size 4 and dimension 2.

Patterns #TWE  Sequence  Comment
1234, 1243  2  1, 4, 36, 440, 5880, 75968, ⋯  new
1234, 1324  1  1, 4, 36, 440, 5872, 77616, ⋯  new
1234, 1342  4  1, 4, 36, 441, 5692, 68500, ⋯  new
1234, 1432  2  1, 4, 36, 440, 5056, 46446, ⋯  new
1234, 2143  1  1, 4, 36, 440, 5064, 45030, ⋯  new
1234, 2341  2  1, 4, 36, 441, 5730, 68040, ⋯  new
1234, 2413  2  1, 4, 36, 441, 5173, 49501, ⋯  new
1234, 2431  4  1, 4, 36, 441, 5180, 46360, ⋯  new
1234, 3412  1  1, 4, 36, 440, 5096, 44026, ⋯  new
1234, 3421  2  1, 4, 36, 441, 5205, 42991, ⋯  new
1234, 4231  1  1, 4, 36, 440, 5068, 43906, ⋯  new
1234, 4321  1  1, 4, 36, 440, 5168, 34784, ⋯  new
1243, 1324  2  1, 4, 36, 444, 6002, 79964, ⋯  new
1243, 1342  4  1, 4, 36, 444, 6015, 81001, ⋯  new
1243, 1432  2  1, 4, 36, 444, 5817, 73686, ⋯  new
1243, 2134  1  1, 4, 36, 444, 5353, 53256, ⋯  new
1243, 2143  2  1, 4, 36, 444, 6060, 82396, ⋯  new
1243, 2314  4  1, 4, 36, 444, 5647, 65690, ⋯  new

1243, 2341  4  1, 4, 36, 444, 5649, 65566, ⋯  new
1243, 2413  4  1, 4, 36, 444, 5700, 69626, ⋯  new
1243, 2431  4  1, 4, 36, 444, 5679, 66392, ⋯  new
1243, 3214  2  1, 4, 36, 444, 5278, 51226, ⋯  new
1243, 3241  4  1, 4, 36, 444, 5339, 54622, ⋯  new
1243, 3412  2  1, 4, 36, 444, 5336, 54613, ⋯  new
1243, 3421  4  1, 4, 36, 444, 5336, 51612, ⋯  new
1243, 4231  2  1, 4, 36, 444, 5296, 52363, ⋯  new
1243, 4321  2  1, 4, 36, 444, 5324, 47835, ⋯  new
1324, 1342  4  1, 4, 36, 444, 6036, 82584, ⋯  new
1324, 1432  2  1, 4, 36, 444, 5827, 73608, ⋯  new
1324, 2143  1  1, 4, 36, 444, 5650, 65194, ⋯  new
1324, 2341  2  1, 4, 36, 444, 5468, 59406, ⋯  new
1324, 2413  2  1, 4, 36, 444, 5726, 70540, ⋯  new
1324, 2431  4  1, 4, 36, 444, 5710, 68014, ⋯  new
1324, 3412  1  1, 4, 36, 444, 5304, 52359, ⋯  new
1324, 3421  2  1, 4, 36, 444, 5317, 53022, ⋯  new
1324, 4231  1  1, 4, 36, 444, 5276, 52016, ⋯  new
1324, 4321  1  1, 4, 36, 444, 5304, 50792, ⋯  new
1342, 1423  2  1, 4, 36, 442, 5978, 82076, ⋯  new
1342, 1432  4  1, 4, 36, 444, 6056, 84402, ⋯  new
1342, 2143  4  1, 4, 36, 444, 5692, 68333, ⋯  new
1342, 2314  2  1, 4, 36, 444, 5710, 69187, ⋯  new
1342, 2341  4  1, 4, 36, 444, 6080, 84954, ⋯  new
1342, 2413  4  1, 4, 36, 444, 5952, 80102, ⋯  new
1342, 2431  4  1, 4, 36, 444, 5726, 70904, ⋯  new
1342, 3124  2  1, 4, 36, 444, 5507, 62078, ⋯  new
1342, 3142  4  1, 4, 36, 444, 6148, 88944, ⋯  new
1342, 3214  4  1, 4, 36, 444, 5334, 54125, ⋯  new
1342, 3241  4  1, 4, 36, 444, 5733, 70753, ⋯  new
1342, 3412  4  1, 4, 36, 444, 5738, 71301, ⋯  new
1342, 3421  4  1, 4, 36, 444, 5715, 68527, ⋯  new
1342, 4123  4  1, 4, 36, 444, 5483, 60355, ⋯  new
1342, 4132  4  1, 4, 36, 444, 5734, 70864, ⋯  new
1342, 4213  4  1, 4, 36, 444, 5364, 56948, ⋯  new
1342, 4231  4  1, 4, 36, 444, 5706, 68457, ⋯  new
1342, 4312  4  1, 4, 36, 444, 5356, 56450, ⋯  new
1342, 4321  4  1, 4, 36, 444, 5324, 51799, ⋯  new
1432, 2143  2  1, 4, 36, 444, 5931, 77775, ⋯  new

1432, 2341  4  1, 4, 36, 444, 5348, 57776, ⋯  new
1432, 2413  4  1, 4, 36, 444, 5766, 73833, ⋯  new
1432, 2431  4  1, 4, 36, 444, 6126, 87630, ⋯  new
1432, 3214  1  1, 4, 36, 444, 5587, 63160, ⋯  new
1432, 3241  4  1, 4, 36, 444, 5536, 63590, ⋯  new
1432, 3412  2  1, 4, 36, 444, 5444, 63144, ⋯  new
1432, 3421  4  1, 4, 36, 444, 5761, 72105, ⋯  new
1432, 4231  2  1, 4, 36, 444, 5485, 62074, ⋯  new
1432, 4321  2  1, 4, 36, 444, 5981, 79272, ⋯  new
2143, 2341  2  1, 4, 36, 444, 5349, 56637, ⋯  new
2143, 2413  2  1, 4, 36, 444, 6146, 88824, ⋯  new
2143, 2431  4  1, 4, 36, 444, 5730, 70097, ⋯  new
2143, 3412  1  1, 4, 36, 444, 5476, 62504, ⋯  new
2143, 3421  2  1, 4, 36, 443, 5357, 56583, ⋯  new
2143, 4231  1  1, 4, 36, 444, 5322, 53529, ⋯  new
2143, 4321  1  1, 4, 36, 444, 5464, 58437, ⋯  new
2341, 2413  4  1, 4, 36, 444, 5731, 72541, ⋯  new
2341, 2431  4  1, 4, 36, 444, 6122, 87944, ⋯  new
2341, 3412  2  1, 4, 36, 443, 5864, 77512, ⋯  new
2341, 3421  2  1, 4, 36, 444, 5922, 80471, ⋯  new
2341, 4123  1  1, 4, 36, 444, 5441, 56318, ⋯  new
2341, 4132  4  1, 4, 36, 444, 5329, 54619, ⋯  new
2341, 4231  2  1, 4, 36, 444, 5894, 78113, ⋯  new
2341, 4312  2  1, 4, 36, 444, 5342, 56655, ⋯  new
2341, 4321  2  1, 4, 36, 444, 5371, 60374, ⋯  new
2413, 2431  4  1, 4, 36, 444, 6164, 89724, ⋯  new
2413, 3142  1  1, 4, 36, 444, 6252, 94588, ⋯  new
2413, 3241  4  1, 4, 36, 444, 5962, 80566, ⋯  new
2413, 3412  2  1, 4, 36, 444, 6162, 90477, ⋯  new
2413, 3421  4  1, 4, 36, 444, 5746, 72759, ⋯  new
2413, 4231  2  1, 4, 36, 444, 5760, 72775, ⋯  new
2413, 4321  2  1, 4, 36, 443, 5359, 58000, ⋯  new
2431, 3241  2  1, 4, 36, 444, 6137, 88439, ⋯  new
2431, 3412  4  1, 4, 36, 444, 5758, 73920, ⋯  new
2431, 3421  4  1, 4, 36, 444, 6149, 89342, ⋯  new
2431, 4132  2  1, 4, 36, 442, 5662, 70024, ⋯  new
2431, 4213  2  1, 4, 36, 444, 5565, 65925, ⋯  new
2431, 4231  4  1, 4, 36, 444, 6134, 88594, ⋯  new
2431, 4312  4  1, 4, 36, 444, 5754, 73295, ⋯  new

2431, 4321  4  1, 4, 36, 444, 5978, 82140, ⋯  new
3412, 3421  2  1, 4, 36, 444, 6196, 91640, ⋯  new
3412, 4231  1  1, 4, 36, 444, 5726, 72248, ⋯  new
3412, 4321  1  1, 4, 36, 444, 5496, 66138, ⋯  new
3421, 4231  2  1, 4, 36, 444, 6152, 90102, ⋯  new
3421, 4312  1  1, 4, 36, 444, 5655, 70866, ⋯  new
3421, 4321  2  1, 4, 36, 444, 6228, 93468, ⋯  new
4231, 4321  1  1, 4, 36, 444, 6176, 92820, ⋯  new

Table 10: Pairs of patterns of size 4 and dimension 2.

Patterns  #TWE  Sequence  Comment
123, (123, 123)  1  1, 4, 20, 100, 410, 1224, 2232, ⋯  123
123, (123, 132)  6  1, 4, 20, 100, 410, 1224, 2232, ⋯  123
123, (123, 231)  6  1, 4, 20, 100, 410, 1224, 2232, ⋯  123
123, (123, 321)  3  1, 4, 20, 100, 410, 1224, 2232, ⋯  123
123, (132, 213)  6  1, 4, 19, 91, 358, 1005, 1601, ⋯  new
123, (132, 312)  12  1, 4, 19, 79, 231, 407, 354, ⋯  new
123, (231, 312)  2  1, 4, 19, 83, 262, 514, 527, ⋯  new
132, (123, 123)  2  1, 4, 20, 100, 490, 2366, 11334, ⋯  new
132, (123, 132)  6  1, 4, 21, 116, 646, 3596, 19981, ⋯  132
132, (123, 213)  6  1, 4, 20, 102, 518, 2618, 13194, ⋯  new
132, (123, 231)  6  1, 4, 20, 100, 486, 2302, 10690, ⋯  new
132, (123, 312)  6  1, 4, 20, 104, 544, 2846, 14880, ⋯  new
132, (123, 321)  6  1, 4, 20, 99, 477, 2252, 10480, ⋯  new
132, (132, 213)  12  1, 4, 21, 116, 646, 3596, 19981, ⋯  132
132, (132, 312)  12  1, 4, 21, 116, 646, 3596, 19981, ⋯  132
132, (213, 231)  12  1, 4, 20, 100, 488, 2335, 11016, ⋯  new
132, (231, 312)  4  1, 4, 20, 105, 559, 2990, 16021, ⋯  new
231, (123, 123)  2  1, 4, 20, 97, 431, 1758, 6669, ⋯  new
231, (123, 132)  4  1, 4, 20, 104, 544, 2855, 15056, ⋯  new
231, (123, 213)  4  1, 4, 20, 106, 573, 3127, 17173, ⋯  new
231, (123, 231)  4  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (123, 312)  4  1, 4, 20, 105, 564, 3094, 17329, ⋯  new
231, (123, 321)  4  1, 4, 20, 106, 581, 3273, 18851, ⋯  new
231, (132, 123)  4  1, 4, 20, 105, 564, 3092, 17289, ⋯  new
231, (132, 213)  4  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (132, 231)  2  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (132, 312)  4  1, 4, 20, 108, 611, 3575, 21455, ⋯  new

231, (132, 321)  4  1, 4, 20, 108, 607, 3504, 20638, ⋯  new
231, (213, 132)  4  1, 4, 20, 109, 629, 3793, 23669, ⋯  new
231, (213, 231)  4  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (213, 312)  2  1, 4, 20, 111, 654, 4013, 25380, ⋯  new
231, (213, 321)  4  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (231, 123)  4  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (231, 213)  4  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (231, 312)  2  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (312, 132)  4  1, 4, 20, 111, 659, 4102, 26435, ⋯  new
231, (312, 231)  2  1, 4, 21, 123, 767, 4994, 33584, ⋯  231
231, (321, 123)  2  1, 4, 20, 112, 673, 4243, 27696, ⋯  new
321, (123, 123)  1  1, 4, 20, 76, 108, 52, 0, ⋯
321, (123, 132)  6  1, 4, 20, 103, 527, 2714, 14274, ⋯  new
321, (123, 231)  6  1, 4, 20, 110, 644, 3934, 24770, ⋯  new
321, (123, 321)  3  1, 4, 21, 128, 850, 5956, 43235, ⋯  321
321, (132, 213)  6  1, 4, 20, 113, 687, 4389, 29046, ⋯  new
321, (132, 312)  12  1, 4, 21, 128, 850, 5956, 43235, ⋯  321
321, (231, 312)  2  1, 4, 20, 117, 745, 5006, 34873, ⋯  new

Table 11: Pairs of patterns of size 3 respectively of dimension 2 and 3.

Patterns  #TWE  Sequence  Comment
(123, 123), (123, 132) 24 1, 4, 34, 480, 9916, 277730, 10023010, ⋯ new
(123, 123), (123, 231) 24 1, 4, 34, 477, 9681, 262606, 9038034, ⋯  new
(123, 123), (123, 321) 6 1, 4, 34, 472, 9324, 241616, 7793548, ⋯ new
(123, 123), (132, 213) 24 1, 4, 34, 476, 9618, 259274, 8857074, ⋯  new
(123, 123), (132, 312) 48 1, 4, 34, 472, 9321, 241306, 7769550, ⋯  new
(123, 123), (231, 312) 8 1, 4, 34, 472, 9286, 237532, 7466512, ⋯ new
(123, 132), (123, 213) 12 1, 4, 34, 478, 9758, 267578, 9366032, ⋯  new
(123, 132), (123, 231) 12 1, 4, 34, 480, 9916, 277792, 10032960, ⋯ new
(123, 132), (123, 312) 12 1, 4, 34, 476, 9622, 259720, 8895656, ⋯  new
(123, 132), (132, 123) 24 1, 4, 34, 480, 9912, 277304, 9987248, ⋯  new
(123, 132), (132, 213) 48 1, 4, 34, 476, 9617, 259152, 8846076, ⋯  new
(123, 132), (132, 312) 48 1, 4, 34, 474, 9463, 249551, 8249751, ⋯  new
(123, 132), (213, 123) 24 1, 4, 34, 476, 9633, 260990, 9007402, ⋯  new
(123, 132), (213, 132) 48 1, 4, 34, 480, 9900, 275992, 9874628, ⋯  new
(123, 132), (213, 231) 48 1, 4, 34, 475, 9555, 255962, 8679070, ⋯  new
(123, 132), (231, 132) 48 1, 4, 34, 476, 9608, 258290, 8782799, ⋯  new
(123, 132), (231, 213) 24 1, 4, 34, 474, 9462, 249440, 8240370, ⋯  new
(123, 132), (231, 312) 48 1, 4, 34, 474, 9441, 247195, 8060190, ⋯  new
(123, 132), (231, 321) 24 1, 4, 34, 476, 9603, 257690, 8728931, ⋯  new

(123, 132), (321, 132) 24 1, 4, 34, 472, 9332, 242344, 7844248, ⋯  new
(123, 132), (321, 213) 24 1, 4, 34, 472, 9316, 240804, 7731538, ⋯  new
(132, 213), (132, 231) 12 1, 4, 34, 476, 9618, 259364, 8871444, ⋯  new
(132, 213), (213, 132) 4 1, 4, 34, 478, 9730, 264334, 9076864, ⋯ new
(132, 213), (213, 312) 12 1, 4, 34, 474, 9450, 248156, 8137074, ⋯  new

Table 12: Pairs of patterns of size 3 and of dimension 3.

Patterns #TWE  Sequence  Comment
(1234, 1234)  4  1, 4, 36, 575, 14291, 508161, 24385927, ⋯  new
(1234, 1243)  24  1, 4, 36, 575, 14291, 508155, 24384283, ⋯  new
(1234, 1324)  12  1, 4, 36, 575, 14291, 508149, 24382888, ⋯  new
(1234, 1342)  24  1, 4, 36, 575, 14291, 508144, 24381346, ⋯  new
(1234, 1423)  24  1, 4, 36, 575, 14291, 508144, 24381396, ⋯  new
(1234, 1432)  24  1, 4, 36, 575, 14291, 508155, 24384181, ⋯  new
(1234, 2143)  12  1, 4, 36, 575, 14291, 508153, 24383579, ⋯  new
(1234, 2413)  12  1, 4, 36, 575, 14291, 508132, 24378096, ⋯  new
(1243, 1324)  48  1, 4, 36, 575, 14291, 508135, 24379128, ⋯  new
(1243, 1423)  48  1, 4, 36, 575, 14291, 508144, 24381329, ⋯  new
(1243, 2134)  24  1, 4, 36, 575, 14291, 508151, 24383081, ⋯  new
(1243, 2314)  48  1, 4, 36, 575, 14291, 508142, 24380642, ⋯  new
(1243, 2413)  48  1, 4, 36, 575, 14291, 508129, 24377368, ⋯  new
(1324, 1342)  48  1, 4, 36, 575, 14291, 508142, 24380847, ⋯  new
(1324, 2143)  24  1, 4, 36, 575, 14291, 508131, 24377763, ⋯  new
(1342, 1423)  16  1, 4, 36, 575, 14291, 508131, 24378031, ⋯  new
(1342, 2143)  24  1, 4, 36, 575, 14291, 508132, 24378046, ⋯  new
(1342, 2314)  16  1, 4, 36, 575, 14291, 508128, 24377163, ⋯  new
(1342, 2413)  48  1, 4, 36, 575, 14291, 508128, 24377001, ⋯  new
(1342, 2431)  24  1, 4, 36, 575, 14291, 508139, 24379797, ⋯  new
(1432, 2143)  24  1, 4, 36, 575, 14291, 508143, 24380822, ⋯  new

Table 13: Patterns of size 4 and dimension 3.

References

[1] 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, Theoret. Comput. Sci. 349 (2005), 309–317.

[2] Andrei Asinowski, Gill Barequet, Mireille Bousquet-Mélou, Toufik Mansour, and Ron Y Pinter, Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations, Electron. J. Combin. 20 (2013), Paper P35.

[3] Andrei Asinowski and Toufik Mansour, Separable d-permutations and guillotine partitions, Ann. Comb. 14 (2010), 17–43.

[4] Mike D. Atkinson, Stephen A. Linton, and Louise A. Walker, Priority queues and multisets, Electron. J. Combin. 2 (1995), R24.

[5] Mike D. Atkinson and Murali Thiyagarajah, The permutational power of a priority queue, BIT 33 (1993), 1–6.

[6] Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Olivier Guibert, and Matteo Silimbani, Baxter tree-like tableaux, (2021), https://arxiv.org/abs/2108.06212.

[7] Glen Baxter, On fixed points of the composite of commuting functions, Proc. Amer. Math. Soc. 15 (1964), 851–855.

[8] Glen Baxter and J. T. Joichi, On permutations induced by commuting functions, and an embedding question, Math. Scand. 13 (1963), 140–150.

[9] Nicolas Bonichon, Mireille Bousquet-Mélou, and Éric Fusy, Baxter permutations and plane bipolar orientations, Sém. Lothar. Combin. 61 (2010), B61Ah.

[10] Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw, Pattern matching for permutations, Inform. Process. Lett. 65 (1998), 277–283.

[11] Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence, SIAM J. Discrete Math. 32 (2018), 2795–2819.

[12] Sophie Burrill, Julien Courtiel, Éric Fusy, Stephen Melczer, and Marni Mishna, Tableau sequences, open diagrams, and Baxter families, European J. Combin. 58 (2016), 144– 165.

[13] Jean Cardinal, Order and geometry workshop 2016 — problem booklet, http://

orderandgeometry2016.tcs.uj.edu.pl/docs/OG2016-Problem-Booklet.pdf, 2016.

[14] Jean Cardinal, Vera Sacristán, and Rodrigo I. Silveira, A note on flips in diagonal rectangulations, Discrete Math. Theor. Comput. Sci. 20 (2) (2018), 1–22.

[15] Serge Dulucq and Olivier Guibert, Baxter permutations, Discrete Math. 180 (1998), 143–156.

[16] Michael J. Earnest and Samuel C. Gutekunst, Permutation patterns in Latin squares, Aust. J. Combin. 59 (2014), 218–228.

[17] Kimmo Eriksson and Svante Linusson, A combinatorial theory of higher-dimensional permutation arrays, Adv. in Appl. Math. 25 (2000), 194–211.

[18] Stefan Felsner, Éric Fusy, Marc Noy, and David Orden, Bijections for Baxter families and related objects, J. Combin. Theory Ser. A 118 (2011), 993–1020.

[19] Stefan Felsner, Kolja Knauer, and Torsten Ueckerdt, Plattenbauten: touching rectangles in space, In Isolde Adler and Haiko Müller, editors, International Workshop on Graph-Theoretic Concepts in Computer Science, Vol. 12301 of Lect. Notes in Comp. Sci., pp. 161–173. Springer, 2020.

[20] Éric Fusy, Baxter permutations and meanders, https://igm.univ-mlv.fr/~fusy/

Talks/baxter_meanders.pdf, 2012.

[21] Éric Fusy, Bijective counting of involutive Baxter permutations, Fund. Inform. 117 (2012), 179–188.

[22] Olivier Guibert and Svante Linusson, Doubly alternating Baxter permutations are Catalan, Discrete Math. 217 (2000), 157–166.

[23] Benjamin Gunby and Dömötör Pálvölgyi, Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings, European J. Combin. 82 (2019), 102992.

[24] Donald E. Knuth, The Art of Computer Programming, volume 3: Searching and sorting, Addison-Wesley Publishing Company, 1973.

[25] Toufik Mansour, Enumeration and Wilf-classification of permutations avoiding four patterns of length 4, Discrete Math. Lett (2020), 67–94.

[26] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2022. Available

at https://oeis.org/.

[27] Doron Rotem, Stack sortable permutations, Discrete Math. 33 (1981), 185–196.

[28] Ville Salo, Cutting corners, Arxiv preprint https://arxiv.org/abs/2002.08730, 2020.

[29] Louis Shapiro and A. Brooke Stephens, Bootstrap percolation, the Schröder numbers, and the n-kings problem, SIAM J. Discrete Math. 4 (1991), 275–280.

[30] Rodica Simion and Frank W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

[31] John R. Stembridge, On the fully commutative elements of Coxeter groups, J. Algebraic Combin. 5 (1996), 353–385.

[32] Julian West and Olivier Guibert, Enumeration of Reading’s twisted Baxter permutations, In The Fourth Annual International Conference on Permutation Patterns. Reykjavik University, Reykjavik, 2006.

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A19, 05A10, 15A69.

Keywords: Baxter permutation, multipermutation, Schröder number, separable permutation.

(Concerned with sequences \underline{A000108}, \underline{A000272}, \underline{A001003}, \underline{A001181}, \underline{A001764}, \underline{A001787}, \underline{A003946}, \underline{A006318}, \underline{A007767}, \underline{A026150}, \underline{A026671}, \underline{A047732}, \underline{A071684}, \underline{A071688}, \underline{A072863}, \underline{A086810}, \underline{A090181}, \underline{A103211}, \underline{A107841}, \underline{A131763}, \underline{A131765}, \underline{A133308}, \underline{A190291}, \underline{A217216}, \underline{A281593}, \underline{A295928} and \underline{A356197} .)