Unshuffling Permutations

arXiv:1601.05962v2 [] 3 Mar 2016

Samuele Giraudo and Stéphane Vialette
Université Paris-Est, LIGM (UMR 8049), CNRS, UPEM, ESIEE Paris, ENPC,
F-77454, Marne-la-Vallée, France
samuele.giraudo@univ-mlv.fr
vialette@univ-mlv.fr

Abstract. A permutation is said to be a square if it can be obtained by
shuffling two order-isomorphic patterns. The definition is intended to be
the natural counterpart to the ordinary shuffle of words and languages.
In this paper, we tackle the problem of recognizing square permutations
from both the point of view of algebra and algorithms. On the one hand,
we present some algebraic and combinatorial properties of the shuffle
product of permutations. We follow an unusual line consisting in defining the shuffle of permutations by means of an unshuffling operator,
known as a coproduct. This strategy allows to obtain easy proofs for algebraic and combinatorial properties of our shuffle product. We besides
exhibit a bijection between square (213, 231)-avoiding permutations and
square binary words. On the other hand, by using a pattern avoidance
criterion on oriented perfect matchings, we prove that recognizing square
permutations is NP-complete.

1

Introduction



The shuffle product, denoted , is a well-known operation on words first defined
by Eilenberg and Mac Lane [6]. Given three words u, v1 , and v2 , u is said to be a
shuffle of v1 and v2 if it can be formed by interleaving the letters from v1 and v2
in a way that maintains the left-to-right ordering of the letters from each word.
Besides purely combinatorial questions, the shuffle product of words naturally
leads to the following computational problems:
1.
2.
3.
4.

Given
Given
Given
Given


 

two words v1 and v2 , compute the set v1 v2 .
three words u, v1 , and v2 , decide if u is a shuffle of v1 and v2 .
words u, v1 , . . . , vk , decide if u is in v1 · · · vk .
a word u, decide if there is a word v such that u is in v v.



Even if these problems seem similar, they radically differ in terms of time complexity. Let us now review some facts about these. In what follows, n denotes
the size of u and mi denotes
the size of each
vi . A solution to Problem 1


m1 +m2
time [14]. An improvement and
can be computed in O (m1 + m2 )
m1
a generalization of Problem 1 has been proposed in [1], where it is proved that
given words v1 , . . . , vk , the iterated shuffle v1 · · · vk can be computed in

 

2



k
O mm1 1+···+m
time. Problem 2 is in P; it is indeed a classical textbook exer,...,mk
cise to design an efficient
 dynamic programming algorithm solving it. It can be
tested in O n2 / log(n) time [15]. To the best of our knowledge, the first O(n2 )
time algorithm for this problem appeared in [9]. This algorithm can easily be
extended to check in polynomial-time whether or not a word is in the shuffle of
any fixed number of given words. Nevertheless, Problem 3 is NP-complete [9,17].
This remains true even if the ground alphabet has size 3 [17]. Of particular interest, it is shown in [17] that Problem 3 remains NP-complete even if all the
words vi , i ∈ [k], are identical, thereby proving that, for two words u and v, it
is NP-complete to decide whether or not u is in the iterated shuffle of v. Again,
this remains true even if the ground alphabet has size 3. Let us now finally focus
on Problem 4. It is shown in [3,11] that it is NP-complete to decide if a word
u is a square (w.r.t. the shuffle), that is a word u with the property that there
exists a word v such that u is a shuffle of v with itself. Hence, Problem 4 is
NP-complete.



