Adjacencies in Permutations
Abstract
A permutation on an alphabet $ \Sigma $, is a sequence where every element in $ \Sigma $ occurs precisely once. Given a permutation $ \pi $= ($\pi_{1} $, $ \pi_{2} $, $ \pi_{3} $,....., $ \pi_{n} $) over the alphabet $ \Sigma $ =$\{ $0, 1, . . . , n$$1 $\}$ the elements in two consecutive positions in $ \pi $ e.g. $ \pi_{i} $ and $ \pi_{i+1} $ are said to form an \emph{adjacency} if $ \pi_{i+1} $ =$ \pi_{i} $+1. The concept of adjacencies is widely used in computation. The set of permutations over $ \Sigma $ forms a symmetric group, that we call P$ _{n} $. The identity permutation, I$ _{n}$ $\in$ P$_{n}$ where I$_{n}$ =(0,1,2,...,n$$1) has exactly n$  $1 adjacencies. Likewise, the reverse order permutation R$_{n} (\in P_{n})$=(n$$1, n$$2, n$$3, n$$4, ...,0) has no adjacencies. We denote the set of permutations in P$_{n} $ with exactly k adjacencies with P$_{n} $(k). We study variations of adjacency. % A transposition exchanges adjacent sublists; when one of the sublists is restricted to be a prefix (suffix) then one obtains a prefix (suffix) transposition. We call the operations: transpositions, prefix transpositions and suffix transpositions as blockmoves. A particular type of adjacency and a particular blockmove are closely related. In this article we compute the cardinalities of P$_{n}$(k) i.e. $ \forall_k \mid $P$ _{n} $ (k) $ \mid $ for each type of adjacency in $O(n^2)$ time. Given a particular adjacency and the corresponding blockmove, we show that $\forall_{k} \mid P_{n}(k)\mid$ and the expected number of moves to sort a permutation in P$_{n} $ are closely related. Consequently, we propose a model to estimate the expected number of moves to sort a permutation in P$_{n} $ with a blockmove. We show the results for prefix transposition. Due to symmetry, these results are also applicable to suffix transposition.
 Publication:

arXiv eprints
 Pub Date:
 January 2016
 arXiv:
 arXiv:1601.04469
 Bibcode:
 2016arXiv160104469C
 Keywords:

 Computer Science  Discrete Mathematics;
 05A05;
 20B10;
 20B30;
 20B40;
 F.2.2;
 G.2.1
 EPrint:
 20 pages. 5 tables