Séminaire SPACE Tours

Enumerating permutations sortable by two stacks in suits, two stacks in parallel and a double ended queue
Andrew Elvey Price (Université de Melbourne)
Friday 19 October 2018 10:30 -  Tours -  Salle 1180 (Bât E2)

Résumé :
In "The Art of Computer Programming", Knuth asked how many permutations of each length can be sorted by each of the following machines: two stacks in parallel (2sip), two stacks in series (2sis) and a double ended queue (deque). I will describe recent results of Albert, Bousquet-Mélou, E. and Guttmann relating the generating functions for 2sip-sortable permutations and deque-sortable permutations to each other as well as a generating function for weighted quarter-plane loops. I will then describe numerical work of E. and Guttmann on the problem of enumerating 2sis-sortable permutations.

Liens :