Stacks, Deques, and Permutations

Mike Atkinson

2008 is the forty-year anniversary of the publication of volume 1 in Knuth's Art of Computer Programming series. This seminar marks the occasion by considering Exercise 2.2.1.13 which asked how many permutations of length n can be obtained with a double-ended queue. This problem is still unsolved but we report on recent progress, and progress on other problems also raised by Knuth. We shall begin by explaining the problems and continue by sketching out some techniques based on finite automata which give rise to approximate solutions.