A267323 -id:A267323 - cp's OEIS frontend

A267324 Number of elements of S_n with strategic pile of size 4.

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

Marion Scheepers, Jan 13 2016

nonn

Strategic pile is defined in A267323.

The formula given below is a specific instance of the formula that will appear in "Quantifying CDS Sortability of Permutations Using Strategic Piles", see link. - Marisa Gaetz, Jan 18 2017

			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 *)

a(n) = (n-4)!*(6*binomial(n-5,3) + 16*binomial(n-5,2) + 16*binomial(n-5,1)) for n>5. - Marisa Gaetz, Jan 18 2017

Typo for a(8) corrected by Marion Scheepers, Jun 26 2016

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

Marion Scheepers, Jan 13 2016

Strategic pile is defined in A267323.

			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.

A281259 Number of elements of S_n with strategic pile of size 6.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1080, 12960, 143424, 1641600, 19915200, 257644800, 3556224000, 52289556480, 817133184000, 13536585216000, 237105792000000, 4380335511552000, 85148431867699200, 1737742314147840000, 37156364106301440000, 830772012055265280000

Offset: 1

Marisa Gaetz, Jan 18 2017

nonn

Strategic pile is as defined in A267323.

The formula given below is a specific instance of the formula that will appear in "Quantifying CDS Sortability of Permutations Using Strategic Piles", see link.

			The permutation P = [3,5,1,8,6,2,7,4] has strategic pile of size 6. This can be found by the following cycle composition: (0,4,7,2,6,8,1,5,3)(0,1,2,3,4,5,6,7,8)=(0,5,8,4,3,7,1,6,2). Therefore, the strategic pile of P is {4,3,7,1,6,2}.

M. Gaetz, B. Molokach, M. Scheepers, and M. Shanks, Quantifying CDS Sortability of Permutations Using Strategic Piles
Marisa Gaetz, Bethany Flanagan, Marion Scheepers, Meghan Shanks, Quantifying CDS Sortability of Permutations by Strategic Pile Size, arXiv:1811.11937 [math.CO], 2018.

Cf. A267323 (size 3), A267324 (size 4), A267391 (size 5).

a(n) = (n-6)!*(120*binomial(n-7,5) + 576*binomial(n-7,4) + 1116*binomial(n-7,3) + 1080*binomial(n-7,2) + 540*binomial(n-7,1)) for n>7.

A338631 Number of Context-Directed Swaps (CDS) contexts in the maximum strategic pile case.

Original entry on oeis.org

3, 10, 20, 36, 57, 79

Offset: 3

Joseph Rogge, Nov 04 2020

Context-Directed Swaps or CDS denotes an operation on permutations, and there can be several ways to apply it to a given permutation, defined by distinct contexts. Permutations that have the maximum strategic pile (cf. A267323) are of special interest. a(n) is the number of distinct CDS contexts that a permutation with maximum strategic pile in S_{2n} can have. The number is the same for S_{2n} and S_{2n+1}.

			In S_6, permutations with maximum strategic pile have either 5,6, or 10 available CDS contexts. Hence a_3 = #{5,6,10}.
For example, the permutation [6, 1, 4, 2, 5, 3] is in S_6 with maximum strategic pile, and it has 5 contexts: { (1,2),(3,4) ; (1,2),(4,5) ; (2,3),(4,5) ; (2,3),(5,6) ; (3,4),(5,6) } The permutation [6, 1, 5, 2, 4, 3] is in S_6 with maximum strategic pile, and it has 6 contexts: { (1,2),(4,5) ; (1,2),(5,6) ; (4,5),(5,6) ; (2,3),(3,4) ; (2,3),(4,5) ; (3,4),(4,5) } The permutation [6, 1, 3, 5, 2, 4] is in S_6 with maximum strategic pile, and it has 10 contexts (all possible pairs of the 5 pointers): { (1,2),(2,3) ; (1,2),(3,4) ; (1,2),(4,5) ; (1,2),(5,6) ; (2,3),(3,4) ; (2,3),(4,5) ; (2,3),(5,6) ; (3,4),(4,5) ; (3,4),(5,6) ; (4,5),(5,6) }

K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner and H. C. Wauck, Sorting permutations: Games, genomes, and cycles, Discrete Mathematics, Algorithms and Applications 09:05 (2017). Also arXiv:1410.2353 [math.CO], 2014-2017.
G. Brown, A. Mitchell, R. Raghavan, J. Rogge, and M. Scheepers, Classifying Permutations under Context-Directed Swaps and the cds game, arXiv:2011.00706 [math.CO], 2020.

Cf. A267323, A267324, A267391, A281259, the number of permutations in S_n with strategic piles of size 3,4,5,6 (respectively).

cp's OEIS Frontend

A267324 Number of elements of S_n with strategic pile of size 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A267391 Number of elements of S_n with strategic pile of size 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A281259 Number of elements of S_n with strategic pile of size 6.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A338631 Number of Context-Directed Swaps (CDS) contexts in the maximum strategic pile case.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs