Algorithmic enumeration of West-3-stack sortable permutations

Orateur : Andrew Elvey Price
11 Octobre 2022 à 14:00 ; lieu : Seminar room 4B125 (Copernic building)

Abstract: In his seminal book, the art of computer programming, Knuth discussed the enumeration of permutations which can be sorted by a single stack. West later defined the stack-sorting map in a deterministic way, such that repeatedly applying this map to a permutation of length n results in the identity permutation after at most n−1 steps. The number of permutations that are sorted by k applications of this map is known only for k≤2. I will discuss recent work on the case k=3, in particular I will describe an algorithm we applied to enumerate these permutations up to length n=1000 and our subsequent analysis of these numbers. This is joint work with Colin Defant and Anthony J. Guttmann.


Seminar room 4B125 (Copernic building)

5 Boulevard Descartes 77420 Champs-sur-Marne