This paper is intended to study a natural generalization of , denoted by •,
as a shuffle of permutations. Roughly speaking, given three permutations π, σ1 ,
and σ2 , π is said to be a shuffle of σ1 and σ2 if π (viewed as a word) is a shuffle
of two words that are order-isomorphic to σ1 and σ2 . This shuffle product was
first introduced by Vargas [16] under the name of supershuffle. Our intention
in this paper is to study this shuffle product of permutations • both from a
combinatorial and from a computational point of view by focusing on square
permutations, that are permutations π being in the shuffle of a permutation σ
with itself. Many other shuffle products on permutations appear in the literature.
For instance, in [5], the authors define the convolution product and the shifted
shuffle product. For this last product, π is a shuffle of σ1 and σ2 if π is in the
shuffle, as words, of σ1 and the word obtained by incrementing all the letters of
σ2 by the size of σ1 . It is a simple exercise to prove that, given three permutations
π, σ1 , and σ2 , deciding if π is in the shifted shuffle of σ1 and σ2 is in P.
This paper is organized as follows. In Section 3 we provide a precise definition
of •. This definition passes through the preliminary definition of an operator ∆,
allowing to unshuffle permutations. This operator is in fact a coproduct, endowing the linear span of all permutations with a coalgebra structure (see [8]
or [7] for the definition of these algebraic structures). By duality, the unshuffling operator ∆ leads to the definition of our shuffle operation on permutations.
This approach has many advantages. First, some combinatorial properties of •
depend on properties of ∆ and are more easy to prove on the coproduct side.
Second, this way of doing allows to obtain a clear description of the multiplicities
of the elements appearing in the shuffle of two permutations, which are worthy
of interest from a combinatorial point of view. Section 4 is devoted to showing that the problems related to the shuffle of words has links with the shuffle
of permutations. In particular, we show that binary words that are square are
in one-to-one correspondence with square permutations avoiding some patterns
(Proposition 1). Next, Section 5 presents some algebraic and combinatorial properties of •. We show that • is associative and commutative (Proposition 2), and

3

that if a permutation is a square, its mirror, complement, and inverse are also
squares (Proposition 3). Finally, Section 6 presents the most important result of
this paper: the fact that deciding if a permutation is a square is NP-complete
(Proposition 4). This result is obtained by exhibiting a reduction from the pattern involvement problem [2] which is NP-complete.

2

Notations

If S is a finite set, the cardinality of S is denoted by |S|, and if P and Q are two
disjoint sets, P ⊔ Q denotes the disjoint union of P and Q. For any nonnegative
integer n, [n] is the set {1, . . . , n}.
We follow the usual terminology on words [4]. Let us recall here the most
important ones. Let u be a word. The length of u is denoted by |u|. The empty
word, the only word of null length, is denoted by ǫ. We denote by u
e the mirror
image of u, that is the word u|u| u|u|−1 . . . u1 . If P is a subset of [|u|], u|P is
the subword of u consisting in the letters of u at the positions specified by
the elements of P . If u is a word of integers and k is an integer, we denote
by u[k] the word obtained by incrementing by k all letters of u. The shuffle of
two words u and v is the set recursively defined by u ǫ = {u} = ǫ u and
ua vb = (u vb)a ∪ (ua v)b, were a and b are letters. A word u is a square
if there exists a word v such that u belongs to v v.
We denote by Sn the set of permutations of size n and by S the set of all
permutations. In this paper, permutations of a size n are specified by words of
length n on the alphabet [n] and without multiple occurrence of a letter, so
that all above definitions about words remain valid on permutations. The only
difference lies on the fact that we shall denote by π(i) (instead of πi ) the i-th
letter of any permutation π. For any nonnegative integer n, we write րn (resp.
ցn ) for the permutation 12 . . . n (resp. n (n − 1) . . . 1). If π is a permutation
of Sn , we denote by π̄ the complement of π, that is the permutation satisfying
π̄(i) = n − π(i) + 1 for all i ∈ [n]. The inverse of π is denoted by π −1 .
If u is a word of integers without multiple occurrences of a same letter, s(u) is
the standardized of u, that is the unique permutation of the same size as u such
that for all i, j ∈ [|u|], ui < uj if and only if s(u)(i) < s(u)(j). In particular, the
image of the map s is the set S of all permutations. Two words u and v having
the same standardized are order-isomorphic. If σ is a permutation, there is an
occurrence of (the pattern) σ in π if there is a set P of indexes of letters of π such
that σ and π|P are order-isomorphic. When π does not admit any occurrence of
σ, π avoids σ. The set of permutations of size n avoiding σ is denoted by Sn (σ).
Let us now provide some definitions about graphs and oriented perfect matchings that are used in the sequel. If G is an oriented graph without loops, two
different edges of G are independent if they do not share any common vertex. We
say that G is an oriented matching if all edges of G are pairwise independent.
Moreover, G is perfect if any vertex of G belongs to at least one arc. For any
permutation π of Sn , an oriented perfect matching on π is an oriented perfect
matching M on the set of vertices [n]. In the sequel, we shall consider a natural













