Pattern matching in
(213, 231)-avoiding permutations

arXiv:1511.01770v1 [cs.DS] 5 Nov 2015

Both Emerite Neou⋆1 Romeo Rizzi2 and Stéphane Vialette1
1

Université Paris-Est, LIGM (UMR 8049), CNRS, UPEM, ESIEE Paris, ENPC,
F-77454, Marne-la-Valle, France
{neou,vialette}@univ-mlv.fr
2
Department of Computer Science, Universit degli Studi di Verona, Italy
romeo.rizzi@univr.it

Abstract. Given permutations σ ∈ Sk and π ∈ Sn with k < n, the
pattern matching problem is to decide whether π matches σ as an orderisomorphic subsequence. We give a linear-time algorithm in case both π
and σ avoid the two size-3 permutations 213 and 231. For the special case
where only σ avoids 213 and 231, we present a O(max(kn2 , n2 log(log(n)))
time algorithm. We extend our research to bivincular patterns that avoid
213 and 231 and present a O(kn4 ) time algorithm. Finally we look at the
related problem of the longest subsequence which avoids 213 and 231.

1

Introduction

A permutation π is said to match another permutation σ, in symbols σ  π, if
there exists a subsequence of elements of π that has the same relative order as
σ. Otherwise, π is said to avoid the permutation σ. For example a permutation
matches the pattern 123 (resp. 321) if it has an increasing (resp. decreasing)
subsequence of length 3. As another example, 6152347 matches 213 but not
231. During the last decade, the study of the pattern matching on permutations
has become a very active area of research [14] and a whole annual conference
(Permutation Patterns) is now devoted to this topic.
We consider here the so-called pattern matching problem (also sometimes
referred to as the pattern involvement problem): Given two permutations σ and
π, this problem is to decide whether σ  π (the problem is ascribed to Wilf
in [5]). The permutation matching problem is known to be NP-hard [5]. It is,
however, polynomial-time solvable by brute-force enumeration if σ has bounded
size. Improvements to this algorithm were presented in [2] and [1], the latter
describing a O(|π|0.47|σ|+o(|σ|) ) time algorithm. Bruner and Lackner [7] gave a
fixed-parameter algorithm solving the pattern matching problem with an exponential worst-case runtime of O(1.79run(π) ), where run(π) denotes the number of
alternating runs of π. (This is an improvement upon the O(2|π| ) runtime required
by brute-force search without imposing restrictions on σ and π.) A recent major
⋆

On a Co-tutelle Agreement with the Department of Mathematics of the University
of Trento

step was taken by Marx and Guillemot [11]. They showed that the permutation
matching problem is fixed-parameter tractable (FPT) for parameter |σ|.
A few particular cases of the pattern matching problem have been attacked
successfully. The case of increasing patterns is solvable in O(|π| log log |σ|) time
in the RAM model [8], improving the previous 30-year bound of O(|π| log |σ|).
Furthermore, the patterns 132, 213, 231, 312 can all be handled in linear-time by
stack sorting algorithms. Any pattern of length 4 can be detected in O(|π| log |π|)
time [2]. Algorithmic issues for 321-avoiding patterns matching has been investigated in [12]. The pattern matching problem is also solvable in polynomial-time
for separable patterns [13, 5] (see also [6] for LCS-like issues of separable permutations). Separable permutations are those permutations that match neither
2413 nor 3142, and they are enumerated by the Schröder numbers (Notice that
the separable permutations include as a special case the stack-sortable permutations, which avoid the pattern 231.)
There exists many generalisation of patterns that are worth considering in
the context of algorithmic issues in pattern matching (see [14] for an up-to-date
survey). Vincular patterns, also called generalized patterns, resemble (classical)
patterns with the additional constraint that some of the elements in a matching must be consecutive in postitions. Of particular importance in our context,
Bruner and Lackner [7] proved that deciding whether a vincular pattern σ of
length k can be match to a longer permutation π is W [1]-complete for parameter
k; for an up to date survey of the W [1] class and related material, see [9]. Bivincular patterns generalize classical patterns even further than vincular patterns
by adding a constraint on values.
We focus in this paper on pattern matching issues for (213, 231)-avoiding
permutations (i.e., those permutations that avoid both 213 and 231). The number of n-permutations that avoid both 213 and 231 is t0 = 1 for n = 0 and
tn = 2n−1 for n ≥ 1 [16]. On an individual basis, the permutations that do
not match the permutation pattern 231 are exactly the stack-sortable permutations and they are counted by the Catalan numbers [15]. A stack-sortable
permutation is a permutation whose elements may be sorted by an algorithm
whose internal storage is limited to a single stack data structure. As for 213,
it is well-known that if π = π1 π . . . πn avoids 132, then its complement π ′ =
(n + 1 − π1 )(n + 1 − π2 ) . . . (n + 1 − πn ) avoids 312, and the reverse of π ′ avoids
213. This paper is organized as follows. In Section 2 the needed definitions are
presented. Section 3 is devoted to presenting an online linear-time algorithm in
case both permutations are (213, 231)-avoiding, whereas Section 4 focuses on
the case where only the pattern is (213, 231)-avoiding. In Section 5 we give a
polynomial-time algorithm for (213, 231)-avoiding bivincular patterns. In Section 6 we consider the problem of finding the longest (213, 231)-avoiding pattern
in permutations.

2

Definitions

A permutation of length n is a one-to-one function from an n-element set to itself.
We write permutations as words π = π1 π2 . . . πn , whose elements are distinct
and usually consist of the integers 12 . . . n, and we let π[i] stands for πi . For the
sake of convenience, we let π[i : j] stand for πi πi+1 . . . πj , π[: j] stand for π[1 : j]
and π[i :] stand for π[i : n]. As usual, we let Sn denote the set of all permutations
of length n. It is convenient to use a geometric representation of permutation to
ease the understanding of algorithms. The geometric representation corresponds
to the set of point with coordinate (i, π[i]) (see figure 1).
A permutation π is said to match the permutation σ if there exists a subsequence of (not necessarily consecutive) element of π that has the same relative
order as σ, and in this case π is said to match σ, written σ  π. Otherwise, π is
said to avoid the permutation σ. For example, the permutation π = 391867452
matches the pattern σ = 51342, as can be seen in the highlighted subsequence
of π = 391867452 (or π = 391867452 or π = 391867452 or π = 391867452
). Each subsequence 91674, 91675, 91672, 91452, in π is called a matching of
σ. Since the permutation π = 391867452 contains no increasing subsequence of
length four, π avoids 1234. Geometrically, π matches σ if there exists a set of
point in π that is isomorph to the set of point of σ. In other word, if there exists
a set of point in π with the same disposition as the set of point of σ, without
regard to the distance (see figure 1).

Fig. 1: The pattern σ = 51342 and four matchings of σ in 391867452.

Suppose P is a set of permutations. We let Avn (P ) denote the set of all
n-permutations avoiding each permutation in P . For the sake of convenience
(and as it is customary [14]), we omit P ’s braces thus having e.g. Avn (213, 231)
instead of Avn ({213, 231}). If π ∈ Avn (P ), we also say that π is P -avoiding.
An ascent of a permutation π ∈ Sn is any element 1 ≤ i < n where the
following value is bigger than the current one. That is, if π = π1 π2 . . . πn , then
πi is an ascent if πi < πi+1 . For example, the permutation 3452167 has ascents
3, 4, 1 and 6. Similarly, a descent is any element 1 ≤ i < n with πi > πi+1 , so
for every 1 ≤ i < n, πi is either an ascent or is a descent of π.
A left to right maxima (abbreviate LRMax) of π is a element that does not
have any element bigger than it on its right (see fig. 2). Formally, π[i] is a
LRMax if and only if π[i] is the biggest element of π[i :]. Similarly π[i :] is a

left to right minima (abbreviate LRMin) if and only if π[i] is the smallest element
of π[i :].

Fig. 2: The element is a LRMax if and only if the dashed area is empty.
A bivincular pattern σ of length k is a permutation in Sk written in two-line
notation (that is the top row is 12 . . . k and the bottom row is a permutation
σ1 σ2 . . . σk ). We have the following conditions on the top and bottom rows of
σ, as see in [14] in definition 1.4.1:
– If the bottom line of σ contains σi σi+1 . . . σj then the elements corresponding to σi σi+1 . . . σj in a matching of σ in π must be adjacent, whereas there
is no adjacency condition for non-underlined consecutive elements. Moreover
if the bottom row of σ begins with x σ1 then any matching of σ in a permutation π must begin with the leftmost element of π, and if the bottom row
of σ begins with σk y then any matching of σ in a permutation π must end
with the rightmost element of π.
– If the top line of σ contains i i + 1 . . . j then the elements corresponding to
i, i + 1, . . . , j in an matching of σ in π must be adjacent in values, whereas
there is no value adjacency restriction for non-overlined elements. Moreover,
if the top row of σ begins with p 1 then any matching of σ is a permutation
π must contain the smallest element of π, and if top row of σ ends with k q
then any matching of σ is a permutation π must contain the largest element
of π.
1234q
. In 3217845, 3217845 is a matching of σ but
For example, let σ = x2143
3217845 is not. The best general reference is [14].
Geometrically, We represent underlined and overlined elements by forbidden
areas. A vertical area between two points indicates that the two matching of
those points must be consecutive in positions, whereas a horizontal area between
two points indicates that the two matching of those points must be consecutive
in value. The forbidden areas can be understand as follow : in a matching, the
forbidden areas must be empty. Thus, π matches a bivincular pattern σ if there
exists a set of point in π that is isomorph to σ and if the forbidden areas are
empty. (see figure 3).

3

Both π and σ are (213, 231)-avoiding

This section is devoted to presenting a fast algorithm for deciding if σ  π in
case both π and σ are (213, 231)-avoiding. We begin with an easy but crucial
structure lemma.

1234q
Fig. 3: From left to right, the bivincular pattern σ = x2143
, A matching of σ in
3216745, A matching of 2143 in 3216745 but not a matching of σ in 3216745
because the point (1, 3) and (5, 7) are in the forbidden area.

Lemma 1 (Folklore). The first element of any (213, 231)-avoiding permutation must be either the minimal or the maximal element.
Proof (of Lemma 1). Any other initial element would serve as a ‘2’ in either a
231 or 213 with 1 and n as the ‘1’ and ‘3’ respectively.
⊓
⊔
Corollary 1. π ∈ Avn (213, 231) if and only if for 1 ≤ i < n, π[i] is a LRMax
or a LRMin.
Corollary 2. Let π ∈ Avn (213, 231) and 1 ≤ i < n. Then, (1) π[i] is an ascent
element if and only if π[i] is a LRMin and (2) π[i] is a descent element if and
only if π[i] is a LRMax
Lemma 2 gives a bijection between Avn (213, 231) and the set of binary word
of size n − 1. The bijected word w of π, is the word where each letter at position
i represents if π[i] is an ascent or descent element (or is a LRMax or a LRMin).
We call this bijection B.
A (213, 231)-avoiding permutation has a particular form. If we take only
the descent elements, the points draw a north-east to south-west line and if
we take only the ascent elements, the points draw a south-east to north-west
line. This shape the permutation as a >. For convenience when drawing a random (213, 231)-avoiding permutation we will sometime represent a sequence of
ascent/descent element by lines (see figure 4 and 5).
The following lemma is central to our algorithm.
Lemma 2. Let π and σ be two (213, 231)-avoiding permutations, Then, π matches
σ if and only if there exists a subsequence t of π such B(t) = B(σ).
Proof (of Lemma 2). The forward direction is obvious. We prove the backward
direction by induction on the size of the pattern σ. The base case is a pattern
of size 2. Suppose that σ = 12 and thus B(σ) = ascent. Let t = πi1 πi2 , i1 < i2 ,
be a subsequence of π such that B(t) = ascent, this reduces to saying that
πi1 < πi2 , and hence that t is a matching of σ = 12 in π. A similar argument

Fig. 4: The (213, 231)-avoiding permutation 123984765, every point which is on a
north-east to south-west line represents a descent element and every point which
is on a south-east to north-west line represents an ascent element.

shows that the lemma holds true for σ = 21. Now, assume that the lemma is
true for all patterns up to size k ≥ 2. Let σ ∈ Avk+1 (231, 213) and let t, be a
subsequence of π of length k + 1 such that B(t) = B(σ). As B(t)[2 :] = B(σ)[2 :]
by the inductive hypothesis, it follows that t[2 :] is a matching of σ[2 :]. Moreover
B(t)[1] = B(σ)[1] thus t[1] and σ[1] are both either the minimal or the maximal
element of their respective subsequences. Therefore, t is a matching of σ in π. ⊓
⊔
We are now ready to solve the pattern matching problem in case both π and
σ are (213, 231)-avoiding.
Proposition 1. Let π and σ be two (213, 231)-avoiding permutations. One can
decide whether π matches σ in linear time.
Proof. According to Lemma 1 the problem reduces to deciding whether sσ occurs
as a subsequence in sπ . A straightforward greedy approach solves this issue in
linear-time.
⊓
⊔
Thank to Corollary 2, we can compute the bijected words in the same time
that we running the greedy algorithm, this gives us a on-line algorithm.

4

σ only is (213, 231)-avoiding

This section focuses on the pattern matching problem in case only the pattern σ
avoids 231 and 213. We need to consider a specific decomposition of σ into factor
: we split the permutation into largest sequences of ascent element and descent
element, respectively called an ascent factor and a descent factor. This correspond to split the permutation between every pair of ascent-descent element and
descent-ascent element (see figure 5). For the special case of (213, 231)-avoiding,
this correspond to split the permutation into largest sequence of consecutive
element. We will label the factors from right to left.
We introduce the notation LMEi(s) : Suppose that s is a subsequence of S,
LMEi(s) is the index of the left most element of s in S. Thus for every factor,
LMEi(factor(j)) stand for the index in σ of the leftmost element of factor(j).
For example, σ = 123984765 is split as 123 − 98 − 4 − 765. Hence σ = factor(4)

Fig. 5: The left figure is the (213, 231)-avoiding permutation 123984765. Every
line represents a factor, every circled point represents the left most element of
each factor. The central figure is a generalisation of (213, 231)-avoiding permutation. The right figure represents a matching of 1276534 in 312598746, the blue
rectangles represent the matching, the red dotted rectangles represent the matching after the first replacement and the green rectangle represents the matching
after the second replacement.

factor(3) factor(2) factor(1) with factor(4) = 123, factor(3) = 98, factor(2) = 4
and factor(1) = 765. Furthermore, LMEi(factor(4)) = 1, LMEi(factor(3)) = 4,
LMEi(factor(2)) = 6 and LMEi(factor(1)) = 7. We represent elements matching
an ascent (resp. descent) factor by a rectangle which has the left most matched
point of the factor as the left bottom (resp. top) corner and the right most
matched point of the factor as the right top (resp. bottom) corner. We can
remove the two right most rectangles and replace it by the smallest rectangle
that contains both of them and repeat this operation to represent part of a
matching (see figure ??).
Remark 1. A factor is either an increasing or a decreasing sequence of element.
Thus while matching a factor, it is enough to find an increasing or a decreasing
subsequence of same size or bigger than the factor.
Corollary 3. Given a permutation σ ∈ Av(213, 231) and a suffix of its decomposition factor(i) factor(i − 1) . . . factor(1), if factor(i) is an ascent (respectively
descent) factor then the maximal (resp. minimal) element of factor(i) factor(i−1)
. . . factor(1) is the left most element of factor(i − 1)
This is a corollary of lemma 1. This states that given a permutation in
Av(213, 231) if the permutation starts with ascent (respectively descent) elements then the maximal (resp. minimal) element of this permutation is the first
descent (resp. ascent) element (see figure 6).
We now define the set Sπσ (i, j) as the set of every subsequence s of π[j :] that
starts at π[j] and that is a matching of factor(i) factor(i − 1) . . . factor(1) and .
Lemma 3. Let σ be a permutation, factor(i) be an ascent (respectively descent)
factor, s be a subsequence of π such that s ∈ Sπσ (i, j) and that minimizes (resp.
maximizes) the match of the left most element of factor(i − 1). For all subsequences s′ ∈ Sπσ (i, j) and for all subsequences t of π, such that t = t′ s′ , if t is a

Maximal y-coordinate

Minimal y-coordinate
Suffix starting at factor(i)

Fig. 6: The maximal element of the suffix starting at factor(i) (represented by the
blue line) is the left most element of factor(i − 1) (represented by the the black
dot). LMπσ (i, j) is the minimal value of the matching of the maximal element
(the black dot) in all the matchings of the suffix starting at LMEi(factor(i)) (the
blue dot) in π[j :].

matching of σ[LMEi(factor(i+1)) :] such that the left most element of factor(i) is
matched to π[j] then the subsequence t′ s is a matching of σ[LMEi(factor(i+1)) :]
such that the left most element of factor(i) is matched to π[j].
This lemma states that given any matching of factor(i + 1) factor(i) . . .
factor(1), where factor(i) is an ascent (resp. descent) factor, we can replace the
part of the match that match factor(i) . . . factor(1) by any match that minimise
(resp. maximise) the left most element of factor(i − 1). Indeed the left most
element of factor(i − 1) is the maximal (resp. minimal) element of factor(i) . . .
factor(1) (see figure 7).
Proof (of Lemma 3). By definition s is a matching of σ[LMEi(factor(i)) :]. To
prove that ts is an matching of σ[LMEi(factor(i + 1)) :] we need to prove that
every element of t is larger than every element of s. If ts′ is a matching of
σ[LMEi(factor(i + 1)) :] then every element of t is larger than every element of
s′ . Moreover the maximal element of s is smaller than the maximal element of
s′ so every element of s is smaller than every element of s′ thus every element
of s is smaller than every element of t. We use a similar argument if factor(i) is
a descent factor.
⊓
⊔
Corollary 4. Let σ be a permutation, factor(i) be an ascent (respectively descent) factor and s be a subsequence of π such that s ∈ Sπσ (i, j) and that minimizes (resp. maximizes) the match of the left most element of factor(i − 1).
These following statements are equivalent :
– There exists a matching of σ in π with the left most element of factor(i) is
matched to π[j].
– There exists a matching t of σ[: LMEi(factor(i)) − 1] in π[: j − 1] such that
ts is a matching of σ in π with the left most element of factor(i) matched to
π[j].

Fig. 7: In a matching, we can replace the green area by the red dashed area.

This corollary takes a step further from the previous one, it states that if
there is no matching using any match that maximise (resp. minimise) the left
most element of factor(i − 1) then there does not exist any matching at all.
This is central to the algorithm because it allows to test only the matching that
maximise (resp. minimise) the left most element of factor(i − 1) (see figure 7).
Proposition 2. Let σ ∈ Avk (213, 231) and π ∈ Sn .
One can decide in O(max(kn2 , n2 log(log(n))) time and O(kn2 ) space if π matches
σ.
Proof. We first introduce a set of values needed to our proof. Let LISπ (i, j, bound)
(resp. LDSπ (i, j, bound)) be the longest increasing (resp. decreasing) sequence
in π[i : j] starting at i, with every element of this sequence smaller (resp. bigger)
than bound. LISπ and LDSπ can be computed in O(n2 log(log(n))) time (see
[3]). As stated before, those values allow us to find a matching of a factor.
Now consider the following set of values (see figure 8) :


The match of LMEi(factor(i − 1))
If factor(i) is




in
a
matching
of
σ[LMEi(factor(i))
:]
in
π[j
:]
an
ascent factor





and that minimizes the match





LMEi(factor(i − 1))





and
starts with π[j]




Or ∞ if no such matching exists

LMπσ (i, j) =



The match of LMEi(factor(i − 1))
If factor(i) is





in a matching of σ[LMEi(factor(i)) :] in π[j :] a descent factor





and
that maximizes the match




 LMEi(factor(i − 1))




and starts with π[j]




Or ∞ if no such matching exists
Clearly there exists a matching of σ in π if and only if there exists a 1 ≤ i ≤ n
such that LM (nf actors , i) 6= 0 and LM (nf actors , i) 6= ∞ with nf actors the number
of factor in σ. We show how to compute recursively those values.

LMπσ (i, j)

LMπσ (i − 1, j ′ + 1)

j

j′
j′ + 1

Fig. 8: When looking for a matching of σ[LMEi(factor(i)) :] (red and blue areas)
starting at π[j :], (1) the red area is a matching of factor(i) ie. if and only if
its contains an increasing subsequence of size equal or bigger than | factor(i)|.
(2) the red and blue areas have to be ”compatible” (their x-coordinates and
y-coordinates have to be disjoint and the red area has to be before the blue
area in the x-coordinate and y-coordinate). AFπσ (i, j) is the set of every top ycoordinate of every blue area which is compatible. LMπσ (i, j) is the minimal value
of AFπσ (i, j) if he set is not void.
BASE :

LMπσ (1, j) =



minj<j ′ {∞} ∪ {π[j ′ ]| j ′ such that



′
′


 | factor(1)| ≤ LIS(j, j , π[j ] + 1)}




maxj<j ′ {0} ∪ {π[j ′ ]| j ′ such that



 | factor(1)| ≤ LDS(j, j ′ , π[j ′ ] − 1)}

If factor(i) is
an ascent factor
If factor(i) is
a descent factor

In the base case, one is looking for a matching of the first factor.

STEP :
LMπσ (i, j)

=

(

min{∞} ∪ AFπσ (i, j) If factor(i) is an ascent factor
max{0} ∪ DFπσ (i, j) If factor(i) is a descent factor

where AFπσ (i, j) and DFπσ (i, j) are the sets of elements matching the left most
element of factor(i − 1) in a match of σ[LMEi(factor(i)) :] starting at π[j :].
Suppose that factor(i) is an ascent (resp descent) factor, index j ′ and matching
t exists if and only if π[j : j ′ ] contains a matching of factor(i) ”compatibles”
with a matching in π[j ′ + 1 :] of σ[LMEi(factor(i − 1)) :]. It is enough to assure
that every element of the matching of factor(i) are smaller (resp. bigger) than
the element of the matching of σ[LMEi(factor(i − 1)) :].

Thus we can compute AFπσ (i, j) and DFπσ (i, j) as follows:
AFπσ (i, j) = {π[j ′ + 1] | j < j ′ < n and LMπσ (i − 1, j ′ + 1) 6= 0 and
| factor(i)| ≤ LISπ (j, j ′ , LMπσ (i − 1, j ′ + 1))}
DFπσ (i, j) = {π[j ′ + 1] | j < j ′ < n and LMπσ (i − 1, j ′ + 1) 6= ∞ and
| factor(i)| ≤ LDSπ (j, j ′ , LMπσ (i − 1, j ′ + 1))}
The number of factor is bound by k. Every instance of LISπ and LDSπ can
be computed in O(n2 log(log(n)). There are n base cases that can be computed
O(n) time, thus computing every base cases takes O(n2 ) time. There are kn
different instance of AF and each one of them take O(n) time to compute,
thus computing every instance of AF takes O(kn2 ) time. There are kn different
instance of LM and each one of them take O(n), because the size of an AF is
bounded by n, thus computing every LM takes O(kn2 ) time. Thus computing
all the values takes O(max(kn2 , n2 log(log(n))). Every value takes O(1) space,
thus the whole problem takes O(kn2 ) space.
⊓
⊔

5

(213, 231)-avoiding bivincular patterns

This section is devoted to the pattern matching problem with (213, 231)-avoiding
bivincular pattern. Recall that a bivincular pattern generalises a permutation
pattern by being able to force elements to be consecutive in value or in position.
Hence, bivincular pattern is stronger in constraint than permutation pattern,
intuitively we can not use the previous algorithm. As in a (213, 231)-avoiding
permutation, we can describe structural property of a (213, 231)-avoiding bivincular pattern.
Lemma 4. Given σ a (213, 231)-avoiding bivincular pattern, If σ[i]σ[j] (this
implies that σ[j] = σ[i] + 1) and if σ[i] is an ascent (resp. decent) element and
σ[i] + 1 is an ascent (resp. decent) element then :
– i < j (resp. j > i)
– For every l, i < l < j (resp. j > l > i), π[l] is a descent (resp. ascent)
element.
This lemma states that if two ascent (resp. decsent) elements need to be
matched to consecutive elements in value then every element between those two
elements (if any) is a descent (resp. ascent) element.
Proof (of Lemma 4). Suppose that there exists l, i < l < j, such that σ[l] is
ascent. Ascent elements are increasing so σ[i] < σ[l] < σ[j] which is in contradiction with σ[j] = σ[i] + 1. We use a similar argument if σ[i] is a descent
element
⊓
⊔
Proposition 3. Let σ be a (213, 231)-avoiding bivincular of length k and π ∈
Sn . One can decide in O(kn4 ) time and O(kn3 ) space if π matches σ.

ub
σ[i′ ](σ[i′ ] + 1)

ub
σ[i′ ](σ[i′ ] + 1)
σ[i]σ[i + 1]

σ[i − 1]σ[i]

π[l]

π[l′ ]
σ[i]σ[i + 1]

lb = π[l] + 1

(σ[i] − 1)σ[i]
lb

Fig. 9: When matching an ascent element, the value of ub does not change, and
the lb is equal to the last match plus one. Note that there is only ascent element
before σ[i′ ]

Proof. We consider the following set of boolean : Given σ a (213, 231)-avoiding
bivincular pattern, and a text π ∈ Avn (231, 213),

true If π[j :] matches σ[i :]




with every element of the matching is in [lb, ub]
PMπ,lb,ub
(i, j) =
σ

and starting π[j]



f alse otherwise
The argument lb (respectively ub) stands for the match of the last ascent
(resp. decsent) element matched plus (resp. minus) one. We now show how to
compute recursively those boolean (see fig. 9).
BASE:

true












if π[j] ∈ [lb, ub]
and if σ[k]y then j = n
q
and if σ[k] then π[j] = ub = k
PMπ,lb,ub
(k, j) =
and if p σ[k] then π[j] = lb = 1
σ



and if (σ[k] − 1)σ[k] then π[j] = lb





and
if (σ[k]σ[k] − 1) then π[j] = ub



f alse otherwise

The base case finds an matching for the rightmost element of the pattern.
If the last element does not have any restriction on positions and on values,
then PMπ,lb,ub
(k, j) is true if and only if σ[k] is matched π[j]. Which is true if
σ
π[j] ∈ [lb, ub]. If σ[k]y then σ[k] must be matched to the right most element of π
q
thus j must be the n. If σ[k] then σ[k] must be matched to the largest element
which is k. If p σ[k] then σ[k] must be matched to the smallest element which
is 1. If (σ[k] − 1)σ[k] then the matched element of σ[k] and σ[k] − 1 must be
consecutive in value, by recursion the value of the matched element of σ[k] − 1
will be recorded in lb and by adding 1 to it thus σ[k] must be matched to lb. If

(σ[k]σ[k] − 1) then the matched element of σ[k] and σ[k]− 1 must be consecutive
in value, by recursion the value of the matched element of σ[k]−1 will be recorded
in ub and by removing 1 to it thus σ[k] must be matched to ub.
STEP:
We need to consider 3 cases for the problem PMπ,lb,ub
(i, j) :
σ

– If π[j] ∈
/ [lb, ub] then :
PMπ,lb,ub
(i, j) = f alse
σ
which is immediate from the definition. If π[j] ∈
/ [lb, ub] then it can not be
part of a matching of σ[i :] in π[i :] with every matched element in [lb, ub].
– If π[j] ∈ [lb, ub] and σ[i] is an ascent element then :
S
π,π[j]+1,ub
(i + 1, l)

j<l PMσ






S

π,π[j]+1,ub

(i + 1, l)

j<l PMσ










π,lb,ub
(i, j) = PMσπ,π[j]+1,ub (i + 1, j + 1)
PMσ












PMσπ,π[j]+1,ub (i + 1, j + 1)








f alse

if σ[i] is not underlined
and σ[i] is not overlined
if σ[i] is not underlined
and (σ[i] − 1)σ[i] or p σ[i]
and π[j] = lb
if σ[i]σ[i + 1]
and (σ[i] − 1)σ[i] or p σ[i]
and π[j] = lb
if σ[i]σ[i + 1]
and σ[i] is not overlined
otherwise

Remark that π[j] can be matched to σ[i] because π[j] ∈ [lb, ub]. Thus if
π[j + 1 :] matches σ[i + 1 :] with every element of the matching in [σ[i] +
1, ub] then π[j :] matches σ[i :]. The last condition correspond to know if
there exists l, j < l such that PMσπ,π[j]+1,ub (i + 1, l) is true. The first case
correspond to a matching without restriction on position and on value. The
second case asks for the match of σ[i] − 1 and σ[i] to be consecutive in value,
but the match of σ[i] − 1 is lb − 1 thus we want π[j] = lb. The fourth case
asks for the match of σ[i] and σ[i + 1] to be consecutive in index, thus the
match of σ[i + 1] must be j + 1. The third case is an union of the second
and fourth case. Note that if π[j] is an ascent element we can not have the
condition that the match of σ[i] and σ[i] + 1 have to consecutive in value.
– If π[j] ∈ [lb, ub] and σ[i] is a descent element then :

S
π,lb,π[j]−1
(i + 1, l)

j<l PMσ






S


π,lb,π[j]−1

(i + 1, l)

j<l PMσ










π,lb,ub
PMσ
(i, j) = PMπ,lb,π[j]−1
(i + 1, j + 1)
σ













PMπ,lb,π[j]−1
(i + 1, j + 1)

σ







f alse

if σ[i] is not underlined
and σ[i] is not overlined
if σ[i] is not underlined
q
and σ[i](σ[i] + 1) or σ[i]
and π[j] = ub
if σ[i]σ[i + 1]
q
and σ[i](σ[i] + 1) or σ[i]
and π[j] = ub
if σ[i]σ[i + 1]
and σ[i] is not overlined
otherwise

The same remark as the last case holds.
S
Clearly if 0<j PMσπ,1,n (1, j) is true then π matches σ. We now discuss the
position and value constraints.
Position Constraint. There are 3 types of position constraints that can be added
by underlined elements.
– If x σ[1] then the leftmost element of σ must be matched to the leftmost
element of π (σ[1] is matched to π[1] on a matching of σ in π). This constraint
is satisfied by requiring that the matching starts at the left most element of
π : if PMσπ,1,n (1, 1) is true.
– If σ[k]y then the rightmost element σ must be matched the rightmost element
of π (σ[k] is matched to π[n] on a matching of σ in π). This constraint is
checked in the base case.
– If σ[i]σ[i + 1] then the index of the matched elements of σ[i] and σ[i+1] must
be consecutive. In other word, if σ[i] is matched to π[j] then σ[i + 1] must
be matched to π[j + 1]. We assure this restriction by recursion by requiring
that the matching of σ[i + 1 :] to start at index j + 1 (see figure 9).
Value Constraint. There are 3 types of position constraints that can be added
by overlined elements.
– If p σ[i] (and thus σ[i] = 1) then the minimal value of σ must be matched to
the minimal value of π.
• If σ[i] is an ascent element, then remark that every problem PMπ,lb,∗
(i, ∗)
σ
is true if σ[i] is matched to element with value lb (by recursion) thus it
is enough to require that lb = 1. Now remark that σ[i] is the leftmost
ascent element, indeed if not, then there exists an ascent element σ[i′ ],
i′ < i and by definition σ[i′ ] < σ[i] which is not possible as σ[i] must
be the minimal element. As a consequence σ[1], . . ., σ[i − 1] are descent

elements. Moreover the recursive call from a descent element does not
modified the lower bound thus for every PMπ,lb,∗
(i, ∗), lb = 1 (see figure
σ
9).
• If σ[i] is a descent element then i = k (σ[i] is the right most element).
Thus every PMπ,∗,∗
(i, ∗) is a base case and is true if σ[i] is matched to
σ
1.
q
– If σ[i] (and thus σ[i] = k) then the maximal value of σ must be matched to
the maximal value of π.
• If σ[i] is an descent element, then remark that every recursive call
PMπ,∗,ub
(i, ∗) is true if σ[i] is matched to element with value ub (by
σ
recursion) thus it is enough to require that ub = nπ . Now remark that
σ[i] is the leftmost descent element, indeed if not, then there exists an
descent element σ[i′ ], i′ < i and by definition σ[i′ ] > σ[i] which is not
possible as σ[i] must be the maximal element. As a consequence σ[1], . . .,
σ[i − 1] are ascent elements. Moreover the recursive call from a ascent
element does not modified the upper bound thus for every PMπ,∗,ub
(i, ∗),
σ
ub = n (see figure 9.
• If σ[i] is an ascent element then σ[i] then i = k (σ[i] is the right most
element). Thus every PMπ,∗,∗
(i, ∗) is a base case and is true if σ[i] is
σ
matched to nπ .
– If σ[i]σ[i′ ], (which implies that σ[i′ ] = σ[i] + 1) then if σ[i] is matched to π[j]
then σ[i′ ] must be matched to π[j] + 1.
• The case σ[i] is a descent element, σ[i′ ] is an ascent element and i < i′
(remark that this case is equivalent to the case σ[i] is an ascent element,
σ[i′ ] is a descent element and i′ < i) is not possible. Indeed σ[i] is the
maximal element of σ[i :] thus σ[i] > σ[i′ ] which is in contradiction with
σ[i′ ] = σ[i] + 1.
• If σ[i] is an ascent element, σ[i′ ] is a descent element and i < i′ (remark
that this case is symmetric to the case σ[i] is a descent element, σ[i′ ]
is an ascent element and i′ < i), then remark that every recursive call
PMπ,lb,∗
(i′ , ∗) is true if σ[i′ ] is matched to the element with lb (by reσ
cursion) thus it is enough to require that lb = π[j] + 1. Now remark that
σ[i] is the right most ascent element and σ[i′ ] is the right most element
(or σ[i′ ] 6= σ[i] + 1). As a consequence σ[i + 1], σ[i + 2], . . ., σ[i′ − 1]
are descent elements. Moreover the recursive call from a descent element
(i, ∗) will put the lower
does not modified the lower bound and PMπ,lb,∗
σ
bound to π[j] + 1 thus for every PMπ,lb,∗
(i′ , ∗), lb = π[j] + 1 (see figure
σ
9.
• If σ[i] is an ascent element and σ[i′ ] is an ascent element then first
remark that every recursive call PMπ,∗,ub
(i′ , ∗) is true if σ[i′ ] is matched
σ
to element with value lb. Now remark that
i < i′ and there is no ascent element between σ[i] and σ[i′ ] (lemma 4),
As a consequence σ[i + 1], σ[i + 2], . . ., σ[i′ − 1] are descent elements.
Moreover the recursive call from a descent element does not modified
the lower bound and PMπ,lb,∗
(i, ∗) will put the lower bound to π[j] + 1
σ
′
thus for every PMπ,lb,∗
(i
,
∗),
lb
= π[j] + 1 (see figure 9.
σ

There are n3 base cases that can be computed in constant time. There are kn3
different cases. Each case takes up to O(n) time to compute. Thus computing
all the cases take O(kn4 ) time. Each case take O(1) space, thus we need O(kn3 )
space.
⊓
⊔

6

Computing the longest (213, 231)-avoiding pattern

This section is focused on a problem related to the pattern matching problem,
finding the longest (213, 231)-avoiding subsequences in permutations: Given a
set of permutations, find a longest (213, 231)-avoiding that can be matched by
each input permutation. This problem is know to be NP-Hard for an arbitrary
number of permutations and we do not hope it to be solvable in polynomial
time even with the constraint of the subsequence must avoid (213, 231). Thus
we focus on the cases where only one or two permutations are given in input.
We start with the easiest case where we are given just one input permutation.
We need the set of descent elements and the set of ascent elements. A(π) =
{i|π[i] is an ascent element}∪{n} and D(π) = {i|π[i] is a descent element∪{n}.
Proposition 4. If s is a longest (213, 231)-avoiding subsequence with last element at index f in π then A(π) is a longest increasing subsequence with last
element at index f and D(π) is a longest decreasing subsequence with last element at index f .
Proof (of Proposition 4). Let s be a longest subsequence avoiding (213,231)
with last element at index f in π, suppose that P (s) is not a longest increasing
subsequence with last element at index f . Let sm be a longest increasing subsequence with last element f . Thus |sm | > |A(s)|, clearly the sequence sm ∪ D(s)
is (213, 231)-avoiding and is longer than s, this is a contradiction. The same idea
can be used to show that D(π) is the longest decreasing subsequence.
⊓
⊔
Proposition 5. Let π be a permutation. One can compute the longest (213, 231)avoiding subsequence that can be matched in π in O(n log(log(n))) time and in
O(n) space.
Proof (of Proposition 5). The proposition 4 lead to an algorithm where one has
to compute longest increasing and decreasing subsequence ending at every index.
Then finding the maximal sum of longest increasing and decreasing subsequence
ending at the same index. Computing the longest increasing subsequence and
the longest decreasing subsequence can be done in O(n log(log(n))) time and
O(n) space (see [3]), then finding the maximal can be done in linear time.
⊓
⊔
We now consider the case where the input is composed of two permutations.
Proposition 6. Given two permutations π1 and π2 , one can compute the longest
common (213, 231)-avoiding subsequence in O(|π1 |3 |π2 |3 ) time and space.

Proof. Consider the following problem that computes the longest stripe common
2 ,ub2
to π1 and π2 : Given two permutations π1 and π2 , we define LCSππ21 ,lb
,lb1 ,ub1 (i1 , i2 )
= max {|s| | s can be matched π1 [i1 :] with every element of the match in
[lb1 , ub1 ] and s can be matched π2 [i2 :] with every element of the match in
[lb2 , ub2 ] }
We show how to solve this problem by dynamic programming.
BASE:


1 if lb1 ≤ π1 [j] ≤ ub1
2 ,ub2
(|π
|,
|π
|)
=
LCSππ21 ,lb
and lb2 ≤ π2 [j] ≤ ub2
1
2
,lb1 ,ub1


0 otherwise
STEP:


2 ,ub2

LCSππ21 ,lb

,lb1 ,ub1 (i1 , i2 + 1)





π2 ,lb2 ,ub2
2 ,ub2
LCSπ1 ,lb1 ,ub1 (i1 , i2 ) = max LCSππ21 ,lb
,lb1 ,ub1 (i1 + 1, i2 )






Mπ2 ,lb2 ,ub2 (i , i )
π1 ,lb1 ,ub1

with

1

2


π ,π [i ]+1,ub

1 + LCSπ21 ,π21 [i21 ]+1,ub21 (i1 , i2 + 1) π1 [i1 ] < lb1





and π2 [i2 ] < lb2






π ,lb ,π [i ]−1
2 ,ub2
(i
,
i
)
=
Mππ21 ,lb
1 + LCSπ21 ,lb21 ,π21 [i21 ]−1 (i1 + 1, i2 ) π1 [i1 ] > ub1
,lb1 ,ub1 1 2




and π2 [i2 ] > ub2








0
otherwise
For every pair i, j we either ignore the element of π1 , or we ignore the element
of π2 , or we match as the same step (if possible). These relations lead to a
O(|π1 |3 |π2 |3 ) time and O(|π1 |3 |π2 |3 ) space algorithm. Indeed there is |π1 |3 |π2 |3
cases possible for the problem and each case is solved in constant time. ⊓
⊔

References
1. S. Ahal and Y. Rabinovich. On complexity of the subpattern problem. SIAM
Journal on Discrete Mathematics, 22(2):629–649, 2008.
2. M.H. Albert, R.E.L. Aldred, M.D. Atkinson, and D.A. Holton. Algorithms for
pattern involvement in permutations. In Proc. International Symposium on Algorithms and Computation (ISAAC), volume 2223 of Lecture Notes in Computer
Science, pages 355–366, 2001.
3. Sergei Bespamyatnikh and Michael Segal. Enumerating longest increasing subsequences and patience sorting, 2000.
4. M. Bóna. Surprising symmetries in objects counted by catalan numbers. The
Electronic Journal of Combinatorics, 19(1):P62, 2012.

5. P. Bose, J.F.Buss, and A. Lubiw. Pattern matching for permutations. Information
Processing Letters, 65(5):277–283, 1998.
6. M. Bouvel, D. Rossin, and S. Vialette. Longest common separable pattern between
permutations. In B. Ma and K. Zhang, editors, Proc. Symposium on Combinatorial
Pattern Matching (CPM’07), London, Ontario, Canada, volume 4580 of Lecture
Notes in Computer Science, pages 316–327, 2007.
7. Marie-Louise Bruner and Martin Lackner. A fast algorithm for permutation pattern matching based on alternating runs. CoRR, abs/1204.5224, 2012.
8. M. Crochemore and E. Porat. Fast computation of a longest increasing subsequence
and application. Information and Compututation, 208(9):1054–1059, 2010.
9. R.G. Downey and M. Fellows. Fundamentals of Parameterized Complexity. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 2013.
10. W. Griffiths, R. Smith, and D.Warren. Almost avoiding pairs of permutations.
Pure Mathematics and Applications, 22(2):129–139, 2011.
11. S. Guillemot and D. Marx. Finding small patterns in permutations in linear time.
In C. Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland, Oregon, USA, pages 82–101.
SIAM, 2014.
12. S. Guillemot and S. Vialette. Pattern matching for 321-avoiding permutations. In
Y. Dong, D.-Z. Du, and O. Ibarra, editors, Proc. 20-th International Symposium
on Algorithms and Computation (ISAAC), Hawaii, USA, volume 5878 of LNCS,
page 10641073. Springer, 2009.
13. L. Ibarra. Finding pattern matchings for permutations. Information Processing
Letters, 61(6):293–295, 1997.
14. S. Kitaev. Patterns in Permutations and Words. Springer-Verlag, 2013.
15. Donald E. Knuth. The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms. Addison Wesley Longman Publishing Co., Inc., Redwood
City, CA, USA, 1997.
16. R. Simion and F.W.Schmidt. Restricted permutations. European Journal of Combinatorics, 6(4):383406, 1985.

