Marion Scheepers has authored 4 sequences.
A267391
Number of elements of S_n with strategic pile of size 5.
Original entry on oeis.org
0, 0, 0, 0, 0, 40, 240, 1980, 18240
Offset: 1
P = [7, 1, 5, 6, 2, 4, 3] has strategic pile size 5. The composition (0,3,4,2,6,5,1,7)(0,1,2,3,4,5,6,7) has cycle (7,3,2,4,1,6,0), and so the strategic pile of P is {1,2,3,4,6}.
- K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, H. C. Wauck, Sorting Permutations: Games, Genomes, and Cycles, arXiv:1410.2353 [math.CO], 2014-2017.
- Marisa Gaetz, Bethany Flanagan, Marion Scheepers, Meghan Shanks, Quantifying CDS Sortability of Permutations by Strategic Pile Size, arXiv:1811.11937 [math.CO], 2018.
A267323 gives the corresponding sequence for strategic piles of size 3.
A267324 gives the corresponding sequence for strategic piles of size 4.
A267323
The number of permutations in S_n with strategic pile of size 3.
Original entry on oeis.org
0, 0, 0, 3, 12, 66, 432, 3240, 27360
Offset: 1
a(4) = 3 because [3,2,4,1], [2,4,1,3] and [4,1,3,2] are the only elements of S_4 that each has a strategic pile of size 3.
- K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, H. C. Wauck, Sorting Permutations: Games, Genomes, and Cycles, arXiv:1410.2353 [math.CO], 2014-2017.
- Marisa Gaetz, Bethany Flanagan, Marion Scheepers, Meghan Shanks, Quantifying CDS Sortability of Permutations by Strategic Pile Size, arXiv:1811.11937 [math.CO], 2018.
A267324 gives the corresponding sequence for strategic piles of size 4.
A267391 gives the corresponding sequence for strategic piles of size 5.
A267324
Number of elements of S_n with strategic pile of size 4.
Original entry on oeis.org
0, 0, 0, 0, 0, 32, 288, 2448, 22080, 216000, 2298240, 26530560, 330946560, 4441651200, 63866880000, 980037273600, 15990989414400, 276529539686400, 5052853757952000, 97290972979200000, 1969085601939456000, 41794695550992384000, 928395406320205824000
Offset: 1
P = [6,4,2,5,3,1] has strategic pile of size 4: The composition of cycles (0,1,3,5,2,4,6)(0,1,2,3,4,5,6) is (0,3,6,1,4,2,5) = (6,1,4,2,5,0,3) and thus the strategic pile of P is {1,2,4,5}.
- K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, H. C. Wauck, Sorting Permutations: Games, Genomes, and Cycles, arXiv:1410.2353 [math.CO], 2014-2017.
- Marisa Gaetz, Bethany Flanagan, Marion Scheepers, Meghan Shanks, Quantifying CDS Sortability of Permutations by Strategic Pile Size, arXiv:1811.11937 [math.CO], 2018.
- M. Gaetz, B. Molokach, M. Scheepers, and M. Shanks, Quantifying CDS Sortability of Permutations Using Strategic Piles
Cf.
A267323 gives the corresponding sequence for strategic piles of size 3,
A267391 for size 5, and
A281259 for size 6.
-
a[n_] := If[n<6, 0, 2(n-5)(n^2-5n+10) Pochhammer[3, n-6]];
Array[a, 23] (* Jean-François Alcover, Dec 12 2018 *)
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
Comments