A256181
The number of permutations of length n sortable by 3 block interchanges.
Original entry on oeis.org
1, 2, 6, 24, 120, 720, 5040, 32256, 169632, 737364, 2731444, 8875868, 25894376, 69053375, 170694383, 395443223, 866147111, 1806459866, 3608498678, 6937282452, 12887902732, 23216767894, 40675018726, 69480583966, 115975600846, 189528370396, 303753983092
Offset: 1
The shortest permutations that cannot be sorted by 3 block interchanges are of length 8.
- Colin Barker, Table of n, a(n) for n = 1..1000
- D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169.
- C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 2013-2015.
- Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).
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.
Original entry on oeis.org
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
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.
- 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.
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).
-
a[n_]:=Abs[StirlingS1[n+2,Mod[n,2]+1]/Binomial[n+2,2]]; Array[a,25,0] (* Stefano Spezia, Apr 01 2024 *)
-
{ A260695(n) = abs(stirling(n+2, n%2+1)) / binomial(n+2, 2); } \\ Max Alekseyev, Nov 20 2020
Edited and extended by
Max Alekseyev incorporating comments from M. Tikhomirov, Nov 20 2020
Showing 1-2 of 2 results.
Comments