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.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne