A260695 - OEIS

%I #42 Apr 01 2024 10:31:52

%S 1,1,1,5,8,84,180,3044,8064,193248,604800,19056960,68428800,

%T 2699672832,10897286400,520105017600,2324754432000,130859579289600,

%U 640237370572800,41680704936960000,221172909834240000,16397141420298240000,93666727314800640000,7809290721329061888000,47726800133326110720000

%N 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.

%C Interweaving of nonzero Hultman numbers A164652(n,k) for k=1 and k=2. - _Max Alekseyev_, Nov 20 2020

%H D. A. Christie, <a href="http://dx.doi.org/10.1016/S0020-0190(96)00155-X">Sorting Permutations by Block-Interchanges</a>, Inf. Process. Lett. 60 (1996), 165-169.

%H Robert Cori, Michel Marcus, and Gilles Schaeffer, <a href="https://doi.org/10.1016/j.ejc.2012.03.012">Odd permutations are nicer than even ones</a>, European Journal of Combinatorics 33:7 (2012), 1467-1478.

%H M. Tikhomirov, <a href="https://mathoverflow.net/q/376956">A conjecture harmonic numbers</a>, MathOverflow, 2020.

%H D. Zagier, <a href="https://people.mpim-bonn.mpg.de/zagier/files/tex/CyclesOfElemsSymmGroups/fulltext.pdf">On the distribution of the number of cycles of elements in symmetric groups</a>.

%F For even n, a(n) = 2 * n! / (n+2).

%F 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.

%F a(n) =  A164652(n, 1+(n mod 2)). - _Max Alekseyev_, Nov 20 2020

%e The next three lines illustrate applying block interchanges to [2 4 6 1 3 5 7], an element of S_7.

%e Step 1: [2 4 6 1 3 5 7]->[3 5 1 2 4 6 7]-interchange blocks 3 5 and 2 4 6.

%e Step 2: [3 5 1 2 4 6 7]->[4 1 2 3 5 6 7]-interchange blocks 3 5 and 4.

%e Step 3: [4 1 2 3 5 6 7]->[1 2 3 4 5 6 7]-interchange blocks 4 and 1 2 3.

%e As [2 4 6 1 3 5 7] requires 3 = floor(7/2) block interchanges, it is one of the a(7) = 3044.

%e 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.

%t a[n_]:=Abs[StirlingS1[n+2,Mod[n,2]+1]/Binomial[n+2,2]]; Array[a,25,0] (* _Stefano Spezia_, Apr 01 2024 *)

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

%Y 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).

%Y 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).

%Y Cf. A000254, A001008, A002805, A164652.

%K nonn

%O 0,4

%A _Marion Scheepers_, Nov 16 2015

%E Edited and extended by _Max Alekseyev_ incorporating comments from M. Tikhomirov, Nov 20 2020