OFFSET
0,4
COMMENTS
Interweaving of nonzero Hultman numbers A164652(n,k) for k=1 and k=2. - Max Alekseyev, Nov 20 2020
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.
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).
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