=Paper=
{{Paper
|id=Vol-2113/paper12
|storemode=property
|title=Permutation patterns in genome rearrangement problems
|pdfUrl=https://ceur-ws.org/Vol-2113/paper12.pdf
|volume=Vol-2113
|authors=Giulio Cerbai,Luca Ferrari
|dblpUrl=https://dblp.org/rec/conf/gascom/CerbaiF18
}}
==Permutation patterns in genome rearrangement problems==
https://ceur-ws.org/Vol-2113/paper12.pdf
Permutation patterns in genome rearrangement problems
Giulio Cerbai Luca Ferrari
giuliocerbai14@gmail.com luca.ferrari@unifi.it
Dipartimento di Matematica e Informatica ”U. Dini”,
viale Morgagni 65, University of Firenze, Firenze, Italy
Abstract
In the context of the genome rearrangement problem, we analyze two
well known models, namely the block transposition and the prefix block
transposition models, by exploiting the connection with the notion of
permutation pattern. More specifically, for any k, we provide a char-
acterization of the set of permutations having distance ≤ k from the
identity (which is known to be a permutation class) in terms of what
we call generating permutations and we describe some properties of its
basis, which allow to compute such a basis for small values of k.
1 Introduction
One of the major trends in bioinformatics and biomathematics is the study of the genome rearrangement problem.
Roughly speaking, given a genome, one is interested in understanding how the genome can evolve into another
genome. To give a proper formalization, several models for rearranging a genome have been introduced, each
of which defines a series of allowed elementary operations to be performed on a genome in order to obtain an
adjacent one. For several models, it is possible to define a distance between two genomes, by counting the
minimum number of elementary operations needed to transform one genome into the other. The investigation
of the main properties of such a distance becomes then a key point in understanding the main features of the
model under consideration.
A common formalization of any such models consists of encoding a genome using a permutation (in linear
notation) and describing an elementary operation as a combinatorial operation on the entries of such a permu-
tation. Many genome rearrangement models have been studied under this general framework. Among them, the
following ones are very well known.
• The reversal model consists of a single operation, defined as follows: a new permutation is obtained
from a given one by selecting a cluster of consecutive elements and reversing it. More formally, given
π = π1 π2 · · · πn , a reversal is performed by choosing i < j < n and then forming the permutation
σ = π1 · · · πi−1 πj πj−1 · · · πi+1 πi πj+1 · · · πn . This model was introduced in [WEHM82], then studied for
instance in [BP93, HP99].
• A variant of the reversal model is the prefix reversal model, which is a specialization of the previous one in
which the reversal operation can only be performed on a prefix of the given permutation. This is clearly an
easier model to investigate, which is also known as pancake sorting (see for instance [GP79]).
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
124
• A very popular and studied model is the transposition model, see [BP98]. Given a permutatation π =
π1 · · · πn , a transposition operation consists of taking two adjacent clusters of consecutive elements and
interchanging their positions. Formally, one has to choose indices 1 ≤ i < j < k ≤ n + 1, then form the
permutation σ = π1 · · · πi−1 πj πj+1 · · · πk−1 πi πi+1 · · · πj−1 πk · · · πn .
• As for the reversal, also for the transposition model there is a “prefix variant”. In the prefix transposition
model the leftmost block of elements to interchange is a prefix of the permutation. Sorting by prefix
transposition is studied in [DM02].
Independently from the chosen model, there are some general questions that can be asked in order to gain
a better understanding of its combinatorial properties. First of all, the operations of the model often (but not
always) allow to define a distance d between two permutations ρ and σ, as the minimum number of elementary
operations needed to transform ρ into σ. Moreover, when the operations are nice enough, the above distance d
could even be left-invariant, meaning that, given permutations π, ρ, σ (of the same length), d(π, ρ) = d(σπ, σρ).
As a consequence, choosing for instance σ = ρ−1 , the problem of evaluating the distance d(π, ρ) reduces to that
of sorting π with the minimum number of elementary allowed operations. Now, if d is a left-invariant distance
(d)
on the set Sn of all permutations of the same length, define the k-ball of Sn to be the set Bk (n) = {ρ ∈
Sn | d(ρ, idn ) ≤ k}, where idn is the identity permutation of length n. The following questions are quite natural
to ask:
(d) (d)
• compute the diameter of Bk (n), i.e. the maximum distance between two permutations of Bk (n);
• compute the diameter of Sn , i.e. the maximum distance between two permutations of Sn ;
(d) (d)
• characterize the permutations of ∂Bk (n), i.e. the permutations of Bk (n) having maximum distance from
the identity;
• characterize the permutations of ∂Sn , i.e. the permutations of Sn having maximum distance from the
identity;
(d)
• characterize and enumerate the permutations of Bk (n);
• design sorting algorithms and study the related complexity issues.
In the literature there are several results, concerning several evolution models, which give some insight into the
(d)
above problems. Our work starts from the observation that, in many cases, the balls Bk (n) can be characterized
in terms of pattern avoidance. Recall that, given two permutation σ ∈ Sk and τ = τ1 τ2 · · · τn ∈ Sn , with k ≤ n,
we say that σ is a pattern of τ when there exist 1 ≤ i1 < i2 < · · · < ik ≤ n such that τi1 τi2 · · · τik as a
permutation is isomorphic to σ (which means that τi1 , τi2 , . . . , τik are in the same relative order as the elements
of σ). This notion of pattern in permutation defines an obvious partial order, and the resulting poset is known
as the permutation pattern poset. When σ is not a pattern of τ , we say that τ avoids σ. A down-set I (also
called a permutation class) of the permutation pattern poset can be described in terms of its minimal excluded
permutations (or, equivalently, the minimal elements of the complementary up-set): these permutations are called
(d)
the basis of I. The idea of studying the balls Bk (n) in terms of pattern avoidance is not new. As far as we know,
the first model which has been investigated from this point of view is the (whole) tandem duplication-random
(d) S (d)
loss model: Bouvel and Rossin [BR09] have in fact shown that, in such a model, the ball Bk = n≥0 Bk (n)
is a class of pattern avoiding permutations, whose basis is the set of minimal permutations having d descents
(here minimal is intended in the permutation pattern order). Subsequent works [BP10, BF13, CGM11] have
been done concerning the enumeration of the basis permutations of such classes. More recently, Homberger and
Vatter [HV16] described an algorithm for the enumeration of any polynomial permutation class, which can be
fruitfully used for all the above mentioned distances, since the resulting balls are indeed polynomial classes.
However, their results do not allow to find information on the basis of the classes.
In the present work we try to enhance what have been obtained in [HV16] in two directions. First, we aim at
giving a structural characterization of the balls for some of the above distances, thus complementing the results
in [HV16], which is more concerned with computational issues. Second, we provide some insight on the properties
of the bases of such balls, hoping to gain a better understanding of them. We will be mainly concerned with the
block transposition and the prefix block transposition models, leaving the reversal models to a future paper.
Some of the results of the present work are contained in the MSc thesis of the first author [Cer17].
125
2 Block transposition
Among the four above mentioned models, the block transposition one is probably the hardest to investigate.
(td)
Denoting with td the transposition distance, the permutation class Bk can be described in terms of its
generating permutations.
A strip of π = π1 π2 · · · πn ∈ Sn is a maximal consecutive substring πi · · · πi+k−1 such that, for all j =
1, . . . , i + k − 2, πj+1 = πj + 1.
A permutation π is said to be plus irreducible [AS02] when, for all i = 1, . . . , n − 1, πi+1 6= πi + 1. In other
words, π is a plus irreducible permutation when it does not have points that are adjacent both in positions and
values, with values increasing. Equivalently, a permutation is plus irreducible if and only if all of its strips have
length 1.
Any permutation π can be associated with a plus irreducible permutation, denoted red(π), which is obtained
by replacing each strip of π with its minimum element, then suitably rescaling the resulting word. For instance,
if π = 435612789, then red(π) = 32415. It is easy to observe that red(π) ≤ π in the permutation pattern order.
Moreover, for every permutation π, we have that td(π) = td(red(π)).
Given π ∈ Sn , let v1 , . . . , vn be nonnegative integers. The monotone inflation of π through v = (v1 , . . . , vn )
is the permutation π[v] = π[idv1 , . . . , idvn ] obtained from π by replacing each element πi of π with the identity
permutation idvi of length i suitably rescaled, so to mantain the relative order of the elements of π. So, for
instance, if π = 41352 and v = (0, 2, 1, 3, 2), we have π[v] = |{z} . . . |{z}
12 |{z}
5 |{z}
678 |{z}
34 . In the following we will
4 1 3 5 2 S
denote with M I(π) the set of all monotone inflations of a permutation π and with M I(C) the set π∈C M I(π),
for a given set of permutations C. The notion of monotone inflation is clearly related to that of geometric grid
class [AABRV13]. More specifically, given a {−1, 0, 1}-matrix M and denoting with Geom(M ) the geometric
grid class of permutations determined by M , if π is a permutation and Mπ is its permutation matrix, then it is
not difficult to realize that:
1. Geom(Mπ ) = Geom(Mred(π) );
2. M I(π) = Geom(Mπ );
3. M I(π) = M I(red(π)).
(td) (td) S
Now define a permutation π to be generating for Bk =
n≥0 Bk (n) when it is a maximal plus irreducible
(td) (td) (td)
permutation of Bk . The set of all generating permutations for Bk will be called the generating set of Bk .
We thus have the following fact, whose easy proof is omitted.
(td) S (td)
Proposition 2.1. For every k, Bk = {M I(π) | π is generating for Bk }.
(td)
A very natural description of the balls Bk is then provided by its generating set. This is our first open
problem.
(td)
Open problem. Characterize the generating permutations of Bk , for every k.
(td)
For instance, it is easy to realize that B1 = M I(1324). In the following, we will provide a structural
(td)
description of the generating permutations of Bk for a generic k.
(td)
Our approach is based on the observation that a generating permutation for Bk is a plus irreducible permu-
tation, and so it will be convenient to work inside the poset of plus irreducible permutations, seen as a subposet
of the classical permutation pattern poset (notice that this is also a subposet of the poset of peg permutations, as
defined in [HV16]). In passing, we remark that the enumeration of plus irreducible permutations is well known:
denoting with fn the number of plus irreducible permutations of length n + 1, we have the recurrence relation
fn = nfn−1 + (n − 1)fn−2 ,
−x
e
for n ≥ 2. With initial conditions f0 = f1 = 1, we get for (fn )n≥0 the exponential generating function (1−x) 2
Pn k n!
and the closed form fn = k=0 (−1) (n + 1 − k) k! . This is sequence A000255 in [S], see also [AAB07].
126
(td)
Suppose π = π1 π2 · · · πn is a plus irreducible permutation of length n in the generating set of Bk . Inflate π
by choosing three (not necessarily distinct) indices 1 ≤ i ≤ j ≤ k ≤ n and replacing πi , πj and πk by strips of
suitable lengths, as follows:
• if the three indices are all distinct, take strips of length 2;
• if two of the indices are equal, take the associated strip of length 3;
• if all indices are equal, take a strip of length 4.
If I is the multiset of the selected indices, the resulting permutation will be denoted πI . Now observe that, in
all of the above cases, there exists a unique block transposition τI that breaks all the new strips in such a way
that, in the resulting permutation, each pair of adjacent elements of a new strip becomes either nonadjacent or
adjacent in the reverse way; more specifically, τI is the transposition with indices i + 1, j + 2, k + 3. We call π̃I
the permutation obtained from π̃I by applying τI . As an example, consider the permutation π = 1324, and the
multiset of indices I = {2, 2, 4}; then we get πI = 1345267 and π̃I = 1352647.
The following lemma gives some basic properties of the above described construction that will be useful in
the sequel. The proof is easy and so left to the reader.
Lemma 2.2. Let π = π1 · · · πn be a plus irreducible permutation of length n and I a multiset of indices of π of
cardinality 3. Then π̃I is a plus irreducible permutation of length n + 3; moreover, if π1 = 1 and πn = n, then
(π̃I )1 = 1 and (π̃I )n+3 = n + 3.
(td)
We are now ready to give an explicit description of the generating set of the ball Bk . Such a result will be
preceded by a technical proposition (stated without proof) which gives a recipe to recursively construct the set
of permutations which are obtainable by means of a single block transposition. In the proof of the next theorem
we also need the definition of breakpoint, which can be found for instance in [FLRTV09]. Given a permutation
π = π1 · · · πn , a breakpoint of π is an integer i ∈ {0, 1, . . . n} such that πi+1 6= πi + 1. By convention, 0 and n are
breakpoints whenever π1 6= 1 and πn 6= n, respectively.
Proposition 2.3. Let I(n) be the set of all multisets of cardinality 3 of {1, 2, . . . n}. For every plus irreducible
permutation π ∈ Sn , denote with M I(π)+1 the set of all permutations which can be obtained with a single block
transposition from any permutation of M I(π). Then
[
M I(π)+1 = M I(π̃I ).
I∈I(n)
(td)
Theorem 2.4. For every k ≥ 1, the generating set of Bk is the set of all plus irreducible permutations of
length 3k + 1 and having distance k from the identity.
Proof. We start by showing that there exists a finite number N = N (k) of permutations α(1) , . . . , α(N ) which
(td) SN
are plus irreducible, of length 3k + 1 and at distance k from the identity, such that Bk = j=1 M I(α(j) ).
(td)
We can proceed by induction on k. When k = 1, we have already observed that B1 = M I(1324), and 1324
is plus irreducible, has length 3+1=4 and has distance 1 from the identity 1234. Now consider a permutation
(td) (td) (td)
π ∈ Bk+1 \ Bk ; this means, in particular, that there is a permutation π ∈ Bk such that π is obtained from
π by a single block transposition. Thus, using the induction hypothesis, we can say that there exists a plus
irreducible permutation α of length 3k + 1 and having distance k from the identity such that π ∈ M I(α)+1 .
By Proposition 2.3, there exists I ∈ I(3k + 1) such that π ∈ M I(α̃I ). Notice that I(3k + 1) is finite and that,
by Lemma 2.2, α̃I is plus irreducible and has length 3k + 4; so what remains to prove is that α̃I has distance
k + 1 from the identity. Clearly td(α̃I ) ≤ k + 1. On the other hand, since Lemma 2.2 implies that α̃I starts with
1 and ends with 3k + 4, recalling that α̃I is plus irreducible, we have that α̃I has exactly 3k + 3 breakpoints,
since the only indices that are not
l breakpoints
m are 0 and 3k + 4. Therefore, denoting with Br(π) the number of
Br(π)
breakpoints of π, since td(π) ≥ 3 (this follows from an observation in [BP98]), we have that
Br(α̃I ) 3k + 3
td(α̃I ) ≥ = = k + 1,
3 3
127
as desired.
To conclude the proof we now have to show that any plus irreducible permutation γ of length 3k + 1 and
(td) (td)
having distance k from the identity is a generating permutation of Bk . In fact, since γ ∈ Bk , γ is the
(td)
monotone inflation of some generating permutation α of Bk . Therefore α is a plus irreducible permutation of
length 3k + 1 at distance k from the identity. So in particular γ and α have the same length, which means that
necessarily γ = α.
(td)
The above theorem allows to design a procedure to list the generating set of Bk : starting from the identity of
length 3k + 1, perform repeated monotone inflations as in Proposition 2.3 (for k times) so to obtain all generating
(td)
permutations of Bk . This is similar to the approach used in [HV16].
(td)
For instance, when k = 2, the generating set for B2 consists of the eleven permutations 1324657, 1352647,
1354627, 1364257, 1426357, 1436527, 1462537, 1524637, 1536247, 1624357, 1632547.
Notice however that, in this way, it is possible to obtain the same generating permutation several times, so in
the list of permutations given in output by the above procedure one has to remove duplicates. This is the main
reason for which the described approach is not useful for enumerating the generating set.
(td)
Open problem. Enumerate the generating permutations of Bk , for every k.
(td)
A very interesting information that we can get on Bk concerns its basis. We start by recalling that monotone
inflations are particular geometric grid classes [AABRV13]; as a consequence, the general theory of geometric
(td)
grid classes allows us to say that Bk is a permutation class having finite basis (and also that it is strongly
rational, meaning that its generating function is rational, together with the generating functions of all of its
subclasses). What we are able to do is to provide a nontrivial upper bound to the length of the basis elements,
which is clearly of great help in effectively computing the basis itself.
(td)
Theorem 2.5. Every permutation belonging to the basis of Bk has length at most 3k + 1.
(td)
Proof. We start by observing that, given π basis permutation of Bk , if π were not plus irreducible, then
necessarily red(π) < π and we have already observed that td(π) = td(red(π)); so π would not be minimal among
the permutations at distance k from the identity, which is impossible. Therefore we can assert that all basis
(td)
permutations of Bk are plus irreducible.
Now it is easy to prove that every basis permutation has length at most 3k + 2. Indeed, it is not difficult to
show that a plus irreducible permutation of length m contains as a pattern at least one permutation of length
m − 1 that is plus irreducible as well. Thus, if π were a basis permutation having length greater than 3k + 2,
then, in the poset of plus irreducible permutations, there would exist at least one plus irreducible permutation
(td)
σ of length greater than 3k + 1 such that σ < π. Since all generating permutations of Bk have length 3k + 1,
(td)
σ cannot belong to Bk , which is not possible since π is a basis permutation.
(td)
Moreover, suppose that π = π1 π2 · · · πn is a permutation in the basis of Bk . First of all we have that
π1 6= 1 and πn 6= n, since otherwise we could remove π1 or πn thus obtaining a smaller permutation having
the same distance from the identity, against the minimality of π. If π had length n = 3k + 2, since π is plus
irreducible, there would exist γ < π which is plus irreducible as well. Since π is minimal in the complement
(td) (td)
of Bk , necessarily td(γ) = k. This would imply that γ = γ1 γ2 · · · γ3k+1 is a generating permutation of Bk .
This is however impossible, since it would be γ1 = 1 and γ3k+1 = 3k + 1 by Lemma 2.2 and the construction
showed in Theorem 2.4, π1 6= 1 and π3k+2 6= 3k + 2 for what we have proved above, and γ is obtained from π by
removing a single entry.
(td)
The above theorem also suggest a procedure to determine the basis of Bk . In the poset of plus irreducible
permutations, consider the set of permutations of length 3k + 1 which are not generating. For each of them (say
π), consider the set of permutation of length 3k covered by it: if all of them are also below some generating
(td) (td)
permutation of Bk , then π is in the basis of Bk . Otherwise, just repeat the same procedure starting from
(td)
the permutations covered by π which do not belong to Bk .
As an instance, we have the following result.
(td)
Proposition 2.6. The basis of B1 is {321, 2143, 2413, 3142}.
128
(td)
Proof. Since B1 = M I(1324), we perform the above procedure with all permutations of length 4 except
(td)
1324. A direct computation shows that the only permutations which cover only elements of B1 are precisely
(td)
2143, 2413, 3142. Moreover, 321 is the unique permutation of length 3 which is not in Bk , and all of its coverings
(td)
are in Bk , so 321 is in the basis as well.
3 Prefix transposition
If we restrict the block transposition operation to pairs of blocks such that the first one is a prefix of the permu-
tation, we obtain the so-called prefix transposition model. It is clearly a special case of the block transposition
model and, as such, it is simpler to analyze. Denoting with ptd the prefix transposition distance, our first goal
(ptd)
is to characterize the balls Bk in terms of generating permutations. As a first example, it is easy to see that
(ptd) (ptd)
B1 = M I(213). The approach we use to determine the generating set Bk is slightly different from the one
we have used for the block transposition model. In the present case, we are able to give an explicit construction
(ptd) (ptd)
of the generating set of Bk+1 starting from the generating set of Bk .
(ptd)
Proposition 3.1. Let τ ∈ Sn be a generating permutation of Bk .
1. Suppose that τ = πaρbγ, where a < b ≤ n and π, ρ and γ are the subwords of τ determined by such a
(ptd)
decomposition. Then the permutation (a + 1)ρ̂(b + 1)π̂a(b + 2)γ̂ is a generating permutation of Bk+1 , where
ρ̂, π̂, γ̂ are obtained from ρ, π, γ (respectively) by increasing by 1 all the entries between a and b and by
increasing by 2 all the entries that are greater than b.
2. Suppose that τ = πaρbγ, where n ≥ a > b and π, ρ and γ are the subwords of τ determined by such a
(ptd)
decomposition. Then the permutation (a + 2)ρ̂bπ̂(a + 1)(b + 1)γ̂ is a generating permutation of Bk+1 , where
ρ̂, π̂, γ̂ are obtained from ρ, π, γ (respectively) by increasing by 1 all the entries between b and a and by
increasing by 2 all the entries that are greater than a.
3. Suppose that τ = πaρ, where a ≤ n and π and ρ are the subwords of τ determined by such a decomposition.
(ptd)
Then the permutation (a + 1)π̂a(a + 2)ρ̂ is a generating permutation of Bk+1 , where π̂, ρ̂ are obtained from
π, ρ by increasing by 2 all the entries that are greater than a.
Proof. We will give details only for the first case, the remaining two being analogous. Since the prefix trans-
position model is a special case of the block transposition one, we have that, if τ is a generating permutation
(ptd) (ptd)
for Bk , we can construct generating permutations for Bk+1 by suitably choosing two elements a and b of τ
(possibly the same one), then suitably inflating them and performing the prefix transposition operation which
exchanges the prefix block ending with a with the adjacent block ending with b. This is done in analogy with
the construction described before Lemma 2.2.
If a < b and a precedes b in τ , then we can decompose τ as τ = πaρbγ. After inflating a and b, we thus get the
permutation π̂a(a + 1)ρ̂(b + 1)(b + 2)γ̂, where the elements of π, ρ and γ have been renamed, namely all entries
greater than a and smaller than b have been increased by 1 and all entries greater than b have been increased by
2. We can now perform the desired prefix transposition, which exchanges the prefix block π̂a with the adjacent
block (a + 1)ρ̂(b + 1), thus obtaining the predicted permutation.
(ptd)
The above proposition gives a recipe for constructing generating permutations of Bk+1 starting from those
(ptd)
of Bk . Notice that, if τ has length m, then the permutations obtained with the previous construction have
(ptd)
length m + 2. Since we have seen that B1 = M I(213), a simple inductive argument shows that the generating
(ptd)
permutations of Bk we have produced all have length 2k + 1. Actually, we have something stronger, which is
the analogous of Theorem 2.4 in the case of the prefix transposition model. Since the proof is similar, we just
give the statement.
(ptd)
Theorem 3.2. For every k ≥ 1, the generating set of Bk is the set of all plus irreducible permutations of
length 2k + 1 and having distance k from the identity.
However, in this case we can also enumerate the generating sets.
(ptd)
Theorem 3.3. The generating set of Bk has cardinality (2k)!/2k .
129
(ptd)
Proof. We observe that, if σ = σ1 σ2 · · · σ2k+3 is a generating permutation for Bk+1 , then it has been obtained
(ptd)
from a generating permutation of Bk by one of the construction described in Proposition 3.1. However, σ
cannot be obtained in two different ways. This can be shown by considering the elements σ1 and σ1 − 1 (notice
that, in this model, a generating permutation cannot start with 1).
1. If the element on the right of σ1 − 1 in σ is larger than or equal to σ1 + 2, then σ is constructed as in 1 of
Proposition 3.1.
2. If the element on the right of σ1 − 1 in σ is smaller than or equal to σ1 − 2, then σ is constructed as in 2 of
Proposition 3.1.
3. If the element on the right of σ1 − 1 in σ is equal to σ1 + 1, then σ is constructed as in 3 of Proposition 3.1.
Since the three above cases are disjoint, we can conclude that σ comes from a unique generating permutation
(ptd)
of Bk through the construction of Proposition 3.1. Thus, the total number of generating permutations of
(ptd) (ptd)
Bk+1 is obtained by multiplying the number of generating permutations of Bk by the number of possible
inflations of each of them, which is equal to the number of multisets of cardinality 2 of a set of cardinality 2k + 1,
(ptd)
i.e. 2k+2 has cardinality 1 = 22 , a simple inductive argument shows that
2 . Since the generating set of B1
Qk
the required cardinality is indeed equal to i=1 2ii = (2k)!/2k .
We have already observed that, for k = 1, the generating set is {213}. For k = 2, the generating set is
{32415, 41325, 31425, 24135, 24315, 42135}.
(ptd)
Concerning the basis of Bk , we have been able to prove the analogue of Theorem 2.5, however the proof is
slightly more complicated, so we cannot reproduce it entirely here, due to limited space.
(ptd)
Theorem 3.4. Every permutation belonging to the basis of Bk has length at most 2k + 1.
(ptd)
Proof. (sketch). The fact that the permutations in the basis of Bk must all have length at most 2k + 2 can
be proved in a similar way as the first part of Theorem 2.5.
(ptd)
Now suppose that π = π1 π2 · · · π2k+2 is a basis permutation for Bk of length 2k + 2, and set n = 2k + 2.
Then it can be shown that π has to be plus irreducible and that πn 6= n, i.e. the last element of π is not its
maximum. From a previous observation, we know that it is possible to remove one element of π in such a way
that the resulting permutation γ = γ1 γ2 · · · γn−1 of length n − 1 is plus irreducible. However, since π belongs
(ptd) (ptd)
to the basis of Bk , γ has to be a generating permutation of Bk . Since it is possible to prove that the last
(ptd)
element of any generating permutation of Bk is its maximum, there are only two possibilities: either the last
element of π is n − 1 and γ is obtained by removing n, or the second-to-last element of π is n and γ is obtained
by removing the last element.
Since the two cases are symmetric in a well precise sense, we just consider the first one. Our goal is now
to show that we can remove another element from π (different from n) and obtain another plus irreducible
permutation, which turns out to be a generating permutation: this is however impossible, since it does not ends
with its maximum. In many cases, if we remove the last element n − 1 of π, we do obtain a plus irreducible
permutation. The only cases in which this does not work are those in which n − 2 is immediately before n in π.
In such cases, if we remove n − 2, we indeed get a plus irreducible permutation, unless n − 3 is immediately before
n − 1 in π. By repeating this argument, we find that we are always able to remove an element different from n
and obtain a plus irreducible permutation, except for the permutation σ = 2468 · · · n1357 · · · (n − 1) (recall that
n = 2k + 2, so n is even). Also in this last case, however, we can remove 1 from σ and the permutation thus
obtained is easily seen to be plus irreducible.
Thanks to the above bound, we are able also in this case to compute the basis for small values of k.
(ptd)
Proposition 3.5. 1. The basis of B1 is {132, 321}.
(ptd)
2. The basis of B2 consists of three permutations of length 4, namely 1432, 2143, 4321, and fifteen permu-
tations of length 5, namely 13524, 14253, 24351, 25314, 25413, 35142, 35214, 35241, 41352, 42513, 42531,
43152, 51324, 52413, 53142.
130
Acknowledgements
Both authors are members of the INdAM Research group GNCS; they are partially supported by INdAM - GNCS
2018 project “Proprietá combinatorie e rilevamento di pattern in strutture discrete lineari e bidimensionali” and
by a grant of the ”Fondazione della Cassa di Risparmio di Firenze” for the project ”Rilevamento di pattern:
applicazioni a memorizzazione basata sul DNA, evoluzione del genoma, scelta sociale”.
References
[AABRV13] M. H. Albert, M. D. Atkinson, M. Bouvel, N. Ruskuc and V. Vatter. Geometric grid classes of
permutations. Transactions of the American Mathematical Society, 365:5859–5881, 2013.
[AAB07] M. H. Albert, M. D. Atkinson and R. Brignall. Permutation Classes of Polynomial Growth. Annals of
Combinatorics, 11:249–264, 2007.
[AS02] M. D. Atkinson and T. Stitt. Restricted permutations and the wreath product. Discrete Mathematics,
259:19–36, 2002.
[BP93] V. Bafna and P. A. Pevzner. Genome rearrangements and sorting by reversals. 34th Annual Symposium
on Foundations of Computer Science (Palo Alto, CA, 1993), IEEE Comput. Soc. Press, Los Alamitos,
CA, pp. 148–157, 1993.
[BP98] V. Bafna and P. A. Pevzner. Sorting by transpositions. SIAM Journal on Discrete Mathematics,
11:224–240, 1998.
[BF13] M. Bouvel and L. Ferrari. On the enumeration of d-minimal permutations. Discrete Mathematics and
Theoretical Computer Science, 15:33–48, 2013.
[BP10] M. Bouvel and E. Pergola. Posets and permutations in the duplication-loss model: minimal permuta-
tions with d descents. Theoretical Computer Science, 411:2487–2501, 2010.
[BR09] M. Bouvel and D. Rossin. A variant of the tandem duplication-random loss model of genome rear-
rangement. Theoretical Computer Science, 410:847–858, 2009.
[Cer17] G. Cerbai. Pattern avoiding permutations in genome rearrangement problems. MSc Thesis, Diparti-
mento di Matematica e Informatica “U. Dini”, University of Firenze, Italy, 2017.
[CCMR06] K. Chaudhuri, K. Chen, R. Mihaescu and S. Rao. On the tandem duplication-random loss model
of genome rearrangement. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete
Algorithms, ACM, New York, pp. 564-570, 2006.
[CGM11] W. Y. C. Chen, C. C. Y. Gu and K. J. Ma. Minimal permutations and 2-regular skew tableaux.
Advances in Applied Mathematics, 47:795–812, 2011.
[DM02] Z. Dias and J. Meidanis. Sorting by prefix transposition. SPIRE2002, Lecture Notes in Computer
Science, 2476:65–76, 2002.
[FLRTV09] G. Fertin, A. Labarre, I. Rusu, E. Tannier and S. Vialette. Combinatorics of Genome Rearrange-
ments. MIT Press, Cambridge, MA, 2009.
[GP79] W. H. Gates and C. H. Papadimitriou. Bounds for sorting by prefix reversal. Discrete Mathematics,
27:47–57, 1979.
[HP99] S. Hannenhalli and P. A. Pevzner. Transforming cabbage into turnip: polynomial algorithm for sorting
signed permutations by reversals. Journal of the ACM, 46:1–27, 1999.
[HV16] C. Homberger and V. Vatter. On the effective and automatic enumeration of polynomial permutation
classes. Journal of Symbolic Computation, 76:84–96, 2016.
[S] N. J. A. Sloane. The on-line encyclopedia of integer sequences. At oeis.org.
[WEHM82] G. A. Watterson, W. J. Ewens, T. Hall and A. Morgan. The chromosome inversion problem. Journal
of Theoretical Biology, 99:1–7, 1982.
131