4

notion of pattern avoidance in oriented perfect matchings on permutations. For
instance, an oriented perfect matching M on a permutation π admits an occurif there are four positions i < j < k < ℓ in π such
rence of the pattern
that (π(k), π(i)) and (π(j), π(ℓ)) are arcs of M. When M does not admit any
occurrence of a pattern P, we say that M avoids P. The definition naturally
extends to sets of patterns: M avoids P = {Pi : 1 ≤ i ≤ k} if it avoids every
pattern Pi .

3

Shuffle product on permutations

The purpose of this section is to define a shuffle product • on permutations.
Recall that a first definition of this product was provided by Vargas [16]. To
present an alternative definition of this product adapted to our study, we shall
first define a coproduct denoted by ∆, enabling to unshuffle permutations. By
duality, ∆ implies the definition of •. The reason why we need to pass by the
definition of ∆ to define • is justified by the fact that a lot of properties of •
depend of properties of ∆, and that this strategy allows to write concise and clear
proofs of them. We invite the reader unfamiliar with the concepts of coproduct
and duality to consult [8] or [7].
Let us denote by Q[S] the linear span of all permutations. We define a linear
coproduct ∆ on Q[S] in the following way. For any permutation π, we set
X


s π|P1 ⊗ s π|P2 .
(1)
∆(π) =
P1 ⊔P2 =[|π|]

We call ∆ the unshuffling coproduct of permutations. For instance,
∆(213) = ǫ ⊗ 213 + 2 · 1 ⊗ 12 + 1 ⊗ 21 + 2 · 12 ⊗ 1 + 21 ⊗ 1 + 213 ⊗ ǫ,

(2)

∆(1234) = ǫ ⊗ 1234 + 4 · 1 ⊗ 123 + 6 · 12 ⊗ 12 + 4 · 123 ⊗ 1 + 1234 ⊗ ǫ,

(3)

∆(1432) = ǫ ⊗ 1432 + 3 · 1 ⊗ 132 + 1 ⊗ 321 + 3 · 12 ⊗ 21
+ 3 · 21 ⊗ 12 + 3 · 132 ⊗ 1 + 321 ⊗ 1 + 1432 ⊗ ǫ.

(4)

Observe that the coefficient of the tensor 1 ⊗ 132 is 3 in (4) because there are
exactly three ways to extract from the permutation 1432 two disjoint subwords
respectively order-isomorphic to the permutations 1 and 132.
As announced, let us now use ∆ to define a shuffle product on permutations.
As any coproduct, ∆ leads to the definition of a product obtained by duality in
the following way. From (1), for any permutation π, we have
X
∆(π) =
λπσ,ν σ ⊗ ν,
(5)
σ,ν∈S

where the λπσ,ν are nonnegative integers. Now, by definition of duality, the dual
product of ∆, denoted by •, is a linear binary product on Q[S]. It satisfies, for
any permutations σ and ν,
X
σ•ν =
λπσ,ν π,
(6)
π∈S

5

