OFFSET

3,1

COMMENTS

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}.

LINKS

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.

EXAMPLE

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

CROSSREFS

KEYWORD

nonn,more

AUTHOR

Joseph Rogge, Nov 04 2020

STATUS

approved