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

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

Mathematica

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

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

Cf. A000254, A001008, A002805, A164652.

Sequence in context: A123819 A286076 A302651 * A153720 A372124 A101016

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