|
%I #24 Apr 28 2021 02:44:26
%S 3,10,20,36,57,79
%N Number of Context-Directed Swaps (CDS) contexts in the maximum strategic pile case.
%C 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}.
%H K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner and H. C. Wauck, <a href="https://doi.org/10.1142/S179383091750063X">Sorting permutations: Games, genomes, and cycles</a>, Discrete Mathematics, Algorithms and Applications 09:05 (2017). Also <a href="https://arxiv.org/abs/1410.2353">arXiv:1410.2353</a> [math.CO], 2014-2017.
%H G. Brown, A. Mitchell, R. Raghavan, J. Rogge, and M. Scheepers, <a href="https://arxiv.org/abs/2011.00706">Classifying Permutations under Context-Directed Swaps and the cds game</a>, arXiv:2011.00706 [math.CO], 2020.
%e In S_6, permutations with maximum strategic pile have either 5,6, or 10 available CDS contexts. Hence a_3 = #{5,6,10}.
%e 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) }
%Y Cf. A267323, A267324, A267391, A281259, the number of permutations in S_n with strategic piles of size 3,4,5,6 (respectively).
%K nonn,more
%O 3,1
%A _Joseph Rogge_, Nov 04 2020
|
