Séminaire SPACE Tours
# Enumerating permutations sortable by two stacks in suits, two stacks in parallel and a double ended queue

##
by

→
Europe/Paris

Salle E2 1180 (Tours)
### Salle E2 1180

#### Tours

Description

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.