Séminaire Lotharingien de Combinatoire, 80B.43 (2018), 12 pp.
Anders Claesson and Bjarki Ágúst
Guðmundsson
Enumerating Permutations Sortable by k Passes Through a Pop-Stack
Abstract.
In an exercise in the first volume of his famous series of books,
Knuth considered sorting permutations by passing them through a stack.
Many variations of this exercise have since been considered, including
allowing multiple passes through the stack and using different data
structures. We are concerned with a variation using pop-stacks that was
introduced by Avis and Newborn in 1981. Let Pk(x) be the generating
function for the permutations sortable by k passes through a
pop-stack. The generating function P2(x) was recently given by
Pudwell and Smith (the case k=1 being trivial). We show that
Pk(x) is rational for any k. Moreover, we give an algorithm to
derive Pk(x), and using it we determine the generating functions
Pk(x) for k <= 6.
Received: November 14, 2017.
Accepted: February 17, 2018.
Final version: April 1, 2018.
The following versions are available: