Enumeration of Permutations sortable by k Pop Stacks in Parallel
by
Rebecca Smith
SUNY Brockport
Coauthors: Vince Vatter

A stack is a last-in, first-out device that can be used to sort permutations. The "push" operation pushes the next available entry into a stack and the "pop" operation removes the top entry from the stack to the next stage or output. A pop stack is a stack where once a single entry in the stack is popped, all entries must be popped from the stack (still in first-in, last-out order).

We show that the set of permutations sortable by k pop stacks in parallel has a regular insertion encoding and construct the finite recognizing automaton for this language. This shows that these permutations have a rational generating function, verifying a conjecture of Atkinson and Sack.

Date received: February 21, 2009