login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169. doi:10.1016/S0020-0190(96)00155-X

R. Cori, M. Marcus, G. Schaeffer, Odd permutations are nicer than even ones, European Journal of Combinatorics 33:7 (2012), 1467-1478. 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 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 08:36 EDT 2021. Contains 345162 sequences. (Running on oeis4.)