

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.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Interweaving of nonzero Hultman numbers A164652(n,k) for k=1 and k=2.  Max Alekseyev, Nov 20 2020


LINKS

Table of n, a(n) for n=0..24.
D. A. Christie, Sorting Permutations by BlockInterchanges, Inf. Process. Lett. 60 (1996), 165169. doi:10.1016/S00200190(96)00155X
R. Cori, M. Marcus, G. Schaeffer, Odd permutations are nicer than even ones, European Journal of Combinatorics 33:7 (2012), 14671478. doi:10.1016/j.ejc.2012.03.012
M. Tikhomirov, A conjecture harmonic numbers, MathOverflow, 2020.
D. Zagier, On the distribution of the number of cycles of elements in symmetric groups.


FORMULA

For even n, a(n) = 2 * n! / (n+2).
For odd n, a(n) = 2 * n! * H(n+1) / (n+2) = 2 * A000254(n+1) / ((n+1)*(n+2)), where H(n+1) = A001008(n+1)/A002805(n+1) is the (n+1)st harmonic number.
a(n) = A164652(n, 1+(n mod 2)).  Max Alekseyev, Nov 20 2020


EXAMPLE

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 nonidentity 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.


PROG

(PARI) { A260695(n) = abs(stirling(n+2, n%2+1)) / binomial(n+2, 2); } \\ Max Alekseyev, Nov 20 2020


CROSSREFS

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).
Sequence in context: A123819 A286076 A302651 * A153720 A101016 A264295
Adjacent sequences: A260692 A260693 A260694 * A260696 A260697 A260698


KEYWORD

nonn


AUTHOR

Marion Scheepers, Nov 16 2015


EXTENSIONS

Edited and extended by Max Alekseyev incorporating comments from M. Tikhomirov, Nov 20 2020


STATUS

approved



