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

3, 10, 20, 36, 57, 79

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

Table of n, a(n) for n=3..8.

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

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

Sequence in context: A208951 A299692 A246520 * A272764 A293765 A295953

Adjacent sequences: A338628 A338629 A338630 * A338632 A338633 A338634

Keyword

nonn,more

Author

Joseph Rogge, Nov 04 2020

Status

approved