2017/10/13 by Claesson, Anders, Guðmundsson, Bjarki Ágúst
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.04978
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.