where the coefficients λπσ,ν are the ones of (5). We call • the shuffle product of
permutations. For instance,
12 • 21 = 1243 + 1324 + 2 · 1342 + 2 · 1423 + 3 · 1432 + 2134 + 2 · 2314
+ 3 · 2341 + 2413 + 2 · 2431 + 2 · 3124 + 3142 + 3 · 3214 + 2 · 3241 (7)
+ 3421 + 3 · 4123 + 2 · 4132 + 2 · 4213 + 4231 + 4312.
Observe that the coefficient 3 of the permutation 1432 in (7) comes from the
fact that the coefficient of the tensor 12 ⊗ 21 is 3 in (4).
Intuitively, this product shuffles the values and the positions of the letters
of the permutations. One can observe that the empty permutation ǫ is a unit
for • and that this product is graded by the sizes of the permutations (i.e., the
product of a permutation of size n with a permutation of size m produces a sum
of permutations of size n + m).
We say that a permutation π appears in the shuffle σ • ν of two permutations
σ and ν if the coefficient λπσ,ν defined above is different from zero. In a more
combinatorial way, this is equivalent to say that there are two sets P1 and P2 of
disjoints indexes of letters of π satisfying P1 ⊔ P2 = [|π|] such that the subword
π|P1 is order-isomorphic to σ and the subword π|P2 is order-isomorphic to ν.
A permutation π is a square if there is a permutation σ such that π appears
in σ • σ. In this case, we say that σ is a square root of π. Equivalently, π is a
square with σ as square root if and only if in the expansion of ∆(π), there is
a tensor σ ⊗ σ with a nonzero coefficient. In a more combinatorial way, this
is equivalent to saying that there are two sets P1 and P2 of disjoints indexes
of letters of π satisfying P1 ⊔ P2 = [|π|] such that the subwords π|P1 and π|P2
are order-isomorphic. Computer experiments give us the first numbers of square
permutations with respects to their size, which are, from size 0 to 10,
1, 0, 2, 0, 20, 0, 504, 0, 21032, 0, 1293418.

(8)

This sequence (and its subsequence obtained by removing the 0’s) is for the time
being not listed in [13]. The square permutations of sizes 0 to 4 are
Size 0
ǫ

4

Size 2

Size 4
1234, 1243, 1423, 1324, 1342, 4132, 3124, 3142, 3412, 4312,
12, 21
2134, 2143, 2413, 4213, 2314, 2431, 4231, 3241, 3421, 4321

Binary square words and permutations

In this section, we shall show that the square binary words are in one-to-one
correspondence with square permutations avoiding some patterns. This property establishes a link between the shuffle of binary words and our shuffle of
permutations and allows to obtain a new description of square binary words.
Let u be a binary word of length n with k occurrences of 0. We denote by
btp (Binary word To Permutation) the map sending any such word u to the
permutation obtained by replacing from left to right each occurrence of 0 in u

6

by 1, 2, . . . , k, and from right to left each occurrence of 1 in u by k + 1, k + 2,
. . . , n. For instance,
btp(100101101000) = C12B3A948567,

(9)

where A, B, and C respectively stand for 10, 11, and 12. Observe that for any
nonempty permutation π in the image of btp, there is exactly one binary word
u such that btp(u0) = btp(u1) = π. In support of this observation, when π has
an even size, we denote by ptb(π) (Permutation To Binary word) the word ua
such that |ua|0 and |ua|1 are both even, where a ∈ {0, 1}.
Proposition 1. For any n ≥ 0, the map btp restricted to the set of square
binary words of length 2n is a bijection between this last set and the set of square
permutations of size 2n avoiding the patterns 213 and 231.
Proof (of Proposition 1). The statement of the proposition is a consequence of
the following claims implying that ptb is the inverse map of btp over the set of
square binary words.
Claim 1. The image of btp is the set of all permutations avoiding 213 and 231.
Proof (of Claim 1). Let us first show that the image of btp contains only permutations avoiding 213 and 231. Let u be a binary word, π = btp(u), and P0
(resp. P1 ) be the set of the positions of the occurrences of 0 (resp. 1) in u. By
definition of btp, from left to right, the subword v = π|P0 is increasing and the
subword w = π|P1 is decreasing, and all letters of w are greater than those of v.
Now, assume that π admits an occurrence of 213. Then, since v is increasing
and w is decreasing, there is an occurrence of 3 (resp. 13, 23) in v and a relative occurrence of 21 (resp. 2, 1). All these three cases contradict the fact that
all letters of w are greater than those of v. A similar argument shows that π
avoids 231 as well.
Finally, observe that any permutation π avoiding 213 and 231 necessarily
starts by the smallest possible letter or the greatest possible letter. This property
is then true for the suffix of π obtained by deleting its first letter, and so on for
all of its suffixes. Thus, by replacing each letter a of π by 0 (resp. 1) if a has the
role of a smallest (resp. greatest) letter, one obtains a binary word u such that
btp(u) = π. Hence, all permutations avoiding 213 and 231 are in the image of
btp.
⊓
⊔
Claim 2. If u is a square binary word, btp(u) is a square permutation.
Proof (of Claim 2). Since u is a square binary word, there is a binary word v
v. Then, there are two disjoint sets P and Q of positions
such that u ∈ v
of letters of u such that u|P = v = u|Q . Now, by definition of btp, the words
btp(u)|P and btp(u)|Q have the same standardized σ. Hence, and by definition
of the shuffle product of permutations, btp(u) appears in σ • σ, showing that
btp(u) is a square permutation.
⊓
⊔



