The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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. 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.

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