Séminaire SPACE Tours

Enumerating permutations sortable by two stacks in suits, two stacks in parallel and a double ended queue

by Andrew Elvey Price

Salle E2 1180 (Tours)

Salle E2 1180



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.