OFFSET
1,2
COMMENTS
a(n) is equivalently the number of signed permutations such that in the reality-desire graph of the permutation, 0 and n are in different cycles.
It is also the number of signed permutations such that the overlap of that permutation contains a partition into two vertex sets, V_1 and V_2, such that (i) vertices (0,1) and (n,n+1) are in different cycles, and (ii) every vertex in V_1 is adjacent to an even number of vertices in V_2, and every vertex in V_2 is adjacent to an even number of vertices in V_1.
It is expected (but not proven) asymptotically that a(n) is about one-third of all permutations, i.e., it is about (2^n * n!) / 3.
LINKS
K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, and H. C. Wauck, Sorting permutations: games, genomes, and cycles, arXiv:1410.2353 [math.CO], 2014.
EXAMPLE
a(2) = 3 because out of the 8 signed permutations of size 2, only [1,2], [1,-2], and [-1,2] are sortable. They each take one cdr move. Three other permutations, [-2,-1], [2,-1], and [-2,1] are not sortable to the identity [1,2] but instead sort to [-2,-1]. Finally, [2,1] and [-1,-2] sort to neither [1,2] nor [-2,-1].
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Caleb Stanford, Jul 27 2015
STATUS
approved