7

Claim 3. If π is a square permutation avoiding 213 and 231, ptb(π) is a square
binary word.
Proof (of Claim 3). Let π be a square permutation avoiding 213 and 231. By
Claim 1, π is in the image of btp and hence, u = ptb(π) is a well-defined binary
word. Since π is a square permutation, there are two disjoint sets P1 and P2 of
indexes of letters of π such that π|P1 and π|P2 are order-isomorphic. This implies,
by the definitions of btp and ptb, that u|P1 = u|P2 , showing that u is a square
binary word.
⊓
⊔
⊓
⊔
The number of square binary words is Sequence A191755 of [13] beginning
by
1, 0, 2, 0, 6, 0, 22, 0, 82, 0, 320, 0, 1268, 0, 5102, 0, 020632.

(10)

According to Proposition 1, this is also the sequence enumerating square permutations avoiding 213 and 231.

5

Algebraic issues

The aim of this section is to establish some of properties of the shuffle product
of permutations •. It is worth to note that, as we will see, algebraic properties
of the unshuffling coproduct ∆ of permutations defined in Section 3 lead to
combinatorial properties of •.
Proposition 2. The shuffle product • of permutations is associative and commutative.
Proof (of Proposition 2). To prove the associativity of •, it is convenient to show
that its dual coproduct ∆ is coassociative, that is
(∆ ⊗ I)∆ = (I ⊗ ∆)∆,

(11)

where I denotes the identity map. This strategy relies on the fact that a product
is associative if and only if its dual coproduct is coassociative. For any permutation π, we have
X


s π|P1 ⊗ s π|P2
(∆ ⊗ I)∆(π) = (∆ ⊗ I)
=

X

P1 ⊔P2 =[|π|]

∆ s π|P1

P1 ⊔P2 =[|π|]

=

X

X



P1 ⊔P2 =[|π|] Q1 ⊔Q2 =[|P1 |]

=

X

P1 ⊔P2 ⊔P3 =[|π|]

⊗ I s π|P2






 
 
s s π|P1 |Q ⊗ s s π|P1 |Q ⊗ s π|P2
1

2




s π|P1 ⊗ s π|P2 ⊗ s π|P3 .
(12)

8

An analogous computation shows that (I ⊗ ∆)∆(π) is equal to the last member
of (12), whence the associativity of •.
Finally, to prove the commutativity of •, we shall show that ∆ is cocommutative, that is for any permutation π, if in the expansion of ∆(π) there is
a tensor σ ⊗ ν with a coefficient λ, there is in the same expansion the tensor
ν ⊗ σ with the same coefficient λ. Clearly, a product is commutative if and
only if its dual coproduct is cocommutative. Now, from the definition (1) of
∆, one observes that
 (P1 , P2 ) of subsets of [|π|] contributes to the
 if the pair
coefficient of s π|P1 ⊗ s π|P2 , the pair (P2 , P1 ) contributes to the coefficient
of s π|P2 ⊗ s π|P1 . This shows that ∆ is cocommutative and hence, that • is
commutative.
⊓
⊔
Proposition 2 implies that Q[S] endowed with the unshuffling coproduct ∆
is a coassociative cocommutative coalgebra, or in an equivalent way, that Q[S]
endowed with the shuffle product • is an associative commutative algebra.
Lemma 1. The three linear maps
φ1 , φ2 , φ3 : Q[S] → Q[S]

