Choose timezone
Your profile timezone:
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.