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.

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

Author

Marion Scheepers, Nov 16 2015

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

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

Cf. A000254, A001008, A002805, A164652.

Programs

Mathematica

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

PARI

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

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

Extensions

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