A267324 -id:A267324 - cp's OEIS frontend

A267323 The number of permutations in S_n with strategic pile of size 3.

0, 0, 0, 3, 12, 66, 432, 3240, 27360

Offset: 1

Marion Scheepers, Jan 13 2016

The strategic pile of permutation P=[a_1,...,a_n] is obtained from the disjoint cycle decomposition of the composition of the cycles (a_n, ..., a_1,0)(0,1, 2, ..., n). If 0 and n are not in the same cycle, the strategic pile of P is empty. Else, the terms appearing from n to 0, not including n or 0, in the cycle (n, ..., 0, ...) is the strategic pile of P.

The strategic pile of P=[3,2,4,1] is {1, 2, 3} which has size 3 because: (1,4,2,3,0)(0,1,2,3,4) = ( 4, 1, 3, 2, 0).

			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.

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

A267323 The number of permutations in S_n with strategic pile of size 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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