login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A260506 Number of signed permutations of length n that are sortable to the identity permutation by some sequence of cdr (context-directed reversal) and cds (context-directed swap) moves. 3
1, 3, 18, 140, 1384, 16428, 228248 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..7.

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

A249165 counts the special case of this property for unsigned permutations. Note that for unsigned permutations, there are no valid cdr moves, so sortability by cdr and cds is equivalent to sortability by cds only.

A000165 counts the total number of signed permutations.

Sequence in context: A216492 A127129 A186266 * A193237 A212030 A259904

Adjacent sequences:  A260503 A260504 A260505 * A260507 A260508 A260509

KEYWORD

nonn,more

AUTHOR

Caleb Stanford, Jul 27 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 01:16 EST 2017. Contains 294837 sequences.