(13)

linearly sending a permutation π to, respectively, π
e, π̄, and π −1 are endomorphims of associative algebras.
We now use the algebraic properties of • exhibited by Lemma 1 to obtain
combinatorial properties of square permutations.
Proposition 3. Let π be a square permutation and σ be a square root of π.
Then,
(i) the permutation π
e is a square and σ
e is one of its square roots;
(ii) the permutation π̄ is a square and σ̄ is one of its square roots;
(iii) the permutation π −1 is a square and σ −1 is one of its square roots.
Proof (of Proposition 3). All statements (i), (ii), and (iii) are consequences of
Lemma 1. Indeed, since π is a square permutation and σ is a square root of π, by
definition, π appears in the product σ • σ. Now, by Lemma 1, for any j = 1, 2, 3,
since φj is a morphism of associative algebras from Q[S] to Q[S], φj commutes
with the shuffle product of permutations •. Hence, in particular, one has
φj (σ • σ) = φj (σ) • φj (σ).

(14)

Then, since π appears in σ • σ, φj (π) appears in φj (σ • σ) and appears also in
φj (σ) • φj (σ). This shows that φj (σ) is a square root of φj (π) and implies (i),
(ii), and (iii).
⊓
⊔
Let us make an observation about Wilf-equivalence classes of permutations
restrained on square permutations. Recall that two permutations σ and ν of
the same size are Wilf equivalent if #Sn (σ) = #Sn (ν) for all n ≥ 0. The wellknown [12] fact that there is a single Wilf-equivalence class of permutations of

9

size 3 together with Proposition 3 imply that 123 and 321 are in the same Wilfequivalence class of square permutations, and that 132, 213, 231, and 312 are in
the same Wilf-equivalence class of square permutations. Computer experiments
show us that there are two Wilf-equivalence classes of square permutations of
size 3. Indeed, the number of square permutations avoiding 123 begins by
1, 0, 2, 0, 12, 0, 118, 0, 1218, 0, 14272,

(15)

while the number of square permutations avoiding 132 begins by
1, 0, 2, 0, 11, 0, 84, 0, 743, 0, 7108.

(16)

Besides, an other consequence of Proposition 3 is that its makes sense to
enumerate the sets of square permutations quotiented by the operations of mirror
image, complement, and inverse. The sequence enumerating these sets begins by
1, 0, 1, 0, 6, 0, 81, 0, 2774, 0, 162945.

(17)

All Sequences (15), (16), and (17) (and their subsequences obtained by removing the 0s) are for the time being not listed in [13].

6

Algorithmic issues

This section is devoted to proving hardness of recognizing square permutations.
In the same way as happens with words, we shall use a linear graph framework
where deciding whether a permutation is a square reduces to computing some
specific matching in the associated linear graph [3,11]. We have, however, to
deal with oriented perfect matchings. The needed properties read as follows (see
Fig. 1).

1

8

3

9

2

7

B

5

C

6

A

4

Fig. 1. An oriented perfect matching M on the permutation π = 183927B5C6A4
satisfying the properties P1 and P2 . From M, it follows that π is a square as it
appears in the shuffle of 1892A4 and 37B5C6, both being order-isomorphic to 145263.

Definition 1 (Property P1 ). Let π be a permutation. An oriented perfect
matching M on π is said to have property P1 if it avoids all the six patterns
,
,
,
,
, and
.

10

a

σ1

a′

b

a′

σ2

b′

σ1

b′

a′

a

σ2

b

(a) An increasing pattern before
and above a decreasing pattern.

a

σ1

σ2

b

b′

a

a′

σ1

σ2

b

b′

(b) A decreasing pattern before and
below an increasing pattern.

Fig. 2. Illustration of Lemma 3.

