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.
Original entry on oeis.org
1, 3, 18, 140, 1384, 16428, 228248
Offset: 1
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].
- 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.
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.
A260695
a(n) is the number of permutations p of {1,..,n} such that the minimum number of block interchanges required to sort the permutation p to the identity permutation is maximized.
Original entry on oeis.org
1, 1, 1, 5, 8, 84, 180, 3044, 8064, 193248, 604800, 19056960, 68428800, 2699672832, 10897286400, 520105017600, 2324754432000, 130859579289600, 640237370572800, 41680704936960000, 221172909834240000, 16397141420298240000, 93666727314800640000, 7809290721329061888000, 47726800133326110720000
Offset: 0
The next three lines illustrate applying block interchanges to [2 4 6 1 3 5 7], an element of S_7.
Step 1: [2 4 6 1 3 5 7]->[3 5 1 2 4 6 7]-interchange blocks 3 5 and 2 4 6.
Step 2: [3 5 1 2 4 6 7]->[4 1 2 3 5 6 7]-interchange blocks 3 5 and 4.
Step 3: [4 1 2 3 5 6 7]->[1 2 3 4 5 6 7]-interchange blocks 4 and 1 2 3.
As [2 4 6 1 3 5 7] requires 3 = floor(7/2) block interchanges, it is one of the a(7) = 3044.
Each of the 23 non-identity elements of S_4 requires at least 1 block interchange to sort to the identity. But only 8 of these require 2 block interchanges, the maximum number required for elements of S_4. They are: [4 3 2 1], [4 1 3 2], [4 2 1 3], [3 1 4 2], [3 2 4 1], [2 4 1 3], [2 1 4 3], [2 4 3 1]. So, a(4) = 8.
- D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169.
- Robert Cori, Michel Marcus, and Gilles Schaeffer, Odd permutations are nicer than even ones, European Journal of Combinatorics 33:7 (2012), 1467-1478.
- M. Tikhomirov, A conjecture harmonic numbers, MathOverflow, 2020.
- D. Zagier, On the distribution of the number of cycles of elements in symmetric groups.
The number of elements of S_n that can be sorted by: a single block interchange (
A145126), two block interchanges (
A228401), three block interchanges (
A256181), context directed block interchanges (
A249165).
The number of signed permutations that can be sorted by: context directed reversals (
A260511), applying either context directed reversals or context directed block interchanges (
A260506).
-
a[n_]:=Abs[StirlingS1[n+2,Mod[n,2]+1]/Binomial[n+2,2]]; Array[a,25,0] (* Stefano Spezia, Apr 01 2024 *)
-
{ A260695(n) = abs(stirling(n+2, n%2+1)) / binomial(n+2, 2); } \\ Max Alekseyev, Nov 20 2020
Edited and extended by
Max Alekseyev incorporating comments from M. Tikhomirov, Nov 20 2020
A260511
Number of signed permutations of length n that are sortable to the identity permutation by some sequence of cdr (context-directed reversal) moves.
Original entry on oeis.org
1, 3, 15, 120, 1227, 15188
Offset: 1
a(2) = 3 because [1,2], [-1,2], and [1,-2] are sortable to the identity [1,2] using only context-directed reversal moves.
- 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.
A249165 gives the number of unsigned permutations sortable by context-directed swaps; this is the analog for signed permutations and context-directed reversals.
A260506 gives the number of signed permutations sortable by both cdr and cds moves together. This sequence is therefore always bounded by
A260506.
A000165 counts the total number of signed permutations.
Showing 1-3 of 3 results.
Comments