Definition 2 (Property P2 ). Let π be a permutation. An oriented perfect
matching M on π is said to have property P2 if, for any two distinct arcs
(π(a), π(a′ )) and (π(b), π(b′ )) in M, we have π(a) < π(b) if and only if π(a′ ) <
π(b′ ).
The rationale for introducing properties P1 and P2 stems from the following
lemma.
Lemma 2. Let π be a permutation. The following statements are equivalent:
1. The permutation π is a square.
2. There exists an oriented perfect matching M on π satisfying P1 and P2 .
Let π be a permutation. For the sake of clarity, we will say that a bunch
of consecutive positions P of π is above (resp. below ) above another bunch of
consecutive positions P ′ in π if π(i) > π(j) (resp. π(i) < π(j)) for every i ∈ P
and every j ∈ P ′ . For example, σ1 is above σ2 (in an equivalent manner, σ2 is
below σ1 ) in Fig. 2(a), whereas σ1 is below σ2 (in an equivalent manner, σ2 is
above σ1 ) in Fig. 2(b).
Before proving hardness, we give an easy lemma that will prove extremely
useful for simplifying the proof of upcoming Proposition 4.
Lemma 3. Let π = π1 σ1 π2 σ2 π3 be a permutation with |σ1 | ≥ 2 and |σ2 | ≥ 2,
and M be an oriented perfect matching on π satisfying P1 and P2 . The following
assertions hold:
1. If σ1 is increasing, σ2 is decreasing, and σ1 is above σ2 (see Fig. 2(a)),
then there is at most one arc between σ1 and σ2 in M (this arc can be a
(σ1 , σ2 )-arc or a (σ2 , σ1 )-arc).

11

ν1′

N1
N1

ν1
ν3′

N3
ν3

N3

ν4

N4
k+2

σ′

n+2

π′

n

π ′′
σ ′′

k
ν4′

N4
ν2

N2

ν2′

N2
N1

N2

N1

N3

k+2

N4

N2

N3

n+2

N4

n

k

Fig. 3. Schematic representation of the permutation µ used in Proposition 4. Black
arcs denote the presence of at least one arc between two bunches of positions in µ.
Grey arcs denote edges that are only considered in the forward direction of the proof.

2. If σ1 is decreasing, σ2 is increasing, and σ1 is below σ2 (see Fig. 2(b)),
then there is at most one arc between σ1 and σ2 in M (this arc can be a
(σ1 , σ2 )-arc or a (σ2 , σ1 )-arc).
Proposition 4. Deciding whether a permutation is a square is NP-complete.
Proof (of Proposition 4). The problem is certainly in NP. We propose a reduction from the pattern involvement problem which is known to be NP-complete [2]:
Given two permutations π and σ, decide whether σ occurs in π (as an orderisomorphic pattern).

12

Let π ∈ Sn and σ ∈ Sk be two arbitrary permutations. Define
N4 = 2(2n + 2k + 4) + 1 = 4n + 4k + 9
N3 = 2(2N4 + 2n + 2k + 4) + 1 = 20n + 20k + 45
N2 = 2(2N3 + 2N4 + 2n + 2k + 4) + 1 = 100n + 100k + 225
N1 = 2(2N2 + 2N3 + 2N4 + 2n + 2k + 4) + 1 = 1000n + 1000k + 1325.
Notice that N1 , N2 , N3 and N4 are polynomial in n. The crucial properties
are

P
+
2n
+
that (i) N1 , N2 , N3 and N4 are odd integers and (ii) Ni >
2N
j
i<j≤4
2k + k for every 1 ≤ i ≤ 4.
We now turn to defining various gadgets (sequences of integers) that act as
building blocks in our construction of a new permutation µ:
σ ′ = ((k + 1) σ (k + 2)) [2N2 + N4 + 2n + k + 2]
π ′ = ((n + 1) π (n + 2)) [2N2 + N4 + n + k]
σ ′′ = σ [2N2 + N4 ]
π ′′ = π [2N2 + N4 + k]
ν1 =րN1 [2N2 + 2N3 + 2N4 + 2n + 2k + 4]
ν1′ =րN1 [N1 + 2N2 + 2N3 + 2N4 + 2n + 2k + 4]
ν2 =րN2 [N2 ]
ν2′ =ցN2
ν3 =րN3 [2N2 + 2N4 + 2n + 2k + 4]
ν3′ =րN3 [2N2 + N3 + 2N4 + 2n + 2k + 4]
ν4 =ցN4 [2N2 + N4 + 2n + 2k + 4]
ν4′ =ցN4 [2N2 ].
We are now in position to define our target permutation µ (see Fig. 3 for an
illustration):
µ = ν1 ν2 ν1′ ν3 σ ′ ν4 ν2′ ν3′ π ′ ν4′ π ′′ σ ′′ .
It is immediate that µ can be constructed in polynomial-time in n and k. It
can be shown that σ occurs in π if and only if there exists an oriented perfect
matching M on µ satisfying P1 and P2 .
⊓
⊔

7

Conclusion

There are a number of further directions of investigation in this general subject. They cover several areas: algorithmic, combinatorics, and algebra. Let us
mention several - not necessarily new - open problems that are, in our opinion,
the most interesting. How many permutations of S2n are squares? How many
(213, 231)-avoiding permutations of S2n are squares? (Equivalently, by Proposition 1, how many binary strings of length 2n are squares; see also Problem 4 in

13

[10])? How hard is the problem of deciding whether a (213, 231)-avoiding permutation is a square (Problem 4 in [10], see also [3,11])? Given two permutations
π and σ, how hard is the problem of deciding whether σ is a square root of π?
As for algebra, one can ask for a complete algebraic study of Q[S] as a graded
associative algebra for the shuffle product •. Describing a generating family for
Q[S], defining multiplicative bases of Q[S], and determining whether Q[S] is free
as an associative algebra are worthwhile questions.

References
1. C. Allauzen. Calcul efficace du shuffle de k mots. Technical report, Institut Gaspard
Monge, Université Marne-la-Vallée, 2000.
2. P. Bose, J.F.Buss, and A. Lubiw. Pattern matching for permutations. Information
Processing Letters, 65(5):277–283, 1998.
3. S. Buss and M. Soltys. Unshuffling a square is NP-hard. Journal of Computer and
System Sciences, 80(4):766–776, 2014.
4. C. Choffrut and J. Karhumäki. Combinatorics of Words, in G. Rozenberg and A.
Salomaa (eds), Handbook of Formal Languages. Springer-Verlag, 1997.
5. G. Duchamp, F. Hivert, and J.-Y. Thibon. Noncommutative symmetric functions.
VI. Free quasi-symmetric functions and related algebras. Int. J. Algebr. Comput.,
12(5):671–717, 2002.
6. S. Eilenberg and S. Mac Lane. On the groups of H(Π, n). I. Ann. of Math. (2),
58:55–106, 1953.
7. D. Grinberg and V. Reiner.
Hopf Algebras in Combinatorics.
2014.
arXiv:1409.8356.
8. S. A. Joni and G.-C. Rota. Coalgebras and bialgebras in combinatorics. Stud.
Appl. Math., 61(2):93–139, 1979.
9. A. Mansfield. On the computational complexity of a merge recognition problem.
Discrete Applied Mathematics, 5:119–122, 1983.
10. D. Henshall N. Rampersad and J. Shallit.
Shuffling and unshuffling.
http://arxiv.org/abs/1106.5767, 2011.
11. R. Rizzi and S. Vialette. On recognizing words that are squares for the shuffle
product. In A.A. Bulatov and A.M. Shur, editors, 8th International Computer
Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, pages 235–245,
2013.
12. R. Simion and F.W.Schmidt. Restricted permutations. European Journal of Combinatorics, 6(4):383–406, 1985.
13. N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. https://oeis.org/.
14. J.-C. Spehner. Le calcul rapide des melanges de deux mots. Theoretical Computer
Science, 47:181–203, 1986.
15. J. van Leeuwen and M. Nivat. Efficient recognition of rational relations. Information Processing Letters, 14(1):34–38, 1982.
16. Y. Vargas. Hopf algebra of permutation pattern functions. 26th International
Conference on Formal Power Series and Algebraic Combinatorics, pages 839–850,
2014.
17. M.K. Warmuth and D. Haussler. On the complexity of iterated shuffle. Journal of
Computer and System Sciences, 28(3):345–358, 1984.

